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)) { 221 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo(); 222 bool IsLiveIn = MBB->isLiveIn(PhysReg); 223 for (MCRegAliasIterator Alias(PhysReg, TRI, false); !IsLiveIn && Alias.isValid(); ++Alias) 224 IsLiveIn = MBB->isLiveIn(*Alias); 225 if (!IsLiveIn) { 226 MBB->getParent()->verify(); 227 errs() << "The register " << printReg(PhysReg, TRI) 228 << " needs to be live in to " << printMBBReference(*MBB) 229 << ", but is missing from the live-in list.\n"; 230 report_fatal_error("Invalid global physical register"); 231 } 232 } 233 #endif 234 FoundUndef |= MBB->pred_empty(); 235 236 for (MachineBasicBlock *Pred : MBB->predecessors()) { 237 // Is this a known live-out block? 238 if (Seen.test(Pred->getNumber())) { 239 if (VNInfo *VNI = Map[Pred].first) { 240 if (TheVNI && TheVNI != VNI) 241 UniqueVNI = false; 242 TheVNI = VNI; 243 } 244 continue; 245 } 246 247 SlotIndex Start, End; 248 std::tie(Start, End) = Indexes->getMBBRange(Pred); 249 250 // First time we see Pred. Try to determine the live-out value, but set 251 // it as null if Pred is live-through with an unknown value. 252 auto EP = LR.extendInBlock(Undefs, Start, End); 253 VNInfo *VNI = EP.first; 254 FoundUndef |= EP.second; 255 setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI); 256 if (VNI) { 257 if (TheVNI && TheVNI != VNI) 258 UniqueVNI = false; 259 TheVNI = VNI; 260 } 261 if (VNI || EP.second) 262 continue; 263 264 // No, we need a live-in value for Pred as well 265 if (Pred != &UseMBB) 266 WorkList.push_back(Pred->getNumber()); 267 else 268 // Loopback to UseMBB, so value is really live through. 269 Use = SlotIndex(); 270 } 271 } 272 273 LiveIn.clear(); 274 FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI); 275 if (!Undefs.empty() && FoundUndef) 276 UniqueVNI = false; 277 278 // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but 279 // neither require it. Skip the sorting overhead for small updates. 280 if (WorkList.size() > 4) 281 array_pod_sort(WorkList.begin(), WorkList.end()); 282 283 // If a unique reaching def was found, blit in the live ranges immediately. 284 if (UniqueVNI) { 285 assert(TheVNI != nullptr && TheVNI != &UndefVNI); 286 LiveRangeUpdater Updater(&LR); 287 for (unsigned BN : WorkList) { 288 SlotIndex Start, End; 289 std::tie(Start, End) = Indexes->getMBBRange(BN); 290 // Trim the live range in UseMBB. 291 if (BN == UseMBBNum && Use.isValid()) 292 End = Use; 293 else 294 Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr); 295 Updater.add(Start, End, TheVNI); 296 } 297 return true; 298 } 299 300 // Prepare the defined/undefined bit vectors. 301 EntryInfoMap::iterator Entry; 302 bool DidInsert; 303 std::tie(Entry, DidInsert) = EntryInfos.insert( 304 std::make_pair(&LR, std::make_pair(BitVector(), BitVector()))); 305 if (DidInsert) { 306 // Initialize newly inserted entries. 307 unsigned N = MF->getNumBlockIDs(); 308 Entry->second.first.resize(N); 309 Entry->second.second.resize(N); 310 } 311 BitVector &DefOnEntry = Entry->second.first; 312 BitVector &UndefOnEntry = Entry->second.second; 313 314 // Multiple values were found, so transfer the work list to the LiveIn array 315 // where UpdateSSA will use it as a work list. 316 LiveIn.reserve(WorkList.size()); 317 for (unsigned BN : WorkList) { 318 MachineBasicBlock *MBB = MF->getBlockNumbered(BN); 319 if (!Undefs.empty() && 320 !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry)) 321 continue; 322 addLiveInBlock(LR, DomTree->getNode(MBB)); 323 if (MBB == &UseMBB) 324 LiveIn.back().Kill = Use; 325 } 326 327 return false; 328 } 329 330 // This is essentially the same iterative algorithm that SSAUpdater uses, 331 // except we already have a dominator tree, so we don't have to recompute it. 332 void LiveRangeCalc::updateSSA() { 333 assert(Indexes && "Missing SlotIndexes"); 334 assert(DomTree && "Missing dominator tree"); 335 336 // Interate until convergence. 337 bool Changed; 338 do { 339 Changed = false; 340 // Propagate live-out values down the dominator tree, inserting phi-defs 341 // when necessary. 342 for (LiveInBlock &I : LiveIn) { 343 MachineDomTreeNode *Node = I.DomNode; 344 // Skip block if the live-in value has already been determined. 345 if (!Node) 346 continue; 347 MachineBasicBlock *MBB = Node->getBlock(); 348 MachineDomTreeNode *IDom = Node->getIDom(); 349 LiveOutPair IDomValue; 350 351 // We need a live-in value to a block with no immediate dominator? 352 // This is probably an unreachable block that has survived somehow. 353 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); 354 355 // IDom dominates all of our predecessors, but it may not be their 356 // immediate dominator. Check if any of them have live-out values that are 357 // properly dominated by IDom. If so, we need a phi-def here. 358 if (!needPHI) { 359 IDomValue = Map[IDom->getBlock()]; 360 361 // Cache the DomTree node that defined the value. 362 if (IDomValue.first && IDomValue.first != &UndefVNI && 363 !IDomValue.second) { 364 Map[IDom->getBlock()].second = IDomValue.second = 365 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); 366 } 367 368 for (MachineBasicBlock *Pred : MBB->predecessors()) { 369 LiveOutPair &Value = Map[Pred]; 370 if (!Value.first || Value.first == IDomValue.first) 371 continue; 372 if (Value.first == &UndefVNI) { 373 needPHI = true; 374 break; 375 } 376 377 // Cache the DomTree node that defined the value. 378 if (!Value.second) 379 Value.second = 380 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); 381 382 // This predecessor is carrying something other than IDomValue. 383 // It could be because IDomValue hasn't propagated yet, or it could be 384 // because MBB is in the dominance frontier of that value. 385 if (DomTree->dominates(IDom, Value.second)) { 386 needPHI = true; 387 break; 388 } 389 } 390 } 391 392 // The value may be live-through even if Kill is set, as can happen when 393 // we are called from extendRange. In that case LiveOutSeen is true, and 394 // LiveOut indicates a foreign or missing value. 395 LiveOutPair &LOP = Map[MBB]; 396 397 // Create a phi-def if required. 398 if (needPHI) { 399 Changed = true; 400 assert(Alloc && "Need VNInfo allocator to create PHI-defs"); 401 SlotIndex Start, End; 402 std::tie(Start, End) = Indexes->getMBBRange(MBB); 403 LiveRange &LR = I.LR; 404 VNInfo *VNI = LR.getNextValue(Start, *Alloc); 405 I.Value = VNI; 406 // This block is done, we know the final value. 407 I.DomNode = nullptr; 408 409 // Add liveness since updateFromLiveIns now skips this node. 410 if (I.Kill.isValid()) { 411 if (VNI) 412 LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI)); 413 } else { 414 if (VNI) 415 LR.addSegment(LiveInterval::Segment(Start, End, VNI)); 416 LOP = LiveOutPair(VNI, Node); 417 } 418 } else if (IDomValue.first && IDomValue.first != &UndefVNI) { 419 // No phi-def here. Remember incoming value. 420 I.Value = IDomValue.first; 421 422 // If the IDomValue is killed in the block, don't propagate through. 423 if (I.Kill.isValid()) 424 continue; 425 426 // Propagate IDomValue if it isn't killed: 427 // MBB is live-out and doesn't define its own value. 428 if (LOP.first == IDomValue.first) 429 continue; 430 Changed = true; 431 LOP = IDomValue; 432 } 433 } 434 } while (Changed); 435 } 436 437 bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB, 438 ArrayRef<SlotIndex> Defs, 439 const SlotIndexes &Indexes) { 440 const MachineFunction &MF = *MBB->getParent(); 441 BitVector DefBlocks(MF.getNumBlockIDs()); 442 for (SlotIndex I : Defs) 443 DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber()); 444 445 SetVector<unsigned> PredQueue; 446 PredQueue.insert(MBB->getNumber()); 447 for (unsigned i = 0; i != PredQueue.size(); ++i) { 448 unsigned BN = PredQueue[i]; 449 if (DefBlocks[BN]) 450 return true; 451 const MachineBasicBlock *B = MF.getBlockNumbered(BN); 452 for (const MachineBasicBlock *P : B->predecessors()) 453 PredQueue.insert(P->getNumber()); 454 } 455 return false; 456 } 457