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