1 //===- LiveRangeCalc.cpp - Calculate live ranges -------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Implementation of the LiveRangeCalc class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/CodeGen/LiveRangeCalc.h" 14 #include "llvm/ADT/BitVector.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/ADT/SetVector.h" 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/CodeGen/LiveInterval.h" 19 #include "llvm/CodeGen/MachineBasicBlock.h" 20 #include "llvm/CodeGen/MachineDominators.h" 21 #include "llvm/CodeGen/MachineFunction.h" 22 #include "llvm/CodeGen/MachineInstr.h" 23 #include "llvm/CodeGen/MachineRegisterInfo.h" 24 #include "llvm/CodeGen/SlotIndexes.h" 25 #include "llvm/CodeGen/TargetRegisterInfo.h" 26 #include "llvm/Support/ErrorHandling.h" 27 #include "llvm/Support/raw_ostream.h" 28 #include <algorithm> 29 #include <cassert> 30 #include <iterator> 31 #include <tuple> 32 #include <utility> 33 34 using namespace llvm; 35 36 #define DEBUG_TYPE "regalloc" 37 38 // Reserve an address that indicates a value that is known to be "undef". 39 static VNInfo UndefVNI(0xbad, SlotIndex()); 40 41 void LiveRangeCalc::resetLiveOutMap() { 42 unsigned NumBlocks = MF->getNumBlockIDs(); 43 Seen.clear(); 44 Seen.resize(NumBlocks); 45 EntryInfos.clear(); 46 Map.resize(NumBlocks); 47 } 48 49 void LiveRangeCalc::reset(const MachineFunction *mf, 50 SlotIndexes *SI, 51 MachineDominatorTree *MDT, 52 VNInfo::Allocator *VNIA) { 53 MF = mf; 54 MRI = &MF->getRegInfo(); 55 Indexes = SI; 56 DomTree = MDT; 57 Alloc = VNIA; 58 resetLiveOutMap(); 59 LiveIn.clear(); 60 } 61 62 void LiveRangeCalc::updateFromLiveIns() { 63 LiveRangeUpdater Updater; 64 for (const LiveInBlock &I : LiveIn) { 65 if (!I.DomNode) 66 continue; 67 MachineBasicBlock *MBB = I.DomNode->getBlock(); 68 assert(I.Value && "No live-in value found"); 69 SlotIndex Start, End; 70 std::tie(Start, End) = Indexes->getMBBRange(MBB); 71 72 if (I.Kill.isValid()) 73 // Value is killed inside this block. 74 End = I.Kill; 75 else { 76 // The value is live-through, update LiveOut as well. 77 // Defer the Domtree lookup until it is needed. 78 assert(Seen.test(MBB->getNumber())); 79 Map[MBB] = LiveOutPair(I.Value, nullptr); 80 } 81 Updater.setDest(&I.LR); 82 Updater.add(Start, End, I.Value); 83 } 84 LiveIn.clear(); 85 } 86 87 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, 88 ArrayRef<SlotIndex> Undefs) { 89 assert(Use.isValid() && "Invalid SlotIndex"); 90 assert(Indexes && "Missing SlotIndexes"); 91 assert(DomTree && "Missing dominator tree"); 92 93 MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot()); 94 assert(UseMBB && "No MBB at Use"); 95 96 // Is there a def in the same MBB we can extend? 97 auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use); 98 if (EP.first != nullptr || EP.second) 99 return; 100 101 // Find the single reaching def, or determine if Use is jointly dominated by 102 // multiple values, and we may need to create even more phi-defs to preserve 103 // VNInfo SSA form. Perform a search for all predecessor blocks where we 104 // know the dominating VNInfo. 105 if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs)) 106 return; 107 108 // When there were multiple different values, we may need new PHIs. 109 calculateValues(); 110 } 111 112 // This function is called by a client after using the low-level API to add 113 // live-out and live-in blocks. The unique value optimization is not 114 // available, SplitEditor::transferValues handles that case directly anyway. 115 void LiveRangeCalc::calculateValues() { 116 assert(Indexes && "Missing SlotIndexes"); 117 assert(DomTree && "Missing dominator tree"); 118 updateSSA(); 119 updateFromLiveIns(); 120 } 121 122 bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs, 123 MachineBasicBlock &MBB, BitVector &DefOnEntry, 124 BitVector &UndefOnEntry) { 125 unsigned BN = MBB.getNumber(); 126 if (DefOnEntry[BN]) 127 return true; 128 if (UndefOnEntry[BN]) 129 return false; 130 131 auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool { 132 for (MachineBasicBlock *S : B.successors()) 133 DefOnEntry[S->getNumber()] = true; 134 DefOnEntry[BN] = true; 135 return true; 136 }; 137 138 SetVector<unsigned> WorkList; 139 // Checking if the entry of MBB is reached by some def: add all predecessors 140 // that are potentially defined-on-exit to the work list. 141 for (MachineBasicBlock *P : MBB.predecessors()) 142 WorkList.insert(P->getNumber()); 143 144 for (unsigned i = 0; i != WorkList.size(); ++i) { 145 // Determine if the exit from the block is reached by some def. 146 unsigned N = WorkList[i]; 147 MachineBasicBlock &B = *MF->getBlockNumbered(N); 148 if (Seen[N]) { 149 const LiveOutPair &LOB = Map[&B]; 150 if (LOB.first != nullptr && LOB.first != &UndefVNI) 151 return MarkDefined(B); 152 } 153 SlotIndex Begin, End; 154 std::tie(Begin, End) = Indexes->getMBBRange(&B); 155 // Treat End as not belonging to B. 156 // If LR has a segment S that starts at the next block, i.e. [End, ...), 157 // std::upper_bound will return the segment following S. Instead, 158 // S should be treated as the first segment that does not overlap B. 159 LiveRange::iterator UB = upper_bound(LR, End.getPrevSlot()); 160 if (UB != LR.begin()) { 161 LiveRange::Segment &Seg = *std::prev(UB); 162 if (Seg.end > Begin) { 163 // There is a segment that overlaps B. If the range is not explicitly 164 // undefined between the end of the segment and the end of the block, 165 // treat the block as defined on exit. If it is, go to the next block 166 // on the work list. 167 if (LR.isUndefIn(Undefs, Seg.end, End)) 168 continue; 169 return MarkDefined(B); 170 } 171 } 172 173 // No segment overlaps with this block. If this block is not defined on 174 // entry, or it undefines the range, do not process its predecessors. 175 if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) { 176 UndefOnEntry[N] = true; 177 continue; 178 } 179 if (DefOnEntry[N]) 180 return MarkDefined(B); 181 182 // Still don't know: add all predecessors to the work list. 183 for (MachineBasicBlock *P : B.predecessors()) 184 WorkList.insert(P->getNumber()); 185 } 186 187 UndefOnEntry[BN] = true; 188 return false; 189 } 190 191 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB, 192 SlotIndex Use, unsigned PhysReg, 193 ArrayRef<SlotIndex> Undefs) { 194 unsigned UseMBBNum = UseMBB.getNumber(); 195 196 // Block numbers where LR should be live-in. 197 SmallVector<unsigned, 16> WorkList(1, UseMBBNum); 198 199 // Remember if we have seen more than one value. 200 bool UniqueVNI = true; 201 VNInfo *TheVNI = nullptr; 202 203 bool FoundUndef = false; 204 205 // Using Seen as a visited set, perform a BFS for all reaching defs. 206 for (unsigned i = 0; i != WorkList.size(); ++i) { 207 MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]); 208 209 #ifndef NDEBUG 210 if (MBB->pred_empty()) { 211 MBB->getParent()->verify(); 212 errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo()) 213 << " does not have a corresponding definition on every path:\n"; 214 const MachineInstr *MI = Indexes->getInstructionFromIndex(Use); 215 if (MI != nullptr) 216 errs() << Use << " " << *MI; 217 report_fatal_error("Use not jointly dominated by defs."); 218 } 219 220 if (Register::isPhysicalRegister(PhysReg) && !MBB->isLiveIn(PhysReg)) { 221 MBB->getParent()->verify(); 222 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo(); 223 errs() << "The register " << printReg(PhysReg, TRI) 224 << " needs to be live in to " << printMBBReference(*MBB) 225 << ", but is missing from the live-in list.\n"; 226 report_fatal_error("Invalid global physical register"); 227 } 228 #endif 229 FoundUndef |= MBB->pred_empty(); 230 231 for (MachineBasicBlock *Pred : MBB->predecessors()) { 232 // Is this a known live-out block? 233 if (Seen.test(Pred->getNumber())) { 234 if (VNInfo *VNI = Map[Pred].first) { 235 if (TheVNI && TheVNI != VNI) 236 UniqueVNI = false; 237 TheVNI = VNI; 238 } 239 continue; 240 } 241 242 SlotIndex Start, End; 243 std::tie(Start, End) = Indexes->getMBBRange(Pred); 244 245 // First time we see Pred. Try to determine the live-out value, but set 246 // it as null if Pred is live-through with an unknown value. 247 auto EP = LR.extendInBlock(Undefs, Start, End); 248 VNInfo *VNI = EP.first; 249 FoundUndef |= EP.second; 250 setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI); 251 if (VNI) { 252 if (TheVNI && TheVNI != VNI) 253 UniqueVNI = false; 254 TheVNI = VNI; 255 } 256 if (VNI || EP.second) 257 continue; 258 259 // No, we need a live-in value for Pred as well 260 if (Pred != &UseMBB) 261 WorkList.push_back(Pred->getNumber()); 262 else 263 // Loopback to UseMBB, so value is really live through. 264 Use = SlotIndex(); 265 } 266 } 267 268 LiveIn.clear(); 269 FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI); 270 if (!Undefs.empty() && FoundUndef) 271 UniqueVNI = false; 272 273 // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but 274 // neither require it. Skip the sorting overhead for small updates. 275 if (WorkList.size() > 4) 276 array_pod_sort(WorkList.begin(), WorkList.end()); 277 278 // If a unique reaching def was found, blit in the live ranges immediately. 279 if (UniqueVNI) { 280 assert(TheVNI != nullptr && TheVNI != &UndefVNI); 281 LiveRangeUpdater Updater(&LR); 282 for (unsigned BN : WorkList) { 283 SlotIndex Start, End; 284 std::tie(Start, End) = Indexes->getMBBRange(BN); 285 // Trim the live range in UseMBB. 286 if (BN == UseMBBNum && Use.isValid()) 287 End = Use; 288 else 289 Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr); 290 Updater.add(Start, End, TheVNI); 291 } 292 return true; 293 } 294 295 // Prepare the defined/undefined bit vectors. 296 EntryInfoMap::iterator Entry; 297 bool DidInsert; 298 std::tie(Entry, DidInsert) = EntryInfos.insert( 299 std::make_pair(&LR, std::make_pair(BitVector(), BitVector()))); 300 if (DidInsert) { 301 // Initialize newly inserted entries. 302 unsigned N = MF->getNumBlockIDs(); 303 Entry->second.first.resize(N); 304 Entry->second.second.resize(N); 305 } 306 BitVector &DefOnEntry = Entry->second.first; 307 BitVector &UndefOnEntry = Entry->second.second; 308 309 // Multiple values were found, so transfer the work list to the LiveIn array 310 // where UpdateSSA will use it as a work list. 311 LiveIn.reserve(WorkList.size()); 312 for (unsigned BN : WorkList) { 313 MachineBasicBlock *MBB = MF->getBlockNumbered(BN); 314 if (!Undefs.empty() && 315 !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry)) 316 continue; 317 addLiveInBlock(LR, DomTree->getNode(MBB)); 318 if (MBB == &UseMBB) 319 LiveIn.back().Kill = Use; 320 } 321 322 return false; 323 } 324 325 // This is essentially the same iterative algorithm that SSAUpdater uses, 326 // except we already have a dominator tree, so we don't have to recompute it. 327 void LiveRangeCalc::updateSSA() { 328 assert(Indexes && "Missing SlotIndexes"); 329 assert(DomTree && "Missing dominator tree"); 330 331 // Interate until convergence. 332 bool Changed; 333 do { 334 Changed = false; 335 // Propagate live-out values down the dominator tree, inserting phi-defs 336 // when necessary. 337 for (LiveInBlock &I : LiveIn) { 338 MachineDomTreeNode *Node = I.DomNode; 339 // Skip block if the live-in value has already been determined. 340 if (!Node) 341 continue; 342 MachineBasicBlock *MBB = Node->getBlock(); 343 MachineDomTreeNode *IDom = Node->getIDom(); 344 LiveOutPair IDomValue; 345 346 // We need a live-in value to a block with no immediate dominator? 347 // This is probably an unreachable block that has survived somehow. 348 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); 349 350 // IDom dominates all of our predecessors, but it may not be their 351 // immediate dominator. Check if any of them have live-out values that are 352 // properly dominated by IDom. If so, we need a phi-def here. 353 if (!needPHI) { 354 IDomValue = Map[IDom->getBlock()]; 355 356 // Cache the DomTree node that defined the value. 357 if (IDomValue.first && IDomValue.first != &UndefVNI && 358 !IDomValue.second) { 359 Map[IDom->getBlock()].second = IDomValue.second = 360 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); 361 } 362 363 for (MachineBasicBlock *Pred : MBB->predecessors()) { 364 LiveOutPair &Value = Map[Pred]; 365 if (!Value.first || Value.first == IDomValue.first) 366 continue; 367 if (Value.first == &UndefVNI) { 368 needPHI = true; 369 break; 370 } 371 372 // Cache the DomTree node that defined the value. 373 if (!Value.second) 374 Value.second = 375 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); 376 377 // This predecessor is carrying something other than IDomValue. 378 // It could be because IDomValue hasn't propagated yet, or it could be 379 // because MBB is in the dominance frontier of that value. 380 if (DomTree->dominates(IDom, Value.second)) { 381 needPHI = true; 382 break; 383 } 384 } 385 } 386 387 // The value may be live-through even if Kill is set, as can happen when 388 // we are called from extendRange. In that case LiveOutSeen is true, and 389 // LiveOut indicates a foreign or missing value. 390 LiveOutPair &LOP = Map[MBB]; 391 392 // Create a phi-def if required. 393 if (needPHI) { 394 Changed = true; 395 assert(Alloc && "Need VNInfo allocator to create PHI-defs"); 396 SlotIndex Start, End; 397 std::tie(Start, End) = Indexes->getMBBRange(MBB); 398 LiveRange &LR = I.LR; 399 VNInfo *VNI = LR.getNextValue(Start, *Alloc); 400 I.Value = VNI; 401 // This block is done, we know the final value. 402 I.DomNode = nullptr; 403 404 // Add liveness since updateFromLiveIns now skips this node. 405 if (I.Kill.isValid()) { 406 if (VNI) 407 LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI)); 408 } else { 409 if (VNI) 410 LR.addSegment(LiveInterval::Segment(Start, End, VNI)); 411 LOP = LiveOutPair(VNI, Node); 412 } 413 } else if (IDomValue.first && IDomValue.first != &UndefVNI) { 414 // No phi-def here. Remember incoming value. 415 I.Value = IDomValue.first; 416 417 // If the IDomValue is killed in the block, don't propagate through. 418 if (I.Kill.isValid()) 419 continue; 420 421 // Propagate IDomValue if it isn't killed: 422 // MBB is live-out and doesn't define its own value. 423 if (LOP.first == IDomValue.first) 424 continue; 425 Changed = true; 426 LOP = IDomValue; 427 } 428 } 429 } while (Changed); 430 } 431 432 bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB, 433 ArrayRef<SlotIndex> Defs, 434 const SlotIndexes &Indexes) { 435 const MachineFunction &MF = *MBB->getParent(); 436 BitVector DefBlocks(MF.getNumBlockIDs()); 437 for (SlotIndex I : Defs) 438 DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber()); 439 440 SetVector<unsigned> PredQueue; 441 PredQueue.insert(MBB->getNumber()); 442 for (unsigned i = 0; i != PredQueue.size(); ++i) { 443 unsigned BN = PredQueue[i]; 444 if (DefBlocks[BN]) 445 return true; 446 const MachineBasicBlock *B = MF.getBlockNumbered(BN); 447 for (const MachineBasicBlock *P : B->predecessors()) 448 PredQueue.insert(P->getNumber()); 449 } 450 return false; 451 } 452