SplitKit.cpp revision edb87555e466e781087e18936f427816c952f3e7
1//===---------- SplitKit.cpp - Toolkit for splitting 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// This file contains the SplitAnalysis class as well as mutator functions for 11// live range splitting. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "regalloc" 16#include "SplitKit.h" 17#include "LiveRangeEdit.h" 18#include "VirtRegMap.h" 19#include "llvm/CodeGen/CalcSpillWeights.h" 20#include "llvm/CodeGen/LiveIntervalAnalysis.h" 21#include "llvm/CodeGen/MachineDominators.h" 22#include "llvm/CodeGen/MachineInstrBuilder.h" 23#include "llvm/CodeGen/MachineRegisterInfo.h" 24#include "llvm/Support/CommandLine.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/raw_ostream.h" 27#include "llvm/Target/TargetInstrInfo.h" 28#include "llvm/Target/TargetMachine.h" 29 30using namespace llvm; 31 32static cl::opt<bool> 33AllowSplit("spiller-splits-edges", 34 cl::desc("Allow critical edge splitting during spilling")); 35 36//===----------------------------------------------------------------------===// 37// Split Analysis 38//===----------------------------------------------------------------------===// 39 40SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 41 const LiveIntervals &lis, 42 const MachineLoopInfo &mli) 43 : MF(vrm.getMachineFunction()), 44 VRM(vrm), 45 LIS(lis), 46 Loops(mli), 47 TII(*MF.getTarget().getInstrInfo()), 48 CurLI(0) {} 49 50void SplitAnalysis::clear() { 51 UseSlots.clear(); 52 UsingInstrs.clear(); 53 UsingBlocks.clear(); 54 LiveBlocks.clear(); 55 CurLI = 0; 56} 57 58bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) { 59 MachineBasicBlock *T, *F; 60 SmallVector<MachineOperand, 4> Cond; 61 return !TII.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond); 62} 63 64/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 65void SplitAnalysis::analyzeUses() { 66 const MachineRegisterInfo &MRI = MF.getRegInfo(); 67 for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(CurLI->reg), 68 E = MRI.reg_end(); I != E; ++I) { 69 MachineOperand &MO = I.getOperand(); 70 if (MO.isUse() && MO.isUndef()) 71 continue; 72 MachineInstr *MI = MO.getParent(); 73 if (MI->isDebugValue() || !UsingInstrs.insert(MI)) 74 continue; 75 UseSlots.push_back(LIS.getInstructionIndex(MI).getDefIndex()); 76 MachineBasicBlock *MBB = MI->getParent(); 77 UsingBlocks[MBB]++; 78 } 79 array_pod_sort(UseSlots.begin(), UseSlots.end()); 80 calcLiveBlockInfo(); 81 DEBUG(dbgs() << " counted " 82 << UsingInstrs.size() << " instrs, " 83 << UsingBlocks.size() << " blocks.\n"); 84} 85 86/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 87/// where CurLI is live. 88void SplitAnalysis::calcLiveBlockInfo() { 89 if (CurLI->empty()) 90 return; 91 92 LiveInterval::const_iterator LVI = CurLI->begin(); 93 LiveInterval::const_iterator LVE = CurLI->end(); 94 95 SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 96 UseI = UseSlots.begin(); 97 UseE = UseSlots.end(); 98 99 // Loop over basic blocks where CurLI is live. 100 MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 101 for (;;) { 102 BlockInfo BI; 103 BI.MBB = MFI; 104 SlotIndex Start, Stop; 105 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 106 107 // The last split point is the latest possible insertion point that dominates 108 // all successor blocks. If interference reaches LastSplitPoint, it is not 109 // possible to insert a split or reload that makes CurLI live in the 110 // outgoing bundle. 111 MachineBasicBlock::iterator LSP = LIS.getLastSplitPoint(*CurLI, BI.MBB); 112 if (LSP == BI.MBB->end()) 113 BI.LastSplitPoint = Stop; 114 else 115 BI.LastSplitPoint = LIS.getInstructionIndex(LSP); 116 117 // LVI is the first live segment overlapping MBB. 118 BI.LiveIn = LVI->start <= Start; 119 if (!BI.LiveIn) 120 BI.Def = LVI->start; 121 122 // Find the first and last uses in the block. 123 BI.Uses = hasUses(MFI); 124 if (BI.Uses && UseI != UseE) { 125 BI.FirstUse = *UseI; 126 assert(BI.FirstUse >= Start); 127 do ++UseI; 128 while (UseI != UseE && *UseI < Stop); 129 BI.LastUse = UseI[-1]; 130 assert(BI.LastUse < Stop); 131 } 132 133 // Look for gaps in the live range. 134 bool hasGap = false; 135 BI.LiveOut = true; 136 while (LVI->end < Stop) { 137 SlotIndex LastStop = LVI->end; 138 if (++LVI == LVE || LVI->start >= Stop) { 139 BI.Kill = LastStop; 140 BI.LiveOut = false; 141 break; 142 } 143 if (LastStop < LVI->start) { 144 hasGap = true; 145 BI.Kill = LastStop; 146 BI.Def = LVI->start; 147 } 148 } 149 150 // Don't set LiveThrough when the block has a gap. 151 BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut; 152 LiveBlocks.push_back(BI); 153 154 // LVI is now at LVE or LVI->end >= Stop. 155 if (LVI == LVE) 156 break; 157 158 // Live segment ends exactly at Stop. Move to the next segment. 159 if (LVI->end == Stop && ++LVI == LVE) 160 break; 161 162 // Pick the next basic block. 163 if (LVI->start < Stop) 164 ++MFI; 165 else 166 MFI = LIS.getMBBFromIndex(LVI->start); 167 } 168} 169 170bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 171 unsigned OrigReg = VRM.getOriginal(CurLI->reg); 172 const LiveInterval &Orig = LIS.getInterval(OrigReg); 173 assert(!Orig.empty() && "Splitting empty interval?"); 174 LiveInterval::const_iterator I = Orig.find(Idx); 175 176 // Range containing Idx should begin at Idx. 177 if (I != Orig.end() && I->start <= Idx) 178 return I->start == Idx; 179 180 // Range does not contain Idx, previous must end at Idx. 181 return I != Orig.begin() && (--I)->end == Idx; 182} 183 184void SplitAnalysis::print(const BlockPtrSet &B, raw_ostream &OS) const { 185 for (BlockPtrSet::const_iterator I = B.begin(), E = B.end(); I != E; ++I) { 186 unsigned count = UsingBlocks.lookup(*I); 187 OS << " BB#" << (*I)->getNumber(); 188 if (count) 189 OS << '(' << count << ')'; 190 } 191} 192 193void SplitAnalysis::analyze(const LiveInterval *li) { 194 clear(); 195 CurLI = li; 196 analyzeUses(); 197} 198 199 200//===----------------------------------------------------------------------===// 201// LiveIntervalMap 202//===----------------------------------------------------------------------===// 203 204// Work around the fact that the std::pair constructors are broken for pointer 205// pairs in some implementations. makeVV(x, 0) works. 206static inline std::pair<const VNInfo*, VNInfo*> 207makeVV(const VNInfo *a, VNInfo *b) { 208 return std::make_pair(a, b); 209} 210 211void LiveIntervalMap::reset(LiveInterval *li) { 212 LI = li; 213 LiveOutCache.clear(); 214} 215 216 217// mapValue - Find the mapped value for ParentVNI at Idx. 218// Potentially create phi-def values. 219VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx, 220 bool *simple) { 221 assert(LI && "call reset first"); 222 assert(ParentVNI && "Mapping NULL value"); 223 assert(Idx.isValid() && "Invalid SlotIndex"); 224 assert(ParentLI.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI"); 225 226 // This is a complex mapped value. There may be multiple defs, and we may need 227 // to create phi-defs. 228 if (simple) *simple = false; 229 MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 230 assert(IdxMBB && "No MBB at Idx"); 231 232 // Is there a def in the same MBB we can extend? 233 if (VNInfo *VNI = extendTo(IdxMBB, Idx)) 234 return VNI; 235 236 // Now for the fun part. We know that ParentVNI potentially has multiple defs, 237 // and we may need to create even more phi-defs to preserve VNInfo SSA form. 238 // Perform a search for all predecessor blocks where we know the dominating 239 // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB. 240 DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber() 241 << " at " << Idx << " in " << *LI << '\n'); 242 243 // Blocks where LI should be live-in. 244 SmallVector<MachineDomTreeNode*, 16> LiveIn; 245 LiveIn.push_back(MDT[IdxMBB]); 246 247 // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 248 for (unsigned i = 0; i != LiveIn.size(); ++i) { 249 MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 250 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 251 PE = MBB->pred_end(); PI != PE; ++PI) { 252 MachineBasicBlock *Pred = *PI; 253 // Is this a known live-out block? 254 std::pair<LiveOutMap::iterator,bool> LOIP = 255 LiveOutCache.insert(std::make_pair(Pred, LiveOutPair())); 256 // Yes, we have been here before. 257 if (!LOIP.second) { 258 DEBUG(if (VNInfo *VNI = LOIP.first->second.first) 259 dbgs() << " known valno #" << VNI->id 260 << " at BB#" << Pred->getNumber() << '\n'); 261 continue; 262 } 263 264 // Does Pred provide a live-out value? 265 SlotIndex Last = LIS.getMBBEndIdx(Pred).getPrevSlot(); 266 if (VNInfo *VNI = extendTo(Pred, Last)) { 267 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def); 268 DEBUG(dbgs() << " found valno #" << VNI->id 269 << " from BB#" << DefMBB->getNumber() 270 << " at BB#" << Pred->getNumber() << '\n'); 271 LiveOutPair &LOP = LOIP.first->second; 272 LOP.first = VNI; 273 LOP.second = MDT[DefMBB]; 274 continue; 275 } 276 // No, we need a live-in value for Pred as well 277 if (Pred != IdxMBB) 278 LiveIn.push_back(MDT[Pred]); 279 } 280 } 281 282 // We may need to add phi-def values to preserve the SSA form. 283 // This is essentially the same iterative algorithm that SSAUpdater uses, 284 // except we already have a dominator tree, so we don't have to recompute it. 285 VNInfo *IdxVNI = 0; 286 unsigned Changes; 287 do { 288 Changes = 0; 289 DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n"); 290 // Propagate live-out values down the dominator tree, inserting phi-defs when 291 // necessary. Since LiveIn was created by a BFS, going backwards makes it more 292 // likely for us to visit immediate dominators before their children. 293 for (unsigned i = LiveIn.size(); i; --i) { 294 MachineDomTreeNode *Node = LiveIn[i-1]; 295 MachineBasicBlock *MBB = Node->getBlock(); 296 MachineDomTreeNode *IDom = Node->getIDom(); 297 LiveOutPair IDomValue; 298 // We need a live-in value to a block with no immediate dominator? 299 // This is probably an unreachable block that has survived somehow. 300 bool needPHI = !IDom; 301 302 // Get the IDom live-out value. 303 if (!needPHI) { 304 LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock()); 305 if (I != LiveOutCache.end()) 306 IDomValue = I->second; 307 else 308 // If IDom is outside our set of live-out blocks, there must be new 309 // defs, and we need a phi-def here. 310 needPHI = true; 311 } 312 313 // IDom dominates all of our predecessors, but it may not be the immediate 314 // dominator. Check if any of them have live-out values that are properly 315 // dominated by IDom. If so, we need a phi-def here. 316 if (!needPHI) { 317 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 318 PE = MBB->pred_end(); PI != PE; ++PI) { 319 LiveOutPair Value = LiveOutCache[*PI]; 320 if (!Value.first || Value.first == IDomValue.first) 321 continue; 322 // This predecessor is carrying something other than IDomValue. 323 // It could be because IDomValue hasn't propagated yet, or it could be 324 // because MBB is in the dominance frontier of that value. 325 if (MDT.dominates(IDom, Value.second)) { 326 needPHI = true; 327 break; 328 } 329 } 330 } 331 332 // Create a phi-def if required. 333 if (needPHI) { 334 ++Changes; 335 SlotIndex Start = LIS.getMBBStartIdx(MBB); 336 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 337 VNI->setIsPHIDef(true); 338 DEBUG(dbgs() << " - BB#" << MBB->getNumber() 339 << " phi-def #" << VNI->id << " at " << Start << '\n'); 340 // We no longer need LI to be live-in. 341 LiveIn.erase(LiveIn.begin()+(i-1)); 342 // Blocks in LiveIn are either IdxMBB, or have a value live-through. 343 if (MBB == IdxMBB) 344 IdxVNI = VNI; 345 // Check if we need to update live-out info. 346 LiveOutMap::iterator I = LiveOutCache.find(MBB); 347 if (I == LiveOutCache.end() || I->second.second == Node) { 348 // We already have a live-out defined in MBB, so this must be IdxMBB. 349 assert(MBB == IdxMBB && "Adding phi-def to known live-out"); 350 LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI)); 351 } else { 352 // This phi-def is also live-out, so color the whole block. 353 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 354 I->second = LiveOutPair(VNI, Node); 355 } 356 } else if (IDomValue.first) { 357 // No phi-def here. Remember incoming value for IdxMBB. 358 if (MBB == IdxMBB) 359 IdxVNI = IDomValue.first; 360 // Propagate IDomValue if needed: 361 // MBB is live-out and doesn't define its own value. 362 LiveOutMap::iterator I = LiveOutCache.find(MBB); 363 if (I != LiveOutCache.end() && I->second.second != Node && 364 I->second.first != IDomValue.first) { 365 ++Changes; 366 I->second = IDomValue; 367 DEBUG(dbgs() << " - BB#" << MBB->getNumber() 368 << " idom valno #" << IDomValue.first->id 369 << " from BB#" << IDom->getBlock()->getNumber() << '\n'); 370 } 371 } 372 } 373 DEBUG(dbgs() << " - made " << Changes << " changes.\n"); 374 } while (Changes); 375 376 assert(IdxVNI && "Didn't find value for Idx"); 377 378#ifndef NDEBUG 379 // Check the LiveOutCache invariants. 380 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); 381 I != E; ++I) { 382 assert(I->first && "Null MBB entry in cache"); 383 assert(I->second.first && "Null VNInfo in cache"); 384 assert(I->second.second && "Null DomTreeNode in cache"); 385 if (I->second.second->getBlock() == I->first) 386 continue; 387 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), 388 PE = I->first->pred_end(); PI != PE; ++PI) 389 assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant"); 390 } 391#endif 392 393 // Since we went through the trouble of a full BFS visiting all reaching defs, 394 // the values in LiveIn are now accurate. No more phi-defs are needed 395 // for these blocks, so we can color the live ranges. 396 // This makes the next mapValue call much faster. 397 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { 398 MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 399 SlotIndex Start = LIS.getMBBStartIdx(MBB); 400 VNInfo *VNI = LiveOutCache.lookup(MBB).first; 401 402 // Anything in LiveIn other than IdxMBB is live-through. 403 // In IdxMBB, we should stop at Idx unless the same value is live-out. 404 if (MBB == IdxMBB && IdxVNI != VNI) 405 LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI)); 406 else 407 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 408 } 409 410 return IdxVNI; 411} 412 413#ifndef NDEBUG 414void LiveIntervalMap::dumpCache() { 415 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); 416 I != E; ++I) { 417 assert(I->first && "Null MBB entry in cache"); 418 assert(I->second.first && "Null VNInfo in cache"); 419 assert(I->second.second && "Null DomTreeNode in cache"); 420 dbgs() << " cache: BB#" << I->first->getNumber() 421 << " has valno #" << I->second.first->id << " from BB#" 422 << I->second.second->getBlock()->getNumber() << ", preds"; 423 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), 424 PE = I->first->pred_end(); PI != PE; ++PI) 425 dbgs() << " BB#" << (*PI)->getNumber(); 426 dbgs() << '\n'; 427 } 428 dbgs() << " cache: " << LiveOutCache.size() << " entries.\n"; 429} 430#endif 431 432// extendTo - Find the last LI value defined in MBB at or before Idx. The 433// ParentLI is assumed to be live at Idx. Extend the live range to Idx. 434// Return the found VNInfo, or NULL. 435VNInfo *LiveIntervalMap::extendTo(const MachineBasicBlock *MBB, SlotIndex Idx) { 436 assert(LI && "call reset first"); 437 LiveInterval::iterator I = std::upper_bound(LI->begin(), LI->end(), Idx); 438 if (I == LI->begin()) 439 return 0; 440 --I; 441 if (I->end <= LIS.getMBBStartIdx(MBB)) 442 return 0; 443 if (I->end <= Idx) 444 I->end = Idx.getNextSlot(); 445 return I->valno; 446} 447 448 449//===----------------------------------------------------------------------===// 450// Split Editor 451//===----------------------------------------------------------------------===// 452 453/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 454SplitEditor::SplitEditor(SplitAnalysis &sa, 455 LiveIntervals &lis, 456 VirtRegMap &vrm, 457 MachineDominatorTree &mdt, 458 LiveRangeEdit &edit) 459 : SA(sa), LIS(lis), VRM(vrm), 460 MRI(vrm.getMachineFunction().getRegInfo()), 461 MDT(mdt), 462 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 463 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 464 Edit(edit), 465 OpenIdx(0), 466 RegAssign(Allocator) 467{ 468 // We don't need an AliasAnalysis since we will only be performing 469 // cheap-as-a-copy remats anyway. 470 Edit.anyRematerializable(LIS, TII, 0); 471} 472 473void SplitEditor::dump() const { 474 if (RegAssign.empty()) { 475 dbgs() << " empty\n"; 476 return; 477 } 478 479 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 480 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 481 dbgs() << '\n'; 482} 483 484VNInfo *SplitEditor::defValue(unsigned RegIdx, 485 const VNInfo *ParentVNI, 486 SlotIndex Idx) { 487 assert(ParentVNI && "Mapping NULL value"); 488 assert(Idx.isValid() && "Invalid SlotIndex"); 489 assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 490 LiveInterval *LI = Edit.get(RegIdx); 491 492 // Create a new value. 493 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 494 495 // Preserve the PHIDef bit. 496 if (ParentVNI->isPHIDef() && Idx == ParentVNI->def) 497 VNI->setIsPHIDef(true); 498 499 // Use insert for lookup, so we can add missing values with a second lookup. 500 std::pair<ValueMap::iterator, bool> InsP = 501 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 502 503 // This was the first time (RegIdx, ParentVNI) was mapped. 504 // Keep it as a simple def without any liveness. 505 if (InsP.second) 506 return VNI; 507 508 // If the previous value was a simple mapping, add liveness for it now. 509 if (VNInfo *OldVNI = InsP.first->second) { 510 SlotIndex Def = OldVNI->def; 511 LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 512 // No longer a simple mapping. 513 InsP.first->second = 0; 514 } 515 516 // This is a complex mapping, add liveness for VNI 517 SlotIndex Def = VNI->def; 518 LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 519 520 return VNI; 521} 522 523void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 524 assert(ParentVNI && "Mapping NULL value"); 525 VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 526 527 // ParentVNI was either unmapped or already complex mapped. Either way. 528 if (!VNI) 529 return; 530 531 // This was previously a single mapping. Make sure the old def is represented 532 // by a trivial live range. 533 SlotIndex Def = VNI->def; 534 Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 535 VNI = 0; 536} 537 538VNInfo *SplitEditor::defFromParent(unsigned RegIdx, 539 VNInfo *ParentVNI, 540 SlotIndex UseIdx, 541 MachineBasicBlock &MBB, 542 MachineBasicBlock::iterator I) { 543 MachineInstr *CopyMI = 0; 544 SlotIndex Def; 545 LiveInterval *LI = Edit.get(RegIdx); 546 547 // Attempt cheap-as-a-copy rematerialization. 548 LiveRangeEdit::Remat RM(ParentVNI); 549 if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) { 550 Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI); 551 } else { 552 // Can't remat, just insert a copy from parent. 553 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 554 .addReg(Edit.getReg()); 555 Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex(); 556 } 557 558 // Temporarily mark all values as complex mapped. 559 markComplexMapped(RegIdx, ParentVNI); 560 561 // Define the value in Reg. 562 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 563 VNI->setCopy(CopyMI); 564 return VNI; 565} 566 567/// Create a new virtual register and live interval. 568void SplitEditor::openIntv() { 569 assert(!OpenIdx && "Previous LI not closed before openIntv"); 570 571 // Create the complement as index 0. 572 if (Edit.empty()) { 573 Edit.create(MRI, LIS, VRM); 574 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent())); 575 LIMappers.back().reset(Edit.get(0)); 576 } 577 578 // Create the open interval. 579 OpenIdx = Edit.size(); 580 Edit.create(MRI, LIS, VRM); 581 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent())); 582 LIMappers[OpenIdx].reset(Edit.get(OpenIdx)); 583} 584 585SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 586 assert(OpenIdx && "openIntv not called before enterIntvBefore"); 587 DEBUG(dbgs() << " enterIntvBefore " << Idx); 588 Idx = Idx.getBaseIndex(); 589 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 590 if (!ParentVNI) { 591 DEBUG(dbgs() << ": not live\n"); 592 return Idx; 593 } 594 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 595 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 596 assert(MI && "enterIntvBefore called with invalid index"); 597 598 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 599 return VNI->def; 600} 601 602SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 603 assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 604 SlotIndex End = LIS.getMBBEndIdx(&MBB); 605 SlotIndex Last = End.getPrevSlot(); 606 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 607 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last); 608 if (!ParentVNI) { 609 DEBUG(dbgs() << ": not live\n"); 610 return End; 611 } 612 DEBUG(dbgs() << ": valno " << ParentVNI->id); 613 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 614 LIS.getLastSplitPoint(Edit.getParent(), &MBB)); 615 RegAssign.insert(VNI->def, End, OpenIdx); 616 DEBUG(dump()); 617 return VNI->def; 618} 619 620/// useIntv - indicate that all instructions in MBB should use OpenLI. 621void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 622 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 623} 624 625void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 626 assert(OpenIdx && "openIntv not called before useIntv"); 627 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 628 RegAssign.insert(Start, End, OpenIdx); 629 DEBUG(dump()); 630} 631 632SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 633 assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 634 DEBUG(dbgs() << " leaveIntvAfter " << Idx); 635 636 // The interval must be live beyond the instruction at Idx. 637 Idx = Idx.getBoundaryIndex(); 638 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 639 if (!ParentVNI) { 640 DEBUG(dbgs() << ": not live\n"); 641 return Idx.getNextSlot(); 642 } 643 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 644 645 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 646 assert(MI && "No instruction at index"); 647 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 648 llvm::next(MachineBasicBlock::iterator(MI))); 649 return VNI->def; 650} 651 652SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 653 assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 654 DEBUG(dbgs() << " leaveIntvBefore " << Idx); 655 656 // The interval must be live into the instruction at Idx. 657 Idx = Idx.getBoundaryIndex(); 658 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 659 if (!ParentVNI) { 660 DEBUG(dbgs() << ": not live\n"); 661 return Idx.getNextSlot(); 662 } 663 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 664 665 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 666 assert(MI && "No instruction at index"); 667 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 668 return VNI->def; 669} 670 671SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 672 assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 673 SlotIndex Start = LIS.getMBBStartIdx(&MBB); 674 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 675 676 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start); 677 if (!ParentVNI) { 678 DEBUG(dbgs() << ": not live\n"); 679 return Start; 680 } 681 682 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 683 MBB.SkipPHIsAndLabels(MBB.begin())); 684 RegAssign.insert(Start, VNI->def, OpenIdx); 685 DEBUG(dump()); 686 return VNI->def; 687} 688 689void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 690 assert(OpenIdx && "openIntv not called before overlapIntv"); 691 assert(Edit.getParent().getVNInfoAt(Start) == 692 Edit.getParent().getVNInfoAt(End.getPrevSlot()) && 693 "Parent changes value in extended range"); 694 assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*"); 695 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 696 "Range cannot span basic blocks"); 697 698 // Treat this as useIntv() for now. The complement interval will be extended 699 // as needed by mapValue(). 700 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 701 RegAssign.insert(Start, End, OpenIdx); 702 DEBUG(dump()); 703} 704 705/// closeIntv - Indicate that we are done editing the currently open 706/// LiveInterval, and ranges can be trimmed. 707void SplitEditor::closeIntv() { 708 assert(OpenIdx && "openIntv not called before closeIntv"); 709 OpenIdx = 0; 710} 711 712/// rewriteAssigned - Rewrite all uses of Edit.getReg(). 713void SplitEditor::rewriteAssigned() { 714 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()), 715 RE = MRI.reg_end(); RI != RE;) { 716 MachineOperand &MO = RI.getOperand(); 717 MachineInstr *MI = MO.getParent(); 718 ++RI; 719 // LiveDebugVariables should have handled all DBG_VALUE instructions. 720 if (MI->isDebugValue()) { 721 DEBUG(dbgs() << "Zapping " << *MI); 722 MO.setReg(0); 723 continue; 724 } 725 726 // <undef> operands don't really read the register, so just assign them to 727 // the complement. 728 if (MO.isUse() && MO.isUndef()) { 729 MO.setReg(Edit.get(0)->reg); 730 continue; 731 } 732 733 SlotIndex Idx = LIS.getInstructionIndex(MI); 734 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 735 736 // Rewrite to the mapped register at Idx. 737 unsigned RegIdx = RegAssign.lookup(Idx); 738 MO.setReg(Edit.get(RegIdx)->reg); 739 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 740 << Idx << ':' << RegIdx << '\t' << *MI); 741 742 // Extend liveness to Idx. 743 const VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 744 LIMappers[RegIdx].mapValue(ParentVNI, Idx); 745 } 746} 747 748/// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping. 749void SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, 750 const ConnectedVNInfoEqClasses &ConEq) { 751 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg), 752 RE = MRI.reg_end(); RI != RE;) { 753 MachineOperand &MO = RI.getOperand(); 754 MachineInstr *MI = MO.getParent(); 755 ++RI; 756 if (MO.isUse() && MO.isUndef()) 757 continue; 758 // DBG_VALUE instructions should have been eliminated earlier. 759 SlotIndex Idx = LIS.getInstructionIndex(MI); 760 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 761 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 762 << Idx << ':'); 763 const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx); 764 assert(VNI && "Interval not live at use."); 765 MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg); 766 DEBUG(dbgs() << VNI->id << '\t' << *MI); 767 } 768} 769 770void SplitEditor::finish() { 771 assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); 772 773 // At this point, the live intervals in Edit contain VNInfos corresponding to 774 // the inserted copies. 775 776 // Add the original defs from the parent interval. 777 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), 778 E = Edit.getParent().vni_end(); I != E; ++I) { 779 const VNInfo *ParentVNI = *I; 780 if (ParentVNI->isUnused()) 781 continue; 782 unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 783 // Mark all values as complex to force liveness computation. 784 // This should really only be necessary for remat victims, but we are lazy. 785 markComplexMapped(RegIdx, ParentVNI); 786 defValue(RegIdx, ParentVNI, ParentVNI->def); 787 } 788 789#ifndef NDEBUG 790 // Every new interval must have a def by now, otherwise the split is bogus. 791 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) 792 assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 793#endif 794 795 // FIXME: Don't recompute the liveness of all values, infer it from the 796 // overlaps between the parent live interval and RegAssign. 797 // The mapValue algorithm is only necessary when: 798 // - The parent value maps to multiple defs, and new phis are needed, or 799 // - The value has been rematerialized before some uses, and we want to 800 // minimize the live range so it only reaches the remaining uses. 801 // All other values have simple liveness that can be computed from RegAssign 802 // and the parent live interval. 803 804 // Extend live ranges to be live-out for successor PHI values. 805 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), 806 E = Edit.getParent().vni_end(); I != E; ++I) { 807 const VNInfo *PHIVNI = *I; 808 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 809 continue; 810 unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 811 LiveIntervalMap &LIM = LIMappers[RegIdx]; 812 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 813 DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def 814 << " -> " << RegIdx << '\n'); 815 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 816 PE = MBB->pred_end(); PI != PE; ++PI) { 817 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 818 DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End); 819 // The predecessor may not have a live-out value. That is OK, like an 820 // undef PHI operand. 821 if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) { 822 DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n"); 823 assert(RegAssign.lookup(End) == RegIdx && 824 "Different register assignment in phi predecessor"); 825 LIM.mapValue(VNI, End); 826 } 827 else 828 DEBUG(dbgs() << " is not live-out\n"); 829 } 830 DEBUG(dbgs() << " " << *LIM.getLI() << '\n'); 831 } 832 833 // Rewrite instructions. 834 rewriteAssigned(); 835 836 // FIXME: Delete defs that were rematted everywhere. 837 838 // Get rid of unused values and set phi-kill flags. 839 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) 840 (*I)->RenumberValues(LIS); 841 842 // Now check if any registers were separated into multiple components. 843 ConnectedVNInfoEqClasses ConEQ(LIS); 844 for (unsigned i = 0, e = Edit.size(); i != e; ++i) { 845 // Don't use iterators, they are invalidated by create() below. 846 LiveInterval *li = Edit.get(i); 847 unsigned NumComp = ConEQ.Classify(li); 848 if (NumComp <= 1) 849 continue; 850 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 851 SmallVector<LiveInterval*, 8> dups; 852 dups.push_back(li); 853 for (unsigned i = 1; i != NumComp; ++i) 854 dups.push_back(&Edit.create(MRI, LIS, VRM)); 855 rewriteComponents(dups, ConEQ); 856 ConEQ.Distribute(&dups[0]); 857 } 858 859 // Calculate spill weight and allocation hints for new intervals. 860 VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops); 861 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){ 862 LiveInterval &li = **I; 863 vrai.CalculateRegClass(li.reg); 864 vrai.CalculateWeightAndHint(li); 865 DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName() 866 << ":" << li << '\n'); 867 } 868} 869 870 871//===----------------------------------------------------------------------===// 872// Single Block Splitting 873//===----------------------------------------------------------------------===// 874 875/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 876/// may be an advantage to split CurLI for the duration of the block. 877bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 878 // If CurLI is local to one block, there is no point to splitting it. 879 if (LiveBlocks.size() <= 1) 880 return false; 881 // Add blocks with multiple uses. 882 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 883 const BlockInfo &BI = LiveBlocks[i]; 884 if (!BI.Uses) 885 continue; 886 unsigned Instrs = UsingBlocks.lookup(BI.MBB); 887 if (Instrs <= 1) 888 continue; 889 if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough) 890 continue; 891 Blocks.insert(BI.MBB); 892 } 893 return !Blocks.empty(); 894} 895 896/// splitSingleBlocks - Split CurLI into a separate live interval inside each 897/// basic block in Blocks. 898void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 899 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 900 901 for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { 902 const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; 903 if (!BI.Uses || !Blocks.count(BI.MBB)) 904 continue; 905 906 openIntv(); 907 SlotIndex SegStart = enterIntvBefore(BI.FirstUse); 908 if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) { 909 useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 910 } else { 911 // The last use is after the last valid split point. 912 SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint); 913 useIntv(SegStart, SegStop); 914 overlapIntv(SegStop, BI.LastUse); 915 } 916 closeIntv(); 917 } 918 finish(); 919} 920