SplitKit.cpp revision 3afab9c57e1afb0b7a4a9fe25a74117461bc0e69
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 Values.clear(); 214 LiveOutCache.clear(); 215} 216 217bool LiveIntervalMap::isComplexMapped(const VNInfo *ParentVNI) const { 218 ValueMap::const_iterator i = Values.find(ParentVNI); 219 return i != Values.end() && i->second == 0; 220} 221 222// defValue - Introduce a LI def for ParentVNI that could be later than 223// ParentVNI->def. 224VNInfo *LiveIntervalMap::defValue(const VNInfo *ParentVNI, SlotIndex Idx) { 225 assert(LI && "call reset first"); 226 assert(ParentVNI && "Mapping NULL value"); 227 assert(Idx.isValid() && "Invalid SlotIndex"); 228 assert(ParentLI.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI"); 229 230 // Create a new value. 231 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 232 233 // Preserve the PHIDef bit. 234 if (ParentVNI->isPHIDef() && Idx == ParentVNI->def) 235 VNI->setIsPHIDef(true); 236 237 // Use insert for lookup, so we can add missing values with a second lookup. 238 std::pair<ValueMap::iterator,bool> InsP = 239 Values.insert(makeVV(ParentVNI, Idx == ParentVNI->def ? VNI : 0)); 240 241 // This is now a complex def. Mark with a NULL in valueMap. 242 if (!InsP.second) 243 InsP.first->second = 0; 244 245 return VNI; 246} 247 248 249// mapValue - Find the mapped value for ParentVNI at Idx. 250// Potentially create phi-def values. 251VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx, 252 bool *simple) { 253 assert(LI && "call reset first"); 254 assert(ParentVNI && "Mapping NULL value"); 255 assert(Idx.isValid() && "Invalid SlotIndex"); 256 assert(ParentLI.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI"); 257 258 // Use insert for lookup, so we can add missing values with a second lookup. 259 std::pair<ValueMap::iterator,bool> InsP = 260 Values.insert(makeVV(ParentVNI, 0)); 261 262 // This was an unknown value. Create a simple mapping. 263 if (InsP.second) { 264 if (simple) *simple = true; 265 return InsP.first->second = LI->createValueCopy(ParentVNI, 266 LIS.getVNInfoAllocator()); 267 } 268 269 // This was a simple mapped value. 270 if (InsP.first->second) { 271 if (simple) *simple = true; 272 return InsP.first->second; 273 } 274 275 // This is a complex mapped value. There may be multiple defs, and we may need 276 // to create phi-defs. 277 if (simple) *simple = false; 278 MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 279 assert(IdxMBB && "No MBB at Idx"); 280 281 // Is there a def in the same MBB we can extend? 282 if (VNInfo *VNI = extendTo(IdxMBB, Idx)) 283 return VNI; 284 285 // Now for the fun part. We know that ParentVNI potentially has multiple defs, 286 // and we may need to create even more phi-defs to preserve VNInfo SSA form. 287 // Perform a search for all predecessor blocks where we know the dominating 288 // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB. 289 DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber() 290 << " at " << Idx << " in " << *LI << '\n'); 291 292 // Blocks where LI should be live-in. 293 SmallVector<MachineDomTreeNode*, 16> LiveIn; 294 LiveIn.push_back(MDT[IdxMBB]); 295 296 // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 297 for (unsigned i = 0; i != LiveIn.size(); ++i) { 298 MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 299 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 300 PE = MBB->pred_end(); PI != PE; ++PI) { 301 MachineBasicBlock *Pred = *PI; 302 // Is this a known live-out block? 303 std::pair<LiveOutMap::iterator,bool> LOIP = 304 LiveOutCache.insert(std::make_pair(Pred, LiveOutPair())); 305 // Yes, we have been here before. 306 if (!LOIP.second) { 307 DEBUG(if (VNInfo *VNI = LOIP.first->second.first) 308 dbgs() << " known valno #" << VNI->id 309 << " at BB#" << Pred->getNumber() << '\n'); 310 continue; 311 } 312 313 // Does Pred provide a live-out value? 314 SlotIndex Last = LIS.getMBBEndIdx(Pred).getPrevSlot(); 315 if (VNInfo *VNI = extendTo(Pred, Last)) { 316 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def); 317 DEBUG(dbgs() << " found valno #" << VNI->id 318 << " from BB#" << DefMBB->getNumber() 319 << " at BB#" << Pred->getNumber() << '\n'); 320 LiveOutPair &LOP = LOIP.first->second; 321 LOP.first = VNI; 322 LOP.second = MDT[DefMBB]; 323 continue; 324 } 325 // No, we need a live-in value for Pred as well 326 if (Pred != IdxMBB) 327 LiveIn.push_back(MDT[Pred]); 328 } 329 } 330 331 // We may need to add phi-def values to preserve the SSA form. 332 // This is essentially the same iterative algorithm that SSAUpdater uses, 333 // except we already have a dominator tree, so we don't have to recompute it. 334 VNInfo *IdxVNI = 0; 335 unsigned Changes; 336 do { 337 Changes = 0; 338 DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n"); 339 // Propagate live-out values down the dominator tree, inserting phi-defs when 340 // necessary. Since LiveIn was created by a BFS, going backwards makes it more 341 // likely for us to visit immediate dominators before their children. 342 for (unsigned i = LiveIn.size(); i; --i) { 343 MachineDomTreeNode *Node = LiveIn[i-1]; 344 MachineBasicBlock *MBB = Node->getBlock(); 345 MachineDomTreeNode *IDom = Node->getIDom(); 346 LiveOutPair IDomValue; 347 // We need a live-in value to a block with no immediate dominator? 348 // This is probably an unreachable block that has survived somehow. 349 bool needPHI = !IDom; 350 351 // Get the IDom live-out value. 352 if (!needPHI) { 353 LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock()); 354 if (I != LiveOutCache.end()) 355 IDomValue = I->second; 356 else 357 // If IDom is outside our set of live-out blocks, there must be new 358 // defs, and we need a phi-def here. 359 needPHI = true; 360 } 361 362 // IDom dominates all of our predecessors, but it may not be the immediate 363 // dominator. Check if any of them have live-out values that are properly 364 // dominated by IDom. If so, we need a phi-def here. 365 if (!needPHI) { 366 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 367 PE = MBB->pred_end(); PI != PE; ++PI) { 368 LiveOutPair Value = LiveOutCache[*PI]; 369 if (!Value.first || Value.first == IDomValue.first) 370 continue; 371 // This predecessor is carrying something other than IDomValue. 372 // It could be because IDomValue hasn't propagated yet, or it could be 373 // because MBB is in the dominance frontier of that value. 374 if (MDT.dominates(IDom, Value.second)) { 375 needPHI = true; 376 break; 377 } 378 } 379 } 380 381 // Create a phi-def if required. 382 if (needPHI) { 383 ++Changes; 384 SlotIndex Start = LIS.getMBBStartIdx(MBB); 385 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 386 VNI->setIsPHIDef(true); 387 DEBUG(dbgs() << " - BB#" << MBB->getNumber() 388 << " phi-def #" << VNI->id << " at " << Start << '\n'); 389 // We no longer need LI to be live-in. 390 LiveIn.erase(LiveIn.begin()+(i-1)); 391 // Blocks in LiveIn are either IdxMBB, or have a value live-through. 392 if (MBB == IdxMBB) 393 IdxVNI = VNI; 394 // Check if we need to update live-out info. 395 LiveOutMap::iterator I = LiveOutCache.find(MBB); 396 if (I == LiveOutCache.end() || I->second.second == Node) { 397 // We already have a live-out defined in MBB, so this must be IdxMBB. 398 assert(MBB == IdxMBB && "Adding phi-def to known live-out"); 399 LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI)); 400 } else { 401 // This phi-def is also live-out, so color the whole block. 402 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 403 I->second = LiveOutPair(VNI, Node); 404 } 405 } else if (IDomValue.first) { 406 // No phi-def here. Remember incoming value for IdxMBB. 407 if (MBB == IdxMBB) 408 IdxVNI = IDomValue.first; 409 // Propagate IDomValue if needed: 410 // MBB is live-out and doesn't define its own value. 411 LiveOutMap::iterator I = LiveOutCache.find(MBB); 412 if (I != LiveOutCache.end() && I->second.second != Node && 413 I->second.first != IDomValue.first) { 414 ++Changes; 415 I->second = IDomValue; 416 DEBUG(dbgs() << " - BB#" << MBB->getNumber() 417 << " idom valno #" << IDomValue.first->id 418 << " from BB#" << IDom->getBlock()->getNumber() << '\n'); 419 } 420 } 421 } 422 DEBUG(dbgs() << " - made " << Changes << " changes.\n"); 423 } while (Changes); 424 425 assert(IdxVNI && "Didn't find value for Idx"); 426 427#ifndef NDEBUG 428 // Check the LiveOutCache invariants. 429 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); 430 I != E; ++I) { 431 assert(I->first && "Null MBB entry in cache"); 432 assert(I->second.first && "Null VNInfo in cache"); 433 assert(I->second.second && "Null DomTreeNode in cache"); 434 if (I->second.second->getBlock() == I->first) 435 continue; 436 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), 437 PE = I->first->pred_end(); PI != PE; ++PI) 438 assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant"); 439 } 440#endif 441 442 // Since we went through the trouble of a full BFS visiting all reaching defs, 443 // the values in LiveIn are now accurate. No more phi-defs are needed 444 // for these blocks, so we can color the live ranges. 445 // This makes the next mapValue call much faster. 446 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { 447 MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 448 SlotIndex Start = LIS.getMBBStartIdx(MBB); 449 VNInfo *VNI = LiveOutCache.lookup(MBB).first; 450 451 // Anything in LiveIn other than IdxMBB is live-through. 452 // In IdxMBB, we should stop at Idx unless the same value is live-out. 453 if (MBB == IdxMBB && IdxVNI != VNI) 454 LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI)); 455 else 456 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 457 } 458 459 return IdxVNI; 460} 461 462#ifndef NDEBUG 463void LiveIntervalMap::dumpCache() { 464 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); 465 I != E; ++I) { 466 assert(I->first && "Null MBB entry in cache"); 467 assert(I->second.first && "Null VNInfo in cache"); 468 assert(I->second.second && "Null DomTreeNode in cache"); 469 dbgs() << " cache: BB#" << I->first->getNumber() 470 << " has valno #" << I->second.first->id << " from BB#" 471 << I->second.second->getBlock()->getNumber() << ", preds"; 472 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), 473 PE = I->first->pred_end(); PI != PE; ++PI) 474 dbgs() << " BB#" << (*PI)->getNumber(); 475 dbgs() << '\n'; 476 } 477 dbgs() << " cache: " << LiveOutCache.size() << " entries.\n"; 478} 479#endif 480 481// extendTo - Find the last LI value defined in MBB at or before Idx. The 482// ParentLI is assumed to be live at Idx. Extend the live range to Idx. 483// Return the found VNInfo, or NULL. 484VNInfo *LiveIntervalMap::extendTo(const MachineBasicBlock *MBB, SlotIndex Idx) { 485 assert(LI && "call reset first"); 486 LiveInterval::iterator I = std::upper_bound(LI->begin(), LI->end(), Idx); 487 if (I == LI->begin()) 488 return 0; 489 --I; 490 if (I->end <= LIS.getMBBStartIdx(MBB)) 491 return 0; 492 if (I->end <= Idx) 493 I->end = Idx.getNextSlot(); 494 return I->valno; 495} 496 497// addSimpleRange - Add a simple range from ParentLI to LI. 498// ParentVNI must be live in the [Start;End) interval. 499void LiveIntervalMap::addSimpleRange(SlotIndex Start, SlotIndex End, 500 const VNInfo *ParentVNI) { 501 assert(LI && "call reset first"); 502 bool simple; 503 VNInfo *VNI = mapValue(ParentVNI, Start, &simple); 504 // A simple mapping is easy. 505 if (simple) { 506 LI->addRange(LiveRange(Start, End, VNI)); 507 return; 508 } 509 510 // ParentVNI is a complex value. We must map per MBB. 511 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 512 MachineFunction::iterator MBBE = LIS.getMBBFromIndex(End.getPrevSlot()); 513 514 if (MBB == MBBE) { 515 LI->addRange(LiveRange(Start, End, VNI)); 516 return; 517 } 518 519 // First block. 520 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 521 522 // Run sequence of full blocks. 523 for (++MBB; MBB != MBBE; ++MBB) { 524 Start = LIS.getMBBStartIdx(MBB); 525 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), 526 mapValue(ParentVNI, Start))); 527 } 528 529 // Final block. 530 Start = LIS.getMBBStartIdx(MBB); 531 if (Start != End) 532 LI->addRange(LiveRange(Start, End, mapValue(ParentVNI, Start))); 533} 534 535/// addRange - Add live ranges to LI where [Start;End) intersects ParentLI. 536/// All needed values whose def is not inside [Start;End) must be defined 537/// beforehand so mapValue will work. 538void LiveIntervalMap::addRange(SlotIndex Start, SlotIndex End) { 539 assert(LI && "call reset first"); 540 LiveInterval::const_iterator B = ParentLI.begin(), E = ParentLI.end(); 541 LiveInterval::const_iterator I = std::lower_bound(B, E, Start); 542 543 // Check if --I begins before Start and overlaps. 544 if (I != B) { 545 --I; 546 if (I->end > Start) 547 addSimpleRange(Start, std::min(End, I->end), I->valno); 548 ++I; 549 } 550 551 // The remaining ranges begin after Start. 552 for (;I != E && I->start < End; ++I) 553 addSimpleRange(I->start, std::min(End, I->end), I->valno); 554} 555 556 557//===----------------------------------------------------------------------===// 558// Split Editor 559//===----------------------------------------------------------------------===// 560 561/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 562SplitEditor::SplitEditor(SplitAnalysis &sa, 563 LiveIntervals &lis, 564 VirtRegMap &vrm, 565 MachineDominatorTree &mdt, 566 LiveRangeEdit &edit) 567 : SA(sa), LIS(lis), VRM(vrm), 568 MRI(vrm.getMachineFunction().getRegInfo()), 569 MDT(mdt), 570 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 571 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 572 Edit(edit), 573 OpenIdx(0), 574 RegAssign(Allocator) 575{ 576 // We don't need an AliasAnalysis since we will only be performing 577 // cheap-as-a-copy remats anyway. 578 Edit.anyRematerializable(LIS, TII, 0); 579} 580 581void SplitEditor::dump() const { 582 if (RegAssign.empty()) { 583 dbgs() << " empty\n"; 584 return; 585 } 586 587 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 588 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 589 dbgs() << '\n'; 590} 591 592VNInfo *SplitEditor::defFromParent(unsigned RegIdx, 593 VNInfo *ParentVNI, 594 SlotIndex UseIdx, 595 MachineBasicBlock &MBB, 596 MachineBasicBlock::iterator I) { 597 MachineInstr *CopyMI = 0; 598 SlotIndex Def; 599 LiveInterval *LI = Edit.get(RegIdx); 600 601 // Attempt cheap-as-a-copy rematerialization. 602 LiveRangeEdit::Remat RM(ParentVNI); 603 if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) { 604 Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI); 605 } else { 606 // Can't remat, just insert a copy from parent. 607 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 608 .addReg(Edit.getReg()); 609 Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex(); 610 } 611 612 // Define the value in Reg. 613 VNInfo *VNI = LIMappers[RegIdx].defValue(ParentVNI, Def); 614 VNI->setCopy(CopyMI); 615 616 // Add minimal liveness for the new value. 617 Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 618 return VNI; 619} 620 621/// Create a new virtual register and live interval. 622void SplitEditor::openIntv() { 623 assert(!OpenIdx && "Previous LI not closed before openIntv"); 624 625 // Create the complement as index 0. 626 if (Edit.empty()) { 627 Edit.create(MRI, LIS, VRM); 628 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent())); 629 LIMappers.back().reset(Edit.get(0)); 630 } 631 632 // Create the open interval. 633 OpenIdx = Edit.size(); 634 Edit.create(MRI, LIS, VRM); 635 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent())); 636 LIMappers[OpenIdx].reset(Edit.get(OpenIdx)); 637} 638 639SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 640 assert(OpenIdx && "openIntv not called before enterIntvBefore"); 641 DEBUG(dbgs() << " enterIntvBefore " << Idx); 642 Idx = Idx.getBaseIndex(); 643 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 644 if (!ParentVNI) { 645 DEBUG(dbgs() << ": not live\n"); 646 return Idx; 647 } 648 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 649 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 650 assert(MI && "enterIntvBefore called with invalid index"); 651 652 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 653 return VNI->def; 654} 655 656SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 657 assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 658 SlotIndex End = LIS.getMBBEndIdx(&MBB); 659 SlotIndex Last = End.getPrevSlot(); 660 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 661 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last); 662 if (!ParentVNI) { 663 DEBUG(dbgs() << ": not live\n"); 664 return End; 665 } 666 DEBUG(dbgs() << ": valno " << ParentVNI->id); 667 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 668 LIS.getLastSplitPoint(Edit.getParent(), &MBB)); 669 RegAssign.insert(VNI->def, End, OpenIdx); 670 DEBUG(dump()); 671 return VNI->def; 672} 673 674/// useIntv - indicate that all instructions in MBB should use OpenLI. 675void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 676 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 677} 678 679void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 680 assert(OpenIdx && "openIntv not called before useIntv"); 681 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 682 RegAssign.insert(Start, End, OpenIdx); 683 DEBUG(dump()); 684} 685 686SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 687 assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 688 DEBUG(dbgs() << " leaveIntvAfter " << Idx); 689 690 // The interval must be live beyond the instruction at Idx. 691 Idx = Idx.getBoundaryIndex(); 692 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 693 if (!ParentVNI) { 694 DEBUG(dbgs() << ": not live\n"); 695 return Idx.getNextSlot(); 696 } 697 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 698 699 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 700 assert(MI && "No instruction at index"); 701 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 702 llvm::next(MachineBasicBlock::iterator(MI))); 703 return VNI->def; 704} 705 706SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 707 assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 708 DEBUG(dbgs() << " leaveIntvBefore " << Idx); 709 710 // The interval must be live into the instruction at Idx. 711 Idx = Idx.getBoundaryIndex(); 712 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 713 if (!ParentVNI) { 714 DEBUG(dbgs() << ": not live\n"); 715 return Idx.getNextSlot(); 716 } 717 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 718 719 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 720 assert(MI && "No instruction at index"); 721 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 722 return VNI->def; 723} 724 725SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 726 assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 727 SlotIndex Start = LIS.getMBBStartIdx(&MBB); 728 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 729 730 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start); 731 if (!ParentVNI) { 732 DEBUG(dbgs() << ": not live\n"); 733 return Start; 734 } 735 736 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 737 MBB.SkipPHIsAndLabels(MBB.begin())); 738 RegAssign.insert(Start, VNI->def, OpenIdx); 739 DEBUG(dump()); 740 return VNI->def; 741} 742 743void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 744 assert(OpenIdx && "openIntv not called before overlapIntv"); 745 assert(Edit.getParent().getVNInfoAt(Start) == 746 Edit.getParent().getVNInfoAt(End.getPrevSlot()) && 747 "Parent changes value in extended range"); 748 assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*"); 749 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 750 "Range cannot span basic blocks"); 751 752 // Treat this as useIntv() for now. The complement interval will be extended 753 // as needed by mapValue(). 754 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 755 RegAssign.insert(Start, End, OpenIdx); 756 DEBUG(dump()); 757} 758 759/// closeIntv - Indicate that we are done editing the currently open 760/// LiveInterval, and ranges can be trimmed. 761void SplitEditor::closeIntv() { 762 assert(OpenIdx && "openIntv not called before closeIntv"); 763 OpenIdx = 0; 764} 765 766/// rewriteAssigned - Rewrite all uses of Edit.getReg(). 767void SplitEditor::rewriteAssigned() { 768 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()), 769 RE = MRI.reg_end(); RI != RE;) { 770 MachineOperand &MO = RI.getOperand(); 771 MachineInstr *MI = MO.getParent(); 772 ++RI; 773 // LiveDebugVariables should have handled all DBG_VALUE instructions. 774 if (MI->isDebugValue()) { 775 DEBUG(dbgs() << "Zapping " << *MI); 776 MO.setReg(0); 777 continue; 778 } 779 780 // <undef> operands don't really read the register, so just assign them to 781 // the complement. 782 if (MO.isUse() && MO.isUndef()) { 783 MO.setReg(Edit.get(0)->reg); 784 continue; 785 } 786 787 SlotIndex Idx = LIS.getInstructionIndex(MI); 788 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 789 790 // Rewrite to the mapped register at Idx. 791 unsigned RegIdx = RegAssign.lookup(Idx); 792 MO.setReg(Edit.get(RegIdx)->reg); 793 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 794 << Idx << ':' << RegIdx << '\t' << *MI); 795 796 // Extend liveness to Idx. 797 const VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 798 LIMappers[RegIdx].mapValue(ParentVNI, Idx); 799 } 800} 801 802/// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping. 803void SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, 804 const ConnectedVNInfoEqClasses &ConEq) { 805 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg), 806 RE = MRI.reg_end(); RI != RE;) { 807 MachineOperand &MO = RI.getOperand(); 808 MachineInstr *MI = MO.getParent(); 809 ++RI; 810 if (MO.isUse() && MO.isUndef()) 811 continue; 812 // DBG_VALUE instructions should have been eliminated earlier. 813 SlotIndex Idx = LIS.getInstructionIndex(MI); 814 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 815 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 816 << Idx << ':'); 817 const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx); 818 assert(VNI && "Interval not live at use."); 819 MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg); 820 DEBUG(dbgs() << VNI->id << '\t' << *MI); 821 } 822} 823 824void SplitEditor::finish() { 825 assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); 826 827 // At this point, the live intervals in Edit contain VNInfos corresponding to 828 // the inserted copies. 829 830 // Add the original defs from the parent interval. 831 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), 832 E = Edit.getParent().vni_end(); I != E; ++I) { 833 const VNInfo *ParentVNI = *I; 834 if (ParentVNI->isUnused()) 835 continue; 836 LiveIntervalMap &LIM = LIMappers[RegAssign.lookup(ParentVNI->def)]; 837 VNInfo *VNI = LIM.defValue(ParentVNI, ParentVNI->def); 838 LIM.getLI()->addRange(LiveRange(ParentVNI->def, 839 ParentVNI->def.getNextSlot(), VNI)); 840 // Mark all values as complex to force liveness computation. 841 // This should really only be necessary for remat victims, but we are lazy. 842 LIM.markComplexMapped(ParentVNI); 843 } 844 845#ifndef NDEBUG 846 // Every new interval must have a def by now, otherwise the split is bogus. 847 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) 848 assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 849#endif 850 851 // FIXME: Don't recompute the liveness of all values, infer it from the 852 // overlaps between the parent live interval and RegAssign. 853 // The mapValue algorithm is only necessary when: 854 // - The parent value maps to multiple defs, and new phis are needed, or 855 // - The value has been rematerialized before some uses, and we want to 856 // minimize the live range so it only reaches the remaining uses. 857 // All other values have simple liveness that can be computed from RegAssign 858 // and the parent live interval. 859 860 // Extend live ranges to be live-out for successor PHI values. 861 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), 862 E = Edit.getParent().vni_end(); I != E; ++I) { 863 const VNInfo *PHIVNI = *I; 864 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 865 continue; 866 unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 867 LiveIntervalMap &LIM = LIMappers[RegIdx]; 868 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 869 DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def 870 << " -> " << RegIdx << '\n'); 871 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 872 PE = MBB->pred_end(); PI != PE; ++PI) { 873 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 874 DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End); 875 // The predecessor may not have a live-out value. That is OK, like an 876 // undef PHI operand. 877 if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) { 878 DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n"); 879 assert(RegAssign.lookup(End) == RegIdx && 880 "Different register assignment in phi predecessor"); 881 LIM.mapValue(VNI, End); 882 } 883 else 884 DEBUG(dbgs() << " is not live-out\n"); 885 } 886 DEBUG(dbgs() << " " << *LIM.getLI() << '\n'); 887 } 888 889 // Rewrite instructions. 890 rewriteAssigned(); 891 892 // FIXME: Delete defs that were rematted everywhere. 893 894 // Get rid of unused values and set phi-kill flags. 895 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) 896 (*I)->RenumberValues(LIS); 897 898 // Now check if any registers were separated into multiple components. 899 ConnectedVNInfoEqClasses ConEQ(LIS); 900 for (unsigned i = 0, e = Edit.size(); i != e; ++i) { 901 // Don't use iterators, they are invalidated by create() below. 902 LiveInterval *li = Edit.get(i); 903 unsigned NumComp = ConEQ.Classify(li); 904 if (NumComp <= 1) 905 continue; 906 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 907 SmallVector<LiveInterval*, 8> dups; 908 dups.push_back(li); 909 for (unsigned i = 1; i != NumComp; ++i) 910 dups.push_back(&Edit.create(MRI, LIS, VRM)); 911 rewriteComponents(dups, ConEQ); 912 ConEQ.Distribute(&dups[0]); 913 } 914 915 // Calculate spill weight and allocation hints for new intervals. 916 VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops); 917 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){ 918 LiveInterval &li = **I; 919 vrai.CalculateRegClass(li.reg); 920 vrai.CalculateWeightAndHint(li); 921 DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName() 922 << ":" << li << '\n'); 923 } 924} 925 926 927//===----------------------------------------------------------------------===// 928// Single Block Splitting 929//===----------------------------------------------------------------------===// 930 931/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 932/// may be an advantage to split CurLI for the duration of the block. 933bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 934 // If CurLI is local to one block, there is no point to splitting it. 935 if (LiveBlocks.size() <= 1) 936 return false; 937 // Add blocks with multiple uses. 938 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 939 const BlockInfo &BI = LiveBlocks[i]; 940 if (!BI.Uses) 941 continue; 942 unsigned Instrs = UsingBlocks.lookup(BI.MBB); 943 if (Instrs <= 1) 944 continue; 945 if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough) 946 continue; 947 Blocks.insert(BI.MBB); 948 } 949 return !Blocks.empty(); 950} 951 952/// splitSingleBlocks - Split CurLI into a separate live interval inside each 953/// basic block in Blocks. 954void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 955 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 956 957 for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { 958 const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; 959 if (!BI.Uses || !Blocks.count(BI.MBB)) 960 continue; 961 962 openIntv(); 963 SlotIndex SegStart = enterIntvBefore(BI.FirstUse); 964 if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) { 965 useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 966 } else { 967 // The last use is after the last valid split point. 968 SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint); 969 useIntv(SegStart, SegStop); 970 overlapIntv(SegStop, BI.LastUse); 971 } 972 closeIntv(); 973 } 974 finish(); 975} 976