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