Home | History | Annotate | Download | only in CodeGen 
      1 //===-- LiveRangeEdit.cpp - Basic tools for editing a register live range -===//
      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 LiveRangeEdit class represents changes done to a virtual register when it
     11 // is spilled or split.
     12 //===----------------------------------------------------------------------===//
     13 
     14 #define DEBUG_TYPE "regalloc"
     15 #include "VirtRegMap.h"
     16 #include "llvm/ADT/SetVector.h"
     17 #include "llvm/ADT/Statistic.h"
     18 #include "llvm/CodeGen/CalcSpillWeights.h"
     19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
     20 #include "llvm/CodeGen/LiveRangeEdit.h"
     21 #include "llvm/CodeGen/MachineRegisterInfo.h"
     22 #include "llvm/Target/TargetInstrInfo.h"
     23 #include "llvm/Support/Debug.h"
     24 #include "llvm/Support/raw_ostream.h"
     25 
     26 using namespace llvm;
     27 
     28 STATISTIC(NumDCEDeleted,     "Number of instructions deleted by DCE");
     29 STATISTIC(NumDCEFoldedLoads, "Number of single use loads folded after DCE");
     30 STATISTIC(NumFracRanges,     "Number of live ranges fractured by DCE");
     31 
     32 void LiveRangeEdit::Delegate::anchor() { }
     33 
     34 LiveInterval &LiveRangeEdit::createFrom(unsigned OldReg) {
     35   unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
     36   if (VRM) {
     37     VRM->grow();
     38     VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
     39   }
     40   LiveInterval &LI = LIS.getOrCreateInterval(VReg);
     41   newRegs_.push_back(&LI);
     42   return LI;
     43 }
     44 
     45 bool LiveRangeEdit::checkRematerializable(VNInfo *VNI,
     46                                           const MachineInstr *DefMI,
     47                                           AliasAnalysis *aa) {
     48   assert(DefMI && "Missing instruction");
     49   scannedRemattable_ = true;
     50   if (!TII.isTriviallyReMaterializable(DefMI, aa))
     51     return false;
     52   remattable_.insert(VNI);
     53   return true;
     54 }
     55 
     56 void LiveRangeEdit::scanRemattable(AliasAnalysis *aa) {
     57   for (LiveInterval::vni_iterator I = parent_.vni_begin(),
     58        E = parent_.vni_end(); I != E; ++I) {
     59     VNInfo *VNI = *I;
     60     if (VNI->isUnused())
     61       continue;
     62     MachineInstr *DefMI = LIS.getInstructionFromIndex(VNI->def);
     63     if (!DefMI)
     64       continue;
     65     checkRematerializable(VNI, DefMI, aa);
     66   }
     67   scannedRemattable_ = true;
     68 }
     69 
     70 bool LiveRangeEdit::anyRematerializable(AliasAnalysis *aa) {
     71   if (!scannedRemattable_)
     72     scanRemattable(aa);
     73   return !remattable_.empty();
     74 }
     75 
     76 /// allUsesAvailableAt - Return true if all registers used by OrigMI at
     77 /// OrigIdx are also available with the same value at UseIdx.
     78 bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
     79                                        SlotIndex OrigIdx,
     80                                        SlotIndex UseIdx) {
     81   OrigIdx = OrigIdx.getRegSlot(true);
     82   UseIdx = UseIdx.getRegSlot(true);
     83   for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
     84     const MachineOperand &MO = OrigMI->getOperand(i);
     85     if (!MO.isReg() || !MO.getReg() || MO.isDef())
     86       continue;
     87     // Reserved registers are OK.
     88     if (MO.isUndef() || !LIS.hasInterval(MO.getReg()))
     89       continue;
     90 
     91     LiveInterval &li = LIS.getInterval(MO.getReg());
     92     const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
     93     if (!OVNI)
     94       continue;
     95     if (OVNI != li.getVNInfoAt(UseIdx))
     96       return false;
     97   }
     98   return true;
     99 }
    100 
    101 bool LiveRangeEdit::canRematerializeAt(Remat &RM,
    102                                        SlotIndex UseIdx,
    103                                        bool cheapAsAMove) {
    104   assert(scannedRemattable_ && "Call anyRematerializable first");
    105 
    106   // Use scanRemattable info.
    107   if (!remattable_.count(RM.ParentVNI))
    108     return false;
    109 
    110   // No defining instruction provided.
    111   SlotIndex DefIdx;
    112   if (RM.OrigMI)
    113     DefIdx = LIS.getInstructionIndex(RM.OrigMI);
    114   else {
    115     DefIdx = RM.ParentVNI->def;
    116     RM.OrigMI = LIS.getInstructionFromIndex(DefIdx);
    117     assert(RM.OrigMI && "No defining instruction for remattable value");
    118   }
    119 
    120   // If only cheap remats were requested, bail out early.
    121   if (cheapAsAMove && !RM.OrigMI->isAsCheapAsAMove())
    122     return false;
    123 
    124   // Verify that all used registers are available with the same values.
    125   if (!allUsesAvailableAt(RM.OrigMI, DefIdx, UseIdx))
    126     return false;
    127 
    128   return true;
    129 }
    130 
    131 SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB,
    132                                          MachineBasicBlock::iterator MI,
    133                                          unsigned DestReg,
    134                                          const Remat &RM,
    135                                          const TargetRegisterInfo &tri,
    136                                          bool Late) {
    137   assert(RM.OrigMI && "Invalid remat");
    138   TII.reMaterialize(MBB, MI, DestReg, 0, RM.OrigMI, tri);
    139   rematted_.insert(RM.ParentVNI);
    140   return LIS.getSlotIndexes()->insertMachineInstrInMaps(--MI, Late)
    141            .getRegSlot();
    142 }
    143 
    144 void LiveRangeEdit::eraseVirtReg(unsigned Reg) {
    145   if (delegate_ && delegate_->LRE_CanEraseVirtReg(Reg))
    146     LIS.removeInterval(Reg);
    147 }
    148 
    149 bool LiveRangeEdit::foldAsLoad(LiveInterval *LI,
    150                                SmallVectorImpl<MachineInstr*> &Dead) {
    151   MachineInstr *DefMI = 0, *UseMI = 0;
    152 
    153   // Check that there is a single def and a single use.
    154   for (MachineRegisterInfo::reg_nodbg_iterator I = MRI.reg_nodbg_begin(LI->reg),
    155        E = MRI.reg_nodbg_end(); I != E; ++I) {
    156     MachineOperand &MO = I.getOperand();
    157     MachineInstr *MI = MO.getParent();
    158     if (MO.isDef()) {
    159       if (DefMI && DefMI != MI)
    160         return false;
    161       if (!MI->canFoldAsLoad())
    162         return false;
    163       DefMI = MI;
    164     } else if (!MO.isUndef()) {
    165       if (UseMI && UseMI != MI)
    166         return false;
    167       // FIXME: Targets don't know how to fold subreg uses.
    168       if (MO.getSubReg())
    169         return false;
    170       UseMI = MI;
    171     }
    172   }
    173   if (!DefMI || !UseMI)
    174     return false;
    175 
    176   DEBUG(dbgs() << "Try to fold single def: " << *DefMI
    177                << "       into single use: " << *UseMI);
    178 
    179   SmallVector<unsigned, 8> Ops;
    180   if (UseMI->readsWritesVirtualRegister(LI->reg, &Ops).second)
    181     return false;
    182 
    183   MachineInstr *FoldMI = TII.foldMemoryOperand(UseMI, Ops, DefMI);
    184   if (!FoldMI)
    185     return false;
    186   DEBUG(dbgs() << "                folded: " << *FoldMI);
    187   LIS.ReplaceMachineInstrInMaps(UseMI, FoldMI);
    188   UseMI->eraseFromParent();
    189   DefMI->addRegisterDead(LI->reg, 0);
    190   Dead.push_back(DefMI);
    191   ++NumDCEFoldedLoads;
    192   return true;
    193 }
    194 
    195 void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
    196                                       ArrayRef<unsigned> RegsBeingSpilled) {
    197   SetVector<LiveInterval*,
    198             SmallVector<LiveInterval*, 8>,
    199             SmallPtrSet<LiveInterval*, 8> > ToShrink;
    200 
    201   for (;;) {
    202     // Erase all dead defs.
    203     while (!Dead.empty()) {
    204       MachineInstr *MI = Dead.pop_back_val();
    205       assert(MI->allDefsAreDead() && "Def isn't really dead");
    206       SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();
    207 
    208       // Never delete inline asm.
    209       if (MI->isInlineAsm()) {
    210         DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI);
    211         continue;
    212       }
    213 
    214       // Use the same criteria as DeadMachineInstructionElim.
    215       bool SawStore = false;
    216       if (!MI->isSafeToMove(&TII, 0, SawStore)) {
    217         DEBUG(dbgs() << "Can't delete: " << Idx << '\t' << *MI);
    218         continue;
    219       }
    220 
    221       DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);
    222 
    223       // Check for live intervals that may shrink
    224       for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
    225              MOE = MI->operands_end(); MOI != MOE; ++MOI) {
    226         if (!MOI->isReg())
    227           continue;
    228         unsigned Reg = MOI->getReg();
    229         if (!TargetRegisterInfo::isVirtualRegister(Reg))
    230           continue;
    231         LiveInterval &LI = LIS.getInterval(Reg);
    232 
    233         // Shrink read registers, unless it is likely to be expensive and
    234         // unlikely to change anything. We typically don't want to shrink the
    235         // PIC base register that has lots of uses everywhere.
    236         // Always shrink COPY uses that probably come from live range splitting.
    237         if (MI->readsVirtualRegister(Reg) &&
    238             (MI->isCopy() || MOI->isDef() || MRI.hasOneNonDBGUse(Reg) ||
    239              LI.killedAt(Idx)))
    240           ToShrink.insert(&LI);
    241 
    242         // Remove defined value.
    243         if (MOI->isDef()) {
    244           if (VNInfo *VNI = LI.getVNInfoAt(Idx)) {
    245             if (delegate_)
    246               delegate_->LRE_WillShrinkVirtReg(LI.reg);
    247             LI.removeValNo(VNI);
    248             if (LI.empty()) {
    249               ToShrink.remove(&LI);
    250               eraseVirtReg(Reg);
    251             }
    252           }
    253         }
    254       }
    255 
    256       if (delegate_)
    257         delegate_->LRE_WillEraseInstruction(MI);
    258       LIS.RemoveMachineInstrFromMaps(MI);
    259       MI->eraseFromParent();
    260       ++NumDCEDeleted;
    261     }
    262 
    263     if (ToShrink.empty())
    264       break;
    265 
    266     // Shrink just one live interval. Then delete new dead defs.
    267     LiveInterval *LI = ToShrink.back();
    268     ToShrink.pop_back();
    269     if (foldAsLoad(LI, Dead))
    270       continue;
    271     if (delegate_)
    272       delegate_->LRE_WillShrinkVirtReg(LI->reg);
    273     if (!LIS.shrinkToUses(LI, &Dead))
    274       continue;
    275 
    276     // Don't create new intervals for a register being spilled.
    277     // The new intervals would have to be spilled anyway so its not worth it.
    278     // Also they currently aren't spilled so creating them and not spilling
    279     // them results in incorrect code.
    280     bool BeingSpilled = false;
    281     for (unsigned i = 0, e = RegsBeingSpilled.size(); i != e; ++i) {
    282       if (LI->reg == RegsBeingSpilled[i]) {
    283         BeingSpilled = true;
    284         break;
    285       }
    286     }
    287 
    288     if (BeingSpilled) continue;
    289 
    290     // LI may have been separated, create new intervals.
    291     LI->RenumberValues(LIS);
    292     ConnectedVNInfoEqClasses ConEQ(LIS);
    293     unsigned NumComp = ConEQ.Classify(LI);
    294     if (NumComp <= 1)
    295       continue;
    296     ++NumFracRanges;
    297     bool IsOriginal = VRM && VRM->getOriginal(LI->reg) == LI->reg;
    298     DEBUG(dbgs() << NumComp << " components: " << *LI << '\n');
    299     SmallVector<LiveInterval*, 8> Dups(1, LI);
    300     for (unsigned i = 1; i != NumComp; ++i) {
    301       Dups.push_back(&createFrom(LI->reg));
    302       // If LI is an original interval that hasn't been split yet, make the new
    303       // intervals their own originals instead of referring to LI. The original
    304       // interval must contain all the split products, and LI doesn't.
    305       if (IsOriginal)
    306         VRM->setIsSplitFromReg(Dups.back()->reg, 0);
    307       if (delegate_)
    308         delegate_->LRE_DidCloneVirtReg(Dups.back()->reg, LI->reg);
    309     }
    310     ConEQ.Distribute(&Dups[0], MRI);
    311   }
    312 }
    313 
    314 void LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF,
    315                                              const MachineLoopInfo &Loops) {
    316   VirtRegAuxInfo VRAI(MF, LIS, Loops);
    317   for (iterator I = begin(), E = end(); I != E; ++I) {
    318     LiveInterval &LI = **I;
    319     if (MRI.recomputeRegClass(LI.reg, MF.getTarget()))
    320       DEBUG(dbgs() << "Inflated " << PrintReg(LI.reg) << " to "
    321                    << MRI.getRegClass(LI.reg)->getName() << '\n');
    322     VRAI.CalculateWeightAndHint(LI);
    323   }
    324 }
    325