CodeGen peephole: fold redundant phys reg copies
[oota-llvm.git] / lib / CodeGen / PeepholeOptimizer.cpp
1 //===-- PeepholeOptimizer.cpp - Peephole Optimizations --------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Perform peephole optimizations on the machine code:
11 //
12 // - Optimize Extensions
13 //
14 //     Optimization of sign / zero extension instructions. It may be extended to
15 //     handle other instructions with similar properties.
16 //
17 //     On some targets, some instructions, e.g. X86 sign / zero extension, may
18 //     leave the source value in the lower part of the result. This optimization
19 //     will replace some uses of the pre-extension value with uses of the
20 //     sub-register of the results.
21 //
22 // - Optimize Comparisons
23 //
24 //     Optimization of comparison instructions. For instance, in this code:
25 //
26 //       sub r1, 1
27 //       cmp r1, 0
28 //       bz  L1
29 //
30 //     If the "sub" instruction all ready sets (or could be modified to set) the
31 //     same flag that the "cmp" instruction sets and that "bz" uses, then we can
32 //     eliminate the "cmp" instruction.
33 //
34 //     Another instance, in this code:
35 //
36 //       sub r1, r3 | sub r1, imm
37 //       cmp r3, r1 or cmp r1, r3 | cmp r1, imm
38 //       bge L1
39 //
40 //     If the branch instruction can use flag from "sub", then we can replace
41 //     "sub" with "subs" and eliminate the "cmp" instruction.
42 //
43 // - Optimize Loads:
44 //
45 //     Loads that can be folded into a later instruction. A load is foldable
46 //     if it loads to virtual registers and the virtual register defined has
47 //     a single use.
48 //
49 // - Optimize Copies and Bitcast (more generally, target specific copies):
50 //
51 //     Rewrite copies and bitcasts to avoid cross register bank copies
52 //     when possible.
53 //     E.g., Consider the following example, where capital and lower
54 //     letters denote different register file:
55 //     b = copy A <-- cross-bank copy
56 //     C = copy b <-- cross-bank copy
57 //   =>
58 //     b = copy A <-- cross-bank copy
59 //     C = copy A <-- same-bank copy
60 //
61 //     E.g., for bitcast:
62 //     b = bitcast A <-- cross-bank copy
63 //     C = bitcast b <-- cross-bank copy
64 //   =>
65 //     b = bitcast A <-- cross-bank copy
66 //     C = copy A    <-- same-bank copy
67 //===----------------------------------------------------------------------===//
68
69 #include "llvm/CodeGen/Passes.h"
70 #include "llvm/ADT/DenseMap.h"
71 #include "llvm/ADT/SmallPtrSet.h"
72 #include "llvm/ADT/SmallSet.h"
73 #include "llvm/ADT/Statistic.h"
74 #include "llvm/CodeGen/MachineDominators.h"
75 #include "llvm/CodeGen/MachineInstrBuilder.h"
76 #include "llvm/CodeGen/MachineRegisterInfo.h"
77 #include "llvm/Support/CommandLine.h"
78 #include "llvm/Support/Debug.h"
79 #include "llvm/Support/raw_ostream.h"
80 #include "llvm/Target/TargetInstrInfo.h"
81 #include "llvm/Target/TargetRegisterInfo.h"
82 #include "llvm/Target/TargetSubtargetInfo.h"
83 #include <utility>
84 using namespace llvm;
85
86 #define DEBUG_TYPE "peephole-opt"
87
88 // Optimize Extensions
89 static cl::opt<bool>
90 Aggressive("aggressive-ext-opt", cl::Hidden,
91            cl::desc("Aggressive extension optimization"));
92
93 static cl::opt<bool>
94 DisablePeephole("disable-peephole", cl::Hidden, cl::init(false),
95                 cl::desc("Disable the peephole optimizer"));
96
97 static cl::opt<bool>
98 DisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden, cl::init(false),
99                   cl::desc("Disable advanced copy optimization"));
100
101 static cl::opt<bool> DisableNAPhysCopyOpt(
102     "disable-non-allocatable-phys-copy-opt", cl::Hidden, cl::init(false),
103     cl::desc("Disable non-allocatable physical register copy optimization"));
104
105 // Limit the number of PHI instructions to process
106 // in PeepholeOptimizer::getNextSource.
107 static cl::opt<unsigned> RewritePHILimit(
108     "rewrite-phi-limit", cl::Hidden, cl::init(10),
109     cl::desc("Limit the length of PHI chains to lookup"));
110
111 STATISTIC(NumReuse,      "Number of extension results reused");
112 STATISTIC(NumCmps,       "Number of compares eliminated");
113 STATISTIC(NumImmFold,    "Number of move immediate folded");
114 STATISTIC(NumLoadFold,   "Number of loads folded");
115 STATISTIC(NumSelects,    "Number of selects optimized");
116 STATISTIC(NumUncoalescableCopies, "Number of uncoalescable copies optimized");
117 STATISTIC(NumRewrittenCopies, "Number of copies rewritten");
118 STATISTIC(NumNAPhysCopies, "Number of non-allocatable physical copies removed");
119
120 namespace {
121   class ValueTrackerResult;
122
123   class PeepholeOptimizer : public MachineFunctionPass {
124     const TargetInstrInfo *TII;
125     const TargetRegisterInfo *TRI;
126     MachineRegisterInfo   *MRI;
127     MachineDominatorTree  *DT;  // Machine dominator tree
128
129   public:
130     static char ID; // Pass identification
131     PeepholeOptimizer() : MachineFunctionPass(ID) {
132       initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry());
133     }
134
135     bool runOnMachineFunction(MachineFunction &MF) override;
136
137     void getAnalysisUsage(AnalysisUsage &AU) const override {
138       AU.setPreservesCFG();
139       MachineFunctionPass::getAnalysisUsage(AU);
140       if (Aggressive) {
141         AU.addRequired<MachineDominatorTree>();
142         AU.addPreserved<MachineDominatorTree>();
143       }
144     }
145
146     /// \brief Track Def -> Use info used for rewriting copies.
147     typedef SmallDenseMap<TargetInstrInfo::RegSubRegPair, ValueTrackerResult>
148         RewriteMapTy;
149
150   private:
151     bool optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB);
152     bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB,
153                           SmallPtrSetImpl<MachineInstr*> &LocalMIs);
154     bool optimizeSelect(MachineInstr *MI,
155                         SmallPtrSetImpl<MachineInstr *> &LocalMIs);
156     bool optimizeCondBranch(MachineInstr *MI);
157     bool optimizeCoalescableCopy(MachineInstr *MI);
158     bool optimizeUncoalescableCopy(MachineInstr *MI,
159                                    SmallPtrSetImpl<MachineInstr *> &LocalMIs);
160     bool findNextSource(unsigned Reg, unsigned SubReg,
161                         RewriteMapTy &RewriteMap);
162     bool isMoveImmediate(MachineInstr *MI,
163                          SmallSet<unsigned, 4> &ImmDefRegs,
164                          DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
165     bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
166                        SmallSet<unsigned, 4> &ImmDefRegs,
167                        DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
168
169     /// \brief If copy instruction \p MI is a virtual register copy, track it in
170     /// the set \p CopySrcRegs and \p CopyMIs. If this virtual register was
171     /// previously seen as a copy, replace the uses of this copy with the
172     /// previously seen copy's destination register.
173     bool foldRedundantCopy(MachineInstr *MI,
174                            SmallSet<unsigned, 4> &CopySrcRegs,
175                            DenseMap<unsigned, MachineInstr *> &CopyMIs);
176
177     /// \brief Is the register \p Reg a non-allocatable physical register?
178     bool isNAPhysCopy(unsigned Reg);
179
180     /// \brief If copy instruction \p MI is a non-allocatable virtual<->physical
181     /// register copy, track it in the \p NAPhysToVirtMIs map. If this
182     /// non-allocatable physical register was previously copied to a virtual
183     /// registered and hasn't been clobbered, the virt->phys copy can be
184     /// deleted.
185     bool foldRedundantNAPhysCopy(
186         MachineInstr *MI,
187         DenseMap<unsigned, MachineInstr *> &NAPhysToVirtMIs);
188
189     bool isLoadFoldable(MachineInstr *MI,
190                         SmallSet<unsigned, 16> &FoldAsLoadDefCandidates);
191
192     /// \brief Check whether \p MI is understood by the register coalescer
193     /// but may require some rewriting.
194     bool isCoalescableCopy(const MachineInstr &MI) {
195       // SubregToRegs are not interesting, because they are already register
196       // coalescer friendly.
197       return MI.isCopy() || (!DisableAdvCopyOpt &&
198                              (MI.isRegSequence() || MI.isInsertSubreg() ||
199                               MI.isExtractSubreg()));
200     }
201
202     /// \brief Check whether \p MI is a copy like instruction that is
203     /// not recognized by the register coalescer.
204     bool isUncoalescableCopy(const MachineInstr &MI) {
205       return MI.isBitcast() ||
206              (!DisableAdvCopyOpt &&
207               (MI.isRegSequenceLike() || MI.isInsertSubregLike() ||
208                MI.isExtractSubregLike()));
209     }
210   };
211
212   /// \brief Helper class to hold a reply for ValueTracker queries. Contains the
213   /// returned sources for a given search and the instructions where the sources
214   /// were tracked from.
215   class ValueTrackerResult {
216   private:
217     /// Track all sources found by one ValueTracker query.
218     SmallVector<TargetInstrInfo::RegSubRegPair, 2> RegSrcs;
219
220     /// Instruction using the sources in 'RegSrcs'.
221     const MachineInstr *Inst;
222
223   public:
224     ValueTrackerResult() : Inst(nullptr) {}
225     ValueTrackerResult(unsigned Reg, unsigned SubReg) : Inst(nullptr) {
226       addSource(Reg, SubReg);
227     }
228
229     bool isValid() const { return getNumSources() > 0; }
230
231     void setInst(const MachineInstr *I) { Inst = I; }
232     const MachineInstr *getInst() const { return Inst; }
233
234     void clear() {
235       RegSrcs.clear();
236       Inst = nullptr;
237     }
238
239     void addSource(unsigned SrcReg, unsigned SrcSubReg) {
240       RegSrcs.push_back(TargetInstrInfo::RegSubRegPair(SrcReg, SrcSubReg));
241     }
242
243     void setSource(int Idx, unsigned SrcReg, unsigned SrcSubReg) {
244       assert(Idx < getNumSources() && "Reg pair source out of index");
245       RegSrcs[Idx] = TargetInstrInfo::RegSubRegPair(SrcReg, SrcSubReg);
246     }
247
248     int getNumSources() const { return RegSrcs.size(); }
249
250     unsigned getSrcReg(int Idx) const {
251       assert(Idx < getNumSources() && "Reg source out of index");
252       return RegSrcs[Idx].Reg;
253     }
254
255     unsigned getSrcSubReg(int Idx) const {
256       assert(Idx < getNumSources() && "SubReg source out of index");
257       return RegSrcs[Idx].SubReg;
258     }
259
260     bool operator==(const ValueTrackerResult &Other) {
261       if (Other.getInst() != getInst())
262         return false;
263
264       if (Other.getNumSources() != getNumSources())
265         return false;
266
267       for (int i = 0, e = Other.getNumSources(); i != e; ++i)
268         if (Other.getSrcReg(i) != getSrcReg(i) ||
269             Other.getSrcSubReg(i) != getSrcSubReg(i))
270           return false;
271       return true;
272     }
273   };
274
275   /// \brief Helper class to track the possible sources of a value defined by
276   /// a (chain of) copy related instructions.
277   /// Given a definition (instruction and definition index), this class
278   /// follows the use-def chain to find successive suitable sources.
279   /// The given source can be used to rewrite the definition into
280   /// def = COPY src.
281   ///
282   /// For instance, let us consider the following snippet:
283   /// v0 =
284   /// v2 = INSERT_SUBREG v1, v0, sub0
285   /// def = COPY v2.sub0
286   ///
287   /// Using a ValueTracker for def = COPY v2.sub0 will give the following
288   /// suitable sources:
289   /// v2.sub0 and v0.
290   /// Then, def can be rewritten into def = COPY v0.
291   class ValueTracker {
292   private:
293     /// The current point into the use-def chain.
294     const MachineInstr *Def;
295     /// The index of the definition in Def.
296     unsigned DefIdx;
297     /// The sub register index of the definition.
298     unsigned DefSubReg;
299     /// The register where the value can be found.
300     unsigned Reg;
301     /// Specifiy whether or not the value tracking looks through
302     /// complex instructions. When this is false, the value tracker
303     /// bails on everything that is not a copy or a bitcast.
304     ///
305     /// Note: This could have been implemented as a specialized version of
306     /// the ValueTracker class but that would have complicated the code of
307     /// the users of this class.
308     bool UseAdvancedTracking;
309     /// MachineRegisterInfo used to perform tracking.
310     const MachineRegisterInfo &MRI;
311     /// Optional TargetInstrInfo used to perform some complex
312     /// tracking.
313     const TargetInstrInfo *TII;
314
315     /// \brief Dispatcher to the right underlying implementation of
316     /// getNextSource.
317     ValueTrackerResult getNextSourceImpl();
318     /// \brief Specialized version of getNextSource for Copy instructions.
319     ValueTrackerResult getNextSourceFromCopy();
320     /// \brief Specialized version of getNextSource for Bitcast instructions.
321     ValueTrackerResult getNextSourceFromBitcast();
322     /// \brief Specialized version of getNextSource for RegSequence
323     /// instructions.
324     ValueTrackerResult getNextSourceFromRegSequence();
325     /// \brief Specialized version of getNextSource for InsertSubreg
326     /// instructions.
327     ValueTrackerResult getNextSourceFromInsertSubreg();
328     /// \brief Specialized version of getNextSource for ExtractSubreg
329     /// instructions.
330     ValueTrackerResult getNextSourceFromExtractSubreg();
331     /// \brief Specialized version of getNextSource for SubregToReg
332     /// instructions.
333     ValueTrackerResult getNextSourceFromSubregToReg();
334     /// \brief Specialized version of getNextSource for PHI instructions.
335     ValueTrackerResult getNextSourceFromPHI();
336
337   public:
338     /// \brief Create a ValueTracker instance for the value defined by \p Reg.
339     /// \p DefSubReg represents the sub register index the value tracker will
340     /// track. It does not need to match the sub register index used in the
341     /// definition of \p Reg.
342     /// \p UseAdvancedTracking specifies whether or not the value tracker looks
343     /// through complex instructions. By default (false), it handles only copy
344     /// and bitcast instructions.
345     /// If \p Reg is a physical register, a value tracker constructed with
346     /// this constructor will not find any alternative source.
347     /// Indeed, when \p Reg is a physical register that constructor does not
348     /// know which definition of \p Reg it should track.
349     /// Use the next constructor to track a physical register.
350     ValueTracker(unsigned Reg, unsigned DefSubReg,
351                  const MachineRegisterInfo &MRI,
352                  bool UseAdvancedTracking = false,
353                  const TargetInstrInfo *TII = nullptr)
354         : Def(nullptr), DefIdx(0), DefSubReg(DefSubReg), Reg(Reg),
355           UseAdvancedTracking(UseAdvancedTracking), MRI(MRI), TII(TII) {
356       if (!TargetRegisterInfo::isPhysicalRegister(Reg)) {
357         Def = MRI.getVRegDef(Reg);
358         DefIdx = MRI.def_begin(Reg).getOperandNo();
359       }
360     }
361
362     /// \brief Create a ValueTracker instance for the value defined by
363     /// the pair \p MI, \p DefIdx.
364     /// Unlike the other constructor, the value tracker produced by this one
365     /// may be able to find a new source when the definition is a physical
366     /// register.
367     /// This could be useful to rewrite target specific instructions into
368     /// generic copy instructions.
369     ValueTracker(const MachineInstr &MI, unsigned DefIdx, unsigned DefSubReg,
370                  const MachineRegisterInfo &MRI,
371                  bool UseAdvancedTracking = false,
372                  const TargetInstrInfo *TII = nullptr)
373         : Def(&MI), DefIdx(DefIdx), DefSubReg(DefSubReg),
374           UseAdvancedTracking(UseAdvancedTracking), MRI(MRI), TII(TII) {
375       assert(DefIdx < Def->getDesc().getNumDefs() &&
376              Def->getOperand(DefIdx).isReg() && "Invalid definition");
377       Reg = Def->getOperand(DefIdx).getReg();
378     }
379
380     /// \brief Following the use-def chain, get the next available source
381     /// for the tracked value.
382     /// \return A ValueTrackerResult containing a set of registers
383     /// and sub registers with tracked values. A ValueTrackerResult with
384     /// an empty set of registers means no source was found.
385     ValueTrackerResult getNextSource();
386
387     /// \brief Get the last register where the initial value can be found.
388     /// Initially this is the register of the definition.
389     /// Then, after each successful call to getNextSource, this is the
390     /// register of the last source.
391     unsigned getReg() const { return Reg; }
392   };
393 }
394
395 char PeepholeOptimizer::ID = 0;
396 char &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID;
397 INITIALIZE_PASS_BEGIN(PeepholeOptimizer, "peephole-opts",
398                 "Peephole Optimizations", false, false)
399 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
400 INITIALIZE_PASS_END(PeepholeOptimizer, "peephole-opts",
401                 "Peephole Optimizations", false, false)
402
403 /// optimizeExtInstr - If instruction is a copy-like instruction, i.e. it reads
404 /// a single register and writes a single register and it does not modify the
405 /// source, and if the source value is preserved as a sub-register of the
406 /// result, then replace all reachable uses of the source with the subreg of the
407 /// result.
408 ///
409 /// Do not generate an EXTRACT that is used only in a debug use, as this changes
410 /// the code. Since this code does not currently share EXTRACTs, just ignore all
411 /// debug uses.
412 bool PeepholeOptimizer::
413 optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB,
414                  SmallPtrSetImpl<MachineInstr*> &LocalMIs) {
415   unsigned SrcReg, DstReg, SubIdx;
416   if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx))
417     return false;
418
419   if (TargetRegisterInfo::isPhysicalRegister(DstReg) ||
420       TargetRegisterInfo::isPhysicalRegister(SrcReg))
421     return false;
422
423   if (MRI->hasOneNonDBGUse(SrcReg))
424     // No other uses.
425     return false;
426
427   // Ensure DstReg can get a register class that actually supports
428   // sub-registers. Don't change the class until we commit.
429   const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
430   DstRC = TRI->getSubClassWithSubReg(DstRC, SubIdx);
431   if (!DstRC)
432     return false;
433
434   // The ext instr may be operating on a sub-register of SrcReg as well.
435   // PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit
436   // register.
437   // If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of
438   // SrcReg:SubIdx should be replaced.
439   bool UseSrcSubIdx =
440       TRI->getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != nullptr;
441
442   // The source has other uses. See if we can replace the other uses with use of
443   // the result of the extension.
444   SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs;
445   for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg))
446     ReachedBBs.insert(UI.getParent());
447
448   // Uses that are in the same BB of uses of the result of the instruction.
449   SmallVector<MachineOperand*, 8> Uses;
450
451   // Uses that the result of the instruction can reach.
452   SmallVector<MachineOperand*, 8> ExtendedUses;
453
454   bool ExtendLife = true;
455   for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) {
456     MachineInstr *UseMI = UseMO.getParent();
457     if (UseMI == MI)
458       continue;
459
460     if (UseMI->isPHI()) {
461       ExtendLife = false;
462       continue;
463     }
464
465     // Only accept uses of SrcReg:SubIdx.
466     if (UseSrcSubIdx && UseMO.getSubReg() != SubIdx)
467       continue;
468
469     // It's an error to translate this:
470     //
471     //    %reg1025 = <sext> %reg1024
472     //     ...
473     //    %reg1026 = SUBREG_TO_REG 0, %reg1024, 4
474     //
475     // into this:
476     //
477     //    %reg1025 = <sext> %reg1024
478     //     ...
479     //    %reg1027 = COPY %reg1025:4
480     //    %reg1026 = SUBREG_TO_REG 0, %reg1027, 4
481     //
482     // The problem here is that SUBREG_TO_REG is there to assert that an
483     // implicit zext occurs. It doesn't insert a zext instruction. If we allow
484     // the COPY here, it will give us the value after the <sext>, not the
485     // original value of %reg1024 before <sext>.
486     if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG)
487       continue;
488
489     MachineBasicBlock *UseMBB = UseMI->getParent();
490     if (UseMBB == MBB) {
491       // Local uses that come after the extension.
492       if (!LocalMIs.count(UseMI))
493         Uses.push_back(&UseMO);
494     } else if (ReachedBBs.count(UseMBB)) {
495       // Non-local uses where the result of the extension is used. Always
496       // replace these unless it's a PHI.
497       Uses.push_back(&UseMO);
498     } else if (Aggressive && DT->dominates(MBB, UseMBB)) {
499       // We may want to extend the live range of the extension result in order
500       // to replace these uses.
501       ExtendedUses.push_back(&UseMO);
502     } else {
503       // Both will be live out of the def MBB anyway. Don't extend live range of
504       // the extension result.
505       ExtendLife = false;
506       break;
507     }
508   }
509
510   if (ExtendLife && !ExtendedUses.empty())
511     // Extend the liveness of the extension result.
512     Uses.append(ExtendedUses.begin(), ExtendedUses.end());
513
514   // Now replace all uses.
515   bool Changed = false;
516   if (!Uses.empty()) {
517     SmallPtrSet<MachineBasicBlock*, 4> PHIBBs;
518
519     // Look for PHI uses of the extended result, we don't want to extend the
520     // liveness of a PHI input. It breaks all kinds of assumptions down
521     // stream. A PHI use is expected to be the kill of its source values.
522     for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg))
523       if (UI.isPHI())
524         PHIBBs.insert(UI.getParent());
525
526     const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
527     for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
528       MachineOperand *UseMO = Uses[i];
529       MachineInstr *UseMI = UseMO->getParent();
530       MachineBasicBlock *UseMBB = UseMI->getParent();
531       if (PHIBBs.count(UseMBB))
532         continue;
533
534       // About to add uses of DstReg, clear DstReg's kill flags.
535       if (!Changed) {
536         MRI->clearKillFlags(DstReg);
537         MRI->constrainRegClass(DstReg, DstRC);
538       }
539
540       unsigned NewVR = MRI->createVirtualRegister(RC);
541       MachineInstr *Copy = BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(),
542                                    TII->get(TargetOpcode::COPY), NewVR)
543         .addReg(DstReg, 0, SubIdx);
544       // SubIdx applies to both SrcReg and DstReg when UseSrcSubIdx is set.
545       if (UseSrcSubIdx) {
546         Copy->getOperand(0).setSubReg(SubIdx);
547         Copy->getOperand(0).setIsUndef();
548       }
549       UseMO->setReg(NewVR);
550       ++NumReuse;
551       Changed = true;
552     }
553   }
554
555   return Changed;
556 }
557
558 /// optimizeCmpInstr - If the instruction is a compare and the previous
559 /// instruction it's comparing against all ready sets (or could be modified to
560 /// set) the same flag as the compare, then we can remove the comparison and use
561 /// the flag from the previous instruction.
562 bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr *MI,
563                                          MachineBasicBlock *MBB) {
564   // If this instruction is a comparison against zero and isn't comparing a
565   // physical register, we can try to optimize it.
566   unsigned SrcReg, SrcReg2;
567   int CmpMask, CmpValue;
568   if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) ||
569       TargetRegisterInfo::isPhysicalRegister(SrcReg) ||
570       (SrcReg2 != 0 && TargetRegisterInfo::isPhysicalRegister(SrcReg2)))
571     return false;
572
573   // Attempt to optimize the comparison instruction.
574   if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) {
575     ++NumCmps;
576     return true;
577   }
578
579   return false;
580 }
581
582 /// Optimize a select instruction.
583 bool PeepholeOptimizer::optimizeSelect(MachineInstr *MI,
584                             SmallPtrSetImpl<MachineInstr *> &LocalMIs) {
585   unsigned TrueOp = 0;
586   unsigned FalseOp = 0;
587   bool Optimizable = false;
588   SmallVector<MachineOperand, 4> Cond;
589   if (TII->analyzeSelect(MI, Cond, TrueOp, FalseOp, Optimizable))
590     return false;
591   if (!Optimizable)
592     return false;
593   if (!TII->optimizeSelect(MI, LocalMIs))
594     return false;
595   MI->eraseFromParent();
596   ++NumSelects;
597   return true;
598 }
599
600 /// \brief Check if a simpler conditional branch can be
601 // generated
602 bool PeepholeOptimizer::optimizeCondBranch(MachineInstr *MI) {
603   return TII->optimizeCondBranch(MI);
604 }
605
606 /// \brief Try to find the next source that share the same register file
607 /// for the value defined by \p Reg and \p SubReg.
608 /// When true is returned, the \p RewriteMap can be used by the client to
609 /// retrieve all Def -> Use along the way up to the next source. Any found
610 /// Use that is not itself a key for another entry, is the next source to
611 /// use. During the search for the next source, multiple sources can be found
612 /// given multiple incoming sources of a PHI instruction. In this case, we
613 /// look in each PHI source for the next source; all found next sources must
614 /// share the same register file as \p Reg and \p SubReg. The client should
615 /// then be capable to rewrite all intermediate PHIs to get the next source.
616 /// \return False if no alternative sources are available. True otherwise.
617 bool PeepholeOptimizer::findNextSource(unsigned Reg, unsigned SubReg,
618                                        RewriteMapTy &RewriteMap) {
619   // Do not try to find a new source for a physical register.
620   // So far we do not have any motivating example for doing that.
621   // Thus, instead of maintaining untested code, we will revisit that if
622   // that changes at some point.
623   if (TargetRegisterInfo::isPhysicalRegister(Reg))
624     return false;
625   const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);
626
627   SmallVector<TargetInstrInfo::RegSubRegPair, 4> SrcToLook;
628   TargetInstrInfo::RegSubRegPair CurSrcPair(Reg, SubReg);
629   SrcToLook.push_back(CurSrcPair);
630
631   unsigned PHICount = 0;
632   while (!SrcToLook.empty() && PHICount < RewritePHILimit) {
633     TargetInstrInfo::RegSubRegPair Pair = SrcToLook.pop_back_val();
634     // As explained above, do not handle physical registers
635     if (TargetRegisterInfo::isPhysicalRegister(Pair.Reg))
636       return false;
637
638     CurSrcPair = Pair;
639     ValueTracker ValTracker(CurSrcPair.Reg, CurSrcPair.SubReg, *MRI,
640                             !DisableAdvCopyOpt, TII);
641     ValueTrackerResult Res;
642     bool ShouldRewrite = false;
643
644     do {
645       // Follow the chain of copies until we reach the top of the use-def chain
646       // or find a more suitable source.
647       Res = ValTracker.getNextSource();
648       if (!Res.isValid())
649         break;
650
651       // Insert the Def -> Use entry for the recently found source.
652       ValueTrackerResult CurSrcRes = RewriteMap.lookup(CurSrcPair);
653       if (CurSrcRes.isValid()) {
654         assert(CurSrcRes == Res && "ValueTrackerResult found must match");
655         // An existent entry with multiple sources is a PHI cycle we must avoid.
656         // Otherwise it's an entry with a valid next source we already found.
657         if (CurSrcRes.getNumSources() > 1) {
658           DEBUG(dbgs() << "findNextSource: found PHI cycle, aborting...\n");
659           return false;
660         }
661         break;
662       }
663       RewriteMap.insert(std::make_pair(CurSrcPair, Res));
664
665       // ValueTrackerResult usually have one source unless it's the result from
666       // a PHI instruction. Add the found PHI edges to be looked up further.
667       unsigned NumSrcs = Res.getNumSources();
668       if (NumSrcs > 1) {
669         PHICount++;
670         for (unsigned i = 0; i < NumSrcs; ++i)
671           SrcToLook.push_back(TargetInstrInfo::RegSubRegPair(
672               Res.getSrcReg(i), Res.getSrcSubReg(i)));
673         break;
674       }
675
676       CurSrcPair.Reg = Res.getSrcReg(0);
677       CurSrcPair.SubReg = Res.getSrcSubReg(0);
678       // Do not extend the live-ranges of physical registers as they add
679       // constraints to the register allocator. Moreover, if we want to extend
680       // the live-range of a physical register, unlike SSA virtual register,
681       // we will have to check that they aren't redefine before the related use.
682       if (TargetRegisterInfo::isPhysicalRegister(CurSrcPair.Reg))
683         return false;
684
685       const TargetRegisterClass *SrcRC = MRI->getRegClass(CurSrcPair.Reg);
686       ShouldRewrite = TRI->shouldRewriteCopySrc(DefRC, SubReg, SrcRC,
687                                                 CurSrcPair.SubReg);
688     } while (!ShouldRewrite);
689
690     // Continue looking for new sources...
691     if (Res.isValid())
692       continue;
693
694     // Do not continue searching for a new source if the there's at least
695     // one use-def which cannot be rewritten.
696     if (!ShouldRewrite)
697       return false;
698   }
699
700   if (PHICount >= RewritePHILimit) {
701     DEBUG(dbgs() << "findNextSource: PHI limit reached\n");
702     return false;
703   }
704
705   // If we did not find a more suitable source, there is nothing to optimize.
706   return CurSrcPair.Reg != Reg;
707 }
708
709 /// \brief Insert a PHI instruction with incoming edges \p SrcRegs that are
710 /// guaranteed to have the same register class. This is necessary whenever we
711 /// successfully traverse a PHI instruction and find suitable sources coming
712 /// from its edges. By inserting a new PHI, we provide a rewritten PHI def
713 /// suitable to be used in a new COPY instruction.
714 static MachineInstr *
715 insertPHI(MachineRegisterInfo *MRI, const TargetInstrInfo *TII,
716           const SmallVectorImpl<TargetInstrInfo::RegSubRegPair> &SrcRegs,
717           MachineInstr *OrigPHI) {
718   assert(!SrcRegs.empty() && "No sources to create a PHI instruction?");
719
720   const TargetRegisterClass *NewRC = MRI->getRegClass(SrcRegs[0].Reg);
721   unsigned NewVR = MRI->createVirtualRegister(NewRC);
722   MachineBasicBlock *MBB = OrigPHI->getParent();
723   MachineInstrBuilder MIB = BuildMI(*MBB, OrigPHI, OrigPHI->getDebugLoc(),
724                                     TII->get(TargetOpcode::PHI), NewVR);
725
726   unsigned MBBOpIdx = 2;
727   for (auto RegPair : SrcRegs) {
728     MIB.addReg(RegPair.Reg, 0, RegPair.SubReg);
729     MIB.addMBB(OrigPHI->getOperand(MBBOpIdx).getMBB());
730     // Since we're extended the lifetime of RegPair.Reg, clear the
731     // kill flags to account for that and make RegPair.Reg reaches
732     // the new PHI.
733     MRI->clearKillFlags(RegPair.Reg);
734     MBBOpIdx += 2;
735   }
736
737   return MIB;
738 }
739
740 namespace {
741 /// \brief Helper class to rewrite the arguments of a copy-like instruction.
742 class CopyRewriter {
743 protected:
744   /// The copy-like instruction.
745   MachineInstr &CopyLike;
746   /// The index of the source being rewritten.
747   unsigned CurrentSrcIdx;
748
749 public:
750   CopyRewriter(MachineInstr &MI) : CopyLike(MI), CurrentSrcIdx(0) {}
751
752   virtual ~CopyRewriter() {}
753
754   /// \brief Get the next rewritable source (SrcReg, SrcSubReg) and
755   /// the related value that it affects (TrackReg, TrackSubReg).
756   /// A source is considered rewritable if its register class and the
757   /// register class of the related TrackReg may not be register
758   /// coalescer friendly. In other words, given a copy-like instruction
759   /// not all the arguments may be returned at rewritable source, since
760   /// some arguments are none to be register coalescer friendly.
761   ///
762   /// Each call of this method moves the current source to the next
763   /// rewritable source.
764   /// For instance, let CopyLike be the instruction to rewrite.
765   /// CopyLike has one definition and one source:
766   /// dst.dstSubIdx = CopyLike src.srcSubIdx.
767   ///
768   /// The first call will give the first rewritable source, i.e.,
769   /// the only source this instruction has:
770   /// (SrcReg, SrcSubReg) = (src, srcSubIdx).
771   /// This source defines the whole definition, i.e.,
772   /// (TrackReg, TrackSubReg) = (dst, dstSubIdx).
773   ///
774   /// The second and subsequent calls will return false, as there is only one
775   /// rewritable source.
776   ///
777   /// \return True if a rewritable source has been found, false otherwise.
778   /// The output arguments are valid if and only if true is returned.
779   virtual bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg,
780                                        unsigned &TrackReg,
781                                        unsigned &TrackSubReg) {
782     // If CurrentSrcIdx == 1, this means this function has already been called
783     // once. CopyLike has one definition and one argument, thus, there is
784     // nothing else to rewrite.
785     if (!CopyLike.isCopy() || CurrentSrcIdx == 1)
786       return false;
787     // This is the first call to getNextRewritableSource.
788     // Move the CurrentSrcIdx to remember that we made that call.
789     CurrentSrcIdx = 1;
790     // The rewritable source is the argument.
791     const MachineOperand &MOSrc = CopyLike.getOperand(1);
792     SrcReg = MOSrc.getReg();
793     SrcSubReg = MOSrc.getSubReg();
794     // What we track are the alternative sources of the definition.
795     const MachineOperand &MODef = CopyLike.getOperand(0);
796     TrackReg = MODef.getReg();
797     TrackSubReg = MODef.getSubReg();
798     return true;
799   }
800
801   /// \brief Rewrite the current source with \p NewReg and \p NewSubReg
802   /// if possible.
803   /// \return True if the rewriting was possible, false otherwise.
804   virtual bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) {
805     if (!CopyLike.isCopy() || CurrentSrcIdx != 1)
806       return false;
807     MachineOperand &MOSrc = CopyLike.getOperand(CurrentSrcIdx);
808     MOSrc.setReg(NewReg);
809     MOSrc.setSubReg(NewSubReg);
810     return true;
811   }
812
813   /// \brief Given a \p Def.Reg and Def.SubReg  pair, use \p RewriteMap to find
814   /// the new source to use for rewrite. If \p HandleMultipleSources is true and
815   /// multiple sources for a given \p Def are found along the way, we found a
816   /// PHI instructions that needs to be rewritten.
817   /// TODO: HandleMultipleSources should be removed once we test PHI handling
818   /// with coalescable copies.
819   TargetInstrInfo::RegSubRegPair
820   getNewSource(MachineRegisterInfo *MRI, const TargetInstrInfo *TII,
821                TargetInstrInfo::RegSubRegPair Def,
822                PeepholeOptimizer::RewriteMapTy &RewriteMap,
823                bool HandleMultipleSources = true) {
824
825     TargetInstrInfo::RegSubRegPair LookupSrc(Def.Reg, Def.SubReg);
826     do {
827       ValueTrackerResult Res = RewriteMap.lookup(LookupSrc);
828       // If there are no entries on the map, LookupSrc is the new source.
829       if (!Res.isValid())
830         return LookupSrc;
831
832       // There's only one source for this definition, keep searching...
833       unsigned NumSrcs = Res.getNumSources();
834       if (NumSrcs == 1) {
835         LookupSrc.Reg = Res.getSrcReg(0);
836         LookupSrc.SubReg = Res.getSrcSubReg(0);
837         continue;
838       }
839
840       // TODO: Remove once multiple srcs w/ coalescable copies are supported.
841       if (!HandleMultipleSources)
842         break;
843
844       // Multiple sources, recurse into each source to find a new source
845       // for it. Then, rewrite the PHI accordingly to its new edges.
846       SmallVector<TargetInstrInfo::RegSubRegPair, 4> NewPHISrcs;
847       for (unsigned i = 0; i < NumSrcs; ++i) {
848         TargetInstrInfo::RegSubRegPair PHISrc(Res.getSrcReg(i),
849                                               Res.getSrcSubReg(i));
850         NewPHISrcs.push_back(
851             getNewSource(MRI, TII, PHISrc, RewriteMap, HandleMultipleSources));
852       }
853
854       // Build the new PHI node and return its def register as the new source.
855       MachineInstr *OrigPHI = const_cast<MachineInstr *>(Res.getInst());
856       MachineInstr *NewPHI = insertPHI(MRI, TII, NewPHISrcs, OrigPHI);
857       DEBUG(dbgs() << "-- getNewSource\n");
858       DEBUG(dbgs() << "   Replacing: " << *OrigPHI);
859       DEBUG(dbgs() << "        With: " << *NewPHI);
860       const MachineOperand &MODef = NewPHI->getOperand(0);
861       return TargetInstrInfo::RegSubRegPair(MODef.getReg(), MODef.getSubReg());
862
863     } while (1);
864
865     return TargetInstrInfo::RegSubRegPair(0, 0);
866   }
867
868   /// \brief Rewrite the source found through \p Def, by using the \p RewriteMap
869   /// and create a new COPY instruction. More info about RewriteMap in
870   /// PeepholeOptimizer::findNextSource. Right now this is only used to handle
871   /// Uncoalescable copies, since they are copy like instructions that aren't
872   /// recognized by the register allocator.
873   virtual MachineInstr *
874   RewriteSource(TargetInstrInfo::RegSubRegPair Def,
875                 PeepholeOptimizer::RewriteMapTy &RewriteMap) {
876     return nullptr;
877   }
878 };
879
880 /// \brief Helper class to rewrite uncoalescable copy like instructions
881 /// into new COPY (coalescable friendly) instructions.
882 class UncoalescableRewriter : public CopyRewriter {
883 protected:
884   const TargetInstrInfo &TII;
885   MachineRegisterInfo   &MRI;
886   /// The number of defs in the bitcast
887   unsigned NumDefs;
888
889 public:
890   UncoalescableRewriter(MachineInstr &MI, const TargetInstrInfo &TII,
891                          MachineRegisterInfo &MRI)
892       : CopyRewriter(MI), TII(TII), MRI(MRI) {
893     NumDefs = MI.getDesc().getNumDefs();
894   }
895
896   /// \brief Get the next rewritable def source (TrackReg, TrackSubReg)
897   /// All such sources need to be considered rewritable in order to
898   /// rewrite a uncoalescable copy-like instruction. This method return
899   /// each definition that must be checked if rewritable.
900   ///
901   bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg,
902                                unsigned &TrackReg,
903                                unsigned &TrackSubReg) override {
904     // Find the next non-dead definition and continue from there.
905     if (CurrentSrcIdx == NumDefs)
906       return false;
907
908     while (CopyLike.getOperand(CurrentSrcIdx).isDead()) {
909       ++CurrentSrcIdx;
910       if (CurrentSrcIdx == NumDefs)
911         return false;
912     }
913
914     // What we track are the alternative sources of the definition.
915     const MachineOperand &MODef = CopyLike.getOperand(CurrentSrcIdx);
916     TrackReg = MODef.getReg();
917     TrackSubReg = MODef.getSubReg();
918
919     CurrentSrcIdx++;
920     return true;
921   }
922
923   /// \brief Rewrite the source found through \p Def, by using the \p RewriteMap
924   /// and create a new COPY instruction. More info about RewriteMap in
925   /// PeepholeOptimizer::findNextSource. Right now this is only used to handle
926   /// Uncoalescable copies, since they are copy like instructions that aren't
927   /// recognized by the register allocator.
928   MachineInstr *
929   RewriteSource(TargetInstrInfo::RegSubRegPair Def,
930                 PeepholeOptimizer::RewriteMapTy &RewriteMap) override {
931     assert(!TargetRegisterInfo::isPhysicalRegister(Def.Reg) &&
932            "We do not rewrite physical registers");
933
934     // Find the new source to use in the COPY rewrite.
935     TargetInstrInfo::RegSubRegPair NewSrc =
936         getNewSource(&MRI, &TII, Def, RewriteMap);
937
938     // Insert the COPY.
939     const TargetRegisterClass *DefRC = MRI.getRegClass(Def.Reg);
940     unsigned NewVR = MRI.createVirtualRegister(DefRC);
941
942     MachineInstr *NewCopy =
943         BuildMI(*CopyLike.getParent(), &CopyLike, CopyLike.getDebugLoc(),
944                 TII.get(TargetOpcode::COPY), NewVR)
945             .addReg(NewSrc.Reg, 0, NewSrc.SubReg);
946
947     NewCopy->getOperand(0).setSubReg(Def.SubReg);
948     if (Def.SubReg)
949       NewCopy->getOperand(0).setIsUndef();
950
951     DEBUG(dbgs() << "-- RewriteSource\n");
952     DEBUG(dbgs() << "   Replacing: " << CopyLike);
953     DEBUG(dbgs() << "        With: " << *NewCopy);
954     MRI.replaceRegWith(Def.Reg, NewVR);
955     MRI.clearKillFlags(NewVR);
956
957     // We extended the lifetime of NewSrc.Reg, clear the kill flags to
958     // account for that.
959     MRI.clearKillFlags(NewSrc.Reg);
960
961     return NewCopy;
962   }
963 };
964
965 /// \brief Specialized rewriter for INSERT_SUBREG instruction.
966 class InsertSubregRewriter : public CopyRewriter {
967 public:
968   InsertSubregRewriter(MachineInstr &MI) : CopyRewriter(MI) {
969     assert(MI.isInsertSubreg() && "Invalid instruction");
970   }
971
972   /// \brief See CopyRewriter::getNextRewritableSource.
973   /// Here CopyLike has the following form:
974   /// dst = INSERT_SUBREG Src1, Src2.src2SubIdx, subIdx.
975   /// Src1 has the same register class has dst, hence, there is
976   /// nothing to rewrite.
977   /// Src2.src2SubIdx, may not be register coalescer friendly.
978   /// Therefore, the first call to this method returns:
979   /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx).
980   /// (TrackReg, TrackSubReg) = (dst, subIdx).
981   ///
982   /// Subsequence calls will return false.
983   bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg,
984                                unsigned &TrackReg,
985                                unsigned &TrackSubReg) override {
986     // If we already get the only source we can rewrite, return false.
987     if (CurrentSrcIdx == 2)
988       return false;
989     // We are looking at v2 = INSERT_SUBREG v0, v1, sub0.
990     CurrentSrcIdx = 2;
991     const MachineOperand &MOInsertedReg = CopyLike.getOperand(2);
992     SrcReg = MOInsertedReg.getReg();
993     SrcSubReg = MOInsertedReg.getSubReg();
994     const MachineOperand &MODef = CopyLike.getOperand(0);
995
996     // We want to track something that is compatible with the
997     // partial definition.
998     TrackReg = MODef.getReg();
999     if (MODef.getSubReg())
1000       // Bail if we have to compose sub-register indices.
1001       return false;
1002     TrackSubReg = (unsigned)CopyLike.getOperand(3).getImm();
1003     return true;
1004   }
1005   bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override {
1006     if (CurrentSrcIdx != 2)
1007       return false;
1008     // We are rewriting the inserted reg.
1009     MachineOperand &MO = CopyLike.getOperand(CurrentSrcIdx);
1010     MO.setReg(NewReg);
1011     MO.setSubReg(NewSubReg);
1012     return true;
1013   }
1014 };
1015
1016 /// \brief Specialized rewriter for EXTRACT_SUBREG instruction.
1017 class ExtractSubregRewriter : public CopyRewriter {
1018   const TargetInstrInfo &TII;
1019
1020 public:
1021   ExtractSubregRewriter(MachineInstr &MI, const TargetInstrInfo &TII)
1022       : CopyRewriter(MI), TII(TII) {
1023     assert(MI.isExtractSubreg() && "Invalid instruction");
1024   }
1025
1026   /// \brief See CopyRewriter::getNextRewritableSource.
1027   /// Here CopyLike has the following form:
1028   /// dst.dstSubIdx = EXTRACT_SUBREG Src, subIdx.
1029   /// There is only one rewritable source: Src.subIdx,
1030   /// which defines dst.dstSubIdx.
1031   bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg,
1032                                unsigned &TrackReg,
1033                                unsigned &TrackSubReg) override {
1034     // If we already get the only source we can rewrite, return false.
1035     if (CurrentSrcIdx == 1)
1036       return false;
1037     // We are looking at v1 = EXTRACT_SUBREG v0, sub0.
1038     CurrentSrcIdx = 1;
1039     const MachineOperand &MOExtractedReg = CopyLike.getOperand(1);
1040     SrcReg = MOExtractedReg.getReg();
1041     // If we have to compose sub-register indices, bail out.
1042     if (MOExtractedReg.getSubReg())
1043       return false;
1044
1045     SrcSubReg = CopyLike.getOperand(2).getImm();
1046
1047     // We want to track something that is compatible with the definition.
1048     const MachineOperand &MODef = CopyLike.getOperand(0);
1049     TrackReg = MODef.getReg();
1050     TrackSubReg = MODef.getSubReg();
1051     return true;
1052   }
1053
1054   bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override {
1055     // The only source we can rewrite is the input register.
1056     if (CurrentSrcIdx != 1)
1057       return false;
1058
1059     CopyLike.getOperand(CurrentSrcIdx).setReg(NewReg);
1060
1061     // If we find a source that does not require to extract something,
1062     // rewrite the operation with a copy.
1063     if (!NewSubReg) {
1064       // Move the current index to an invalid position.
1065       // We do not want another call to this method to be able
1066       // to do any change.
1067       CurrentSrcIdx = -1;
1068       // Rewrite the operation as a COPY.
1069       // Get rid of the sub-register index.
1070       CopyLike.RemoveOperand(2);
1071       // Morph the operation into a COPY.
1072       CopyLike.setDesc(TII.get(TargetOpcode::COPY));
1073       return true;
1074     }
1075     CopyLike.getOperand(CurrentSrcIdx + 1).setImm(NewSubReg);
1076     return true;
1077   }
1078 };
1079
1080 /// \brief Specialized rewriter for REG_SEQUENCE instruction.
1081 class RegSequenceRewriter : public CopyRewriter {
1082 public:
1083   RegSequenceRewriter(MachineInstr &MI) : CopyRewriter(MI) {
1084     assert(MI.isRegSequence() && "Invalid instruction");
1085   }
1086
1087   /// \brief See CopyRewriter::getNextRewritableSource.
1088   /// Here CopyLike has the following form:
1089   /// dst = REG_SEQUENCE Src1.src1SubIdx, subIdx1, Src2.src2SubIdx, subIdx2.
1090   /// Each call will return a different source, walking all the available
1091   /// source.
1092   ///
1093   /// The first call returns:
1094   /// (SrcReg, SrcSubReg) = (Src1, src1SubIdx).
1095   /// (TrackReg, TrackSubReg) = (dst, subIdx1).
1096   ///
1097   /// The second call returns:
1098   /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx).
1099   /// (TrackReg, TrackSubReg) = (dst, subIdx2).
1100   ///
1101   /// And so on, until all the sources have been traversed, then
1102   /// it returns false.
1103   bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg,
1104                                unsigned &TrackReg,
1105                                unsigned &TrackSubReg) override {
1106     // We are looking at v0 = REG_SEQUENCE v1, sub1, v2, sub2, etc.
1107
1108     // If this is the first call, move to the first argument.
1109     if (CurrentSrcIdx == 0) {
1110       CurrentSrcIdx = 1;
1111     } else {
1112       // Otherwise, move to the next argument and check that it is valid.
1113       CurrentSrcIdx += 2;
1114       if (CurrentSrcIdx >= CopyLike.getNumOperands())
1115         return false;
1116     }
1117     const MachineOperand &MOInsertedReg = CopyLike.getOperand(CurrentSrcIdx);
1118     SrcReg = MOInsertedReg.getReg();
1119     // If we have to compose sub-register indices, bail out.
1120     if ((SrcSubReg = MOInsertedReg.getSubReg()))
1121       return false;
1122
1123     // We want to track something that is compatible with the related
1124     // partial definition.
1125     TrackSubReg = CopyLike.getOperand(CurrentSrcIdx + 1).getImm();
1126
1127     const MachineOperand &MODef = CopyLike.getOperand(0);
1128     TrackReg = MODef.getReg();
1129     // If we have to compose sub-registers, bail.
1130     return MODef.getSubReg() == 0;
1131   }
1132
1133   bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override {
1134     // We cannot rewrite out of bound operands.
1135     // Moreover, rewritable sources are at odd positions.
1136     if ((CurrentSrcIdx & 1) != 1 || CurrentSrcIdx > CopyLike.getNumOperands())
1137       return false;
1138
1139     MachineOperand &MO = CopyLike.getOperand(CurrentSrcIdx);
1140     MO.setReg(NewReg);
1141     MO.setSubReg(NewSubReg);
1142     return true;
1143   }
1144 };
1145 } // End namespace.
1146
1147 /// \brief Get the appropriated CopyRewriter for \p MI.
1148 /// \return A pointer to a dynamically allocated CopyRewriter or nullptr
1149 /// if no rewriter works for \p MI.
1150 static CopyRewriter *getCopyRewriter(MachineInstr &MI,
1151                                      const TargetInstrInfo &TII,
1152                                      MachineRegisterInfo &MRI) {
1153   // Handle uncoalescable copy-like instructions.
1154   if (MI.isBitcast() || (MI.isRegSequenceLike() || MI.isInsertSubregLike() ||
1155                          MI.isExtractSubregLike()))
1156     return new UncoalescableRewriter(MI, TII, MRI);
1157
1158   switch (MI.getOpcode()) {
1159   default:
1160     return nullptr;
1161   case TargetOpcode::COPY:
1162     return new CopyRewriter(MI);
1163   case TargetOpcode::INSERT_SUBREG:
1164     return new InsertSubregRewriter(MI);
1165   case TargetOpcode::EXTRACT_SUBREG:
1166     return new ExtractSubregRewriter(MI, TII);
1167   case TargetOpcode::REG_SEQUENCE:
1168     return new RegSequenceRewriter(MI);
1169   }
1170   llvm_unreachable(nullptr);
1171 }
1172
1173 /// \brief Optimize generic copy instructions to avoid cross
1174 /// register bank copy. The optimization looks through a chain of
1175 /// copies and tries to find a source that has a compatible register
1176 /// class.
1177 /// Two register classes are considered to be compatible if they share
1178 /// the same register bank.
1179 /// New copies issued by this optimization are register allocator
1180 /// friendly. This optimization does not remove any copy as it may
1181 /// overconstrain the register allocator, but replaces some operands
1182 /// when possible.
1183 /// \pre isCoalescableCopy(*MI) is true.
1184 /// \return True, when \p MI has been rewritten. False otherwise.
1185 bool PeepholeOptimizer::optimizeCoalescableCopy(MachineInstr *MI) {
1186   assert(MI && isCoalescableCopy(*MI) && "Invalid argument");
1187   assert(MI->getDesc().getNumDefs() == 1 &&
1188          "Coalescer can understand multiple defs?!");
1189   const MachineOperand &MODef = MI->getOperand(0);
1190   // Do not rewrite physical definitions.
1191   if (TargetRegisterInfo::isPhysicalRegister(MODef.getReg()))
1192     return false;
1193
1194   bool Changed = false;
1195   // Get the right rewriter for the current copy.
1196   std::unique_ptr<CopyRewriter> CpyRewriter(getCopyRewriter(*MI, *TII, *MRI));
1197   // If none exists, bail out.
1198   if (!CpyRewriter)
1199     return false;
1200   // Rewrite each rewritable source.
1201   unsigned SrcReg, SrcSubReg, TrackReg, TrackSubReg;
1202   while (CpyRewriter->getNextRewritableSource(SrcReg, SrcSubReg, TrackReg,
1203                                               TrackSubReg)) {
1204     // Keep track of PHI nodes and its incoming edges when looking for sources.
1205     RewriteMapTy RewriteMap;
1206     // Try to find a more suitable source. If we failed to do so, or get the
1207     // actual source, move to the next source.
1208     if (!findNextSource(TrackReg, TrackSubReg, RewriteMap))
1209       continue;
1210
1211     // Get the new source to rewrite. TODO: Only enable handling of multiple
1212     // sources (PHIs) once we have a motivating example and testcases for it.
1213     TargetInstrInfo::RegSubRegPair TrackPair(TrackReg, TrackSubReg);
1214     TargetInstrInfo::RegSubRegPair NewSrc = CpyRewriter->getNewSource(
1215         MRI, TII, TrackPair, RewriteMap, false /* multiple sources */);
1216     if (SrcReg == NewSrc.Reg || NewSrc.Reg == 0)
1217       continue;
1218
1219     // Rewrite source.
1220     if (CpyRewriter->RewriteCurrentSource(NewSrc.Reg, NewSrc.SubReg)) {
1221       // We may have extended the live-range of NewSrc, account for that.
1222       MRI->clearKillFlags(NewSrc.Reg);
1223       Changed = true;
1224     }
1225   }
1226   // TODO: We could have a clean-up method to tidy the instruction.
1227   // E.g., v0 = INSERT_SUBREG v1, v1.sub0, sub0
1228   // => v0 = COPY v1
1229   // Currently we haven't seen motivating example for that and we
1230   // want to avoid untested code.
1231   NumRewrittenCopies += Changed;
1232   return Changed;
1233 }
1234
1235 /// \brief Optimize copy-like instructions to create
1236 /// register coalescer friendly instruction.
1237 /// The optimization tries to kill-off the \p MI by looking
1238 /// through a chain of copies to find a source that has a compatible
1239 /// register class.
1240 /// If such a source is found, it replace \p MI by a generic COPY
1241 /// operation.
1242 /// \pre isUncoalescableCopy(*MI) is true.
1243 /// \return True, when \p MI has been optimized. In that case, \p MI has
1244 /// been removed from its parent.
1245 /// All COPY instructions created, are inserted in \p LocalMIs.
1246 bool PeepholeOptimizer::optimizeUncoalescableCopy(
1247     MachineInstr *MI, SmallPtrSetImpl<MachineInstr *> &LocalMIs) {
1248   assert(MI && isUncoalescableCopy(*MI) && "Invalid argument");
1249
1250   // Check if we can rewrite all the values defined by this instruction.
1251   SmallVector<TargetInstrInfo::RegSubRegPair, 4> RewritePairs;
1252   // Get the right rewriter for the current copy.
1253   std::unique_ptr<CopyRewriter> CpyRewriter(getCopyRewriter(*MI, *TII, *MRI));
1254   // If none exists, bail out.
1255   if (!CpyRewriter)
1256     return false;
1257
1258   // Rewrite each rewritable source by generating new COPYs. This works
1259   // differently from optimizeCoalescableCopy since it first makes sure that all
1260   // definitions can be rewritten.
1261   RewriteMapTy RewriteMap;
1262   unsigned Reg, SubReg, CopyDefReg, CopyDefSubReg;
1263   while (CpyRewriter->getNextRewritableSource(Reg, SubReg, CopyDefReg,
1264                                               CopyDefSubReg)) {
1265     // If a physical register is here, this is probably for a good reason.
1266     // Do not rewrite that.
1267     if (TargetRegisterInfo::isPhysicalRegister(CopyDefReg))
1268       return false;
1269
1270     // If we do not know how to rewrite this definition, there is no point
1271     // in trying to kill this instruction.
1272     TargetInstrInfo::RegSubRegPair Def(CopyDefReg, CopyDefSubReg);
1273     if (!findNextSource(Def.Reg, Def.SubReg, RewriteMap))
1274       return false;
1275
1276     RewritePairs.push_back(Def);
1277   }
1278
1279   // The change is possible for all defs, do it.
1280   for (const auto &Def : RewritePairs) {
1281     // Rewrite the "copy" in a way the register coalescer understands.
1282     MachineInstr *NewCopy = CpyRewriter->RewriteSource(Def, RewriteMap);
1283     assert(NewCopy && "Should be able to always generate a new copy");
1284     LocalMIs.insert(NewCopy);
1285   }
1286
1287   // MI is now dead.
1288   MI->eraseFromParent();
1289   ++NumUncoalescableCopies;
1290   return true;
1291 }
1292
1293 /// isLoadFoldable - Check whether MI is a candidate for folding into a later
1294 /// instruction. We only fold loads to virtual registers and the virtual
1295 /// register defined has a single use.
1296 bool PeepholeOptimizer::isLoadFoldable(
1297                               MachineInstr *MI,
1298                               SmallSet<unsigned, 16> &FoldAsLoadDefCandidates) {
1299   if (!MI->canFoldAsLoad() || !MI->mayLoad())
1300     return false;
1301   const MCInstrDesc &MCID = MI->getDesc();
1302   if (MCID.getNumDefs() != 1)
1303     return false;
1304
1305   unsigned Reg = MI->getOperand(0).getReg();
1306   // To reduce compilation time, we check MRI->hasOneNonDBGUse when inserting
1307   // loads. It should be checked when processing uses of the load, since
1308   // uses can be removed during peephole.
1309   if (!MI->getOperand(0).getSubReg() &&
1310       TargetRegisterInfo::isVirtualRegister(Reg) &&
1311       MRI->hasOneNonDBGUse(Reg)) {
1312     FoldAsLoadDefCandidates.insert(Reg);
1313     return true;
1314   }
1315   return false;
1316 }
1317
1318 bool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI,
1319                                         SmallSet<unsigned, 4> &ImmDefRegs,
1320                                  DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
1321   const MCInstrDesc &MCID = MI->getDesc();
1322   if (!MI->isMoveImmediate())
1323     return false;
1324   if (MCID.getNumDefs() != 1)
1325     return false;
1326   unsigned Reg = MI->getOperand(0).getReg();
1327   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1328     ImmDefMIs.insert(std::make_pair(Reg, MI));
1329     ImmDefRegs.insert(Reg);
1330     return true;
1331   }
1332
1333   return false;
1334 }
1335
1336 /// foldImmediate - Try folding register operands that are defined by move
1337 /// immediate instructions, i.e. a trivial constant folding optimization, if
1338 /// and only if the def and use are in the same BB.
1339 bool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
1340                                       SmallSet<unsigned, 4> &ImmDefRegs,
1341                                  DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
1342   for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
1343     MachineOperand &MO = MI->getOperand(i);
1344     if (!MO.isReg() || MO.isDef())
1345       continue;
1346     unsigned Reg = MO.getReg();
1347     if (!TargetRegisterInfo::isVirtualRegister(Reg))
1348       continue;
1349     if (ImmDefRegs.count(Reg) == 0)
1350       continue;
1351     DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg);
1352     assert(II != ImmDefMIs.end() && "couldn't find immediate definition");
1353     if (TII->FoldImmediate(MI, II->second, Reg, MRI)) {
1354       ++NumImmFold;
1355       return true;
1356     }
1357   }
1358   return false;
1359 }
1360
1361 // FIXME: This is very simple and misses some cases which should be handled when
1362 // motivating examples are found.
1363 //
1364 // The copy rewriting logic should look at uses as well as defs and be able to
1365 // eliminate copies across blocks.
1366 //
1367 // Later copies that are subregister extracts will also not be eliminated since
1368 // only the first copy is considered.
1369 //
1370 // e.g.
1371 // %vreg1 = COPY %vreg0
1372 // %vreg2 = COPY %vreg0:sub1
1373 //
1374 // Should replace %vreg2 uses with %vreg1:sub1
1375 bool PeepholeOptimizer::foldRedundantCopy(
1376     MachineInstr *MI,
1377     SmallSet<unsigned, 4> &CopySrcRegs,
1378     DenseMap<unsigned, MachineInstr *> &CopyMIs) {
1379   assert(MI->isCopy() && "expected a COPY machine instruction");
1380
1381   unsigned SrcReg = MI->getOperand(1).getReg();
1382   if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
1383     return false;
1384
1385   unsigned DstReg = MI->getOperand(0).getReg();
1386   if (!TargetRegisterInfo::isVirtualRegister(DstReg))
1387     return false;
1388
1389   if (CopySrcRegs.insert(SrcReg).second) {
1390     // First copy of this reg seen.
1391     CopyMIs.insert(std::make_pair(SrcReg, MI));
1392     return false;
1393   }
1394
1395   MachineInstr *PrevCopy = CopyMIs.find(SrcReg)->second;
1396
1397   unsigned SrcSubReg = MI->getOperand(1).getSubReg();
1398   unsigned PrevSrcSubReg = PrevCopy->getOperand(1).getSubReg();
1399
1400   // Can't replace different subregister extracts.
1401   if (SrcSubReg != PrevSrcSubReg)
1402     return false;
1403
1404   unsigned PrevDstReg = PrevCopy->getOperand(0).getReg();
1405
1406   // Only replace if the copy register class is the same.
1407   //
1408   // TODO: If we have multiple copies to different register classes, we may want
1409   // to track multiple copies of the same source register.
1410   if (MRI->getRegClass(DstReg) != MRI->getRegClass(PrevDstReg))
1411     return false;
1412
1413   MRI->replaceRegWith(DstReg, PrevDstReg);
1414
1415   // Lifetime of the previous copy has been extended.
1416   MRI->clearKillFlags(PrevDstReg);
1417   return true;
1418 }
1419
1420 bool PeepholeOptimizer::isNAPhysCopy(unsigned Reg) {
1421   return TargetRegisterInfo::isPhysicalRegister(Reg) &&
1422          !MRI->isAllocatable(Reg);
1423 }
1424
1425 bool PeepholeOptimizer::foldRedundantNAPhysCopy(
1426     MachineInstr *MI, DenseMap<unsigned, MachineInstr *> &NAPhysToVirtMIs) {
1427   assert(MI->isCopy() && "expected a COPY machine instruction");
1428
1429   if (DisableNAPhysCopyOpt)
1430     return false;
1431
1432   unsigned DstReg = MI->getOperand(0).getReg();
1433   unsigned SrcReg = MI->getOperand(1).getReg();
1434   if (isNAPhysCopy(SrcReg) && TargetRegisterInfo::isVirtualRegister(DstReg)) {
1435     // %vreg = COPY %PHYSREG
1436     // Avoid using a datastructure which can track multiple live non-allocatable
1437     // phys->virt copies since LLVM doesn't seem to do this.
1438     NAPhysToVirtMIs.insert({SrcReg, MI});
1439     return false;
1440   }
1441
1442   if (!(TargetRegisterInfo::isVirtualRegister(SrcReg) && isNAPhysCopy(DstReg)))
1443     return false;
1444
1445   // %PHYSREG = COPY %vreg
1446   auto PrevCopy = NAPhysToVirtMIs.find(DstReg);
1447   if (PrevCopy == NAPhysToVirtMIs.end()) {
1448     // We can't remove the copy: there was an intervening clobber of the
1449     // non-allocatable physical register after the copy to virtual.
1450     DEBUG(dbgs() << "NAPhysCopy: intervening clobber forbids erasing " << *MI
1451                  << '\n');
1452     return false;
1453   }
1454
1455   unsigned PrevDstReg = PrevCopy->second->getOperand(0).getReg();
1456   if (PrevDstReg == SrcReg) {
1457     // Remove the virt->phys copy: we saw the virtual register definition, and
1458     // the non-allocatable physical register's state hasn't changed since then.
1459     DEBUG(dbgs() << "NAPhysCopy: erasing " << *MI << '\n');
1460     ++NumNAPhysCopies;
1461     return true;
1462   }
1463
1464   // Potential missed optimization opportunity: we saw a different virtual
1465   // register get a copy of the non-allocatable physical register, and we only
1466   // track one such copy. Avoid getting confused by this new non-allocatable
1467   // physical register definition, and remove it from the tracked copies.
1468   DEBUG(dbgs() << "NAPhysCopy: missed opportunity " << *MI << '\n');
1469   NAPhysToVirtMIs.erase(PrevCopy);
1470   return false;
1471 }
1472
1473 bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) {
1474   if (skipOptnoneFunction(*MF.getFunction()))
1475     return false;
1476
1477   DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n");
1478   DEBUG(dbgs() << "********** Function: " << MF.getName() << '\n');
1479
1480   if (DisablePeephole)
1481     return false;
1482
1483   TII = MF.getSubtarget().getInstrInfo();
1484   TRI = MF.getSubtarget().getRegisterInfo();
1485   MRI = &MF.getRegInfo();
1486   DT  = Aggressive ? &getAnalysis<MachineDominatorTree>() : nullptr;
1487
1488   bool Changed = false;
1489
1490   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
1491     MachineBasicBlock *MBB = &*I;
1492
1493     bool SeenMoveImm = false;
1494
1495     // During this forward scan, at some point it needs to answer the question
1496     // "given a pointer to an MI in the current BB, is it located before or
1497     // after the current instruction".
1498     // To perform this, the following set keeps track of the MIs already seen
1499     // during the scan, if a MI is not in the set, it is assumed to be located
1500     // after. Newly created MIs have to be inserted in the set as well.
1501     SmallPtrSet<MachineInstr*, 16> LocalMIs;
1502     SmallSet<unsigned, 4> ImmDefRegs;
1503     DenseMap<unsigned, MachineInstr*> ImmDefMIs;
1504     SmallSet<unsigned, 16> FoldAsLoadDefCandidates;
1505
1506     // Track when a non-allocatable physical register is copied to a virtual
1507     // register so that useless moves can be removed.
1508     //
1509     // %PHYSREG is the map index; MI is the last valid `%vreg = COPY %PHYSREG`
1510     // without any intervening re-definition of %PHYSREG.
1511     DenseMap<unsigned, MachineInstr *> NAPhysToVirtMIs;
1512
1513     // Set of virtual registers that are copied from.
1514     SmallSet<unsigned, 4> CopySrcRegs;
1515     DenseMap<unsigned, MachineInstr *> CopySrcMIs;
1516
1517     for (MachineBasicBlock::iterator
1518            MII = I->begin(), MIE = I->end(); MII != MIE; ) {
1519       MachineInstr *MI = &*MII;
1520       // We may be erasing MI below, increment MII now.
1521       ++MII;
1522       LocalMIs.insert(MI);
1523
1524       // Skip debug values. They should not affect this peephole optimization.
1525       if (MI->isDebugValue())
1526           continue;
1527
1528       // If we run into an instruction we can't fold across, discard
1529       // the load candidates.
1530       if (MI->isLoadFoldBarrier())
1531         FoldAsLoadDefCandidates.clear();
1532
1533       if (MI->isPosition() || MI->isPHI())
1534         continue;
1535
1536       if (!MI->isCopy()) {
1537         for (const auto &Op : MI->operands()) {
1538           // Visit all operands: definitions can be implicit or explicit.
1539           if (Op.isReg()) {
1540             unsigned Reg = Op.getReg();
1541             if (Op.isDef() && isNAPhysCopy(Reg)) {
1542               const auto &Def = NAPhysToVirtMIs.find(Reg);
1543               if (Def != NAPhysToVirtMIs.end()) {
1544                 // A new definition of the non-allocatable physical register
1545                 // invalidates previous copies.
1546                 DEBUG(dbgs() << "NAPhysCopy: invalidating because of " << *MI
1547                              << '\n');
1548                 NAPhysToVirtMIs.erase(Def);
1549               }
1550             }
1551           } else if (Op.isRegMask()) {
1552             const uint32_t *RegMask = Op.getRegMask();
1553             for (auto &RegMI : NAPhysToVirtMIs) {
1554               unsigned Def = RegMI.first;
1555               if (MachineOperand::clobbersPhysReg(RegMask, Def)) {
1556                 DEBUG(dbgs() << "NAPhysCopy: invalidating because of " << *MI
1557                              << '\n');
1558                 NAPhysToVirtMIs.erase(Def);
1559               }
1560             }
1561           }
1562         }
1563       }
1564
1565       if (MI->isImplicitDef() || MI->isKill())
1566         continue;
1567
1568       if (MI->isInlineAsm() || MI->hasUnmodeledSideEffects()) {
1569         // Blow away all non-allocatable physical registers knowledge since we
1570         // don't know what's correct anymore.
1571         //
1572         // FIXME: handle explicit asm clobbers.
1573         DEBUG(dbgs() << "NAPhysCopy: blowing away all info due to " << *MI
1574                      << '\n');
1575         NAPhysToVirtMIs.clear();
1576         continue;
1577       }
1578
1579       if ((isUncoalescableCopy(*MI) &&
1580            optimizeUncoalescableCopy(MI, LocalMIs)) ||
1581           (MI->isCompare() && optimizeCmpInstr(MI, MBB)) ||
1582           (MI->isSelect() && optimizeSelect(MI, LocalMIs))) {
1583         // MI is deleted.
1584         LocalMIs.erase(MI);
1585         Changed = true;
1586         continue;
1587       }
1588
1589       if (MI->isConditionalBranch() && optimizeCondBranch(MI)) {
1590         Changed = true;
1591         continue;
1592       }
1593
1594       if (isCoalescableCopy(*MI) && optimizeCoalescableCopy(MI)) {
1595         // MI is just rewritten.
1596         Changed = true;
1597         continue;
1598       }
1599
1600       if (MI->isCopy() &&
1601           (foldRedundantCopy(MI, CopySrcRegs, CopySrcMIs) ||
1602            foldRedundantNAPhysCopy(MI, NAPhysToVirtMIs))) {
1603         LocalMIs.erase(MI);
1604         MI->eraseFromParent();
1605         Changed = true;
1606         continue;
1607       }
1608
1609       if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) {
1610         SeenMoveImm = true;
1611       } else {
1612         Changed |= optimizeExtInstr(MI, MBB, LocalMIs);
1613         // optimizeExtInstr might have created new instructions after MI
1614         // and before the already incremented MII. Adjust MII so that the
1615         // next iteration sees the new instructions.
1616         MII = MI;
1617         ++MII;
1618         if (SeenMoveImm)
1619           Changed |= foldImmediate(MI, MBB, ImmDefRegs, ImmDefMIs);
1620       }
1621
1622       // Check whether MI is a load candidate for folding into a later
1623       // instruction. If MI is not a candidate, check whether we can fold an
1624       // earlier load into MI.
1625       if (!isLoadFoldable(MI, FoldAsLoadDefCandidates) &&
1626           !FoldAsLoadDefCandidates.empty()) {
1627         const MCInstrDesc &MIDesc = MI->getDesc();
1628         for (unsigned i = MIDesc.getNumDefs(); i != MIDesc.getNumOperands();
1629              ++i) {
1630           const MachineOperand &MOp = MI->getOperand(i);
1631           if (!MOp.isReg())
1632             continue;
1633           unsigned FoldAsLoadDefReg = MOp.getReg();
1634           if (FoldAsLoadDefCandidates.count(FoldAsLoadDefReg)) {
1635             // We need to fold load after optimizeCmpInstr, since
1636             // optimizeCmpInstr can enable folding by converting SUB to CMP.
1637             // Save FoldAsLoadDefReg because optimizeLoadInstr() resets it and
1638             // we need it for markUsesInDebugValueAsUndef().
1639             unsigned FoldedReg = FoldAsLoadDefReg;
1640             MachineInstr *DefMI = nullptr;
1641             MachineInstr *FoldMI = TII->optimizeLoadInstr(MI, MRI,
1642                                                           FoldAsLoadDefReg,
1643                                                           DefMI);
1644             if (FoldMI) {
1645               // Update LocalMIs since we replaced MI with FoldMI and deleted
1646               // DefMI.
1647               DEBUG(dbgs() << "Replacing: " << *MI);
1648               DEBUG(dbgs() << "     With: " << *FoldMI);
1649               LocalMIs.erase(MI);
1650               LocalMIs.erase(DefMI);
1651               LocalMIs.insert(FoldMI);
1652               MI->eraseFromParent();
1653               DefMI->eraseFromParent();
1654               MRI->markUsesInDebugValueAsUndef(FoldedReg);
1655               FoldAsLoadDefCandidates.erase(FoldedReg);
1656               ++NumLoadFold;
1657               // MI is replaced with FoldMI.
1658               Changed = true;
1659               break;
1660             }
1661           }
1662         }
1663       }
1664     }
1665   }
1666
1667   return Changed;
1668 }
1669
1670 ValueTrackerResult ValueTracker::getNextSourceFromCopy() {
1671   assert(Def->isCopy() && "Invalid definition");
1672   // Copy instruction are supposed to be: Def = Src.
1673   // If someone breaks this assumption, bad things will happen everywhere.
1674   assert(Def->getNumOperands() == 2 && "Invalid number of operands");
1675
1676   if (Def->getOperand(DefIdx).getSubReg() != DefSubReg)
1677     // If we look for a different subreg, it means we want a subreg of src.
1678     // Bails as we do not support composing subregs yet.
1679     return ValueTrackerResult();
1680   // Otherwise, we want the whole source.
1681   const MachineOperand &Src = Def->getOperand(1);
1682   return ValueTrackerResult(Src.getReg(), Src.getSubReg());
1683 }
1684
1685 ValueTrackerResult ValueTracker::getNextSourceFromBitcast() {
1686   assert(Def->isBitcast() && "Invalid definition");
1687
1688   // Bail if there are effects that a plain copy will not expose.
1689   if (Def->hasUnmodeledSideEffects())
1690     return ValueTrackerResult();
1691
1692   // Bitcasts with more than one def are not supported.
1693   if (Def->getDesc().getNumDefs() != 1)
1694     return ValueTrackerResult();
1695   if (Def->getOperand(DefIdx).getSubReg() != DefSubReg)
1696     // If we look for a different subreg, it means we want a subreg of the src.
1697     // Bails as we do not support composing subregs yet.
1698     return ValueTrackerResult();
1699
1700   unsigned SrcIdx = Def->getNumOperands();
1701   for (unsigned OpIdx = DefIdx + 1, EndOpIdx = SrcIdx; OpIdx != EndOpIdx;
1702        ++OpIdx) {
1703     const MachineOperand &MO = Def->getOperand(OpIdx);
1704     if (!MO.isReg() || !MO.getReg())
1705       continue;
1706     assert(!MO.isDef() && "We should have skipped all the definitions by now");
1707     if (SrcIdx != EndOpIdx)
1708       // Multiple sources?
1709       return ValueTrackerResult();
1710     SrcIdx = OpIdx;
1711   }
1712   const MachineOperand &Src = Def->getOperand(SrcIdx);
1713   return ValueTrackerResult(Src.getReg(), Src.getSubReg());
1714 }
1715
1716 ValueTrackerResult ValueTracker::getNextSourceFromRegSequence() {
1717   assert((Def->isRegSequence() || Def->isRegSequenceLike()) &&
1718          "Invalid definition");
1719
1720   if (Def->getOperand(DefIdx).getSubReg())
1721     // If we are composing subregs, bail out.
1722     // The case we are checking is Def.<subreg> = REG_SEQUENCE.
1723     // This should almost never happen as the SSA property is tracked at
1724     // the register level (as opposed to the subreg level).
1725     // I.e.,
1726     // Def.sub0 =
1727     // Def.sub1 =
1728     // is a valid SSA representation for Def.sub0 and Def.sub1, but not for
1729     // Def. Thus, it must not be generated.
1730     // However, some code could theoretically generates a single
1731     // Def.sub0 (i.e, not defining the other subregs) and we would
1732     // have this case.
1733     // If we can ascertain (or force) that this never happens, we could
1734     // turn that into an assertion.
1735     return ValueTrackerResult();
1736
1737   if (!TII)
1738     // We could handle the REG_SEQUENCE here, but we do not want to
1739     // duplicate the code from the generic TII.
1740     return ValueTrackerResult();
1741
1742   SmallVector<TargetInstrInfo::RegSubRegPairAndIdx, 8> RegSeqInputRegs;
1743   if (!TII->getRegSequenceInputs(*Def, DefIdx, RegSeqInputRegs))
1744     return ValueTrackerResult();
1745
1746   // We are looking at:
1747   // Def = REG_SEQUENCE v0, sub0, v1, sub1, ...
1748   // Check if one of the operand defines the subreg we are interested in.
1749   for (auto &RegSeqInput : RegSeqInputRegs) {
1750     if (RegSeqInput.SubIdx == DefSubReg) {
1751       if (RegSeqInput.SubReg)
1752         // Bail if we have to compose sub registers.
1753         return ValueTrackerResult();
1754
1755       return ValueTrackerResult(RegSeqInput.Reg, RegSeqInput.SubReg);
1756     }
1757   }
1758
1759   // If the subreg we are tracking is super-defined by another subreg,
1760   // we could follow this value. However, this would require to compose
1761   // the subreg and we do not do that for now.
1762   return ValueTrackerResult();
1763 }
1764
1765 ValueTrackerResult ValueTracker::getNextSourceFromInsertSubreg() {
1766   assert((Def->isInsertSubreg() || Def->isInsertSubregLike()) &&
1767          "Invalid definition");
1768
1769   if (Def->getOperand(DefIdx).getSubReg())
1770     // If we are composing subreg, bail out.
1771     // Same remark as getNextSourceFromRegSequence.
1772     // I.e., this may be turned into an assert.
1773     return ValueTrackerResult();
1774
1775   if (!TII)
1776     // We could handle the REG_SEQUENCE here, but we do not want to
1777     // duplicate the code from the generic TII.
1778     return ValueTrackerResult();
1779
1780   TargetInstrInfo::RegSubRegPair BaseReg;
1781   TargetInstrInfo::RegSubRegPairAndIdx InsertedReg;
1782   if (!TII->getInsertSubregInputs(*Def, DefIdx, BaseReg, InsertedReg))
1783     return ValueTrackerResult();
1784
1785   // We are looking at:
1786   // Def = INSERT_SUBREG v0, v1, sub1
1787   // There are two cases:
1788   // 1. DefSubReg == sub1, get v1.
1789   // 2. DefSubReg != sub1, the value may be available through v0.
1790
1791   // #1 Check if the inserted register matches the required sub index.
1792   if (InsertedReg.SubIdx == DefSubReg) {
1793     return ValueTrackerResult(InsertedReg.Reg, InsertedReg.SubReg);
1794   }
1795   // #2 Otherwise, if the sub register we are looking for is not partial
1796   // defined by the inserted element, we can look through the main
1797   // register (v0).
1798   const MachineOperand &MODef = Def->getOperand(DefIdx);
1799   // If the result register (Def) and the base register (v0) do not
1800   // have the same register class or if we have to compose
1801   // subregisters, bail out.
1802   if (MRI.getRegClass(MODef.getReg()) != MRI.getRegClass(BaseReg.Reg) ||
1803       BaseReg.SubReg)
1804     return ValueTrackerResult();
1805
1806   // Get the TRI and check if the inserted sub-register overlaps with the
1807   // sub-register we are tracking.
1808   const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
1809   if (!TRI ||
1810       (TRI->getSubRegIndexLaneMask(DefSubReg) &
1811        TRI->getSubRegIndexLaneMask(InsertedReg.SubIdx)) != 0)
1812     return ValueTrackerResult();
1813   // At this point, the value is available in v0 via the same subreg
1814   // we used for Def.
1815   return ValueTrackerResult(BaseReg.Reg, DefSubReg);
1816 }
1817
1818 ValueTrackerResult ValueTracker::getNextSourceFromExtractSubreg() {
1819   assert((Def->isExtractSubreg() ||
1820           Def->isExtractSubregLike()) && "Invalid definition");
1821   // We are looking at:
1822   // Def = EXTRACT_SUBREG v0, sub0
1823
1824   // Bail if we have to compose sub registers.
1825   // Indeed, if DefSubReg != 0, we would have to compose it with sub0.
1826   if (DefSubReg)
1827     return ValueTrackerResult();
1828
1829   if (!TII)
1830     // We could handle the EXTRACT_SUBREG here, but we do not want to
1831     // duplicate the code from the generic TII.
1832     return ValueTrackerResult();
1833
1834   TargetInstrInfo::RegSubRegPairAndIdx ExtractSubregInputReg;
1835   if (!TII->getExtractSubregInputs(*Def, DefIdx, ExtractSubregInputReg))
1836     return ValueTrackerResult();
1837
1838   // Bail if we have to compose sub registers.
1839   // Likewise, if v0.subreg != 0, we would have to compose v0.subreg with sub0.
1840   if (ExtractSubregInputReg.SubReg)
1841     return ValueTrackerResult();
1842   // Otherwise, the value is available in the v0.sub0.
1843   return ValueTrackerResult(ExtractSubregInputReg.Reg, ExtractSubregInputReg.SubIdx);
1844 }
1845
1846 ValueTrackerResult ValueTracker::getNextSourceFromSubregToReg() {
1847   assert(Def->isSubregToReg() && "Invalid definition");
1848   // We are looking at:
1849   // Def = SUBREG_TO_REG Imm, v0, sub0
1850
1851   // Bail if we have to compose sub registers.
1852   // If DefSubReg != sub0, we would have to check that all the bits
1853   // we track are included in sub0 and if yes, we would have to
1854   // determine the right subreg in v0.
1855   if (DefSubReg != Def->getOperand(3).getImm())
1856     return ValueTrackerResult();
1857   // Bail if we have to compose sub registers.
1858   // Likewise, if v0.subreg != 0, we would have to compose it with sub0.
1859   if (Def->getOperand(2).getSubReg())
1860     return ValueTrackerResult();
1861
1862   return ValueTrackerResult(Def->getOperand(2).getReg(),
1863                             Def->getOperand(3).getImm());
1864 }
1865
1866 /// \brief Explore each PHI incoming operand and return its sources
1867 ValueTrackerResult ValueTracker::getNextSourceFromPHI() {
1868   assert(Def->isPHI() && "Invalid definition");
1869   ValueTrackerResult Res;
1870
1871   // If we look for a different subreg, bail as we do not support composing
1872   // subregs yet.
1873   if (Def->getOperand(0).getSubReg() != DefSubReg)
1874     return ValueTrackerResult();
1875
1876   // Return all register sources for PHI instructions.
1877   for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) {
1878     auto &MO = Def->getOperand(i);
1879     assert(MO.isReg() && "Invalid PHI instruction");
1880     Res.addSource(MO.getReg(), MO.getSubReg());
1881   }
1882
1883   return Res;
1884 }
1885
1886 ValueTrackerResult ValueTracker::getNextSourceImpl() {
1887   assert(Def && "This method needs a valid definition");
1888
1889   assert(
1890       (DefIdx < Def->getDesc().getNumDefs() || Def->getDesc().isVariadic()) &&
1891       Def->getOperand(DefIdx).isDef() && "Invalid DefIdx");
1892   if (Def->isCopy())
1893     return getNextSourceFromCopy();
1894   if (Def->isBitcast())
1895     return getNextSourceFromBitcast();
1896   // All the remaining cases involve "complex" instructions.
1897   // Bail if we did not ask for the advanced tracking.
1898   if (!UseAdvancedTracking)
1899     return ValueTrackerResult();
1900   if (Def->isRegSequence() || Def->isRegSequenceLike())
1901     return getNextSourceFromRegSequence();
1902   if (Def->isInsertSubreg() || Def->isInsertSubregLike())
1903     return getNextSourceFromInsertSubreg();
1904   if (Def->isExtractSubreg() || Def->isExtractSubregLike())
1905     return getNextSourceFromExtractSubreg();
1906   if (Def->isSubregToReg())
1907     return getNextSourceFromSubregToReg();
1908   if (Def->isPHI())
1909     return getNextSourceFromPHI();
1910   return ValueTrackerResult();
1911 }
1912
1913 ValueTrackerResult ValueTracker::getNextSource() {
1914   // If we reach a point where we cannot move up in the use-def chain,
1915   // there is nothing we can get.
1916   if (!Def)
1917     return ValueTrackerResult();
1918
1919   ValueTrackerResult Res = getNextSourceImpl();
1920   if (Res.isValid()) {
1921     // Update definition, definition index, and subregister for the
1922     // next call of getNextSource.
1923     // Update the current register.
1924     bool OneRegSrc = Res.getNumSources() == 1;
1925     if (OneRegSrc)
1926       Reg = Res.getSrcReg(0);
1927     // Update the result before moving up in the use-def chain
1928     // with the instruction containing the last found sources.
1929     Res.setInst(Def);
1930
1931     // If we can still move up in the use-def chain, move to the next
1932     // definition.
1933     if (!TargetRegisterInfo::isPhysicalRegister(Reg) && OneRegSrc) {
1934       Def = MRI.getVRegDef(Reg);
1935       DefIdx = MRI.def_begin(Reg).getOperandNo();
1936       DefSubReg = Res.getSrcSubReg(0);
1937       return Res;
1938     }
1939   }
1940   // If we end up here, this means we will not be able to find another source
1941   // for the next iteration. Make sure any new call to getNextSource bails out
1942   // early by cutting the use-def chain.
1943   Def = nullptr;
1944   return Res;
1945 }