lib/CodeGen/LiveRangeEdit.cpp

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