lib/CodeGen/LiveRangeCalc.cpp

   1 //===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===//
   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 // Implementation of the LiveRangeCalc class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "regalloc"
  15 #include "LiveRangeCalc.h"
  16 #include "llvm/CodeGen/MachineDominators.h"
  17 #include "llvm/CodeGen/MachineRegisterInfo.h"
  18
  19 using namespace llvm;
  20
  21 void LiveRangeCalc::reset(const MachineFunction *mf,
  22                           SlotIndexes *SI,
  23                           MachineDominatorTree *MDT,
  24                           VNInfo::Allocator *VNIA) {
  25   MF = mf;
  26   MRI = &MF->getRegInfo();
  27   Indexes = SI;
  28   DomTree = MDT;
  29   Alloc = VNIA;
  30
  31   unsigned N = MF->getNumBlockIDs();
  32   Seen.clear();
  33   Seen.resize(N);
  34   LiveOut.resize(N);
  35   LiveIn.clear();
  36 }
  37
  38
  39 void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
  40   assert(MRI && Indexes && "call reset() first");
  41
  42   // Visit all def operands. If the same instruction has multiple defs of Reg,
  43   // LR.createDeadDef() will deduplicate.
  44   for (MachineOperand &MO : MRI->def_operands(Reg)) {
  45     const MachineInstr *MI = MO.getParent();
  46     // Find the corresponding slot index.
  47     SlotIndex Idx;
  48     if (MI->isPHI())
  49       // PHI defs begin at the basic block start index.
  50       Idx = Indexes->getMBBStartIdx(MI->getParent());
  51     else
  52       // Instructions are either normal 'r', or early clobber 'e'.
  53       Idx = Indexes->getInstructionIndex(MI)
  54         .getRegSlot(MO.isEarlyClobber());
  55
  56     // Create the def in LR. This may find an existing def.
  57     LR.createDeadDef(Idx, *Alloc);
  58   }
  59 }
  60
  61
  62 void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg) {
  63   assert(MRI && Indexes && "call reset() first");
  64
  65   // Visit all operands that read Reg. This may include partial defs.
  66   for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
  67     // Clear all kill flags. They will be reinserted after register allocation
  68     // by LiveIntervalAnalysis::addKillFlags().
  69     if (MO.isUse())
  70       MO.setIsKill(false);
  71     if (!MO.readsReg())
  72       continue;
  73     // MI is reading Reg. We may have visited MI before if it happens to be
  74     // reading Reg multiple times. That is OK, extend() is idempotent.
  75     const MachineInstr *MI = MO.getParent();
  76     unsigned OpNo = (&MO - &MI->getOperand(0));
  77
  78     // Find the SlotIndex being read.
  79     SlotIndex Idx;
  80     if (MI->isPHI()) {
  81       assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
  82       // PHI operands are paired: (Reg, PredMBB).
  83       // Extend the live range to be live-out from PredMBB.
  84       Idx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
  85     } else {
  86       // This is a normal instruction.
  87       Idx = Indexes->getInstructionIndex(MI).getRegSlot();
  88       // Check for early-clobber redefs.
  89       unsigned DefIdx;
  90       if (MO.isDef()) {
  91         if (MO.isEarlyClobber())
  92           Idx = Idx.getRegSlot(true);
  93       } else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
  94         // FIXME: This would be a lot easier if tied early-clobber uses also
  95         // had an early-clobber flag.
  96         if (MI->getOperand(DefIdx).isEarlyClobber())
  97           Idx = Idx.getRegSlot(true);
  98       }
  99     }
 100     extend(LR, Idx, Reg);
 101   }
 102 }
 103
 104
 105 // Transfer information from the LiveIn vector to the live ranges.
 106 void LiveRangeCalc::updateLiveIns() {
 107   LiveRangeUpdater Updater;
 108   for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
 109          E = LiveIn.end(); I != E; ++I) {
 110     if (!I->DomNode)
 111       continue;
 112     MachineBasicBlock *MBB = I->DomNode->getBlock();
 113     assert(I->Value && "No live-in value found");
 114     SlotIndex Start, End;
 115     std::tie(Start, End) = Indexes->getMBBRange(MBB);
 116
 117     if (I->Kill.isValid())
 118       // Value is killed inside this block.
 119       End = I->Kill;
 120     else {
 121       // The value is live-through, update LiveOut as well.
 122       // Defer the Domtree lookup until it is needed.
 123       assert(Seen.test(MBB->getNumber()));
 124       LiveOut[MBB] = LiveOutPair(I->Value, (MachineDomTreeNode *)0);
 125     }
 126     Updater.setDest(&I->LR);
 127     Updater.add(Start, End, I->Value);
 128   }
 129   LiveIn.clear();
 130 }
 131
 132
 133 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg) {
 134   assert(Kill.isValid() && "Invalid SlotIndex");
 135   assert(Indexes && "Missing SlotIndexes");
 136   assert(DomTree && "Missing dominator tree");
 137
 138   MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot());
 139   assert(KillMBB && "No MBB at Kill");
 140
 141   // Is there a def in the same MBB we can extend?
 142   if (LR.extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill))
 143     return;
 144
 145   // Find the single reaching def, or determine if Kill is jointly dominated by
 146   // multiple values, and we may need to create even more phi-defs to preserve
 147   // VNInfo SSA form.  Perform a search for all predecessor blocks where we
 148   // know the dominating VNInfo.
 149   if (findReachingDefs(LR, *KillMBB, Kill, PhysReg))
 150     return;
 151
 152   // When there were multiple different values, we may need new PHIs.
 153   calculateValues();
 154 }
 155
 156
 157 // This function is called by a client after using the low-level API to add
 158 // live-out and live-in blocks.  The unique value optimization is not
 159 // available, SplitEditor::transferValues handles that case directly anyway.
 160 void LiveRangeCalc::calculateValues() {
 161   assert(Indexes && "Missing SlotIndexes");
 162   assert(DomTree && "Missing dominator tree");
 163   updateSSA();
 164   updateLiveIns();
 165 }
 166
 167
 168 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB,
 169                                      SlotIndex Kill, unsigned PhysReg) {
 170   unsigned KillMBBNum = KillMBB.getNumber();
 171
 172   // Block numbers where LR should be live-in.
 173   SmallVector<unsigned, 16> WorkList(1, KillMBBNum);
 174
 175   // Remember if we have seen more than one value.
 176   bool UniqueVNI = true;
 177   VNInfo *TheVNI = 0;
 178
 179   // Using Seen as a visited set, perform a BFS for all reaching defs.
 180   for (unsigned i = 0; i != WorkList.size(); ++i) {
 181     MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
 182
 183 #ifndef NDEBUG
 184     if (MBB->pred_empty()) {
 185       MBB->getParent()->verify();
 186       llvm_unreachable("Use not jointly dominated by defs.");
 187     }
 188
 189     if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
 190         !MBB->isLiveIn(PhysReg)) {
 191       MBB->getParent()->verify();
 192       errs() << "The register needs to be live in to BB#" << MBB->getNumber()
 193              << ", but is missing from the live-in list.\n";
 194       llvm_unreachable("Invalid global physical register");
 195     }
 196 #endif
 197
 198     for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 199          PE = MBB->pred_end(); PI != PE; ++PI) {
 200        MachineBasicBlock *Pred = *PI;
 201
 202        // Is this a known live-out block?
 203        if (Seen.test(Pred->getNumber())) {
 204          if (VNInfo *VNI = LiveOut[Pred].first) {
 205            if (TheVNI && TheVNI != VNI)
 206              UniqueVNI = false;
 207            TheVNI = VNI;
 208          }
 209          continue;
 210        }
 211
 212        SlotIndex Start, End;
 213        std::tie(Start, End) = Indexes->getMBBRange(Pred);
 214
 215        // First time we see Pred.  Try to determine the live-out value, but set
 216        // it as null if Pred is live-through with an unknown value.
 217        VNInfo *VNI = LR.extendInBlock(Start, End);
 218        setLiveOutValue(Pred, VNI);
 219        if (VNI) {
 220          if (TheVNI && TheVNI != VNI)
 221            UniqueVNI = false;
 222          TheVNI = VNI;
 223          continue;
 224        }
 225
 226        // No, we need a live-in value for Pred as well
 227        if (Pred != &KillMBB)
 228           WorkList.push_back(Pred->getNumber());
 229        else
 230           // Loopback to KillMBB, so value is really live through.
 231          Kill = SlotIndex();
 232     }
 233   }
 234
 235   LiveIn.clear();
 236
 237   // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
 238   // neither require it. Skip the sorting overhead for small updates.
 239   if (WorkList.size() > 4)
 240     array_pod_sort(WorkList.begin(), WorkList.end());
 241
 242   // If a unique reaching def was found, blit in the live ranges immediately.
 243   if (UniqueVNI) {
 244     LiveRangeUpdater Updater(&LR);
 245     for (SmallVectorImpl<unsigned>::const_iterator I = WorkList.begin(),
 246          E = WorkList.end(); I != E; ++I) {
 247        SlotIndex Start, End;
 248        std::tie(Start, End) = Indexes->getMBBRange(*I);
 249        // Trim the live range in KillMBB.
 250        if (*I == KillMBBNum && Kill.isValid())
 251          End = Kill;
 252        else
 253          LiveOut[MF->getBlockNumbered(*I)] =
 254            LiveOutPair(TheVNI, (MachineDomTreeNode *)0);
 255        Updater.add(Start, End, TheVNI);
 256     }
 257     return true;
 258   }
 259
 260   // Multiple values were found, so transfer the work list to the LiveIn array
 261   // where UpdateSSA will use it as a work list.
 262   LiveIn.reserve(WorkList.size());
 263   for (SmallVectorImpl<unsigned>::const_iterator
 264        I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
 265     MachineBasicBlock *MBB = MF->getBlockNumbered(*I);
 266     addLiveInBlock(LR, DomTree->getNode(MBB));
 267     if (MBB == &KillMBB)
 268       LiveIn.back().Kill = Kill;
 269   }
 270
 271   return false;
 272 }
 273
 274
 275 // This is essentially the same iterative algorithm that SSAUpdater uses,
 276 // except we already have a dominator tree, so we don't have to recompute it.
 277 void LiveRangeCalc::updateSSA() {
 278   assert(Indexes && "Missing SlotIndexes");
 279   assert(DomTree && "Missing dominator tree");
 280
 281   // Interate until convergence.
 282   unsigned Changes;
 283   do {
 284     Changes = 0;
 285     // Propagate live-out values down the dominator tree, inserting phi-defs
 286     // when necessary.
 287     for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
 288            E = LiveIn.end(); I != E; ++I) {
 289       MachineDomTreeNode *Node = I->DomNode;
 290       // Skip block if the live-in value has already been determined.
 291       if (!Node)
 292         continue;
 293       MachineBasicBlock *MBB = Node->getBlock();
 294       MachineDomTreeNode *IDom = Node->getIDom();
 295       LiveOutPair IDomValue;
 296
 297       // We need a live-in value to a block with no immediate dominator?
 298       // This is probably an unreachable block that has survived somehow.
 299       bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
 300
 301       // IDom dominates all of our predecessors, but it may not be their
 302       // immediate dominator. Check if any of them have live-out values that are
 303       // properly dominated by IDom. If so, we need a phi-def here.
 304       if (!needPHI) {
 305         IDomValue = LiveOut[IDom->getBlock()];
 306
 307         // Cache the DomTree node that defined the value.
 308         if (IDomValue.first && !IDomValue.second)
 309           LiveOut[IDom->getBlock()].second = IDomValue.second =
 310             DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
 311
 312         for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 313                PE = MBB->pred_end(); PI != PE; ++PI) {
 314           LiveOutPair &Value = LiveOut[*PI];
 315           if (!Value.first || Value.first == IDomValue.first)
 316             continue;
 317
 318           // Cache the DomTree node that defined the value.
 319           if (!Value.second)
 320             Value.second =
 321               DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
 322
 323           // This predecessor is carrying something other than IDomValue.
 324           // It could be because IDomValue hasn't propagated yet, or it could be
 325           // because MBB is in the dominance frontier of that value.
 326           if (DomTree->dominates(IDom, Value.second)) {
 327             needPHI = true;
 328             break;
 329           }
 330         }
 331       }
 332
 333       // The value may be live-through even if Kill is set, as can happen when
 334       // we are called from extendRange. In that case LiveOutSeen is true, and
 335       // LiveOut indicates a foreign or missing value.
 336       LiveOutPair &LOP = LiveOut[MBB];
 337
 338       // Create a phi-def if required.
 339       if (needPHI) {
 340         ++Changes;
 341         assert(Alloc && "Need VNInfo allocator to create PHI-defs");
 342         SlotIndex Start, End;
 343         std::tie(Start, End) = Indexes->getMBBRange(MBB);
 344         LiveRange &LR = I->LR;
 345         VNInfo *VNI = LR.getNextValue(Start, *Alloc);
 346         I->Value = VNI;
 347         // This block is done, we know the final value.
 348         I->DomNode = 0;
 349
 350         // Add liveness since updateLiveIns now skips this node.
 351         if (I->Kill.isValid())
 352           LR.addSegment(LiveInterval::Segment(Start, I->Kill, VNI));
 353         else {
 354           LR.addSegment(LiveInterval::Segment(Start, End, VNI));
 355           LOP = LiveOutPair(VNI, Node);
 356         }
 357       } else if (IDomValue.first) {
 358         // No phi-def here. Remember incoming value.
 359         I->Value = IDomValue.first;
 360
 361         // If the IDomValue is killed in the block, don't propagate through.
 362         if (I->Kill.isValid())
 363           continue;
 364
 365         // Propagate IDomValue if it isn't killed:
 366         // MBB is live-out and doesn't define its own value.
 367         if (LOP.first == IDomValue.first)
 368           continue;
 369         ++Changes;
 370         LOP = IDomValue;
 371       }
 372     }
 373   } while (Changes);
 374 }