LLVM API Documentation

LiveRangeCalc.cpp
Go to the documentation of this file.
00001 //===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Implementation of the LiveRangeCalc class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #define DEBUG_TYPE "regalloc"
00015 #include "LiveRangeCalc.h"
00016 #include "llvm/CodeGen/MachineDominators.h"
00017 #include "llvm/CodeGen/MachineRegisterInfo.h"
00018 
00019 using namespace llvm;
00020 
00021 void LiveRangeCalc::reset(const MachineFunction *mf,
00022                           SlotIndexes *SI,
00023                           MachineDominatorTree *MDT,
00024                           VNInfo::Allocator *VNIA) {
00025   MF = mf;
00026   MRI = &MF->getRegInfo();
00027   Indexes = SI;
00028   DomTree = MDT;
00029   Alloc = VNIA;
00030 
00031   unsigned N = MF->getNumBlockIDs();
00032   Seen.clear();
00033   Seen.resize(N);
00034   LiveOut.resize(N);
00035   LiveIn.clear();
00036 }
00037 
00038 
00039 void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
00040   assert(MRI && Indexes && "call reset() first");
00041 
00042   // Visit all def operands. If the same instruction has multiple defs of Reg,
00043   // LR.createDeadDef() will deduplicate.
00044   for (MachineOperand &MO : MRI->def_operands(Reg)) {
00045     const MachineInstr *MI = MO.getParent();
00046     // Find the corresponding slot index.
00047     SlotIndex Idx;
00048     if (MI->isPHI())
00049       // PHI defs begin at the basic block start index.
00050       Idx = Indexes->getMBBStartIdx(MI->getParent());
00051     else
00052       // Instructions are either normal 'r', or early clobber 'e'.
00053       Idx = Indexes->getInstructionIndex(MI)
00054         .getRegSlot(MO.isEarlyClobber());
00055 
00056     // Create the def in LR. This may find an existing def.
00057     LR.createDeadDef(Idx, *Alloc);
00058   }
00059 }
00060 
00061 
00062 void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg) {
00063   assert(MRI && Indexes && "call reset() first");
00064 
00065   // Visit all operands that read Reg. This may include partial defs.
00066   for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
00067     // Clear all kill flags. They will be reinserted after register allocation
00068     // by LiveIntervalAnalysis::addKillFlags().
00069     if (MO.isUse())
00070       MO.setIsKill(false);
00071     if (!MO.readsReg())
00072       continue;
00073     // MI is reading Reg. We may have visited MI before if it happens to be
00074     // reading Reg multiple times. That is OK, extend() is idempotent.
00075     const MachineInstr *MI = MO.getParent();
00076     unsigned OpNo = (&MO - &MI->getOperand(0));
00077 
00078     // Find the SlotIndex being read.
00079     SlotIndex Idx;
00080     if (MI->isPHI()) {
00081       assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
00082       // PHI operands are paired: (Reg, PredMBB).
00083       // Extend the live range to be live-out from PredMBB.
00084       Idx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
00085     } else {
00086       // This is a normal instruction.
00087       Idx = Indexes->getInstructionIndex(MI).getRegSlot();
00088       // Check for early-clobber redefs.
00089       unsigned DefIdx;
00090       if (MO.isDef()) {
00091         if (MO.isEarlyClobber())
00092           Idx = Idx.getRegSlot(true);
00093       } else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
00094         // FIXME: This would be a lot easier if tied early-clobber uses also
00095         // had an early-clobber flag.
00096         if (MI->getOperand(DefIdx).isEarlyClobber())
00097           Idx = Idx.getRegSlot(true);
00098       }
00099     }
00100     extend(LR, Idx, Reg);
00101   }
00102 }
00103 
00104 
00105 // Transfer information from the LiveIn vector to the live ranges.
00106 void LiveRangeCalc::updateLiveIns() {
00107   LiveRangeUpdater Updater;
00108   for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
00109          E = LiveIn.end(); I != E; ++I) {
00110     if (!I->DomNode)
00111       continue;
00112     MachineBasicBlock *MBB = I->DomNode->getBlock();
00113     assert(I->Value && "No live-in value found");
00114     SlotIndex Start, End;
00115     std::tie(Start, End) = Indexes->getMBBRange(MBB);
00116 
00117     if (I->Kill.isValid())
00118       // Value is killed inside this block.
00119       End = I->Kill;
00120     else {
00121       // The value is live-through, update LiveOut as well.
00122       // Defer the Domtree lookup until it is needed.
00123       assert(Seen.test(MBB->getNumber()));
00124       LiveOut[MBB] = LiveOutPair(I->Value, (MachineDomTreeNode *)nullptr);
00125     }
00126     Updater.setDest(&I->LR);
00127     Updater.add(Start, End, I->Value);
00128   }
00129   LiveIn.clear();
00130 }
00131 
00132 
00133 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg) {
00134   assert(Kill.isValid() && "Invalid SlotIndex");
00135   assert(Indexes && "Missing SlotIndexes");
00136   assert(DomTree && "Missing dominator tree");
00137 
00138   MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot());
00139   assert(KillMBB && "No MBB at Kill");
00140 
00141   // Is there a def in the same MBB we can extend?
00142   if (LR.extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill))
00143     return;
00144 
00145   // Find the single reaching def, or determine if Kill is jointly dominated by
00146   // multiple values, and we may need to create even more phi-defs to preserve
00147   // VNInfo SSA form.  Perform a search for all predecessor blocks where we
00148   // know the dominating VNInfo.
00149   if (findReachingDefs(LR, *KillMBB, Kill, PhysReg))
00150     return;
00151 
00152   // When there were multiple different values, we may need new PHIs.
00153   calculateValues();
00154 }
00155 
00156 
00157 // This function is called by a client after using the low-level API to add
00158 // live-out and live-in blocks.  The unique value optimization is not
00159 // available, SplitEditor::transferValues handles that case directly anyway.
00160 void LiveRangeCalc::calculateValues() {
00161   assert(Indexes && "Missing SlotIndexes");
00162   assert(DomTree && "Missing dominator tree");
00163   updateSSA();
00164   updateLiveIns();
00165 }
00166 
00167 
00168 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB,
00169                                      SlotIndex Kill, unsigned PhysReg) {
00170   unsigned KillMBBNum = KillMBB.getNumber();
00171 
00172   // Block numbers where LR should be live-in.
00173   SmallVector<unsigned, 16> WorkList(1, KillMBBNum);
00174 
00175   // Remember if we have seen more than one value.
00176   bool UniqueVNI = true;
00177   VNInfo *TheVNI = nullptr;
00178 
00179   // Using Seen as a visited set, perform a BFS for all reaching defs.
00180   for (unsigned i = 0; i != WorkList.size(); ++i) {
00181     MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
00182 
00183 #ifndef NDEBUG
00184     if (MBB->pred_empty()) {
00185       MBB->getParent()->verify();
00186       llvm_unreachable("Use not jointly dominated by defs.");
00187     }
00188 
00189     if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
00190         !MBB->isLiveIn(PhysReg)) {
00191       MBB->getParent()->verify();
00192       errs() << "The register needs to be live in to BB#" << MBB->getNumber()
00193              << ", but is missing from the live-in list.\n";
00194       llvm_unreachable("Invalid global physical register");
00195     }
00196 #endif
00197 
00198     for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
00199          PE = MBB->pred_end(); PI != PE; ++PI) {
00200        MachineBasicBlock *Pred = *PI;
00201 
00202        // Is this a known live-out block?
00203        if (Seen.test(Pred->getNumber())) {
00204          if (VNInfo *VNI = LiveOut[Pred].first) {
00205            if (TheVNI && TheVNI != VNI)
00206              UniqueVNI = false;
00207            TheVNI = VNI;
00208          }
00209          continue;
00210        }
00211 
00212        SlotIndex Start, End;
00213        std::tie(Start, End) = Indexes->getMBBRange(Pred);
00214 
00215        // First time we see Pred.  Try to determine the live-out value, but set
00216        // it as null if Pred is live-through with an unknown value.
00217        VNInfo *VNI = LR.extendInBlock(Start, End);
00218        setLiveOutValue(Pred, VNI);
00219        if (VNI) {
00220          if (TheVNI && TheVNI != VNI)
00221            UniqueVNI = false;
00222          TheVNI = VNI;
00223          continue;
00224        }
00225 
00226        // No, we need a live-in value for Pred as well
00227        if (Pred != &KillMBB)
00228           WorkList.push_back(Pred->getNumber());
00229        else
00230           // Loopback to KillMBB, so value is really live through.
00231          Kill = SlotIndex();
00232     }
00233   }
00234 
00235   LiveIn.clear();
00236 
00237   // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
00238   // neither require it. Skip the sorting overhead for small updates.
00239   if (WorkList.size() > 4)
00240     array_pod_sort(WorkList.begin(), WorkList.end());
00241 
00242   // If a unique reaching def was found, blit in the live ranges immediately.
00243   if (UniqueVNI) {
00244     LiveRangeUpdater Updater(&LR);
00245     for (SmallVectorImpl<unsigned>::const_iterator I = WorkList.begin(),
00246          E = WorkList.end(); I != E; ++I) {
00247        SlotIndex Start, End;
00248        std::tie(Start, End) = Indexes->getMBBRange(*I);
00249        // Trim the live range in KillMBB.
00250        if (*I == KillMBBNum && Kill.isValid())
00251          End = Kill;
00252        else
00253          LiveOut[MF->getBlockNumbered(*I)] =
00254            LiveOutPair(TheVNI, nullptr);
00255        Updater.add(Start, End, TheVNI);
00256     }
00257     return true;
00258   }
00259 
00260   // Multiple values were found, so transfer the work list to the LiveIn array
00261   // where UpdateSSA will use it as a work list.
00262   LiveIn.reserve(WorkList.size());
00263   for (SmallVectorImpl<unsigned>::const_iterator
00264        I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
00265     MachineBasicBlock *MBB = MF->getBlockNumbered(*I);
00266     addLiveInBlock(LR, DomTree->getNode(MBB));
00267     if (MBB == &KillMBB)
00268       LiveIn.back().Kill = Kill;
00269   }
00270 
00271   return false;
00272 }
00273 
00274 
00275 // This is essentially the same iterative algorithm that SSAUpdater uses,
00276 // except we already have a dominator tree, so we don't have to recompute it.
00277 void LiveRangeCalc::updateSSA() {
00278   assert(Indexes && "Missing SlotIndexes");
00279   assert(DomTree && "Missing dominator tree");
00280 
00281   // Interate until convergence.
00282   unsigned Changes;
00283   do {
00284     Changes = 0;
00285     // Propagate live-out values down the dominator tree, inserting phi-defs
00286     // when necessary.
00287     for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
00288            E = LiveIn.end(); I != E; ++I) {
00289       MachineDomTreeNode *Node = I->DomNode;
00290       // Skip block if the live-in value has already been determined.
00291       if (!Node)
00292         continue;
00293       MachineBasicBlock *MBB = Node->getBlock();
00294       MachineDomTreeNode *IDom = Node->getIDom();
00295       LiveOutPair IDomValue;
00296 
00297       // We need a live-in value to a block with no immediate dominator?
00298       // This is probably an unreachable block that has survived somehow.
00299       bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
00300 
00301       // IDom dominates all of our predecessors, but it may not be their
00302       // immediate dominator. Check if any of them have live-out values that are
00303       // properly dominated by IDom. If so, we need a phi-def here.
00304       if (!needPHI) {
00305         IDomValue = LiveOut[IDom->getBlock()];
00306 
00307         // Cache the DomTree node that defined the value.
00308         if (IDomValue.first && !IDomValue.second)
00309           LiveOut[IDom->getBlock()].second = IDomValue.second =
00310             DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
00311 
00312         for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
00313                PE = MBB->pred_end(); PI != PE; ++PI) {
00314           LiveOutPair &Value = LiveOut[*PI];
00315           if (!Value.first || Value.first == IDomValue.first)
00316             continue;
00317 
00318           // Cache the DomTree node that defined the value.
00319           if (!Value.second)
00320             Value.second =
00321               DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
00322 
00323           // This predecessor is carrying something other than IDomValue.
00324           // It could be because IDomValue hasn't propagated yet, or it could be
00325           // because MBB is in the dominance frontier of that value.
00326           if (DomTree->dominates(IDom, Value.second)) {
00327             needPHI = true;
00328             break;
00329           }
00330         }
00331       }
00332 
00333       // The value may be live-through even if Kill is set, as can happen when
00334       // we are called from extendRange. In that case LiveOutSeen is true, and
00335       // LiveOut indicates a foreign or missing value.
00336       LiveOutPair &LOP = LiveOut[MBB];
00337 
00338       // Create a phi-def if required.
00339       if (needPHI) {
00340         ++Changes;
00341         assert(Alloc && "Need VNInfo allocator to create PHI-defs");
00342         SlotIndex Start, End;
00343         std::tie(Start, End) = Indexes->getMBBRange(MBB);
00344         LiveRange &LR = I->LR;
00345         VNInfo *VNI = LR.getNextValue(Start, *Alloc);
00346         I->Value = VNI;
00347         // This block is done, we know the final value.
00348         I->DomNode = nullptr;
00349 
00350         // Add liveness since updateLiveIns now skips this node.
00351         if (I->Kill.isValid())
00352           LR.addSegment(LiveInterval::Segment(Start, I->Kill, VNI));
00353         else {
00354           LR.addSegment(LiveInterval::Segment(Start, End, VNI));
00355           LOP = LiveOutPair(VNI, Node);
00356         }
00357       } else if (IDomValue.first) {
00358         // No phi-def here. Remember incoming value.
00359         I->Value = IDomValue.first;
00360 
00361         // If the IDomValue is killed in the block, don't propagate through.
00362         if (I->Kill.isValid())
00363           continue;
00364 
00365         // Propagate IDomValue if it isn't killed:
00366         // MBB is live-out and doesn't define its own value.
00367         if (LOP.first == IDomValue.first)
00368           continue;
00369         ++Changes;
00370         LOP = IDomValue;
00371       }
00372     }
00373   } while (Changes);
00374 }