1226584Sdim//===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===// 2226584Sdim// 3226584Sdim// The LLVM Compiler Infrastructure 4226584Sdim// 5226584Sdim// This file is distributed under the University of Illinois Open Source 6226584Sdim// License. See LICENSE.TXT for details. 7226584Sdim// 8226584Sdim//===----------------------------------------------------------------------===// 9226584Sdim// 10226584Sdim// Implementation of the LiveRangeCalc class. 11226584Sdim// 12226584Sdim//===----------------------------------------------------------------------===// 13226584Sdim 14226584Sdim#define DEBUG_TYPE "regalloc" 15226584Sdim#include "LiveRangeCalc.h" 16226584Sdim#include "llvm/CodeGen/MachineDominators.h" 17239462Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 18226584Sdim 19226584Sdimusing namespace llvm; 20226584Sdim 21249423Sdimvoid LiveRangeCalc::reset(const MachineFunction *mf, 22239462Sdim SlotIndexes *SI, 23239462Sdim MachineDominatorTree *MDT, 24239462Sdim VNInfo::Allocator *VNIA) { 25249423Sdim MF = mf; 26239462Sdim MRI = &MF->getRegInfo(); 27239462Sdim Indexes = SI; 28239462Sdim DomTree = MDT; 29239462Sdim Alloc = VNIA; 30239462Sdim 31226584Sdim unsigned N = MF->getNumBlockIDs(); 32226584Sdim Seen.clear(); 33226584Sdim Seen.resize(N); 34226584Sdim LiveOut.resize(N); 35226584Sdim LiveIn.clear(); 36226584Sdim} 37226584Sdim 38226584Sdim 39263508Sdimvoid LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) { 40239462Sdim assert(MRI && Indexes && "call reset() first"); 41239462Sdim 42239462Sdim // Visit all def operands. If the same instruction has multiple defs of Reg, 43263508Sdim // LR.createDeadDef() will deduplicate. 44239462Sdim for (MachineRegisterInfo::def_iterator 45239462Sdim I = MRI->def_begin(Reg), E = MRI->def_end(); I != E; ++I) { 46239462Sdim const MachineInstr *MI = &*I; 47239462Sdim // Find the corresponding slot index. 48239462Sdim SlotIndex Idx; 49239462Sdim if (MI->isPHI()) 50239462Sdim // PHI defs begin at the basic block start index. 51239462Sdim Idx = Indexes->getMBBStartIdx(MI->getParent()); 52239462Sdim else 53239462Sdim // Instructions are either normal 'r', or early clobber 'e'. 54239462Sdim Idx = Indexes->getInstructionIndex(MI) 55239462Sdim .getRegSlot(I.getOperand().isEarlyClobber()); 56239462Sdim 57263508Sdim // Create the def in LR. This may find an existing def. 58263508Sdim LR.createDeadDef(Idx, *Alloc); 59239462Sdim } 60239462Sdim} 61239462Sdim 62239462Sdim 63263508Sdimvoid LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg) { 64239462Sdim assert(MRI && Indexes && "call reset() first"); 65239462Sdim 66239462Sdim // Visit all operands that read Reg. This may include partial defs. 67239462Sdim for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg), 68239462Sdim E = MRI->reg_nodbg_end(); I != E; ++I) { 69243830Sdim MachineOperand &MO = I.getOperand(); 70243830Sdim // Clear all kill flags. They will be reinserted after register allocation 71243830Sdim // by LiveIntervalAnalysis::addKillFlags(). 72243830Sdim if (MO.isUse()) 73243830Sdim MO.setIsKill(false); 74239462Sdim if (!MO.readsReg()) 75239462Sdim continue; 76239462Sdim // MI is reading Reg. We may have visited MI before if it happens to be 77239462Sdim // reading Reg multiple times. That is OK, extend() is idempotent. 78239462Sdim const MachineInstr *MI = &*I; 79239462Sdim 80239462Sdim // Find the SlotIndex being read. 81239462Sdim SlotIndex Idx; 82239462Sdim if (MI->isPHI()) { 83239462Sdim assert(!MO.isDef() && "Cannot handle PHI def of partial register."); 84239462Sdim // PHI operands are paired: (Reg, PredMBB). 85239462Sdim // Extend the live range to be live-out from PredMBB. 86239462Sdim Idx = Indexes->getMBBEndIdx(MI->getOperand(I.getOperandNo()+1).getMBB()); 87239462Sdim } else { 88239462Sdim // This is a normal instruction. 89239462Sdim Idx = Indexes->getInstructionIndex(MI).getRegSlot(); 90239462Sdim // Check for early-clobber redefs. 91239462Sdim unsigned DefIdx; 92239462Sdim if (MO.isDef()) { 93239462Sdim if (MO.isEarlyClobber()) 94239462Sdim Idx = Idx.getRegSlot(true); 95239462Sdim } else if (MI->isRegTiedToDefOperand(I.getOperandNo(), &DefIdx)) { 96239462Sdim // FIXME: This would be a lot easier if tied early-clobber uses also 97239462Sdim // had an early-clobber flag. 98239462Sdim if (MI->getOperand(DefIdx).isEarlyClobber()) 99239462Sdim Idx = Idx.getRegSlot(true); 100239462Sdim } 101239462Sdim } 102263508Sdim extend(LR, Idx, Reg); 103239462Sdim } 104239462Sdim} 105239462Sdim 106239462Sdim 107226584Sdim// Transfer information from the LiveIn vector to the live ranges. 108249423Sdimvoid LiveRangeCalc::updateLiveIns() { 109249423Sdim LiveRangeUpdater Updater; 110226584Sdim for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 111226584Sdim E = LiveIn.end(); I != E; ++I) { 112226584Sdim if (!I->DomNode) 113226584Sdim continue; 114226584Sdim MachineBasicBlock *MBB = I->DomNode->getBlock(); 115249423Sdim assert(I->Value && "No live-in value found"); 116226584Sdim SlotIndex Start, End; 117226584Sdim tie(Start, End) = Indexes->getMBBRange(MBB); 118226584Sdim 119226584Sdim if (I->Kill.isValid()) 120249423Sdim // Value is killed inside this block. 121249423Sdim End = I->Kill; 122226584Sdim else { 123249423Sdim // The value is live-through, update LiveOut as well. 124249423Sdim // Defer the Domtree lookup until it is needed. 125226584Sdim assert(Seen.test(MBB->getNumber())); 126249423Sdim LiveOut[MBB] = LiveOutPair(I->Value, (MachineDomTreeNode *)0); 127226584Sdim } 128263508Sdim Updater.setDest(&I->LR); 129249423Sdim Updater.add(Start, End, I->Value); 130226584Sdim } 131226584Sdim LiveIn.clear(); 132226584Sdim} 133226584Sdim 134226584Sdim 135263508Sdimvoid LiveRangeCalc::extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg) { 136226584Sdim assert(Kill.isValid() && "Invalid SlotIndex"); 137226584Sdim assert(Indexes && "Missing SlotIndexes"); 138226584Sdim assert(DomTree && "Missing dominator tree"); 139226584Sdim 140226584Sdim MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot()); 141234353Sdim assert(KillMBB && "No MBB at Kill"); 142226584Sdim 143226584Sdim // Is there a def in the same MBB we can extend? 144263508Sdim if (LR.extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill)) 145226584Sdim return; 146226584Sdim 147226584Sdim // Find the single reaching def, or determine if Kill is jointly dominated by 148226584Sdim // multiple values, and we may need to create even more phi-defs to preserve 149226584Sdim // VNInfo SSA form. Perform a search for all predecessor blocks where we 150226584Sdim // know the dominating VNInfo. 151263508Sdim if (findReachingDefs(LR, *KillMBB, Kill, PhysReg)) 152249423Sdim return; 153226584Sdim 154226584Sdim // When there were multiple different values, we may need new PHIs. 155249423Sdim calculateValues(); 156226584Sdim} 157226584Sdim 158226584Sdim 159226584Sdim// This function is called by a client after using the low-level API to add 160226584Sdim// live-out and live-in blocks. The unique value optimization is not 161226584Sdim// available, SplitEditor::transferValues handles that case directly anyway. 162239462Sdimvoid LiveRangeCalc::calculateValues() { 163226584Sdim assert(Indexes && "Missing SlotIndexes"); 164226584Sdim assert(DomTree && "Missing dominator tree"); 165239462Sdim updateSSA(); 166249423Sdim updateLiveIns(); 167226584Sdim} 168226584Sdim 169226584Sdim 170263508Sdimbool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB, 171263508Sdim SlotIndex Kill, unsigned PhysReg) { 172263508Sdim unsigned KillMBBNum = KillMBB.getNumber(); 173226584Sdim 174263508Sdim // Block numbers where LR should be live-in. 175249423Sdim SmallVector<unsigned, 16> WorkList(1, KillMBBNum); 176249423Sdim 177226584Sdim // Remember if we have seen more than one value. 178226584Sdim bool UniqueVNI = true; 179226584Sdim VNInfo *TheVNI = 0; 180226584Sdim 181226584Sdim // Using Seen as a visited set, perform a BFS for all reaching defs. 182226584Sdim for (unsigned i = 0; i != WorkList.size(); ++i) { 183249423Sdim MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]); 184239462Sdim 185239462Sdim#ifndef NDEBUG 186239462Sdim if (MBB->pred_empty()) { 187239462Sdim MBB->getParent()->verify(); 188239462Sdim llvm_unreachable("Use not jointly dominated by defs."); 189239462Sdim } 190239462Sdim 191239462Sdim if (TargetRegisterInfo::isPhysicalRegister(PhysReg) && 192239462Sdim !MBB->isLiveIn(PhysReg)) { 193239462Sdim MBB->getParent()->verify(); 194239462Sdim errs() << "The register needs to be live in to BB#" << MBB->getNumber() 195239462Sdim << ", but is missing from the live-in list.\n"; 196239462Sdim llvm_unreachable("Invalid global physical register"); 197239462Sdim } 198239462Sdim#endif 199239462Sdim 200226584Sdim for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 201263508Sdim PE = MBB->pred_end(); PI != PE; ++PI) { 202226584Sdim MachineBasicBlock *Pred = *PI; 203226584Sdim 204226584Sdim // Is this a known live-out block? 205226584Sdim if (Seen.test(Pred->getNumber())) { 206226584Sdim if (VNInfo *VNI = LiveOut[Pred].first) { 207226584Sdim if (TheVNI && TheVNI != VNI) 208226584Sdim UniqueVNI = false; 209226584Sdim TheVNI = VNI; 210226584Sdim } 211226584Sdim continue; 212226584Sdim } 213226584Sdim 214226584Sdim SlotIndex Start, End; 215226584Sdim tie(Start, End) = Indexes->getMBBRange(Pred); 216226584Sdim 217226584Sdim // First time we see Pred. Try to determine the live-out value, but set 218226584Sdim // it as null if Pred is live-through with an unknown value. 219263508Sdim VNInfo *VNI = LR.extendInBlock(Start, End); 220226584Sdim setLiveOutValue(Pred, VNI); 221226584Sdim if (VNI) { 222226584Sdim if (TheVNI && TheVNI != VNI) 223226584Sdim UniqueVNI = false; 224226584Sdim TheVNI = VNI; 225226584Sdim continue; 226226584Sdim } 227226584Sdim 228226584Sdim // No, we need a live-in value for Pred as well 229263508Sdim if (Pred != &KillMBB) 230249423Sdim WorkList.push_back(Pred->getNumber()); 231226584Sdim else 232226584Sdim // Loopback to KillMBB, so value is really live through. 233226584Sdim Kill = SlotIndex(); 234226584Sdim } 235226584Sdim } 236226584Sdim 237226584Sdim LiveIn.clear(); 238249423Sdim 239249423Sdim // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but 240249423Sdim // neither require it. Skip the sorting overhead for small updates. 241249423Sdim if (WorkList.size() > 4) 242249423Sdim array_pod_sort(WorkList.begin(), WorkList.end()); 243249423Sdim 244249423Sdim // If a unique reaching def was found, blit in the live ranges immediately. 245249423Sdim if (UniqueVNI) { 246263508Sdim LiveRangeUpdater Updater(&LR); 247263508Sdim for (SmallVectorImpl<unsigned>::const_iterator I = WorkList.begin(), 248263508Sdim E = WorkList.end(); I != E; ++I) { 249249423Sdim SlotIndex Start, End; 250249423Sdim tie(Start, End) = Indexes->getMBBRange(*I); 251249423Sdim // Trim the live range in KillMBB. 252249423Sdim if (*I == KillMBBNum && Kill.isValid()) 253249423Sdim End = Kill; 254249423Sdim else 255249423Sdim LiveOut[MF->getBlockNumbered(*I)] = 256249423Sdim LiveOutPair(TheVNI, (MachineDomTreeNode *)0); 257249423Sdim Updater.add(Start, End, TheVNI); 258249423Sdim } 259249423Sdim return true; 260249423Sdim } 261249423Sdim 262249423Sdim // Multiple values were found, so transfer the work list to the LiveIn array 263249423Sdim // where UpdateSSA will use it as a work list. 264226584Sdim LiveIn.reserve(WorkList.size()); 265249423Sdim for (SmallVectorImpl<unsigned>::const_iterator 266249423Sdim I = WorkList.begin(), E = WorkList.end(); I != E; ++I) { 267249423Sdim MachineBasicBlock *MBB = MF->getBlockNumbered(*I); 268263508Sdim addLiveInBlock(LR, DomTree->getNode(MBB)); 269263508Sdim if (MBB == &KillMBB) 270249423Sdim LiveIn.back().Kill = Kill; 271249423Sdim } 272226584Sdim 273249423Sdim return false; 274226584Sdim} 275226584Sdim 276226584Sdim 277226584Sdim// This is essentially the same iterative algorithm that SSAUpdater uses, 278226584Sdim// except we already have a dominator tree, so we don't have to recompute it. 279239462Sdimvoid LiveRangeCalc::updateSSA() { 280226584Sdim assert(Indexes && "Missing SlotIndexes"); 281226584Sdim assert(DomTree && "Missing dominator tree"); 282226584Sdim 283226584Sdim // Interate until convergence. 284226584Sdim unsigned Changes; 285226584Sdim do { 286226584Sdim Changes = 0; 287226584Sdim // Propagate live-out values down the dominator tree, inserting phi-defs 288226584Sdim // when necessary. 289226584Sdim for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(), 290226584Sdim E = LiveIn.end(); I != E; ++I) { 291226584Sdim MachineDomTreeNode *Node = I->DomNode; 292226584Sdim // Skip block if the live-in value has already been determined. 293226584Sdim if (!Node) 294226584Sdim continue; 295226584Sdim MachineBasicBlock *MBB = Node->getBlock(); 296226584Sdim MachineDomTreeNode *IDom = Node->getIDom(); 297226584Sdim LiveOutPair IDomValue; 298226584Sdim 299226584Sdim // We need a live-in value to a block with no immediate dominator? 300226584Sdim // This is probably an unreachable block that has survived somehow. 301226584Sdim bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); 302226584Sdim 303226584Sdim // IDom dominates all of our predecessors, but it may not be their 304226584Sdim // immediate dominator. Check if any of them have live-out values that are 305226584Sdim // properly dominated by IDom. If so, we need a phi-def here. 306226584Sdim if (!needPHI) { 307226584Sdim IDomValue = LiveOut[IDom->getBlock()]; 308226584Sdim 309226584Sdim // Cache the DomTree node that defined the value. 310226584Sdim if (IDomValue.first && !IDomValue.second) 311226584Sdim LiveOut[IDom->getBlock()].second = IDomValue.second = 312226584Sdim DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); 313226584Sdim 314226584Sdim for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 315226584Sdim PE = MBB->pred_end(); PI != PE; ++PI) { 316226584Sdim LiveOutPair &Value = LiveOut[*PI]; 317226584Sdim if (!Value.first || Value.first == IDomValue.first) 318226584Sdim continue; 319226584Sdim 320226584Sdim // Cache the DomTree node that defined the value. 321226584Sdim if (!Value.second) 322226584Sdim Value.second = 323226584Sdim DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); 324226584Sdim 325226584Sdim // This predecessor is carrying something other than IDomValue. 326226584Sdim // It could be because IDomValue hasn't propagated yet, or it could be 327226584Sdim // because MBB is in the dominance frontier of that value. 328226584Sdim if (DomTree->dominates(IDom, Value.second)) { 329226584Sdim needPHI = true; 330226584Sdim break; 331226584Sdim } 332226584Sdim } 333226584Sdim } 334226584Sdim 335226584Sdim // The value may be live-through even if Kill is set, as can happen when 336226584Sdim // we are called from extendRange. In that case LiveOutSeen is true, and 337226584Sdim // LiveOut indicates a foreign or missing value. 338226584Sdim LiveOutPair &LOP = LiveOut[MBB]; 339226584Sdim 340226584Sdim // Create a phi-def if required. 341226584Sdim if (needPHI) { 342226584Sdim ++Changes; 343226584Sdim assert(Alloc && "Need VNInfo allocator to create PHI-defs"); 344226584Sdim SlotIndex Start, End; 345226584Sdim tie(Start, End) = Indexes->getMBBRange(MBB); 346263508Sdim LiveRange &LR = I->LR; 347263508Sdim VNInfo *VNI = LR.getNextValue(Start, *Alloc); 348226584Sdim I->Value = VNI; 349226584Sdim // This block is done, we know the final value. 350226584Sdim I->DomNode = 0; 351226584Sdim 352226584Sdim // Add liveness since updateLiveIns now skips this node. 353226584Sdim if (I->Kill.isValid()) 354263508Sdim LR.addSegment(LiveInterval::Segment(Start, I->Kill, VNI)); 355226584Sdim else { 356263508Sdim LR.addSegment(LiveInterval::Segment(Start, End, VNI)); 357226584Sdim LOP = LiveOutPair(VNI, Node); 358226584Sdim } 359226584Sdim } else if (IDomValue.first) { 360226584Sdim // No phi-def here. Remember incoming value. 361226584Sdim I->Value = IDomValue.first; 362226584Sdim 363226584Sdim // If the IDomValue is killed in the block, don't propagate through. 364226584Sdim if (I->Kill.isValid()) 365226584Sdim continue; 366226584Sdim 367226584Sdim // Propagate IDomValue if it isn't killed: 368226584Sdim // MBB is live-out and doesn't define its own value. 369226584Sdim if (LOP.first == IDomValue.first) 370226584Sdim continue; 371226584Sdim ++Changes; 372226584Sdim LOP = IDomValue; 373226584Sdim } 374226584Sdim } 375226584Sdim } while (Changes); 376226584Sdim} 377