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 }
  63
  64 bool LiveRangeEdit::anyRematerializable(LiveIntervals &lis,
  65                                         const TargetInstrInfo &tii,
  66                                         AliasAnalysis *aa) {
  67   if (!scannedRemattable_)
  68     scanRemattable(lis, tii, aa);
  69   return !remattable_.empty();
  70 }
  71
  72 /// allUsesAvailableAt - Return true if all registers used by OrigMI at
  73 /// OrigIdx are also available with the same value at UseIdx.
  74 bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
  75                                        SlotIndex OrigIdx,
  76                                        SlotIndex UseIdx,
  77                                        LiveIntervals &lis) {
  78   OrigIdx = OrigIdx.getUseIndex();
  79   UseIdx = UseIdx.getUseIndex();
  80   for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
  81     const MachineOperand &MO = OrigMI->getOperand(i);
  82     if (!MO.isReg() || !MO.getReg() || MO.isDef())
  83       continue;
  84     // Reserved registers are OK.
  85     if (MO.isUndef() || !lis.hasInterval(MO.getReg()))
  86       continue;
  87     // We cannot depend on virtual registers in uselessRegs_.
  88     if (uselessRegs_)
  89       for (unsigned ui = 0, ue = uselessRegs_->size(); ui != ue; ++ui)
  90         if ((*uselessRegs_)[ui]->reg == MO.getReg())
  91           return false;
  92
  93     LiveInterval &li = lis.getInterval(MO.getReg());
  94     const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
  95     if (!OVNI)
  96       continue;
  97     if (OVNI != li.getVNInfoAt(UseIdx))
  98       return false;
  99   }
 100   return true;
 101 }
 102
 103 bool LiveRangeEdit::canRematerializeAt(Remat &RM,
 104                                        SlotIndex UseIdx,
 105                                        bool cheapAsAMove,
 106                                        LiveIntervals &lis) {
 107   assert(scannedRemattable_ && "Call anyRematerializable first");
 108
 109   // Use scanRemattable info.
 110   if (!remattable_.count(RM.ParentVNI))
 111     return false;
 112
 113   // No defining instruction provided.
 114   SlotIndex DefIdx;
 115   if (RM.OrigMI)
 116     DefIdx = lis.getInstructionIndex(RM.OrigMI);
 117   else {
 118     DefIdx = RM.ParentVNI->def;
 119     RM.OrigMI = lis.getInstructionFromIndex(DefIdx);
 120     assert(RM.OrigMI && "No defining instruction for remattable value");
 121   }
 122
 123   // If only cheap remats were requested, bail out early.
 124   if (cheapAsAMove && !RM.OrigMI->getDesc().isAsCheapAsAMove())
 125     return false;
 126
 127   // Verify that all used registers are available with the same values.
 128   if (!allUsesAvailableAt(RM.OrigMI, DefIdx, UseIdx, lis))
 129     return false;
 130
 131   return true;
 132 }
 133
 134 SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB,
 135                                          MachineBasicBlock::iterator MI,
 136                                          unsigned DestReg,
 137                                          const Remat &RM,
 138                                          LiveIntervals &lis,
 139                                          const TargetInstrInfo &tii,
 140                                          const TargetRegisterInfo &tri) {
 141   assert(RM.OrigMI && "Invalid remat");
 142   tii.reMaterialize(MBB, MI, DestReg, 0, RM.OrigMI, tri);
 143   rematted_.insert(RM.ParentVNI);
 144   return lis.InsertMachineInstrInMaps(--MI).getDefIndex();
 145 }
 146
 147 void LiveRangeEdit::eraseVirtReg(unsigned Reg, LiveIntervals &LIS) {
 148   if (delegate_ && delegate_->LRE_CanEraseVirtReg(Reg))
 149     LIS.removeInterval(Reg);
 150 }
 151
 152 void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
 153                                       LiveIntervals &LIS, VirtRegMap &VRM,
 154                                       const TargetInstrInfo &TII) {
 155   SetVector<LiveInterval*,
 156             SmallVector<LiveInterval*, 8>,
 157             SmallPtrSet<LiveInterval*, 8> > ToShrink;
 158
 159   for (;;) {
 160     // Erase all dead defs.
 161     while (!Dead.empty()) {
 162       MachineInstr *MI = Dead.pop_back_val();
 163       assert(MI->allDefsAreDead() && "Def isn't really dead");
 164       SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex();
 165
 166       // Never delete inline asm.
 167       if (MI->isInlineAsm()) {
 168         DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI);
 169         continue;
 170       }
 171
 172       // Use the same criteria as DeadMachineInstructionElim.
 173       bool SawStore = false;
 174       if (!MI->isSafeToMove(&TII, 0, SawStore)) {
 175         DEBUG(dbgs() << "Can't delete: " << Idx << '\t' << *MI);
 176         continue;
 177       }
 178
 179       DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);
 180
 181       // Check for live intervals that may shrink
 182       for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
 183              MOE = MI->operands_end(); MOI != MOE; ++MOI) {
 184         if (!MOI->isReg())
 185           continue;
 186         unsigned Reg = MOI->getReg();
 187         if (!TargetRegisterInfo::isVirtualRegister(Reg))
 188           continue;
 189         LiveInterval &LI = LIS.getInterval(Reg);
 190
 191         // Shrink read registers.
 192         if (MI->readsVirtualRegister(Reg))
 193           ToShrink.insert(&LI);
 194
 195         // Remove defined value.
 196         if (MOI->isDef()) {
 197           if (VNInfo *VNI = LI.getVNInfoAt(Idx)) {
 198             if (delegate_)
 199               delegate_->LRE_WillShrinkVirtReg(LI.reg);
 200             LI.removeValNo(VNI);
 201             if (LI.empty()) {
 202               ToShrink.remove(&LI);
 203               eraseVirtReg(Reg, LIS);
 204             }
 205           }
 206         }
 207       }
 208
 209       if (delegate_)
 210         delegate_->LRE_WillEraseInstruction(MI);
 211       LIS.RemoveMachineInstrFromMaps(MI);
 212       MI->eraseFromParent();
 213     }
 214
 215     if (ToShrink.empty())
 216       break;
 217
 218     // Shrink just one live interval. Then delete new dead defs.
 219     LiveInterval *LI = ToShrink.back();
 220     ToShrink.pop_back();
 221     if (delegate_)
 222       delegate_->LRE_WillShrinkVirtReg(LI->reg);
 223     if (!LIS.shrinkToUses(LI, &Dead))
 224       continue;
 225
 226     // LI may have been separated, create new intervals.
 227     LI->RenumberValues(LIS);
 228     ConnectedVNInfoEqClasses ConEQ(LIS);
 229     unsigned NumComp = ConEQ.Classify(LI);
 230     if (NumComp <= 1)
 231       continue;
 232     DEBUG(dbgs() << NumComp << " components: " << *LI << '\n');
 233     SmallVector<LiveInterval*, 8> Dups(1, LI);
 234     for (unsigned i = 1; i != NumComp; ++i)
 235       Dups.push_back(&createFrom(LI->reg, LIS, VRM));
 236     ConEQ.Distribute(&Dups[0], VRM.getRegInfo());
 237   }
 238 }
 239
 240 void LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF,
 241                                              LiveIntervals &LIS,
 242                                              const MachineLoopInfo &Loops) {
 243   VirtRegAuxInfo VRAI(MF, LIS, Loops);
 244   for (iterator I = begin(), E = end(); I != E; ++I) {
 245     LiveInterval &LI = **I;
 246     VRAI.CalculateRegClass(LI.reg);
 247     VRAI.CalculateWeightAndHint(LI);
 248   }
 249 }