/
PeepholeOptimizer.cpp
2128 lines (1851 loc) · 78.5 KB
/
PeepholeOptimizer.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//===- PeepholeOptimizer.cpp - Peephole Optimizations ---------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Perform peephole optimizations on the machine code:
//
// - Optimize Extensions
//
// Optimization of sign / zero extension instructions. It may be extended to
// handle other instructions with similar properties.
//
// On some targets, some instructions, e.g. X86 sign / zero extension, may
// leave the source value in the lower part of the result. This optimization
// will replace some uses of the pre-extension value with uses of the
// sub-register of the results.
//
// - Optimize Comparisons
//
// Optimization of comparison instructions. For instance, in this code:
//
// sub r1, 1
// cmp r1, 0
// bz L1
//
// If the "sub" instruction all ready sets (or could be modified to set) the
// same flag that the "cmp" instruction sets and that "bz" uses, then we can
// eliminate the "cmp" instruction.
//
// Another instance, in this code:
//
// sub r1, r3 | sub r1, imm
// cmp r3, r1 or cmp r1, r3 | cmp r1, imm
// bge L1
//
// If the branch instruction can use flag from "sub", then we can replace
// "sub" with "subs" and eliminate the "cmp" instruction.
//
// - Optimize Loads:
//
// Loads that can be folded into a later instruction. A load is foldable
// if it loads to virtual registers and the virtual register defined has
// a single use.
//
// - Optimize Copies and Bitcast (more generally, target specific copies):
//
// Rewrite copies and bitcasts to avoid cross register bank copies
// when possible.
// E.g., Consider the following example, where capital and lower
// letters denote different register file:
// b = copy A <-- cross-bank copy
// C = copy b <-- cross-bank copy
// =>
// b = copy A <-- cross-bank copy
// C = copy A <-- same-bank copy
//
// E.g., for bitcast:
// b = bitcast A <-- cross-bank copy
// C = bitcast b <-- cross-bank copy
// =>
// b = bitcast A <-- cross-bank copy
// C = copy A <-- same-bank copy
//===----------------------------------------------------------------------===//
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <memory>
#include <utility>
using namespace llvm;
using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
using RegSubRegPairAndIdx = TargetInstrInfo::RegSubRegPairAndIdx;
#define DEBUG_TYPE "peephole-opt"
// Optimize Extensions
static cl::opt<bool>
Aggressive("aggressive-ext-opt", cl::Hidden,
cl::desc("Aggressive extension optimization"));
static cl::opt<bool>
DisablePeephole("disable-peephole", cl::Hidden, cl::init(false),
cl::desc("Disable the peephole optimizer"));
/// Specifiy whether or not the value tracking looks through
/// complex instructions. When this is true, the value tracker
/// bails on everything that is not a copy or a bitcast.
static cl::opt<bool>
DisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden, cl::init(false),
cl::desc("Disable advanced copy optimization"));
static cl::opt<bool> DisableNAPhysCopyOpt(
"disable-non-allocatable-phys-copy-opt", cl::Hidden, cl::init(false),
cl::desc("Disable non-allocatable physical register copy optimization"));
// Limit the number of PHI instructions to process
// in PeepholeOptimizer::getNextSource.
static cl::opt<unsigned> RewritePHILimit(
"rewrite-phi-limit", cl::Hidden, cl::init(10),
cl::desc("Limit the length of PHI chains to lookup"));
// Limit the length of recurrence chain when evaluating the benefit of
// commuting operands.
static cl::opt<unsigned> MaxRecurrenceChain(
"recurrence-chain-limit", cl::Hidden, cl::init(3),
cl::desc("Maximum length of recurrence chain when evaluating the benefit "
"of commuting operands"));
STATISTIC(NumReuse, "Number of extension results reused");
STATISTIC(NumCmps, "Number of compares eliminated");
STATISTIC(NumImmFold, "Number of move immediate folded");
STATISTIC(NumLoadFold, "Number of loads folded");
STATISTIC(NumSelects, "Number of selects optimized");
STATISTIC(NumUncoalescableCopies, "Number of uncoalescable copies optimized");
STATISTIC(NumRewrittenCopies, "Number of copies rewritten");
STATISTIC(NumNAPhysCopies, "Number of non-allocatable physical copies removed");
namespace {
class ValueTrackerResult;
class RecurrenceInstr;
class PeepholeOptimizer : public MachineFunctionPass {
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
MachineRegisterInfo *MRI;
MachineDominatorTree *DT; // Machine dominator tree
MachineLoopInfo *MLI;
public:
static char ID; // Pass identification
PeepholeOptimizer() : MachineFunctionPass(ID) {
initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry());
}
bool runOnMachineFunction(MachineFunction &MF) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
AU.addRequired<MachineLoopInfo>();
AU.addPreserved<MachineLoopInfo>();
if (Aggressive) {
AU.addRequired<MachineDominatorTree>();
AU.addPreserved<MachineDominatorTree>();
}
}
MachineFunctionProperties getRequiredProperties() const override {
return MachineFunctionProperties()
.set(MachineFunctionProperties::Property::IsSSA);
}
/// Track Def -> Use info used for rewriting copies.
using RewriteMapTy = SmallDenseMap<RegSubRegPair, ValueTrackerResult>;
/// Sequence of instructions that formulate recurrence cycle.
using RecurrenceCycle = SmallVector<RecurrenceInstr, 4>;
private:
bool optimizeCmpInstr(MachineInstr &MI);
bool optimizeExtInstr(MachineInstr &MI, MachineBasicBlock &MBB,
SmallPtrSetImpl<MachineInstr*> &LocalMIs);
bool optimizeSelect(MachineInstr &MI,
SmallPtrSetImpl<MachineInstr *> &LocalMIs);
bool optimizeCondBranch(MachineInstr &MI);
bool optimizeCoalescableCopy(MachineInstr &MI);
bool optimizeUncoalescableCopy(MachineInstr &MI,
SmallPtrSetImpl<MachineInstr *> &LocalMIs);
bool optimizeRecurrence(MachineInstr &PHI);
bool findNextSource(RegSubRegPair RegSubReg, RewriteMapTy &RewriteMap);
bool isMoveImmediate(MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs,
DenseMap<Register, MachineInstr *> &ImmDefMIs);
bool foldImmediate(MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs,
DenseMap<Register, MachineInstr *> &ImmDefMIs);
/// Finds recurrence cycles, but only ones that formulated around
/// a def operand and a use operand that are tied. If there is a use
/// operand commutable with the tied use operand, find recurrence cycle
/// along that operand as well.
bool findTargetRecurrence(Register Reg,
const SmallSet<Register, 2> &TargetReg,
RecurrenceCycle &RC);
/// If copy instruction \p MI is a virtual register copy or a copy of a
/// constant physical register to a virtual register, track it in the
/// set \p CopyMIs. If this virtual register was previously seen as a
/// copy, replace the uses of this copy with the previously seen copy's
/// destination register.
bool foldRedundantCopy(MachineInstr &MI,
DenseMap<RegSubRegPair, MachineInstr *> &CopyMIs);
/// Is the register \p Reg a non-allocatable physical register?
bool isNAPhysCopy(Register Reg);
/// If copy instruction \p MI is a non-allocatable virtual<->physical
/// register copy, track it in the \p NAPhysToVirtMIs map. If this
/// non-allocatable physical register was previously copied to a virtual
/// registered and hasn't been clobbered, the virt->phys copy can be
/// deleted.
bool foldRedundantNAPhysCopy(
MachineInstr &MI, DenseMap<Register, MachineInstr *> &NAPhysToVirtMIs);
bool isLoadFoldable(MachineInstr &MI,
SmallSet<Register, 16> &FoldAsLoadDefCandidates);
/// Check whether \p MI is understood by the register coalescer
/// but may require some rewriting.
bool isCoalescableCopy(const MachineInstr &MI) {
// SubregToRegs are not interesting, because they are already register
// coalescer friendly.
return MI.isCopy() || (!DisableAdvCopyOpt &&
(MI.isRegSequence() || MI.isInsertSubreg() ||
MI.isExtractSubreg()));
}
/// Check whether \p MI is a copy like instruction that is
/// not recognized by the register coalescer.
bool isUncoalescableCopy(const MachineInstr &MI) {
return MI.isBitcast() ||
(!DisableAdvCopyOpt &&
(MI.isRegSequenceLike() || MI.isInsertSubregLike() ||
MI.isExtractSubregLike()));
}
MachineInstr &rewriteSource(MachineInstr &CopyLike,
RegSubRegPair Def, RewriteMapTy &RewriteMap);
};
/// Helper class to hold instructions that are inside recurrence cycles.
/// The recurrence cycle is formulated around 1) a def operand and its
/// tied use operand, or 2) a def operand and a use operand that is commutable
/// with another use operand which is tied to the def operand. In the latter
/// case, index of the tied use operand and the commutable use operand are
/// maintained with CommutePair.
class RecurrenceInstr {
public:
using IndexPair = std::pair<unsigned, unsigned>;
RecurrenceInstr(MachineInstr *MI) : MI(MI) {}
RecurrenceInstr(MachineInstr *MI, unsigned Idx1, unsigned Idx2)
: MI(MI), CommutePair(std::make_pair(Idx1, Idx2)) {}
MachineInstr *getMI() const { return MI; }
std::optional<IndexPair> getCommutePair() const { return CommutePair; }
private:
MachineInstr *MI;
std::optional<IndexPair> CommutePair;
};
/// Helper class to hold a reply for ValueTracker queries.
/// Contains the returned sources for a given search and the instructions
/// where the sources were tracked from.
class ValueTrackerResult {
private:
/// Track all sources found by one ValueTracker query.
SmallVector<RegSubRegPair, 2> RegSrcs;
/// Instruction using the sources in 'RegSrcs'.
const MachineInstr *Inst = nullptr;
public:
ValueTrackerResult() = default;
ValueTrackerResult(Register Reg, unsigned SubReg) {
addSource(Reg, SubReg);
}
bool isValid() const { return getNumSources() > 0; }
void setInst(const MachineInstr *I) { Inst = I; }
const MachineInstr *getInst() const { return Inst; }
void clear() {
RegSrcs.clear();
Inst = nullptr;
}
void addSource(Register SrcReg, unsigned SrcSubReg) {
RegSrcs.push_back(RegSubRegPair(SrcReg, SrcSubReg));
}
void setSource(int Idx, Register SrcReg, unsigned SrcSubReg) {
assert(Idx < getNumSources() && "Reg pair source out of index");
RegSrcs[Idx] = RegSubRegPair(SrcReg, SrcSubReg);
}
int getNumSources() const { return RegSrcs.size(); }
RegSubRegPair getSrc(int Idx) const {
return RegSrcs[Idx];
}
Register getSrcReg(int Idx) const {
assert(Idx < getNumSources() && "Reg source out of index");
return RegSrcs[Idx].Reg;
}
unsigned getSrcSubReg(int Idx) const {
assert(Idx < getNumSources() && "SubReg source out of index");
return RegSrcs[Idx].SubReg;
}
bool operator==(const ValueTrackerResult &Other) const {
if (Other.getInst() != getInst())
return false;
if (Other.getNumSources() != getNumSources())
return false;
for (int i = 0, e = Other.getNumSources(); i != e; ++i)
if (Other.getSrcReg(i) != getSrcReg(i) ||
Other.getSrcSubReg(i) != getSrcSubReg(i))
return false;
return true;
}
};
/// Helper class to track the possible sources of a value defined by
/// a (chain of) copy related instructions.
/// Given a definition (instruction and definition index), this class
/// follows the use-def chain to find successive suitable sources.
/// The given source can be used to rewrite the definition into
/// def = COPY src.
///
/// For instance, let us consider the following snippet:
/// v0 =
/// v2 = INSERT_SUBREG v1, v0, sub0
/// def = COPY v2.sub0
///
/// Using a ValueTracker for def = COPY v2.sub0 will give the following
/// suitable sources:
/// v2.sub0 and v0.
/// Then, def can be rewritten into def = COPY v0.
class ValueTracker {
private:
/// The current point into the use-def chain.
const MachineInstr *Def = nullptr;
/// The index of the definition in Def.
unsigned DefIdx = 0;
/// The sub register index of the definition.
unsigned DefSubReg;
/// The register where the value can be found.
Register Reg;
/// MachineRegisterInfo used to perform tracking.
const MachineRegisterInfo &MRI;
/// Optional TargetInstrInfo used to perform some complex tracking.
const TargetInstrInfo *TII;
/// Dispatcher to the right underlying implementation of getNextSource.
ValueTrackerResult getNextSourceImpl();
/// Specialized version of getNextSource for Copy instructions.
ValueTrackerResult getNextSourceFromCopy();
/// Specialized version of getNextSource for Bitcast instructions.
ValueTrackerResult getNextSourceFromBitcast();
/// Specialized version of getNextSource for RegSequence instructions.
ValueTrackerResult getNextSourceFromRegSequence();
/// Specialized version of getNextSource for InsertSubreg instructions.
ValueTrackerResult getNextSourceFromInsertSubreg();
/// Specialized version of getNextSource for ExtractSubreg instructions.
ValueTrackerResult getNextSourceFromExtractSubreg();
/// Specialized version of getNextSource for SubregToReg instructions.
ValueTrackerResult getNextSourceFromSubregToReg();
/// Specialized version of getNextSource for PHI instructions.
ValueTrackerResult getNextSourceFromPHI();
public:
/// Create a ValueTracker instance for the value defined by \p Reg.
/// \p DefSubReg represents the sub register index the value tracker will
/// track. It does not need to match the sub register index used in the
/// definition of \p Reg.
/// If \p Reg is a physical register, a value tracker constructed with
/// this constructor will not find any alternative source.
/// Indeed, when \p Reg is a physical register that constructor does not
/// know which definition of \p Reg it should track.
/// Use the next constructor to track a physical register.
ValueTracker(Register Reg, unsigned DefSubReg,
const MachineRegisterInfo &MRI,
const TargetInstrInfo *TII = nullptr)
: DefSubReg(DefSubReg), Reg(Reg), MRI(MRI), TII(TII) {
if (!Reg.isPhysical()) {
Def = MRI.getVRegDef(Reg);
DefIdx = MRI.def_begin(Reg).getOperandNo();
}
}
/// Following the use-def chain, get the next available source
/// for the tracked value.
/// \return A ValueTrackerResult containing a set of registers
/// and sub registers with tracked values. A ValueTrackerResult with
/// an empty set of registers means no source was found.
ValueTrackerResult getNextSource();
};
} // end anonymous namespace
char PeepholeOptimizer::ID = 0;
char &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID;
INITIALIZE_PASS_BEGIN(PeepholeOptimizer, DEBUG_TYPE,
"Peephole Optimizations", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
INITIALIZE_PASS_END(PeepholeOptimizer, DEBUG_TYPE,
"Peephole Optimizations", false, false)
/// If instruction is a copy-like instruction, i.e. it reads a single register
/// and writes a single register and it does not modify the source, and if the
/// source value is preserved as a sub-register of the result, then replace all
/// reachable uses of the source with the subreg of the result.
///
/// Do not generate an EXTRACT that is used only in a debug use, as this changes
/// the code. Since this code does not currently share EXTRACTs, just ignore all
/// debug uses.
bool PeepholeOptimizer::
optimizeExtInstr(MachineInstr &MI, MachineBasicBlock &MBB,
SmallPtrSetImpl<MachineInstr*> &LocalMIs) {
Register SrcReg, DstReg;
unsigned SubIdx;
if (!TII->isCoalescableExtInstr(MI, SrcReg, DstReg, SubIdx))
return false;
if (DstReg.isPhysical() || SrcReg.isPhysical())
return false;
if (MRI->hasOneNonDBGUse(SrcReg))
// No other uses.
return false;
// Ensure DstReg can get a register class that actually supports
// sub-registers. Don't change the class until we commit.
const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
DstRC = TRI->getSubClassWithSubReg(DstRC, SubIdx);
if (!DstRC)
return false;
// The ext instr may be operating on a sub-register of SrcReg as well.
// PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit
// register.
// If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of
// SrcReg:SubIdx should be replaced.
bool UseSrcSubIdx =
TRI->getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != nullptr;
// The source has other uses. See if we can replace the other uses with use of
// the result of the extension.
SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs;
for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg))
ReachedBBs.insert(UI.getParent());
// Uses that are in the same BB of uses of the result of the instruction.
SmallVector<MachineOperand*, 8> Uses;
// Uses that the result of the instruction can reach.
SmallVector<MachineOperand*, 8> ExtendedUses;
bool ExtendLife = true;
for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) {
MachineInstr *UseMI = UseMO.getParent();
if (UseMI == &MI)
continue;
if (UseMI->isPHI()) {
ExtendLife = false;
continue;
}
// Only accept uses of SrcReg:SubIdx.
if (UseSrcSubIdx && UseMO.getSubReg() != SubIdx)
continue;
// It's an error to translate this:
//
// %reg1025 = <sext> %reg1024
// ...
// %reg1026 = SUBREG_TO_REG 0, %reg1024, 4
//
// into this:
//
// %reg1025 = <sext> %reg1024
// ...
// %reg1027 = COPY %reg1025:4
// %reg1026 = SUBREG_TO_REG 0, %reg1027, 4
//
// The problem here is that SUBREG_TO_REG is there to assert that an
// implicit zext occurs. It doesn't insert a zext instruction. If we allow
// the COPY here, it will give us the value after the <sext>, not the
// original value of %reg1024 before <sext>.
if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG)
continue;
MachineBasicBlock *UseMBB = UseMI->getParent();
if (UseMBB == &MBB) {
// Local uses that come after the extension.
if (!LocalMIs.count(UseMI))
Uses.push_back(&UseMO);
} else if (ReachedBBs.count(UseMBB)) {
// Non-local uses where the result of the extension is used. Always
// replace these unless it's a PHI.
Uses.push_back(&UseMO);
} else if (Aggressive && DT->dominates(&MBB, UseMBB)) {
// We may want to extend the live range of the extension result in order
// to replace these uses.
ExtendedUses.push_back(&UseMO);
} else {
// Both will be live out of the def MBB anyway. Don't extend live range of
// the extension result.
ExtendLife = false;
break;
}
}
if (ExtendLife && !ExtendedUses.empty())
// Extend the liveness of the extension result.
Uses.append(ExtendedUses.begin(), ExtendedUses.end());
// Now replace all uses.
bool Changed = false;
if (!Uses.empty()) {
SmallPtrSet<MachineBasicBlock*, 4> PHIBBs;
// Look for PHI uses of the extended result, we don't want to extend the
// liveness of a PHI input. It breaks all kinds of assumptions down
// stream. A PHI use is expected to be the kill of its source values.
for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg))
if (UI.isPHI())
PHIBBs.insert(UI.getParent());
const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
MachineOperand *UseMO = Uses[i];
MachineInstr *UseMI = UseMO->getParent();
MachineBasicBlock *UseMBB = UseMI->getParent();
if (PHIBBs.count(UseMBB))
continue;
// About to add uses of DstReg, clear DstReg's kill flags.
if (!Changed) {
MRI->clearKillFlags(DstReg);
MRI->constrainRegClass(DstReg, DstRC);
}
// SubReg defs are illegal in machine SSA phase,
// we should not generate SubReg defs.
//
// For example, for the instructions:
//
// %1:g8rc_and_g8rc_nox0 = EXTSW %0:g8rc
// %3:gprc_and_gprc_nor0 = COPY %0.sub_32:g8rc
//
// We should generate:
//
// %1:g8rc_and_g8rc_nox0 = EXTSW %0:g8rc
// %6:gprc_and_gprc_nor0 = COPY %1.sub_32:g8rc_and_g8rc_nox0
// %3:gprc_and_gprc_nor0 = COPY %6:gprc_and_gprc_nor0
//
if (UseSrcSubIdx)
RC = MRI->getRegClass(UseMI->getOperand(0).getReg());
Register NewVR = MRI->createVirtualRegister(RC);
BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(),
TII->get(TargetOpcode::COPY), NewVR)
.addReg(DstReg, 0, SubIdx);
if (UseSrcSubIdx)
UseMO->setSubReg(0);
UseMO->setReg(NewVR);
++NumReuse;
Changed = true;
}
}
return Changed;
}
/// If the instruction is a compare and the previous instruction it's comparing
/// against already sets (or could be modified to set) the same flag as the
/// compare, then we can remove the comparison and use the flag from the
/// previous instruction.
bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr &MI) {
// If this instruction is a comparison against zero and isn't comparing a
// physical register, we can try to optimize it.
Register SrcReg, SrcReg2;
int64_t CmpMask, CmpValue;
if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) ||
SrcReg.isPhysical() || SrcReg2.isPhysical())
return false;
// Attempt to optimize the comparison instruction.
LLVM_DEBUG(dbgs() << "Attempting to optimize compare: " << MI);
if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) {
LLVM_DEBUG(dbgs() << " -> Successfully optimized compare!\n");
++NumCmps;
return true;
}
return false;
}
/// Optimize a select instruction.
bool PeepholeOptimizer::optimizeSelect(MachineInstr &MI,
SmallPtrSetImpl<MachineInstr *> &LocalMIs) {
unsigned TrueOp = 0;
unsigned FalseOp = 0;
bool Optimizable = false;
SmallVector<MachineOperand, 4> Cond;
if (TII->analyzeSelect(MI, Cond, TrueOp, FalseOp, Optimizable))
return false;
if (!Optimizable)
return false;
if (!TII->optimizeSelect(MI, LocalMIs))
return false;
LLVM_DEBUG(dbgs() << "Deleting select: " << MI);
MI.eraseFromParent();
++NumSelects;
return true;
}
/// Check if a simpler conditional branch can be generated.
bool PeepholeOptimizer::optimizeCondBranch(MachineInstr &MI) {
return TII->optimizeCondBranch(MI);
}
/// Try to find the next source that share the same register file
/// for the value defined by \p Reg and \p SubReg.
/// When true is returned, the \p RewriteMap can be used by the client to
/// retrieve all Def -> Use along the way up to the next source. Any found
/// Use that is not itself a key for another entry, is the next source to
/// use. During the search for the next source, multiple sources can be found
/// given multiple incoming sources of a PHI instruction. In this case, we
/// look in each PHI source for the next source; all found next sources must
/// share the same register file as \p Reg and \p SubReg. The client should
/// then be capable to rewrite all intermediate PHIs to get the next source.
/// \return False if no alternative sources are available. True otherwise.
bool PeepholeOptimizer::findNextSource(RegSubRegPair RegSubReg,
RewriteMapTy &RewriteMap) {
// Do not try to find a new source for a physical register.
// So far we do not have any motivating example for doing that.
// Thus, instead of maintaining untested code, we will revisit that if
// that changes at some point.
Register Reg = RegSubReg.Reg;
if (Reg.isPhysical())
return false;
const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);
SmallVector<RegSubRegPair, 4> SrcToLook;
RegSubRegPair CurSrcPair = RegSubReg;
SrcToLook.push_back(CurSrcPair);
unsigned PHICount = 0;
do {
CurSrcPair = SrcToLook.pop_back_val();
// As explained above, do not handle physical registers
if (CurSrcPair.Reg.isPhysical())
return false;
ValueTracker ValTracker(CurSrcPair.Reg, CurSrcPair.SubReg, *MRI, TII);
// Follow the chain of copies until we find a more suitable source, a phi
// or have to abort.
while (true) {
ValueTrackerResult Res = ValTracker.getNextSource();
// Abort at the end of a chain (without finding a suitable source).
if (!Res.isValid())
return false;
// Insert the Def -> Use entry for the recently found source.
ValueTrackerResult CurSrcRes = RewriteMap.lookup(CurSrcPair);
if (CurSrcRes.isValid()) {
assert(CurSrcRes == Res && "ValueTrackerResult found must match");
// An existent entry with multiple sources is a PHI cycle we must avoid.
// Otherwise it's an entry with a valid next source we already found.
if (CurSrcRes.getNumSources() > 1) {
LLVM_DEBUG(dbgs()
<< "findNextSource: found PHI cycle, aborting...\n");
return false;
}
break;
}
RewriteMap.insert(std::make_pair(CurSrcPair, Res));
// ValueTrackerResult usually have one source unless it's the result from
// a PHI instruction. Add the found PHI edges to be looked up further.
unsigned NumSrcs = Res.getNumSources();
if (NumSrcs > 1) {
PHICount++;
if (PHICount >= RewritePHILimit) {
LLVM_DEBUG(dbgs() << "findNextSource: PHI limit reached\n");
return false;
}
for (unsigned i = 0; i < NumSrcs; ++i)
SrcToLook.push_back(Res.getSrc(i));
break;
}
CurSrcPair = Res.getSrc(0);
// Do not extend the live-ranges of physical registers as they add
// constraints to the register allocator. Moreover, if we want to extend
// the live-range of a physical register, unlike SSA virtual register,
// we will have to check that they aren't redefine before the related use.
if (CurSrcPair.Reg.isPhysical())
return false;
// Keep following the chain if the value isn't any better yet.
const TargetRegisterClass *SrcRC = MRI->getRegClass(CurSrcPair.Reg);
if (!TRI->shouldRewriteCopySrc(DefRC, RegSubReg.SubReg, SrcRC,
CurSrcPair.SubReg))
continue;
// We currently cannot deal with subreg operands on PHI instructions
// (see insertPHI()).
if (PHICount > 0 && CurSrcPair.SubReg != 0)
continue;
// We found a suitable source, and are done with this chain.
break;
}
} while (!SrcToLook.empty());
// If we did not find a more suitable source, there is nothing to optimize.
return CurSrcPair.Reg != Reg;
}
/// Insert a PHI instruction with incoming edges \p SrcRegs that are
/// guaranteed to have the same register class. This is necessary whenever we
/// successfully traverse a PHI instruction and find suitable sources coming
/// from its edges. By inserting a new PHI, we provide a rewritten PHI def
/// suitable to be used in a new COPY instruction.
static MachineInstr &
insertPHI(MachineRegisterInfo &MRI, const TargetInstrInfo &TII,
const SmallVectorImpl<RegSubRegPair> &SrcRegs,
MachineInstr &OrigPHI) {
assert(!SrcRegs.empty() && "No sources to create a PHI instruction?");
const TargetRegisterClass *NewRC = MRI.getRegClass(SrcRegs[0].Reg);
// NewRC is only correct if no subregisters are involved. findNextSource()
// should have rejected those cases already.
assert(SrcRegs[0].SubReg == 0 && "should not have subreg operand");
Register NewVR = MRI.createVirtualRegister(NewRC);
MachineBasicBlock *MBB = OrigPHI.getParent();
MachineInstrBuilder MIB = BuildMI(*MBB, &OrigPHI, OrigPHI.getDebugLoc(),
TII.get(TargetOpcode::PHI), NewVR);
unsigned MBBOpIdx = 2;
for (const RegSubRegPair &RegPair : SrcRegs) {
MIB.addReg(RegPair.Reg, 0, RegPair.SubReg);
MIB.addMBB(OrigPHI.getOperand(MBBOpIdx).getMBB());
// Since we're extended the lifetime of RegPair.Reg, clear the
// kill flags to account for that and make RegPair.Reg reaches
// the new PHI.
MRI.clearKillFlags(RegPair.Reg);
MBBOpIdx += 2;
}
return *MIB;
}
namespace {
/// Interface to query instructions amenable to copy rewriting.
class Rewriter {
protected:
MachineInstr &CopyLike;
unsigned CurrentSrcIdx = 0; ///< The index of the source being rewritten.
public:
Rewriter(MachineInstr &CopyLike) : CopyLike(CopyLike) {}
virtual ~Rewriter() = default;
/// Get the next rewritable source (SrcReg, SrcSubReg) and
/// the related value that it affects (DstReg, DstSubReg).
/// A source is considered rewritable if its register class and the
/// register class of the related DstReg may not be register
/// coalescer friendly. In other words, given a copy-like instruction
/// not all the arguments may be returned at rewritable source, since
/// some arguments are none to be register coalescer friendly.
///
/// Each call of this method moves the current source to the next
/// rewritable source.
/// For instance, let CopyLike be the instruction to rewrite.
/// CopyLike has one definition and one source:
/// dst.dstSubIdx = CopyLike src.srcSubIdx.
///
/// The first call will give the first rewritable source, i.e.,
/// the only source this instruction has:
/// (SrcReg, SrcSubReg) = (src, srcSubIdx).
/// This source defines the whole definition, i.e.,
/// (DstReg, DstSubReg) = (dst, dstSubIdx).
///
/// The second and subsequent calls will return false, as there is only one
/// rewritable source.
///
/// \return True if a rewritable source has been found, false otherwise.
/// The output arguments are valid if and only if true is returned.
virtual bool getNextRewritableSource(RegSubRegPair &Src,
RegSubRegPair &Dst) = 0;
/// Rewrite the current source with \p NewReg and \p NewSubReg if possible.
/// \return True if the rewriting was possible, false otherwise.
virtual bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) = 0;
};
/// Rewriter for COPY instructions.
class CopyRewriter : public Rewriter {
public:
CopyRewriter(MachineInstr &MI) : Rewriter(MI) {
assert(MI.isCopy() && "Expected copy instruction");
}
virtual ~CopyRewriter() = default;
bool getNextRewritableSource(RegSubRegPair &Src,
RegSubRegPair &Dst) override {
// CurrentSrcIdx > 0 means this function has already been called.
if (CurrentSrcIdx > 0)
return false;
// This is the first call to getNextRewritableSource.
// Move the CurrentSrcIdx to remember that we made that call.
CurrentSrcIdx = 1;
// The rewritable source is the argument.
const MachineOperand &MOSrc = CopyLike.getOperand(1);
Src = RegSubRegPair(MOSrc.getReg(), MOSrc.getSubReg());
// What we track are the alternative sources of the definition.
const MachineOperand &MODef = CopyLike.getOperand(0);
Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg());
return true;
}
bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override {
if (CurrentSrcIdx != 1)
return false;
MachineOperand &MOSrc = CopyLike.getOperand(CurrentSrcIdx);
MOSrc.setReg(NewReg);
MOSrc.setSubReg(NewSubReg);
return true;
}
};
/// Helper class to rewrite uncoalescable copy like instructions
/// into new COPY (coalescable friendly) instructions.
class UncoalescableRewriter : public Rewriter {
unsigned NumDefs; ///< Number of defs in the bitcast.
public:
UncoalescableRewriter(MachineInstr &MI) : Rewriter(MI) {
NumDefs = MI.getDesc().getNumDefs();
}
/// \see See Rewriter::getNextRewritableSource()
/// All such sources need to be considered rewritable in order to
/// rewrite a uncoalescable copy-like instruction. This method return
/// each definition that must be checked if rewritable.
bool getNextRewritableSource(RegSubRegPair &Src,
RegSubRegPair &Dst) override {
// Find the next non-dead definition and continue from there.
if (CurrentSrcIdx == NumDefs)
return false;
while (CopyLike.getOperand(CurrentSrcIdx).isDead()) {
++CurrentSrcIdx;
if (CurrentSrcIdx == NumDefs)
return false;
}
// What we track are the alternative sources of the definition.
Src = RegSubRegPair(0, 0);
const MachineOperand &MODef = CopyLike.getOperand(CurrentSrcIdx);
Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg());
CurrentSrcIdx++;
return true;
}
bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override {
return false;
}
};
/// Specialized rewriter for INSERT_SUBREG instruction.
class InsertSubregRewriter : public Rewriter {
public:
InsertSubregRewriter(MachineInstr &MI) : Rewriter(MI) {
assert(MI.isInsertSubreg() && "Invalid instruction");
}
/// \see See Rewriter::getNextRewritableSource()
/// Here CopyLike has the following form:
/// dst = INSERT_SUBREG Src1, Src2.src2SubIdx, subIdx.
/// Src1 has the same register class has dst, hence, there is
/// nothing to rewrite.
/// Src2.src2SubIdx, may not be register coalescer friendly.
/// Therefore, the first call to this method returns:
/// (SrcReg, SrcSubReg) = (Src2, src2SubIdx).
/// (DstReg, DstSubReg) = (dst, subIdx).
///
/// Subsequence calls will return false.
bool getNextRewritableSource(RegSubRegPair &Src,
RegSubRegPair &Dst) override {
// If we already get the only source we can rewrite, return false.
if (CurrentSrcIdx == 2)
return false;
// We are looking at v2 = INSERT_SUBREG v0, v1, sub0.
CurrentSrcIdx = 2;
const MachineOperand &MOInsertedReg = CopyLike.getOperand(2);
Src = RegSubRegPair(MOInsertedReg.getReg(), MOInsertedReg.getSubReg());
const MachineOperand &MODef = CopyLike.getOperand(0);
// We want to track something that is compatible with the
// partial definition.
if (MODef.getSubReg())
// Bail if we have to compose sub-register indices.
return false;
Dst = RegSubRegPair(MODef.getReg(),
(unsigned)CopyLike.getOperand(3).getImm());
return true;
}
bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override {
if (CurrentSrcIdx != 2)
return false;
// We are rewriting the inserted reg.
MachineOperand &MO = CopyLike.getOperand(CurrentSrcIdx);
MO.setReg(NewReg);
MO.setSubReg(NewSubReg);
return true;
}
};
/// Specialized rewriter for EXTRACT_SUBREG instruction.
class ExtractSubregRewriter : public Rewriter {
const TargetInstrInfo &TII;
public:
ExtractSubregRewriter(MachineInstr &MI, const TargetInstrInfo &TII)
: Rewriter(MI), TII(TII) {
assert(MI.isExtractSubreg() && "Invalid instruction");
}
/// \see Rewriter::getNextRewritableSource()
/// Here CopyLike has the following form:
/// dst.dstSubIdx = EXTRACT_SUBREG Src, subIdx.
/// There is only one rewritable source: Src.subIdx,
/// which defines dst.dstSubIdx.
bool getNextRewritableSource(RegSubRegPair &Src,
RegSubRegPair &Dst) override {
// If we already get the only source we can rewrite, return false.
if (CurrentSrcIdx == 1)
return false;
// We are looking at v1 = EXTRACT_SUBREG v0, sub0.
CurrentSrcIdx = 1;
const MachineOperand &MOExtractedReg = CopyLike.getOperand(1);
// If we have to compose sub-register indices, bail out.
if (MOExtractedReg.getSubReg())
return false;
Src = RegSubRegPair(MOExtractedReg.getReg(),
CopyLike.getOperand(2).getImm());