Home | History | Annotate | Download | only in CodeGen
      1 //===-------- InlineSpiller.cpp - Insert spills and restores inline -------===//
      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 // The inline spiller modifies the machine function directly instead of
     11 // inserting spills and restores in VirtRegMap.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "Spiller.h"
     16 #include "llvm/ADT/SetVector.h"
     17 #include "llvm/ADT/Statistic.h"
     18 #include "llvm/ADT/TinyPtrVector.h"
     19 #include "llvm/Analysis/AliasAnalysis.h"
     20 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
     21 #include "llvm/CodeGen/LiveRangeEdit.h"
     22 #include "llvm/CodeGen/LiveStackAnalysis.h"
     23 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
     24 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
     25 #include "llvm/CodeGen/MachineDominators.h"
     26 #include "llvm/CodeGen/MachineFrameInfo.h"
     27 #include "llvm/CodeGen/MachineFunction.h"
     28 #include "llvm/CodeGen/MachineInstrBuilder.h"
     29 #include "llvm/CodeGen/MachineInstrBundle.h"
     30 #include "llvm/CodeGen/MachineLoopInfo.h"
     31 #include "llvm/CodeGen/MachineRegisterInfo.h"
     32 #include "llvm/CodeGen/VirtRegMap.h"
     33 #include "llvm/Support/CommandLine.h"
     34 #include "llvm/Support/Debug.h"
     35 #include "llvm/Support/raw_ostream.h"
     36 #include "llvm/Target/TargetInstrInfo.h"
     37 
     38 using namespace llvm;
     39 
     40 #define DEBUG_TYPE "regalloc"
     41 
     42 STATISTIC(NumSpilledRanges,   "Number of spilled live ranges");
     43 STATISTIC(NumSnippets,        "Number of spilled snippets");
     44 STATISTIC(NumSpills,          "Number of spills inserted");
     45 STATISTIC(NumSpillsRemoved,   "Number of spills removed");
     46 STATISTIC(NumReloads,         "Number of reloads inserted");
     47 STATISTIC(NumReloadsRemoved,  "Number of reloads removed");
     48 STATISTIC(NumFolded,          "Number of folded stack accesses");
     49 STATISTIC(NumFoldedLoads,     "Number of folded loads");
     50 STATISTIC(NumRemats,          "Number of rematerialized defs for spilling");
     51 STATISTIC(NumOmitReloadSpill, "Number of omitted spills of reloads");
     52 STATISTIC(NumHoists,          "Number of hoisted spills");
     53 
     54 static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden,
     55                                      cl::desc("Disable inline spill hoisting"));
     56 
     57 namespace {
     58 class InlineSpiller : public Spiller {
     59   MachineFunction &MF;
     60   LiveIntervals &LIS;
     61   LiveStacks &LSS;
     62   AliasAnalysis *AA;
     63   MachineDominatorTree &MDT;
     64   MachineLoopInfo &Loops;
     65   VirtRegMap &VRM;
     66   MachineFrameInfo &MFI;
     67   MachineRegisterInfo &MRI;
     68   const TargetInstrInfo &TII;
     69   const TargetRegisterInfo &TRI;
     70   const MachineBlockFrequencyInfo &MBFI;
     71 
     72   // Variables that are valid during spill(), but used by multiple methods.
     73   LiveRangeEdit *Edit;
     74   LiveInterval *StackInt;
     75   int StackSlot;
     76   unsigned Original;
     77 
     78   // All registers to spill to StackSlot, including the main register.
     79   SmallVector<unsigned, 8> RegsToSpill;
     80 
     81   // All COPY instructions to/from snippets.
     82   // They are ignored since both operands refer to the same stack slot.
     83   SmallPtrSet<MachineInstr*, 8> SnippetCopies;
     84 
     85   // Values that failed to remat at some point.
     86   SmallPtrSet<VNInfo*, 8> UsedValues;
     87 
     88 public:
     89   // Information about a value that was defined by a copy from a sibling
     90   // register.
     91   struct SibValueInfo {
     92     // True when all reaching defs were reloads: No spill is necessary.
     93     bool AllDefsAreReloads;
     94 
     95     // True when value is defined by an original PHI not from splitting.
     96     bool DefByOrigPHI;
     97 
     98     // True when the COPY defining this value killed its source.
     99     bool KillsSource;
    100 
    101     // The preferred register to spill.
    102     unsigned SpillReg;
    103 
    104     // The value of SpillReg that should be spilled.
    105     VNInfo *SpillVNI;
    106 
    107     // The block where SpillVNI should be spilled. Currently, this must be the
    108     // block containing SpillVNI->def.
    109     MachineBasicBlock *SpillMBB;
    110 
    111     // A defining instruction that is not a sibling copy or a reload, or NULL.
    112     // This can be used as a template for rematerialization.
    113     MachineInstr *DefMI;
    114 
    115     // List of values that depend on this one.  These values are actually the
    116     // same, but live range splitting has placed them in different registers,
    117     // or SSA update needed to insert PHI-defs to preserve SSA form.  This is
    118     // copies of the current value and phi-kills.  Usually only phi-kills cause
    119     // more than one dependent value.
    120     TinyPtrVector<VNInfo*> Deps;
    121 
    122     SibValueInfo(unsigned Reg, VNInfo *VNI)
    123       : AllDefsAreReloads(true), DefByOrigPHI(false), KillsSource(false),
    124         SpillReg(Reg), SpillVNI(VNI), SpillMBB(nullptr), DefMI(nullptr) {}
    125 
    126     // Returns true when a def has been found.
    127     bool hasDef() const { return DefByOrigPHI || DefMI; }
    128   };
    129 
    130 private:
    131   // Values in RegsToSpill defined by sibling copies.
    132   typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap;
    133   SibValueMap SibValues;
    134 
    135   // Dead defs generated during spilling.
    136   SmallVector<MachineInstr*, 8> DeadDefs;
    137 
    138   ~InlineSpiller() override {}
    139 
    140 public:
    141   InlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
    142       : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
    143         LSS(pass.getAnalysis<LiveStacks>()),
    144         AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
    145         MDT(pass.getAnalysis<MachineDominatorTree>()),
    146         Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
    147         MFI(*mf.getFrameInfo()), MRI(mf.getRegInfo()),
    148         TII(*mf.getSubtarget().getInstrInfo()),
    149         TRI(*mf.getSubtarget().getRegisterInfo()),
    150         MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()) {}
    151 
    152   void spill(LiveRangeEdit &) override;
    153 
    154 private:
    155   bool isSnippet(const LiveInterval &SnipLI);
    156   void collectRegsToSpill();
    157 
    158   bool isRegToSpill(unsigned Reg) {
    159     return std::find(RegsToSpill.begin(),
    160                      RegsToSpill.end(), Reg) != RegsToSpill.end();
    161   }
    162 
    163   bool isSibling(unsigned Reg);
    164   MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*);
    165   void propagateSiblingValue(SibValueMap::iterator, VNInfo *VNI = nullptr);
    166   void analyzeSiblingValues();
    167 
    168   bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI);
    169   void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
    170 
    171   void markValueUsed(LiveInterval*, VNInfo*);
    172   bool reMaterializeFor(LiveInterval&, MachineBasicBlock::iterator MI);
    173   void reMaterializeAll();
    174 
    175   bool coalesceStackAccess(MachineInstr *MI, unsigned Reg);
    176   bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> >,
    177                          MachineInstr *LoadMI = nullptr);
    178   void insertReload(unsigned VReg, SlotIndex, MachineBasicBlock::iterator MI);
    179   void insertSpill(unsigned VReg, bool isKill, MachineBasicBlock::iterator MI);
    180 
    181   void spillAroundUses(unsigned Reg);
    182   void spillAll();
    183 };
    184 }
    185 
    186 namespace llvm {
    187 
    188 Spiller::~Spiller() { }
    189 void Spiller::anchor() { }
    190 
    191 Spiller *createInlineSpiller(MachineFunctionPass &pass,
    192                              MachineFunction &mf,
    193                              VirtRegMap &vrm) {
    194   return new InlineSpiller(pass, mf, vrm);
    195 }
    196 
    197 }
    198 
    199 //===----------------------------------------------------------------------===//
    200 //                                Snippets
    201 //===----------------------------------------------------------------------===//
    202 
    203 // When spilling a virtual register, we also spill any snippets it is connected
    204 // to. The snippets are small live ranges that only have a single real use,
    205 // leftovers from live range splitting. Spilling them enables memory operand
    206 // folding or tightens the live range around the single use.
    207 //
    208 // This minimizes register pressure and maximizes the store-to-load distance for
    209 // spill slots which can be important in tight loops.
    210 
    211 /// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
    212 /// otherwise return 0.
    213 static unsigned isFullCopyOf(const MachineInstr *MI, unsigned Reg) {
    214   if (!MI->isFullCopy())
    215     return 0;
    216   if (MI->getOperand(0).getReg() == Reg)
    217       return MI->getOperand(1).getReg();
    218   if (MI->getOperand(1).getReg() == Reg)
    219       return MI->getOperand(0).getReg();
    220   return 0;
    221 }
    222 
    223 /// isSnippet - Identify if a live interval is a snippet that should be spilled.
    224 /// It is assumed that SnipLI is a virtual register with the same original as
    225 /// Edit->getReg().
    226 bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
    227   unsigned Reg = Edit->getReg();
    228 
    229   // A snippet is a tiny live range with only a single instruction using it
    230   // besides copies to/from Reg or spills/fills. We accept:
    231   //
    232   //   %snip = COPY %Reg / FILL fi#
    233   //   %snip = USE %snip
    234   //   %Reg = COPY %snip / SPILL %snip, fi#
    235   //
    236   if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
    237     return false;
    238 
    239   MachineInstr *UseMI = nullptr;
    240 
    241   // Check that all uses satisfy our criteria.
    242   for (MachineRegisterInfo::reg_instr_nodbg_iterator
    243        RI = MRI.reg_instr_nodbg_begin(SnipLI.reg),
    244        E = MRI.reg_instr_nodbg_end(); RI != E; ) {
    245     MachineInstr *MI = &*(RI++);
    246 
    247     // Allow copies to/from Reg.
    248     if (isFullCopyOf(MI, Reg))
    249       continue;
    250 
    251     // Allow stack slot loads.
    252     int FI;
    253     if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
    254       continue;
    255 
    256     // Allow stack slot stores.
    257     if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
    258       continue;
    259 
    260     // Allow a single additional instruction.
    261     if (UseMI && MI != UseMI)
    262       return false;
    263     UseMI = MI;
    264   }
    265   return true;
    266 }
    267 
    268 /// collectRegsToSpill - Collect live range snippets that only have a single
    269 /// real use.
    270 void InlineSpiller::collectRegsToSpill() {
    271   unsigned Reg = Edit->getReg();
    272 
    273   // Main register always spills.
    274   RegsToSpill.assign(1, Reg);
    275   SnippetCopies.clear();
    276 
    277   // Snippets all have the same original, so there can't be any for an original
    278   // register.
    279   if (Original == Reg)
    280     return;
    281 
    282   for (MachineRegisterInfo::reg_instr_iterator
    283        RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); RI != E; ) {
    284     MachineInstr *MI = &*(RI++);
    285     unsigned SnipReg = isFullCopyOf(MI, Reg);
    286     if (!isSibling(SnipReg))
    287       continue;
    288     LiveInterval &SnipLI = LIS.getInterval(SnipReg);
    289     if (!isSnippet(SnipLI))
    290       continue;
    291     SnippetCopies.insert(MI);
    292     if (isRegToSpill(SnipReg))
    293       continue;
    294     RegsToSpill.push_back(SnipReg);
    295     DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n');
    296     ++NumSnippets;
    297   }
    298 }
    299 
    300 
    301 //===----------------------------------------------------------------------===//
    302 //                            Sibling Values
    303 //===----------------------------------------------------------------------===//
    304 
    305 // After live range splitting, some values to be spilled may be defined by
    306 // copies from sibling registers. We trace the sibling copies back to the
    307 // original value if it still exists. We need it for rematerialization.
    308 //
    309 // Even when the value can't be rematerialized, we still want to determine if
    310 // the value has already been spilled, or we may want to hoist the spill from a
    311 // loop.
    312 
    313 bool InlineSpiller::isSibling(unsigned Reg) {
    314   return TargetRegisterInfo::isVirtualRegister(Reg) &&
    315            VRM.getOriginal(Reg) == Original;
    316 }
    317 
    318 #ifndef NDEBUG
    319 static raw_ostream &operator<<(raw_ostream &OS,
    320                                const InlineSpiller::SibValueInfo &SVI) {
    321   OS << "spill " << PrintReg(SVI.SpillReg) << ':'
    322      << SVI.SpillVNI->id << '@' << SVI.SpillVNI->def;
    323   if (SVI.SpillMBB)
    324     OS << " in BB#" << SVI.SpillMBB->getNumber();
    325   if (SVI.AllDefsAreReloads)
    326     OS << " all-reloads";
    327   if (SVI.DefByOrigPHI)
    328     OS << " orig-phi";
    329   if (SVI.KillsSource)
    330     OS << " kill";
    331   OS << " deps[";
    332   for (unsigned i = 0, e = SVI.Deps.size(); i != e; ++i)
    333     OS << ' ' << SVI.Deps[i]->id << '@' << SVI.Deps[i]->def;
    334   OS << " ]";
    335   if (SVI.DefMI)
    336     OS << " def: " << *SVI.DefMI;
    337   else
    338     OS << '\n';
    339   return OS;
    340 }
    341 #endif
    342 
    343 /// propagateSiblingValue - Propagate the value in SVI to dependents if it is
    344 /// known.  Otherwise remember the dependency for later.
    345 ///
    346 /// @param SVIIter SibValues entry to propagate.
    347 /// @param VNI Dependent value, or NULL to propagate to all saved dependents.
    348 void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVIIter,
    349                                           VNInfo *VNI) {
    350   SibValueMap::value_type *SVI = &*SVIIter;
    351 
    352   // When VNI is non-NULL, add it to SVI's deps, and only propagate to that.
    353   TinyPtrVector<VNInfo*> FirstDeps;
    354   if (VNI) {
    355     FirstDeps.push_back(VNI);
    356     SVI->second.Deps.push_back(VNI);
    357   }
    358 
    359   // Has the value been completely determined yet?  If not, defer propagation.
    360   if (!SVI->second.hasDef())
    361     return;
    362 
    363   // Work list of values to propagate.
    364   SmallSetVector<SibValueMap::value_type *, 8> WorkList;
    365   WorkList.insert(SVI);
    366 
    367   do {
    368     SVI = WorkList.pop_back_val();
    369     TinyPtrVector<VNInfo*> *Deps = VNI ? &FirstDeps : &SVI->second.Deps;
    370     VNI = nullptr;
    371 
    372     SibValueInfo &SV = SVI->second;
    373     if (!SV.SpillMBB)
    374       SV.SpillMBB = LIS.getMBBFromIndex(SV.SpillVNI->def);
    375 
    376     DEBUG(dbgs() << "  prop to " << Deps->size() << ": "
    377                  << SVI->first->id << '@' << SVI->first->def << ":\t" << SV);
    378 
    379     assert(SV.hasDef() && "Propagating undefined value");
    380 
    381     // Should this value be propagated as a preferred spill candidate?  We don't
    382     // propagate values of registers that are about to spill.
    383     bool PropSpill = !DisableHoisting && !isRegToSpill(SV.SpillReg);
    384     unsigned SpillDepth = ~0u;
    385 
    386     for (TinyPtrVector<VNInfo*>::iterator DepI = Deps->begin(),
    387          DepE = Deps->end(); DepI != DepE; ++DepI) {
    388       SibValueMap::iterator DepSVI = SibValues.find(*DepI);
    389       assert(DepSVI != SibValues.end() && "Dependent value not in SibValues");
    390       SibValueInfo &DepSV = DepSVI->second;
    391       if (!DepSV.SpillMBB)
    392         DepSV.SpillMBB = LIS.getMBBFromIndex(DepSV.SpillVNI->def);
    393 
    394       bool Changed = false;
    395 
    396       // Propagate defining instruction.
    397       if (!DepSV.hasDef()) {
    398         Changed = true;
    399         DepSV.DefMI = SV.DefMI;
    400         DepSV.DefByOrigPHI = SV.DefByOrigPHI;
    401       }
    402 
    403       // Propagate AllDefsAreReloads.  For PHI values, this computes an AND of
    404       // all predecessors.
    405       if (!SV.AllDefsAreReloads && DepSV.AllDefsAreReloads) {
    406         Changed = true;
    407         DepSV.AllDefsAreReloads = false;
    408       }
    409 
    410       // Propagate best spill value.
    411       if (PropSpill && SV.SpillVNI != DepSV.SpillVNI) {
    412         if (SV.SpillMBB == DepSV.SpillMBB) {
    413           // DepSV is in the same block.  Hoist when dominated.
    414           if (DepSV.KillsSource && SV.SpillVNI->def < DepSV.SpillVNI->def) {
    415             // This is an alternative def earlier in the same MBB.
    416             // Hoist the spill as far as possible in SpillMBB. This can ease
    417             // register pressure:
    418             //
    419             //   x = def
    420             //   y = use x
    421             //   s = copy x
    422             //
    423             // Hoisting the spill of s to immediately after the def removes the
    424             // interference between x and y:
    425             //
    426             //   x = def
    427             //   spill x
    428             //   y = use x<kill>
    429             //
    430             // This hoist only helps when the DepSV copy kills its source.
    431             Changed = true;
    432             DepSV.SpillReg = SV.SpillReg;
    433             DepSV.SpillVNI = SV.SpillVNI;
    434             DepSV.SpillMBB = SV.SpillMBB;
    435           }
    436         } else {
    437           // DepSV is in a different block.
    438           if (SpillDepth == ~0u)
    439             SpillDepth = Loops.getLoopDepth(SV.SpillMBB);
    440 
    441           // Also hoist spills to blocks with smaller loop depth, but make sure
    442           // that the new value dominates.  Non-phi dependents are always
    443           // dominated, phis need checking.
    444 
    445           const BranchProbability MarginProb(4, 5); // 80%
    446           // Hoist a spill to outer loop if there are multiple dependents (it
    447           // can be beneficial if more than one dependents are hoisted) or
    448           // if DepSV (the hoisting source) is hotter than SV (the hoisting
    449           // destination) (we add a 80% margin to bias a little towards
    450           // loop depth).
    451           bool HoistCondition =
    452             (MBFI.getBlockFreq(DepSV.SpillMBB) >=
    453              (MBFI.getBlockFreq(SV.SpillMBB) * MarginProb)) ||
    454             Deps->size() > 1;
    455 
    456           if ((Loops.getLoopDepth(DepSV.SpillMBB) > SpillDepth) &&
    457               HoistCondition &&
    458               (!DepSVI->first->isPHIDef() ||
    459                MDT.dominates(SV.SpillMBB, DepSV.SpillMBB))) {
    460             Changed = true;
    461             DepSV.SpillReg = SV.SpillReg;
    462             DepSV.SpillVNI = SV.SpillVNI;
    463             DepSV.SpillMBB = SV.SpillMBB;
    464           }
    465         }
    466       }
    467 
    468       if (!Changed)
    469         continue;
    470 
    471       // Something changed in DepSVI. Propagate to dependents.
    472       WorkList.insert(&*DepSVI);
    473 
    474       DEBUG(dbgs() << "  update " << DepSVI->first->id << '@'
    475             << DepSVI->first->def << " to:\t" << DepSV);
    476     }
    477   } while (!WorkList.empty());
    478 }
    479 
    480 /// traceSiblingValue - Trace a value that is about to be spilled back to the
    481 /// real defining instructions by looking through sibling copies. Always stay
    482 /// within the range of OrigVNI so the registers are known to carry the same
    483 /// value.
    484 ///
    485 /// Determine if the value is defined by all reloads, so spilling isn't
    486 /// necessary - the value is already in the stack slot.
    487 ///
    488 /// Return a defining instruction that may be a candidate for rematerialization.
    489 ///
    490 MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
    491                                                VNInfo *OrigVNI) {
    492   // Check if a cached value already exists.
    493   SibValueMap::iterator SVI;
    494   bool Inserted;
    495   std::tie(SVI, Inserted) =
    496     SibValues.insert(std::make_pair(UseVNI, SibValueInfo(UseReg, UseVNI)));
    497   if (!Inserted) {
    498     DEBUG(dbgs() << "Cached value " << PrintReg(UseReg) << ':'
    499                  << UseVNI->id << '@' << UseVNI->def << ' ' << SVI->second);
    500     return SVI->second.DefMI;
    501   }
    502 
    503   DEBUG(dbgs() << "Tracing value " << PrintReg(UseReg) << ':'
    504                << UseVNI->id << '@' << UseVNI->def << '\n');
    505 
    506   // List of (Reg, VNI) that have been inserted into SibValues, but need to be
    507   // processed.
    508   SmallVector<std::pair<unsigned, VNInfo*>, 8> WorkList;
    509   WorkList.push_back(std::make_pair(UseReg, UseVNI));
    510 
    511   LiveInterval &OrigLI = LIS.getInterval(Original);
    512   do {
    513     unsigned Reg;
    514     VNInfo *VNI;
    515     std::tie(Reg, VNI) = WorkList.pop_back_val();
    516     DEBUG(dbgs() << "  " << PrintReg(Reg) << ':' << VNI->id << '@' << VNI->def
    517                  << ":\t");
    518 
    519     // First check if this value has already been computed.
    520     SVI = SibValues.find(VNI);
    521     assert(SVI != SibValues.end() && "Missing SibValues entry");
    522 
    523     // Trace through PHI-defs created by live range splitting.
    524     if (VNI->isPHIDef()) {
    525       // Stop at original PHIs.  We don't know the value at the
    526       // predecessors. Look up the VNInfo for the current definition
    527       // in OrigLI, to properly determine whether or not this phi was
    528       // added by splitting.
    529       if (VNI->def == OrigLI.getVNInfoAt(VNI->def)->def) {
    530         DEBUG(dbgs() << "orig phi value\n");
    531         SVI->second.DefByOrigPHI = true;
    532         SVI->second.AllDefsAreReloads = false;
    533         propagateSiblingValue(SVI);
    534         continue;
    535       }
    536 
    537       // This is a PHI inserted by live range splitting.  We could trace the
    538       // live-out value from predecessor blocks, but that search can be very
    539       // expensive if there are many predecessors and many more PHIs as
    540       // generated by tail-dup when it sees an indirectbr.  Instead, look at
    541       // all the non-PHI defs that have the same value as OrigVNI.  They must
    542       // jointly dominate VNI->def.  This is not optimal since VNI may actually
    543       // be jointly dominated by a smaller subset of defs, so there is a change
    544       // we will miss a AllDefsAreReloads optimization.
    545 
    546       // Separate all values dominated by OrigVNI into PHIs and non-PHIs.
    547       SmallVector<VNInfo*, 8> PHIs, NonPHIs;
    548       LiveInterval &LI = LIS.getInterval(Reg);
    549 
    550       for (LiveInterval::vni_iterator VI = LI.vni_begin(), VE = LI.vni_end();
    551            VI != VE; ++VI) {
    552         VNInfo *VNI2 = *VI;
    553         if (VNI2->isUnused())
    554           continue;
    555         if (!OrigLI.containsOneValue() &&
    556             OrigLI.getVNInfoAt(VNI2->def) != OrigVNI)
    557           continue;
    558         if (VNI2->isPHIDef() && VNI2->def != OrigVNI->def)
    559           PHIs.push_back(VNI2);
    560         else
    561           NonPHIs.push_back(VNI2);
    562       }
    563       DEBUG(dbgs() << "split phi value, checking " << PHIs.size()
    564                    << " phi-defs, and " << NonPHIs.size()
    565                    << " non-phi/orig defs\n");
    566 
    567       // Create entries for all the PHIs.  Don't add them to the worklist, we
    568       // are processing all of them in one go here.
    569       for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
    570         SibValues.insert(std::make_pair(PHIs[i], SibValueInfo(Reg, PHIs[i])));
    571 
    572       // Add every PHI as a dependent of all the non-PHIs.
    573       for (unsigned i = 0, e = NonPHIs.size(); i != e; ++i) {
    574         VNInfo *NonPHI = NonPHIs[i];
    575         // Known value? Try an insertion.
    576         std::tie(SVI, Inserted) =
    577           SibValues.insert(std::make_pair(NonPHI, SibValueInfo(Reg, NonPHI)));
    578         // Add all the PHIs as dependents of NonPHI.
    579         SVI->second.Deps.insert(SVI->second.Deps.end(), PHIs.begin(),
    580                                 PHIs.end());
    581         // This is the first time we see NonPHI, add it to the worklist.
    582         if (Inserted)
    583           WorkList.push_back(std::make_pair(Reg, NonPHI));
    584         else
    585           // Propagate to all inserted PHIs, not just VNI.
    586           propagateSiblingValue(SVI);
    587       }
    588 
    589       // Next work list item.
    590       continue;
    591     }
    592 
    593     MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
    594     assert(MI && "Missing def");
    595 
    596     // Trace through sibling copies.
    597     if (unsigned SrcReg = isFullCopyOf(MI, Reg)) {
    598       if (isSibling(SrcReg)) {
    599         LiveInterval &SrcLI = LIS.getInterval(SrcReg);
    600         LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
    601         assert(SrcQ.valueIn() && "Copy from non-existing value");
    602         // Check if this COPY kills its source.
    603         SVI->second.KillsSource = SrcQ.isKill();
    604         VNInfo *SrcVNI = SrcQ.valueIn();
    605         DEBUG(dbgs() << "copy of " << PrintReg(SrcReg) << ':'
    606                      << SrcVNI->id << '@' << SrcVNI->def
    607                      << " kill=" << unsigned(SVI->second.KillsSource) << '\n');
    608         // Known sibling source value? Try an insertion.
    609         std::tie(SVI, Inserted) = SibValues.insert(
    610             std::make_pair(SrcVNI, SibValueInfo(SrcReg, SrcVNI)));
    611         // This is the first time we see Src, add it to the worklist.
    612         if (Inserted)
    613           WorkList.push_back(std::make_pair(SrcReg, SrcVNI));
    614         propagateSiblingValue(SVI, VNI);
    615         // Next work list item.
    616         continue;
    617       }
    618     }
    619 
    620     // Track reachable reloads.
    621     SVI->second.DefMI = MI;
    622     SVI->second.SpillMBB = MI->getParent();
    623     int FI;
    624     if (Reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) {
    625       DEBUG(dbgs() << "reload\n");
    626       propagateSiblingValue(SVI);
    627       // Next work list item.
    628       continue;
    629     }
    630 
    631     // Potential remat candidate.
    632     DEBUG(dbgs() << "def " << *MI);
    633     SVI->second.AllDefsAreReloads = false;
    634     propagateSiblingValue(SVI);
    635   } while (!WorkList.empty());
    636 
    637   // Look up the value we were looking for.  We already did this lookup at the
    638   // top of the function, but SibValues may have been invalidated.
    639   SVI = SibValues.find(UseVNI);
    640   assert(SVI != SibValues.end() && "Didn't compute requested info");
    641   DEBUG(dbgs() << "  traced to:\t" << SVI->second);
    642   return SVI->second.DefMI;
    643 }
    644 
    645 /// analyzeSiblingValues - Trace values defined by sibling copies back to
    646 /// something that isn't a sibling copy.
    647 ///
    648 /// Keep track of values that may be rematerializable.
    649 void InlineSpiller::analyzeSiblingValues() {
    650   SibValues.clear();
    651 
    652   // No siblings at all?
    653   if (Edit->getReg() == Original)
    654     return;
    655 
    656   LiveInterval &OrigLI = LIS.getInterval(Original);
    657   for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
    658     unsigned Reg = RegsToSpill[i];
    659     LiveInterval &LI = LIS.getInterval(Reg);
    660     for (LiveInterval::const_vni_iterator VI = LI.vni_begin(),
    661          VE = LI.vni_end(); VI != VE; ++VI) {
    662       VNInfo *VNI = *VI;
    663       if (VNI->isUnused())
    664         continue;
    665       MachineInstr *DefMI = nullptr;
    666       if (!VNI->isPHIDef()) {
    667        DefMI = LIS.getInstructionFromIndex(VNI->def);
    668        assert(DefMI && "No defining instruction");
    669       }
    670       // Check possible sibling copies.
    671       if (VNI->isPHIDef() || DefMI->isCopy()) {
    672         VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
    673         assert(OrigVNI && "Def outside original live range");
    674         if (OrigVNI->def != VNI->def)
    675           DefMI = traceSiblingValue(Reg, VNI, OrigVNI);
    676       }
    677       if (DefMI && Edit->checkRematerializable(VNI, DefMI, AA)) {
    678         DEBUG(dbgs() << "Value " << PrintReg(Reg) << ':' << VNI->id << '@'
    679                      << VNI->def << " may remat from " << *DefMI);
    680       }
    681     }
    682   }
    683 }
    684 
    685 /// hoistSpill - Given a sibling copy that defines a value to be spilled, insert
    686 /// a spill at a better location.
    687 bool InlineSpiller::hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI) {
    688   SlotIndex Idx = LIS.getInstructionIndex(CopyMI);
    689   VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot());
    690   assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy");
    691   SibValueMap::iterator I = SibValues.find(VNI);
    692   if (I == SibValues.end())
    693     return false;
    694 
    695   const SibValueInfo &SVI = I->second;
    696 
    697   // Let the normal folding code deal with the boring case.
    698   if (!SVI.AllDefsAreReloads && SVI.SpillVNI == VNI)
    699     return false;
    700 
    701   // SpillReg may have been deleted by remat and DCE.
    702   if (!LIS.hasInterval(SVI.SpillReg)) {
    703     DEBUG(dbgs() << "Stale interval: " << PrintReg(SVI.SpillReg) << '\n');
    704     SibValues.erase(I);
    705     return false;
    706   }
    707 
    708   LiveInterval &SibLI = LIS.getInterval(SVI.SpillReg);
    709   if (!SibLI.containsValue(SVI.SpillVNI)) {
    710     DEBUG(dbgs() << "Stale value: " << PrintReg(SVI.SpillReg) << '\n');
    711     SibValues.erase(I);
    712     return false;
    713   }
    714 
    715   // Conservatively extend the stack slot range to the range of the original
    716   // value. We may be able to do better with stack slot coloring by being more
    717   // careful here.
    718   assert(StackInt && "No stack slot assigned yet.");
    719   LiveInterval &OrigLI = LIS.getInterval(Original);
    720   VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
    721   StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
    722   DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "
    723                << *StackInt << '\n');
    724 
    725   // Already spilled everywhere.
    726   if (SVI.AllDefsAreReloads) {
    727     DEBUG(dbgs() << "\tno spill needed: " << SVI);
    728     ++NumOmitReloadSpill;
    729     return true;
    730   }
    731   // We are going to spill SVI.SpillVNI immediately after its def, so clear out
    732   // any later spills of the same value.
    733   eliminateRedundantSpills(SibLI, SVI.SpillVNI);
    734 
    735   MachineBasicBlock *MBB = LIS.getMBBFromIndex(SVI.SpillVNI->def);
    736   MachineBasicBlock::iterator MII;
    737   if (SVI.SpillVNI->isPHIDef())
    738     MII = MBB->SkipPHIsAndLabels(MBB->begin());
    739   else {
    740     MachineInstr *DefMI = LIS.getInstructionFromIndex(SVI.SpillVNI->def);
    741     assert(DefMI && "Defining instruction disappeared");
    742     MII = DefMI;
    743     ++MII;
    744   }
    745   // Insert spill without kill flag immediately after def.
    746   TII.storeRegToStackSlot(*MBB, MII, SVI.SpillReg, false, StackSlot,
    747                           MRI.getRegClass(SVI.SpillReg), &TRI);
    748   --MII; // Point to store instruction.
    749   LIS.InsertMachineInstrInMaps(MII);
    750   DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII);
    751 
    752   ++NumSpills;
    753   ++NumHoists;
    754   return true;
    755 }
    756 
    757 /// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any
    758 /// redundant spills of this value in SLI.reg and sibling copies.
    759 void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
    760   assert(VNI && "Missing value");
    761   SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
    762   WorkList.push_back(std::make_pair(&SLI, VNI));
    763   assert(StackInt && "No stack slot assigned yet.");
    764 
    765   do {
    766     LiveInterval *LI;
    767     std::tie(LI, VNI) = WorkList.pop_back_val();
    768     unsigned Reg = LI->reg;
    769     DEBUG(dbgs() << "Checking redundant spills for "
    770                  << VNI->id << '@' << VNI->def << " in " << *LI << '\n');
    771 
    772     // Regs to spill are taken care of.
    773     if (isRegToSpill(Reg))
    774       continue;
    775 
    776     // Add all of VNI's live range to StackInt.
    777     StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
    778     DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n');
    779 
    780     // Find all spills and copies of VNI.
    781     for (MachineRegisterInfo::use_instr_nodbg_iterator
    782          UI = MRI.use_instr_nodbg_begin(Reg), E = MRI.use_instr_nodbg_end();
    783          UI != E; ) {
    784       MachineInstr *MI = &*(UI++);
    785       if (!MI->isCopy() && !MI->mayStore())
    786         continue;
    787       SlotIndex Idx = LIS.getInstructionIndex(MI);
    788       if (LI->getVNInfoAt(Idx) != VNI)
    789         continue;
    790 
    791       // Follow sibling copies down the dominator tree.
    792       if (unsigned DstReg = isFullCopyOf(MI, Reg)) {
    793         if (isSibling(DstReg)) {
    794            LiveInterval &DstLI = LIS.getInterval(DstReg);
    795            VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot());
    796            assert(DstVNI && "Missing defined value");
    797            assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot");
    798            WorkList.push_back(std::make_pair(&DstLI, DstVNI));
    799         }
    800         continue;
    801       }
    802 
    803       // Erase spills.
    804       int FI;
    805       if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
    806         DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << *MI);
    807         // eliminateDeadDefs won't normally remove stores, so switch opcode.
    808         MI->setDesc(TII.get(TargetOpcode::KILL));
    809         DeadDefs.push_back(MI);
    810         ++NumSpillsRemoved;
    811         --NumSpills;
    812       }
    813     }
    814   } while (!WorkList.empty());
    815 }
    816 
    817 
    818 //===----------------------------------------------------------------------===//
    819 //                            Rematerialization
    820 //===----------------------------------------------------------------------===//
    821 
    822 /// markValueUsed - Remember that VNI failed to rematerialize, so its defining
    823 /// instruction cannot be eliminated. See through snippet copies
    824 void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {
    825   SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
    826   WorkList.push_back(std::make_pair(LI, VNI));
    827   do {
    828     std::tie(LI, VNI) = WorkList.pop_back_val();
    829     if (!UsedValues.insert(VNI).second)
    830       continue;
    831 
    832     if (VNI->isPHIDef()) {
    833       MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
    834       for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
    835              PE = MBB->pred_end(); PI != PE; ++PI) {
    836         VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI));
    837         if (PVNI)
    838           WorkList.push_back(std::make_pair(LI, PVNI));
    839       }
    840       continue;
    841     }
    842 
    843     // Follow snippet copies.
    844     MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
    845     if (!SnippetCopies.count(MI))
    846       continue;
    847     LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());
    848     assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy");
    849     VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true));
    850     assert(SnipVNI && "Snippet undefined before copy");
    851     WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));
    852   } while (!WorkList.empty());
    853 }
    854 
    855 /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
    856 bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg,
    857                                      MachineBasicBlock::iterator MI) {
    858 
    859   // Analyze instruction
    860   SmallVector<std::pair<MachineInstr *, unsigned>, 8> Ops;
    861   MIBundleOperands::VirtRegInfo RI =
    862     MIBundleOperands(MI).analyzeVirtReg(VirtReg.reg, &Ops);
    863 
    864   if (!RI.Reads)
    865     return false;
    866 
    867   SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);
    868   VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex());
    869 
    870   if (!ParentVNI) {
    871     DEBUG(dbgs() << "\tadding <undef> flags: ");
    872     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    873       MachineOperand &MO = MI->getOperand(i);
    874       if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg)
    875         MO.setIsUndef();
    876     }
    877     DEBUG(dbgs() << UseIdx << '\t' << *MI);
    878     return true;
    879   }
    880 
    881   if (SnippetCopies.count(MI))
    882     return false;
    883 
    884   // Use an OrigVNI from traceSiblingValue when ParentVNI is a sibling copy.
    885   LiveRangeEdit::Remat RM(ParentVNI);
    886   SibValueMap::const_iterator SibI = SibValues.find(ParentVNI);
    887   if (SibI != SibValues.end())
    888     RM.OrigMI = SibI->second.DefMI;
    889   if (!Edit->canRematerializeAt(RM, UseIdx, false)) {
    890     markValueUsed(&VirtReg, ParentVNI);
    891     DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI);
    892     return false;
    893   }
    894 
    895   // If the instruction also writes VirtReg.reg, it had better not require the
    896   // same register for uses and defs.
    897   if (RI.Tied) {
    898     markValueUsed(&VirtReg, ParentVNI);
    899     DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI);
    900     return false;
    901   }
    902 
    903   // Before rematerializing into a register for a single instruction, try to
    904   // fold a load into the instruction. That avoids allocating a new register.
    905   if (RM.OrigMI->canFoldAsLoad() &&
    906       foldMemoryOperand(Ops, RM.OrigMI)) {
    907     Edit->markRematerialized(RM.ParentVNI);
    908     ++NumFoldedLoads;
    909     return true;
    910   }
    911 
    912   // Alocate a new register for the remat.
    913   unsigned NewVReg = Edit->createFrom(Original);
    914 
    915   // Finally we can rematerialize OrigMI before MI.
    916   SlotIndex DefIdx = Edit->rematerializeAt(*MI->getParent(), MI, NewVReg, RM,
    917                                            TRI);
    918   (void)DefIdx;
    919   DEBUG(dbgs() << "\tremat:  " << DefIdx << '\t'
    920                << *LIS.getInstructionFromIndex(DefIdx));
    921 
    922   // Replace operands
    923   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
    924     MachineOperand &MO = Ops[i].first->getOperand(Ops[i].second);
    925     if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) {
    926       MO.setReg(NewVReg);
    927       MO.setIsKill();
    928     }
    929   }
    930   DEBUG(dbgs() << "\t        " << UseIdx << '\t' << *MI << '\n');
    931 
    932   ++NumRemats;
    933   return true;
    934 }
    935 
    936 /// reMaterializeAll - Try to rematerialize as many uses as possible,
    937 /// and trim the live ranges after.
    938 void InlineSpiller::reMaterializeAll() {
    939   // analyzeSiblingValues has already tested all relevant defining instructions.
    940   if (!Edit->anyRematerializable(AA))
    941     return;
    942 
    943   UsedValues.clear();
    944 
    945   // Try to remat before all uses of snippets.
    946   bool anyRemat = false;
    947   for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
    948     unsigned Reg = RegsToSpill[i];
    949     LiveInterval &LI = LIS.getInterval(Reg);
    950     for (MachineRegisterInfo::reg_bundle_iterator
    951            RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
    952          RegI != E; ) {
    953       MachineInstr *MI = &*(RegI++);
    954 
    955       // Debug values are not allowed to affect codegen.
    956       if (MI->isDebugValue())
    957         continue;
    958 
    959       anyRemat |= reMaterializeFor(LI, MI);
    960     }
    961   }
    962   if (!anyRemat)
    963     return;
    964 
    965   // Remove any values that were completely rematted.
    966   for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
    967     unsigned Reg = RegsToSpill[i];
    968     LiveInterval &LI = LIS.getInterval(Reg);
    969     for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end();
    970          I != E; ++I) {
    971       VNInfo *VNI = *I;
    972       if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI))
    973         continue;
    974       MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
    975       MI->addRegisterDead(Reg, &TRI);
    976       if (!MI->allDefsAreDead())
    977         continue;
    978       DEBUG(dbgs() << "All defs dead: " << *MI);
    979       DeadDefs.push_back(MI);
    980     }
    981   }
    982 
    983   // Eliminate dead code after remat. Note that some snippet copies may be
    984   // deleted here.
    985   if (DeadDefs.empty())
    986     return;
    987   DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n");
    988   Edit->eliminateDeadDefs(DeadDefs, RegsToSpill);
    989 
    990   // Get rid of deleted and empty intervals.
    991   unsigned ResultPos = 0;
    992   for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
    993     unsigned Reg = RegsToSpill[i];
    994     if (!LIS.hasInterval(Reg))
    995       continue;
    996 
    997     LiveInterval &LI = LIS.getInterval(Reg);
    998     if (LI.empty()) {
    999       Edit->eraseVirtReg(Reg);
   1000       continue;
   1001     }
   1002 
   1003     RegsToSpill[ResultPos++] = Reg;
   1004   }
   1005   RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end());
   1006   DEBUG(dbgs() << RegsToSpill.size() << " registers to spill after remat.\n");
   1007 }
   1008 
   1009 
   1010 //===----------------------------------------------------------------------===//
   1011 //                                 Spilling
   1012 //===----------------------------------------------------------------------===//
   1013 
   1014 /// If MI is a load or store of StackSlot, it can be removed.
   1015 bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) {
   1016   int FI = 0;
   1017   unsigned InstrReg = TII.isLoadFromStackSlot(MI, FI);
   1018   bool IsLoad = InstrReg;
   1019   if (!IsLoad)
   1020     InstrReg = TII.isStoreToStackSlot(MI, FI);
   1021 
   1022   // We have a stack access. Is it the right register and slot?
   1023   if (InstrReg != Reg || FI != StackSlot)
   1024     return false;
   1025 
   1026   DEBUG(dbgs() << "Coalescing stack access: " << *MI);
   1027   LIS.RemoveMachineInstrFromMaps(MI);
   1028   MI->eraseFromParent();
   1029 
   1030   if (IsLoad) {
   1031     ++NumReloadsRemoved;
   1032     --NumReloads;
   1033   } else {
   1034     ++NumSpillsRemoved;
   1035     --NumSpills;
   1036   }
   1037 
   1038   return true;
   1039 }
   1040 
   1041 #if !defined(NDEBUG)
   1042 // Dump the range of instructions from B to E with their slot indexes.
   1043 static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B,
   1044                                                MachineBasicBlock::iterator E,
   1045                                                LiveIntervals const &LIS,
   1046                                                const char *const header,
   1047                                                unsigned VReg =0) {
   1048   char NextLine = '\n';
   1049   char SlotIndent = '\t';
   1050 
   1051   if (std::next(B) == E) {
   1052     NextLine = ' ';
   1053     SlotIndent = ' ';
   1054   }
   1055 
   1056   dbgs() << '\t' << header << ": " << NextLine;
   1057 
   1058   for (MachineBasicBlock::iterator I = B; I != E; ++I) {
   1059     SlotIndex Idx = LIS.getInstructionIndex(I).getRegSlot();
   1060 
   1061     // If a register was passed in and this instruction has it as a
   1062     // destination that is marked as an early clobber, print the
   1063     // early-clobber slot index.
   1064     if (VReg) {
   1065       MachineOperand *MO = I->findRegisterDefOperand(VReg);
   1066       if (MO && MO->isEarlyClobber())
   1067         Idx = Idx.getRegSlot(true);
   1068     }
   1069 
   1070     dbgs() << SlotIndent << Idx << '\t' << *I;
   1071   }
   1072 }
   1073 #endif
   1074 
   1075 /// foldMemoryOperand - Try folding stack slot references in Ops into their
   1076 /// instructions.
   1077 ///
   1078 /// @param Ops    Operand indices from analyzeVirtReg().
   1079 /// @param LoadMI Load instruction to use instead of stack slot when non-null.
   1080 /// @return       True on success.
   1081 bool InlineSpiller::
   1082 foldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> > Ops,
   1083                   MachineInstr *LoadMI) {
   1084   if (Ops.empty())
   1085     return false;
   1086   // Don't attempt folding in bundles.
   1087   MachineInstr *MI = Ops.front().first;
   1088   if (Ops.back().first != MI || MI->isBundled())
   1089     return false;
   1090 
   1091   bool WasCopy = MI->isCopy();
   1092   unsigned ImpReg = 0;
   1093 
   1094   bool SpillSubRegs = (MI->getOpcode() == TargetOpcode::STATEPOINT ||
   1095                        MI->getOpcode() == TargetOpcode::PATCHPOINT ||
   1096                        MI->getOpcode() == TargetOpcode::STACKMAP);
   1097 
   1098   // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
   1099   // operands.
   1100   SmallVector<unsigned, 8> FoldOps;
   1101   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
   1102     unsigned Idx = Ops[i].second;
   1103     assert(MI == Ops[i].first && "Instruction conflict during operand folding");
   1104     MachineOperand &MO = MI->getOperand(Idx);
   1105     if (MO.isImplicit()) {
   1106       ImpReg = MO.getReg();
   1107       continue;
   1108     }
   1109     // FIXME: Teach targets to deal with subregs.
   1110     if (!SpillSubRegs && MO.getSubReg())
   1111       return false;
   1112     // We cannot fold a load instruction into a def.
   1113     if (LoadMI && MO.isDef())
   1114       return false;
   1115     // Tied use operands should not be passed to foldMemoryOperand.
   1116     if (!MI->isRegTiedToDefOperand(Idx))
   1117       FoldOps.push_back(Idx);
   1118   }
   1119 
   1120   MachineInstrSpan MIS(MI);
   1121 
   1122   MachineInstr *FoldMI =
   1123                 LoadMI ? TII.foldMemoryOperand(MI, FoldOps, LoadMI)
   1124                        : TII.foldMemoryOperand(MI, FoldOps, StackSlot);
   1125   if (!FoldMI)
   1126     return false;
   1127 
   1128   // Remove LIS for any dead defs in the original MI not in FoldMI.
   1129   for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
   1130     if (!MO->isReg())
   1131       continue;
   1132     unsigned Reg = MO->getReg();
   1133     if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
   1134         MRI.isReserved(Reg)) {
   1135       continue;
   1136     }
   1137     // Skip non-Defs, including undef uses and internal reads.
   1138     if (MO->isUse())
   1139       continue;
   1140     MIBundleOperands::PhysRegInfo RI =
   1141       MIBundleOperands(FoldMI).analyzePhysReg(Reg, &TRI);
   1142     if (RI.FullyDefined)
   1143       continue;
   1144     // FoldMI does not define this physreg. Remove the LI segment.
   1145     assert(MO->isDead() && "Cannot fold physreg def");
   1146     SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();
   1147     LIS.removePhysRegDefAt(Reg, Idx);
   1148   }
   1149 
   1150   LIS.ReplaceMachineInstrInMaps(MI, FoldMI);
   1151   MI->eraseFromParent();
   1152 
   1153   // Insert any new instructions other than FoldMI into the LIS maps.
   1154   assert(!MIS.empty() && "Unexpected empty span of instructions!");
   1155   for (MachineBasicBlock::iterator MII = MIS.begin(), End = MIS.end();
   1156        MII != End; ++MII)
   1157     if (&*MII != FoldMI)
   1158       LIS.InsertMachineInstrInMaps(&*MII);
   1159 
   1160   // TII.foldMemoryOperand may have left some implicit operands on the
   1161   // instruction.  Strip them.
   1162   if (ImpReg)
   1163     for (unsigned i = FoldMI->getNumOperands(); i; --i) {
   1164       MachineOperand &MO = FoldMI->getOperand(i - 1);
   1165       if (!MO.isReg() || !MO.isImplicit())
   1166         break;
   1167       if (MO.getReg() == ImpReg)
   1168         FoldMI->RemoveOperand(i - 1);
   1169     }
   1170 
   1171   DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS,
   1172                                            "folded"));
   1173 
   1174   if (!WasCopy)
   1175     ++NumFolded;
   1176   else if (Ops.front().second == 0)
   1177     ++NumSpills;
   1178   else
   1179     ++NumReloads;
   1180   return true;
   1181 }
   1182 
   1183 void InlineSpiller::insertReload(unsigned NewVReg,
   1184                                  SlotIndex Idx,
   1185                                  MachineBasicBlock::iterator MI) {
   1186   MachineBasicBlock &MBB = *MI->getParent();
   1187 
   1188   MachineInstrSpan MIS(MI);
   1189   TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot,
   1190                            MRI.getRegClass(NewVReg), &TRI);
   1191 
   1192   LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI);
   1193 
   1194   DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload",
   1195                                            NewVReg));
   1196   ++NumReloads;
   1197 }
   1198 
   1199 /// insertSpill - Insert a spill of NewVReg after MI.
   1200 void InlineSpiller::insertSpill(unsigned NewVReg, bool isKill,
   1201                                  MachineBasicBlock::iterator MI) {
   1202   MachineBasicBlock &MBB = *MI->getParent();
   1203 
   1204   MachineInstrSpan MIS(MI);
   1205   TII.storeRegToStackSlot(MBB, std::next(MI), NewVReg, isKill, StackSlot,
   1206                           MRI.getRegClass(NewVReg), &TRI);
   1207 
   1208   LIS.InsertMachineInstrRangeInMaps(std::next(MI), MIS.end());
   1209 
   1210   DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI), MIS.end(), LIS,
   1211                                            "spill"));
   1212   ++NumSpills;
   1213 }
   1214 
   1215 /// spillAroundUses - insert spill code around each use of Reg.
   1216 void InlineSpiller::spillAroundUses(unsigned Reg) {
   1217   DEBUG(dbgs() << "spillAroundUses " << PrintReg(Reg) << '\n');
   1218   LiveInterval &OldLI = LIS.getInterval(Reg);
   1219 
   1220   // Iterate over instructions using Reg.
   1221   for (MachineRegisterInfo::reg_bundle_iterator
   1222        RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
   1223        RegI != E; ) {
   1224     MachineInstr *MI = &*(RegI++);
   1225 
   1226     // Debug values are not allowed to affect codegen.
   1227     if (MI->isDebugValue()) {
   1228       // Modify DBG_VALUE now that the value is in a spill slot.
   1229       bool IsIndirect = MI->isIndirectDebugValue();
   1230       uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0;
   1231       const MDNode *Var = MI->getDebugVariable();
   1232       const MDNode *Expr = MI->getDebugExpression();
   1233       DebugLoc DL = MI->getDebugLoc();
   1234       DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
   1235       MachineBasicBlock *MBB = MI->getParent();
   1236       assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
   1237              "Expected inlined-at fields to agree");
   1238       BuildMI(*MBB, MBB->erase(MI), DL, TII.get(TargetOpcode::DBG_VALUE))
   1239           .addFrameIndex(StackSlot)
   1240           .addImm(Offset)
   1241           .addMetadata(Var)
   1242           .addMetadata(Expr);
   1243       continue;
   1244     }
   1245 
   1246     // Ignore copies to/from snippets. We'll delete them.
   1247     if (SnippetCopies.count(MI))
   1248       continue;
   1249 
   1250     // Stack slot accesses may coalesce away.
   1251     if (coalesceStackAccess(MI, Reg))
   1252       continue;
   1253 
   1254     // Analyze instruction.
   1255     SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops;
   1256     MIBundleOperands::VirtRegInfo RI =
   1257       MIBundleOperands(MI).analyzeVirtReg(Reg, &Ops);
   1258 
   1259     // Find the slot index where this instruction reads and writes OldLI.
   1260     // This is usually the def slot, except for tied early clobbers.
   1261     SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();
   1262     if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))
   1263       if (SlotIndex::isSameInstr(Idx, VNI->def))
   1264         Idx = VNI->def;
   1265 
   1266     // Check for a sibling copy.
   1267     unsigned SibReg = isFullCopyOf(MI, Reg);
   1268     if (SibReg && isSibling(SibReg)) {
   1269       // This may actually be a copy between snippets.
   1270       if (isRegToSpill(SibReg)) {
   1271         DEBUG(dbgs() << "Found new snippet copy: " << *MI);
   1272         SnippetCopies.insert(MI);
   1273         continue;
   1274       }
   1275       if (RI.Writes) {
   1276         // Hoist the spill of a sib-reg copy.
   1277         if (hoistSpill(OldLI, MI)) {
   1278           // This COPY is now dead, the value is already in the stack slot.
   1279           MI->getOperand(0).setIsDead();
   1280           DeadDefs.push_back(MI);
   1281           continue;
   1282         }
   1283       } else {
   1284         // This is a reload for a sib-reg copy. Drop spills downstream.
   1285         LiveInterval &SibLI = LIS.getInterval(SibReg);
   1286         eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));
   1287         // The COPY will fold to a reload below.
   1288       }
   1289     }
   1290 
   1291     // Attempt to fold memory ops.
   1292     if (foldMemoryOperand(Ops))
   1293       continue;
   1294 
   1295     // Create a new virtual register for spill/fill.
   1296     // FIXME: Infer regclass from instruction alone.
   1297     unsigned NewVReg = Edit->createFrom(Reg);
   1298 
   1299     if (RI.Reads)
   1300       insertReload(NewVReg, Idx, MI);
   1301 
   1302     // Rewrite instruction operands.
   1303     bool hasLiveDef = false;
   1304     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
   1305       MachineOperand &MO = Ops[i].first->getOperand(Ops[i].second);
   1306       MO.setReg(NewVReg);
   1307       if (MO.isUse()) {
   1308         if (!Ops[i].first->isRegTiedToDefOperand(Ops[i].second))
   1309           MO.setIsKill();
   1310       } else {
   1311         if (!MO.isDead())
   1312           hasLiveDef = true;
   1313       }
   1314     }
   1315     DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI << '\n');
   1316 
   1317     // FIXME: Use a second vreg if instruction has no tied ops.
   1318     if (RI.Writes)
   1319       if (hasLiveDef)
   1320         insertSpill(NewVReg, true, MI);
   1321   }
   1322 }
   1323 
   1324 /// spillAll - Spill all registers remaining after rematerialization.
   1325 void InlineSpiller::spillAll() {
   1326   // Update LiveStacks now that we are committed to spilling.
   1327   if (StackSlot == VirtRegMap::NO_STACK_SLOT) {
   1328     StackSlot = VRM.assignVirt2StackSlot(Original);
   1329     StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));
   1330     StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator());
   1331   } else
   1332     StackInt = &LSS.getInterval(StackSlot);
   1333 
   1334   if (Original != Edit->getReg())
   1335     VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);
   1336 
   1337   assert(StackInt->getNumValNums() == 1 && "Bad stack interval values");
   1338   for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
   1339     StackInt->MergeSegmentsInAsValue(LIS.getInterval(RegsToSpill[i]),
   1340                                      StackInt->getValNumInfo(0));
   1341   DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');
   1342 
   1343   // Spill around uses of all RegsToSpill.
   1344   for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
   1345     spillAroundUses(RegsToSpill[i]);
   1346 
   1347   // Hoisted spills may cause dead code.
   1348   if (!DeadDefs.empty()) {
   1349     DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n");
   1350     Edit->eliminateDeadDefs(DeadDefs, RegsToSpill);
   1351   }
   1352 
   1353   // Finally delete the SnippetCopies.
   1354   for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
   1355     for (MachineRegisterInfo::reg_instr_iterator
   1356          RI = MRI.reg_instr_begin(RegsToSpill[i]), E = MRI.reg_instr_end();
   1357          RI != E; ) {
   1358       MachineInstr *MI = &*(RI++);
   1359       assert(SnippetCopies.count(MI) && "Remaining use wasn't a snippet copy");
   1360       // FIXME: Do this with a LiveRangeEdit callback.
   1361       LIS.RemoveMachineInstrFromMaps(MI);
   1362       MI->eraseFromParent();
   1363     }
   1364   }
   1365 
   1366   // Delete all spilled registers.
   1367   for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
   1368     Edit->eraseVirtReg(RegsToSpill[i]);
   1369 }
   1370 
   1371 void InlineSpiller::spill(LiveRangeEdit &edit) {
   1372   ++NumSpilledRanges;
   1373   Edit = &edit;
   1374   assert(!TargetRegisterInfo::isStackSlot(edit.getReg())
   1375          && "Trying to spill a stack slot.");
   1376   // Share a stack slot among all descendants of Original.
   1377   Original = VRM.getOriginal(edit.getReg());
   1378   StackSlot = VRM.getStackSlot(Original);
   1379   StackInt = nullptr;
   1380 
   1381   DEBUG(dbgs() << "Inline spilling "
   1382                << TRI.getRegClassName(MRI.getRegClass(edit.getReg()))
   1383                << ':' << edit.getParent()
   1384                << "\nFrom original " << PrintReg(Original) << '\n');
   1385   assert(edit.getParent().isSpillable() &&
   1386          "Attempting to spill already spilled value.");
   1387   assert(DeadDefs.empty() && "Previous spill didn't remove dead defs");
   1388 
   1389   collectRegsToSpill();
   1390   analyzeSiblingValues();
   1391   reMaterializeAll();
   1392 
   1393   // Remat may handle everything.
   1394   if (!RegsToSpill.empty())
   1395     spillAll();
   1396 
   1397   Edit->calculateRegClassAndHint(MF, Loops, MBFI);
   1398 }
   1399