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