1 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the LiveInterval analysis pass which is used
11 // by the Linear Scan Register allocator. This pass linearizes the
12 // basic blocks of the function in DFS order and uses the
13 // LiveVariables pass to conservatively compute live intervals for
14 // each virtual and physical register.
16 //===----------------------------------------------------------------------===//
18 #define DEBUG_TYPE "liveintervals"
19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
20 #include "VirtRegMap.h"
21 #include "llvm/Value.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/CodeGen/LiveVariables.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineInstr.h"
26 #include "llvm/CodeGen/MachineInstrBuilder.h"
27 #include "llvm/CodeGen/MachineLoopInfo.h"
28 #include "llvm/CodeGen/MachineRegisterInfo.h"
29 #include "llvm/CodeGen/Passes.h"
30 #include "llvm/CodeGen/PseudoSourceValue.h"
31 #include "llvm/Target/TargetRegisterInfo.h"
32 #include "llvm/Target/TargetInstrInfo.h"
33 #include "llvm/Target/TargetMachine.h"
34 #include "llvm/Target/TargetOptions.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/raw_ostream.h"
39 #include "llvm/ADT/DepthFirstIterator.h"
40 #include "llvm/ADT/SmallSet.h"
41 #include "llvm/ADT/Statistic.h"
42 #include "llvm/ADT/STLExtras.h"
48 // Hidden options for help debugging.
49 static cl::opt<bool> DisableReMat("disable-rematerialization",
50 cl::init(false), cl::Hidden);
52 static cl::opt<bool> SplitAtBB("split-intervals-at-bb",
53 cl::init(true), cl::Hidden);
54 static cl::opt<int> SplitLimit("split-limit",
55 cl::init(-1), cl::Hidden);
57 static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden);
59 static cl::opt<bool> EnableFastSpilling("fast-spill",
60 cl::init(false), cl::Hidden);
62 STATISTIC(numIntervals, "Number of original intervals");
63 STATISTIC(numFolds , "Number of loads/stores folded into instructions");
64 STATISTIC(numSplits , "Number of intervals split");
66 char LiveIntervals::ID = 0;
67 static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
69 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
71 AU.addRequired<AliasAnalysis>();
72 AU.addPreserved<AliasAnalysis>();
73 AU.addPreserved<LiveVariables>();
74 AU.addRequired<LiveVariables>();
75 AU.addPreservedID(MachineLoopInfoID);
76 AU.addPreservedID(MachineDominatorsID);
79 AU.addPreservedID(PHIEliminationID);
80 AU.addRequiredID(PHIEliminationID);
83 AU.addRequiredID(TwoAddressInstructionPassID);
84 MachineFunctionPass::getAnalysisUsage(AU);
87 void LiveIntervals::releaseMemory() {
88 // Free the live intervals themselves.
89 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
90 E = r2iMap_.end(); I != E; ++I)
98 terminatorGaps.clear();
100 // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
101 VNInfoAllocator.Reset();
102 while (!ClonedMIs.empty()) {
103 MachineInstr *MI = ClonedMIs.back();
104 ClonedMIs.pop_back();
105 mf_->DeleteMachineInstr(MI);
109 static bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg,
110 const TargetInstrInfo *tii_) {
111 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
112 if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
116 if ((MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
117 MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) &&
118 MI->getOperand(2).getReg() == Reg)
120 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG &&
121 MI->getOperand(1).getReg() == Reg)
126 /// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure
127 /// there is one implicit_def for each use. Add isUndef marker to
128 /// implicit_def defs and their uses.
129 void LiveIntervals::processImplicitDefs() {
130 SmallSet<unsigned, 8> ImpDefRegs;
131 SmallVector<MachineInstr*, 8> ImpDefMIs;
132 MachineBasicBlock *Entry = mf_->begin();
133 SmallPtrSet<MachineBasicBlock*,16> Visited;
134 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
135 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
137 MachineBasicBlock *MBB = *DFI;
138 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
140 MachineInstr *MI = &*I;
142 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
143 unsigned Reg = MI->getOperand(0).getReg();
144 ImpDefRegs.insert(Reg);
145 ImpDefMIs.push_back(MI);
149 bool ChangedToImpDef = false;
150 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
151 MachineOperand& MO = MI->getOperand(i);
152 if (!MO.isReg() || !MO.isUse() || MO.isUndef())
154 unsigned Reg = MO.getReg();
157 if (!ImpDefRegs.count(Reg))
159 // Use is a copy, just turn it into an implicit_def.
160 if (CanTurnIntoImplicitDef(MI, Reg, tii_)) {
161 bool isKill = MO.isKill();
162 MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
163 for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
164 MI->RemoveOperand(j);
166 ImpDefRegs.erase(Reg);
167 ChangedToImpDef = true;
172 if (MO.isKill() || MI->isRegTiedToDefOperand(i)) {
173 // Make sure other uses of
174 for (unsigned j = i+1; j != e; ++j) {
175 MachineOperand &MOJ = MI->getOperand(j);
176 if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg)
179 ImpDefRegs.erase(Reg);
183 if (ChangedToImpDef) {
184 // Backtrack to process this new implicit_def.
187 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
188 MachineOperand& MO = MI->getOperand(i);
189 if (!MO.isReg() || !MO.isDef())
191 ImpDefRegs.erase(MO.getReg());
196 // Any outstanding liveout implicit_def's?
197 for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) {
198 MachineInstr *MI = ImpDefMIs[i];
199 unsigned Reg = MI->getOperand(0).getReg();
200 if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
201 !ImpDefRegs.count(Reg)) {
202 // Delete all "local" implicit_def's. That include those which define
203 // physical registers since they cannot be liveout.
204 MI->eraseFromParent();
208 // If there are multiple defs of the same register and at least one
209 // is not an implicit_def, do not insert implicit_def's before the
212 for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg),
213 DE = mri_->def_end(); DI != DE; ++DI) {
214 if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) {
222 // The only implicit_def which we want to keep are those that are live
224 MI->eraseFromParent();
226 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
227 UE = mri_->use_end(); UI != UE; ) {
228 MachineOperand &RMO = UI.getOperand();
229 MachineInstr *RMI = &*UI;
231 MachineBasicBlock *RMBB = RMI->getParent();
235 // Turn a copy use into an implicit_def.
236 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
237 if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
239 RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
240 for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j)
241 RMI->RemoveOperand(j);
245 const TargetRegisterClass* RC = mri_->getRegClass(Reg);
246 unsigned NewVReg = mri_->createVirtualRegister(RC);
257 void LiveIntervals::computeNumbering() {
258 Index2MiMap OldI2MI = i2miMap_;
259 std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap;
265 terminatorGaps.clear();
269 // Number MachineInstrs and MachineBasicBlocks.
270 // Initialize MBB indexes to a sentinal.
271 MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
273 unsigned MIIndex = 0;
274 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
276 unsigned StartIdx = MIIndex;
278 // Insert an empty slot at the beginning of each block.
279 MIIndex += InstrSlots::NUM;
280 i2miMap_.push_back(0);
282 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
285 if (I == MBB->getFirstTerminator()) {
286 // Leave a gap for before terminators, this is where we will point
289 terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
291 "Multiple 'first' terminators encountered during numbering.");
292 inserted = inserted; // Avoid compiler warning if assertions turned off.
293 i2miMap_.push_back(0);
295 MIIndex += InstrSlots::NUM;
298 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
299 assert(inserted && "multiple MachineInstr -> index mappings");
301 i2miMap_.push_back(I);
302 MIIndex += InstrSlots::NUM;
305 // Insert max(1, numdefs) empty slots after every instruction.
306 unsigned Slots = I->getDesc().getNumDefs();
309 MIIndex += InstrSlots::NUM * Slots;
311 i2miMap_.push_back(0);
314 if (MBB->getFirstTerminator() == MBB->end()) {
315 // Leave a gap for before terminators, this is where we will point
318 terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
320 "Multiple 'first' terminators encountered during numbering.");
321 inserted = inserted; // Avoid compiler warning if assertions turned off.
322 i2miMap_.push_back(0);
324 MIIndex += InstrSlots::NUM;
327 // Set the MBB2IdxMap entry for this MBB.
328 MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
329 Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
332 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
334 if (!OldI2MI.empty())
335 for (iterator OI = begin(), OE = end(); OI != OE; ++OI) {
336 for (LiveInterval::iterator LI = OI->second->begin(),
337 LE = OI->second->end(); LI != LE; ++LI) {
339 // Remap the start index of the live range to the corresponding new
340 // number, or our best guess at what it _should_ correspond to if the
341 // original instruction has been erased. This is either the following
342 // instruction or its predecessor.
343 unsigned index = LI->start / InstrSlots::NUM;
344 unsigned offset = LI->start % InstrSlots::NUM;
345 if (offset == InstrSlots::LOAD) {
346 std::vector<IdxMBBPair>::const_iterator I =
347 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start);
348 // Take the pair containing the index
349 std::vector<IdxMBBPair>::const_iterator J =
350 (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
352 LI->start = getMBBStartIdx(J->second);
354 LI->start = mi2iMap_[OldI2MI[index]] + offset;
357 // Remap the ending index in the same way that we remapped the start,
358 // except for the final step where we always map to the immediately
359 // following instruction.
360 index = (LI->end - 1) / InstrSlots::NUM;
361 offset = LI->end % InstrSlots::NUM;
362 if (offset == InstrSlots::LOAD) {
363 // VReg dies at end of block.
364 std::vector<IdxMBBPair>::const_iterator I =
365 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end);
368 LI->end = getMBBEndIdx(I->second) + 1;
370 unsigned idx = index;
371 while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
373 if (index != OldI2MI.size())
374 LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0);
376 LI->end = InstrSlots::NUM * i2miMap_.size();
380 for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(),
381 VNE = OI->second->vni_end(); VNI != VNE; ++VNI) {
384 // Remap the VNInfo def index, which works the same as the
385 // start indices above. VN's with special sentinel defs
386 // don't need to be remapped.
387 if (vni->isDefAccurate() && !vni->isUnused()) {
388 unsigned index = vni->def / InstrSlots::NUM;
389 unsigned offset = vni->def % InstrSlots::NUM;
390 if (offset == InstrSlots::LOAD) {
391 std::vector<IdxMBBPair>::const_iterator I =
392 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def);
393 // Take the pair containing the index
394 std::vector<IdxMBBPair>::const_iterator J =
395 (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
397 vni->def = getMBBStartIdx(J->second);
399 vni->def = mi2iMap_[OldI2MI[index]] + offset;
403 // Remap the VNInfo kill indices, which works the same as
404 // the end indices above.
405 for (size_t i = 0; i < vni->kills.size(); ++i) {
406 unsigned killIdx = vni->kills[i].killIdx;
408 unsigned index = (killIdx - 1) / InstrSlots::NUM;
409 unsigned offset = killIdx % InstrSlots::NUM;
411 if (offset == InstrSlots::LOAD) {
412 assert("Value killed at a load slot.");
413 /*std::vector<IdxMBBPair>::const_iterator I =
414 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
417 vni->kills[i] = getMBBEndIdx(I->second);*/
419 if (vni->kills[i].isPHIKill) {
420 std::vector<IdxMBBPair>::const_iterator I =
421 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), index);
423 vni->kills[i].killIdx = terminatorGaps[I->second];
425 assert(OldI2MI[index] != 0 &&
426 "Kill refers to instruction not present in index maps.");
427 vni->kills[i].killIdx = mi2iMap_[OldI2MI[index]] + offset;
431 unsigned idx = index;
432 while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
434 if (index != OldI2MI.size())
435 vni->kills[i] = mi2iMap_[OldI2MI[index]] +
436 (idx == index ? offset : 0);
438 vni->kills[i] = InstrSlots::NUM * i2miMap_.size();
446 void LiveIntervals::scaleNumbering(int factor) {
448 // * scale MBB begin and end points
449 // * scale all ranges.
450 // * Update VNI structures.
451 // * Scale instruction numberings
453 // Scale the MBB indices.
455 for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end();
456 MBB != MBBE; ++MBB) {
457 std::pair<unsigned, unsigned> &mbbIndices = MBB2IdxMap[MBB->getNumber()];
458 mbbIndices.first = InstrSlots::scale(mbbIndices.first, factor);
459 mbbIndices.second = InstrSlots::scale(mbbIndices.second, factor);
460 Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB));
462 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
464 // Scale terminator gaps.
465 for (DenseMap<MachineBasicBlock*, unsigned>::iterator
466 TGI = terminatorGaps.begin(), TGE = terminatorGaps.end();
468 terminatorGaps[TGI->first] = InstrSlots::scale(TGI->second, factor);
471 // Scale the intervals.
472 for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
473 LI->second->scaleNumbering(factor);
476 // Scale MachineInstrs.
477 Mi2IndexMap oldmi2iMap = mi2iMap_;
478 unsigned highestSlot = 0;
479 for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end();
481 unsigned newSlot = InstrSlots::scale(MI->second, factor);
482 mi2iMap_[MI->first] = newSlot;
483 highestSlot = std::max(highestSlot, newSlot);
487 i2miMap_.resize(highestSlot + 1);
488 for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end();
490 i2miMap_[MI->second] = const_cast<MachineInstr *>(MI->first);
496 /// runOnMachineFunction - Register allocate the whole function
498 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
500 mri_ = &mf_->getRegInfo();
501 tm_ = &fn.getTarget();
502 tri_ = tm_->getRegisterInfo();
503 tii_ = tm_->getInstrInfo();
504 aa_ = &getAnalysis<AliasAnalysis>();
505 lv_ = &getAnalysis<LiveVariables>();
506 allocatableRegs_ = tri_->getAllocatableSet(fn);
508 processImplicitDefs();
512 numIntervals += getNumIntervals();
518 /// print - Implement the dump method.
519 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
520 OS << "********** INTERVALS **********\n";
521 for (const_iterator I = begin(), E = end(); I != E; ++I) {
522 I->second->print(OS, tri_);
526 OS << "********** MACHINEINSTRS **********\n";
528 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
529 mbbi != mbbe; ++mbbi) {
530 OS << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
531 for (MachineBasicBlock::iterator mii = mbbi->begin(),
532 mie = mbbi->end(); mii != mie; ++mii) {
533 OS << getInstructionIndex(mii) << '\t' << *mii;
538 /// conflictsWithPhysRegDef - Returns true if the specified register
539 /// is defined during the duration of the specified interval.
540 bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
541 VirtRegMap &vrm, unsigned reg) {
542 for (LiveInterval::Ranges::const_iterator
543 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
544 for (unsigned index = getBaseIndex(I->start),
545 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
546 index += InstrSlots::NUM) {
547 // skip deleted instructions
548 while (index != end && !getInstructionFromIndex(index))
549 index += InstrSlots::NUM;
550 if (index == end) break;
552 MachineInstr *MI = getInstructionFromIndex(index);
553 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
554 if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
555 if (SrcReg == li.reg || DstReg == li.reg)
557 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
558 MachineOperand& mop = MI->getOperand(i);
561 unsigned PhysReg = mop.getReg();
562 if (PhysReg == 0 || PhysReg == li.reg)
564 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
565 if (!vrm.hasPhys(PhysReg))
567 PhysReg = vrm.getPhys(PhysReg);
569 if (PhysReg && tri_->regsOverlap(PhysReg, reg))
578 /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except
579 /// it can check use as well.
580 bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li,
581 unsigned Reg, bool CheckUse,
582 SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
583 for (LiveInterval::Ranges::const_iterator
584 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
585 for (unsigned index = getBaseIndex(I->start),
586 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
587 index += InstrSlots::NUM) {
588 // Skip deleted instructions.
589 MachineInstr *MI = 0;
590 while (index != end) {
591 MI = getInstructionFromIndex(index);
594 index += InstrSlots::NUM;
596 if (index == end) break;
598 if (JoinedCopies.count(MI))
600 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
601 MachineOperand& MO = MI->getOperand(i);
604 if (MO.isUse() && !CheckUse)
606 unsigned PhysReg = MO.getReg();
607 if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg))
609 if (tri_->isSubRegister(Reg, PhysReg))
619 void LiveIntervals::printRegName(unsigned reg) const {
620 if (TargetRegisterInfo::isPhysicalRegister(reg))
621 errs() << tri_->getName(reg);
623 errs() << "%reg" << reg;
626 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
627 MachineBasicBlock::iterator mi,
628 unsigned MIIdx, MachineOperand& MO,
630 LiveInterval &interval) {
632 errs() << "\t\tregister: ";
633 printRegName(interval.reg);
636 // Virtual registers may be defined multiple times (due to phi
637 // elimination and 2-addr elimination). Much of what we do only has to be
638 // done once for the vreg. We use an empty interval to detect the first
639 // time we see a vreg.
640 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
641 if (interval.empty()) {
642 // Get the Idx of the defining instructions.
643 unsigned defIndex = getDefIndex(MIIdx);
644 // Earlyclobbers move back one.
645 if (MO.isEarlyClobber())
646 defIndex = getUseIndex(MIIdx);
648 MachineInstr *CopyMI = NULL;
649 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
650 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
651 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
652 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
653 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
655 // Earlyclobbers move back one.
656 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
658 assert(ValNo->id == 0 && "First value in interval is not 0?");
660 // Loop over all of the blocks that the vreg is defined in. There are
661 // two cases we have to handle here. The most common case is a vreg
662 // whose lifetime is contained within a basic block. In this case there
663 // will be a single kill, in MBB, which comes after the definition.
664 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
665 // FIXME: what about dead vars?
667 if (vi.Kills[0] != mi)
668 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
670 killIdx = defIndex+1;
672 // If the kill happens after the definition, we have an intra-block
674 if (killIdx > defIndex) {
675 assert(vi.AliveBlocks.empty() &&
676 "Shouldn't be alive across any blocks!");
677 LiveRange LR(defIndex, killIdx, ValNo);
678 interval.addRange(LR);
679 DEBUG(errs() << " +" << LR << "\n");
680 interval.addKill(ValNo, killIdx, false);
685 // The other case we handle is when a virtual register lives to the end
686 // of the defining block, potentially live across some blocks, then is
687 // live into some number of blocks, but gets killed. Start by adding a
688 // range that goes from this definition to the end of the defining block.
689 LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo);
690 DEBUG(errs() << " +" << NewLR);
691 interval.addRange(NewLR);
693 // Iterate over all of the blocks that the variable is completely
694 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
696 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
697 E = vi.AliveBlocks.end(); I != E; ++I) {
698 LiveRange LR(getMBBStartIdx(*I),
699 getMBBEndIdx(*I)+1, // MBB ends at -1.
701 interval.addRange(LR);
702 DEBUG(errs() << " +" << LR);
705 // Finally, this virtual register is live from the start of any killing
706 // block to the 'use' slot of the killing instruction.
707 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
708 MachineInstr *Kill = vi.Kills[i];
709 unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
710 LiveRange LR(getMBBStartIdx(Kill->getParent()),
712 interval.addRange(LR);
713 interval.addKill(ValNo, killIdx, false);
714 DEBUG(errs() << " +" << LR);
718 // If this is the second time we see a virtual register definition, it
719 // must be due to phi elimination or two addr elimination. If this is
720 // the result of two address elimination, then the vreg is one of the
721 // def-and-use register operand.
722 if (mi->isRegTiedToUseOperand(MOIdx)) {
723 // If this is a two-address definition, then we have already processed
724 // the live range. The only problem is that we didn't realize there
725 // are actually two values in the live interval. Because of this we
726 // need to take the LiveRegion that defines this register and split it
728 assert(interval.containsOneValue());
729 unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
730 unsigned RedefIndex = getDefIndex(MIIdx);
731 if (MO.isEarlyClobber())
732 RedefIndex = getUseIndex(MIIdx);
734 const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
735 VNInfo *OldValNo = OldLR->valno;
737 // Delete the initial value, which should be short and continuous,
738 // because the 2-addr copy must be in the same MBB as the redef.
739 interval.removeRange(DefIndex, RedefIndex);
741 // Two-address vregs should always only be redefined once. This means
742 // that at this point, there should be exactly one value number in it.
743 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
745 // The new value number (#1) is defined by the instruction we claimed
747 VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(),
748 false, // update at *
750 ValNo->setFlags(OldValNo->getFlags()); // * <- updating here
752 // Value#0 is now defined by the 2-addr instruction.
753 OldValNo->def = RedefIndex;
754 OldValNo->setCopy(0);
755 if (MO.isEarlyClobber())
756 OldValNo->setHasRedefByEC(true);
758 // Add the new live interval which replaces the range for the input copy.
759 LiveRange LR(DefIndex, RedefIndex, ValNo);
760 DEBUG(errs() << " replace range with " << LR);
761 interval.addRange(LR);
762 interval.addKill(ValNo, RedefIndex, false);
764 // If this redefinition is dead, we need to add a dummy unit live
765 // range covering the def slot.
767 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
770 errs() << " RESULT: ";
771 interval.print(errs(), tri_);
774 // Otherwise, this must be because of phi elimination. If this is the
775 // first redefinition of the vreg that we have seen, go back and change
776 // the live range in the PHI block to be a different value number.
777 if (interval.containsOneValue()) {
778 assert(vi.Kills.size() == 1 &&
779 "PHI elimination vreg should have one kill, the PHI itself!");
781 // Remove the old range that we now know has an incorrect number.
782 VNInfo *VNI = interval.getValNumInfo(0);
783 MachineInstr *Killer = vi.Kills[0];
784 unsigned Start = getMBBStartIdx(Killer->getParent());
785 unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
787 errs() << " Removing [" << Start << "," << End << "] from: ";
788 interval.print(errs(), tri_);
791 interval.removeRange(Start, End);
792 assert(interval.ranges.size() == 1 &&
793 "newly discovered PHI interval has >1 ranges.");
794 MachineBasicBlock *killMBB = getMBBFromIndex(interval.endNumber());
795 interval.addKill(VNI, terminatorGaps[killMBB], true);
796 VNI->setHasPHIKill(true);
798 errs() << " RESULT: ";
799 interval.print(errs(), tri_);
802 // Replace the interval with one of a NEW value number. Note that this
803 // value number isn't actually defined by an instruction, weird huh? :)
804 LiveRange LR(Start, End,
805 interval.getNextValue(mbb->getNumber(), 0, false, VNInfoAllocator));
806 LR.valno->setIsPHIDef(true);
807 DEBUG(errs() << " replace range with " << LR);
808 interval.addRange(LR);
809 interval.addKill(LR.valno, End, false);
811 errs() << " RESULT: ";
812 interval.print(errs(), tri_);
816 // In the case of PHI elimination, each variable definition is only
817 // live until the end of the block. We've already taken care of the
818 // rest of the live range.
819 unsigned defIndex = getDefIndex(MIIdx);
820 if (MO.isEarlyClobber())
821 defIndex = getUseIndex(MIIdx);
824 MachineInstr *CopyMI = NULL;
825 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
826 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
827 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
828 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
829 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
831 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
833 unsigned killIndex = getMBBEndIdx(mbb) + 1;
834 LiveRange LR(defIndex, killIndex, ValNo);
835 interval.addRange(LR);
836 interval.addKill(ValNo, terminatorGaps[mbb], true);
837 ValNo->setHasPHIKill(true);
838 DEBUG(errs() << " +" << LR);
842 DEBUG(errs() << '\n');
845 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
846 MachineBasicBlock::iterator mi,
849 LiveInterval &interval,
850 MachineInstr *CopyMI) {
851 // A physical register cannot be live across basic block, so its
852 // lifetime must end somewhere in its defining basic block.
854 errs() << "\t\tregister: ";
855 printRegName(interval.reg);
858 unsigned baseIndex = MIIdx;
859 unsigned start = getDefIndex(baseIndex);
860 // Earlyclobbers move back one.
861 if (MO.isEarlyClobber())
862 start = getUseIndex(MIIdx);
863 unsigned end = start;
865 // If it is not used after definition, it is considered dead at
866 // the instruction defining it. Hence its interval is:
867 // [defSlot(def), defSlot(def)+1)
869 DEBUG(errs() << " dead");
874 // If it is not dead on definition, it must be killed by a
875 // subsequent instruction. Hence its interval is:
876 // [defSlot(def), useSlot(kill)+1)
877 baseIndex += InstrSlots::NUM;
878 while (++mi != MBB->end()) {
879 while (baseIndex / InstrSlots::NUM < i2miMap_.size() &&
880 getInstructionFromIndex(baseIndex) == 0)
881 baseIndex += InstrSlots::NUM;
882 if (mi->killsRegister(interval.reg, tri_)) {
883 DEBUG(errs() << " killed");
884 end = getUseIndex(baseIndex) + 1;
887 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_);
889 if (mi->isRegTiedToUseOperand(DefIdx)) {
890 // Two-address instruction.
891 end = getDefIndex(baseIndex);
892 if (mi->getOperand(DefIdx).isEarlyClobber())
893 end = getUseIndex(baseIndex);
895 // Another instruction redefines the register before it is ever read.
896 // Then the register is essentially dead at the instruction that defines
897 // it. Hence its interval is:
898 // [defSlot(def), defSlot(def)+1)
899 DEBUG(errs() << " dead");
906 baseIndex += InstrSlots::NUM;
909 // The only case we should have a dead physreg here without a killing or
910 // instruction where we know it's dead is if it is live-in to the function
911 // and never used. Another possible case is the implicit use of the
912 // physical register has been deleted by two-address pass.
916 assert(start < end && "did not find end of interval?");
918 // Already exists? Extend old live interval.
919 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
920 bool Extend = OldLR != interval.end();
921 VNInfo *ValNo = Extend
922 ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator);
923 if (MO.isEarlyClobber() && Extend)
924 ValNo->setHasRedefByEC(true);
925 LiveRange LR(start, end, ValNo);
926 interval.addRange(LR);
927 interval.addKill(LR.valno, end, false);
928 DEBUG(errs() << " +" << LR << '\n');
931 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
932 MachineBasicBlock::iterator MI,
936 if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
937 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
938 getOrCreateInterval(MO.getReg()));
939 else if (allocatableRegs_[MO.getReg()]) {
940 MachineInstr *CopyMI = NULL;
941 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
942 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
943 MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
944 MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
945 tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
947 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
948 getOrCreateInterval(MO.getReg()), CopyMI);
949 // Def of a register also defines its sub-registers.
950 for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS)
951 // If MI also modifies the sub-register explicitly, avoid processing it
952 // more than once. Do not pass in TRI here so it checks for exact match.
953 if (!MI->modifiesRegister(*AS))
954 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
955 getOrCreateInterval(*AS), 0);
959 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
961 LiveInterval &interval, bool isAlias) {
963 errs() << "\t\tlivein register: ";
964 printRegName(interval.reg);
967 // Look for kills, if it reaches a def before it's killed, then it shouldn't
968 // be considered a livein.
969 MachineBasicBlock::iterator mi = MBB->begin();
970 unsigned baseIndex = MIIdx;
971 unsigned start = baseIndex;
972 while (baseIndex / InstrSlots::NUM < i2miMap_.size() &&
973 getInstructionFromIndex(baseIndex) == 0)
974 baseIndex += InstrSlots::NUM;
975 unsigned end = baseIndex;
976 bool SeenDefUse = false;
978 while (mi != MBB->end()) {
979 if (mi->killsRegister(interval.reg, tri_)) {
980 DEBUG(errs() << " killed");
981 end = getUseIndex(baseIndex) + 1;
984 } else if (mi->modifiesRegister(interval.reg, tri_)) {
985 // Another instruction redefines the register before it is ever read.
986 // Then the register is essentially dead at the instruction that defines
987 // it. Hence its interval is:
988 // [defSlot(def), defSlot(def)+1)
989 DEBUG(errs() << " dead");
990 end = getDefIndex(start) + 1;
995 baseIndex += InstrSlots::NUM;
997 if (mi != MBB->end()) {
998 while (baseIndex / InstrSlots::NUM < i2miMap_.size() &&
999 getInstructionFromIndex(baseIndex) == 0)
1000 baseIndex += InstrSlots::NUM;
1004 // Live-in register might not be used at all.
1007 DEBUG(errs() << " dead");
1008 end = getDefIndex(MIIdx) + 1;
1010 DEBUG(errs() << " live through");
1016 interval.getNextValue(MBB->getNumber(), 0, false, VNInfoAllocator);
1017 vni->setIsPHIDef(true);
1018 LiveRange LR(start, end, vni);
1020 interval.addRange(LR);
1021 interval.addKill(LR.valno, end, false);
1022 DEBUG(errs() << " +" << LR << '\n');
1025 /// computeIntervals - computes the live intervals for virtual
1026 /// registers. for some ordering of the machine instructions [1,N] a
1027 /// live interval is an interval [i, j) where 1 <= i <= j < N for
1028 /// which a variable is live
1029 void LiveIntervals::computeIntervals() {
1030 DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n"
1031 << "********** Function: "
1032 << ((Value*)mf_->getFunction())->getName() << '\n');
1034 SmallVector<unsigned, 8> UndefUses;
1035 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
1036 MBBI != E; ++MBBI) {
1037 MachineBasicBlock *MBB = MBBI;
1038 // Track the index of the current machine instr.
1039 unsigned MIIndex = getMBBStartIdx(MBB);
1040 DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
1042 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
1044 // Create intervals for live-ins to this BB first.
1045 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
1046 LE = MBB->livein_end(); LI != LE; ++LI) {
1047 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
1048 // Multiple live-ins can alias the same register.
1049 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
1050 if (!hasInterval(*AS))
1051 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
1055 // Skip over empty initial indices.
1056 while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
1057 getInstructionFromIndex(MIIndex) == 0)
1058 MIIndex += InstrSlots::NUM;
1060 for (; MI != miEnd; ++MI) {
1061 DEBUG(errs() << MIIndex << "\t" << *MI);
1064 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
1065 MachineOperand &MO = MI->getOperand(i);
1066 if (!MO.isReg() || !MO.getReg())
1069 // handle register defs - build intervals
1071 handleRegisterDef(MBB, MI, MIIndex, MO, i);
1072 else if (MO.isUndef())
1073 UndefUses.push_back(MO.getReg());
1076 // Skip over the empty slots after each instruction.
1077 unsigned Slots = MI->getDesc().getNumDefs();
1080 MIIndex += InstrSlots::NUM * Slots;
1082 // Skip over empty indices.
1083 while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
1084 getInstructionFromIndex(MIIndex) == 0)
1085 MIIndex += InstrSlots::NUM;
1089 // Create empty intervals for registers defined by implicit_def's (except
1090 // for those implicit_def that define values which are liveout of their
1092 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
1093 unsigned UndefReg = UndefUses[i];
1094 (void)getOrCreateInterval(UndefReg);
1098 bool LiveIntervals::findLiveInMBBs(unsigned Start, unsigned End,
1099 SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
1100 std::vector<IdxMBBPair>::const_iterator I =
1101 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
1103 bool ResVal = false;
1104 while (I != Idx2MBBMap.end()) {
1105 if (I->first >= End)
1107 MBBs.push_back(I->second);
1114 bool LiveIntervals::findReachableMBBs(unsigned Start, unsigned End,
1115 SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
1116 std::vector<IdxMBBPair>::const_iterator I =
1117 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
1119 bool ResVal = false;
1120 while (I != Idx2MBBMap.end()) {
1123 MachineBasicBlock *MBB = I->second;
1124 if (getMBBEndIdx(MBB) > End)
1126 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
1127 SE = MBB->succ_end(); SI != SE; ++SI)
1128 MBBs.push_back(*SI);
1135 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
1136 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
1137 return new LiveInterval(reg, Weight);
1140 /// dupInterval - Duplicate a live interval. The caller is responsible for
1141 /// managing the allocated memory.
1142 LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
1143 LiveInterval *NewLI = createInterval(li->reg);
1144 NewLI->Copy(*li, mri_, getVNInfoAllocator());
1148 /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
1149 /// copy field and returns the source register that defines it.
1150 unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const {
1151 if (!VNI->getCopy())
1154 if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
1155 // If it's extracting out of a physical register, return the sub-register.
1156 unsigned Reg = VNI->getCopy()->getOperand(1).getReg();
1157 if (TargetRegisterInfo::isPhysicalRegister(Reg))
1158 Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm());
1160 } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
1161 VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
1162 return VNI->getCopy()->getOperand(2).getReg();
1164 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
1165 if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg))
1167 llvm_unreachable("Unrecognized copy instruction!");
1171 //===----------------------------------------------------------------------===//
1172 // Register allocator hooks.
1175 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
1176 /// allow one) virtual register operand, then its uses are implicitly using
1177 /// the register. Returns the virtual register.
1178 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
1179 MachineInstr *MI) const {
1181 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1182 MachineOperand &MO = MI->getOperand(i);
1183 if (!MO.isReg() || !MO.isUse())
1185 unsigned Reg = MO.getReg();
1186 if (Reg == 0 || Reg == li.reg)
1189 if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
1190 !allocatableRegs_[Reg])
1192 // FIXME: For now, only remat MI with at most one register operand.
1194 "Can't rematerialize instruction with multiple register operand!");
1195 RegOp = MO.getReg();
1203 /// isValNoAvailableAt - Return true if the val# of the specified interval
1204 /// which reaches the given instruction also reaches the specified use index.
1205 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
1206 unsigned UseIdx) const {
1207 unsigned Index = getInstructionIndex(MI);
1208 VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
1209 LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
1210 return UI != li.end() && UI->valno == ValNo;
1213 /// isReMaterializable - Returns true if the definition MI of the specified
1214 /// val# of the specified interval is re-materializable.
1215 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1216 const VNInfo *ValNo, MachineInstr *MI,
1217 SmallVectorImpl<LiveInterval*> &SpillIs,
1222 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
1226 if (tii_->isLoadFromStackSlot(MI, FrameIdx) &&
1227 mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
1228 // FIXME: Let target specific isReallyTriviallyReMaterializable determines
1229 // this but remember this is not safe to fold into a two-address
1231 // This is a load from fixed stack slot. It can be rematerialized.
1234 // If the target-specific rules don't identify an instruction as
1235 // being trivially rematerializable, use some target-independent
1237 if (!MI->getDesc().isRematerializable() ||
1238 !tii_->isTriviallyReMaterializable(MI)) {
1239 if (!EnableAggressiveRemat)
1242 // If the instruction accesses memory but the memoperands have been lost,
1243 // we can't analyze it.
1244 const TargetInstrDesc &TID = MI->getDesc();
1245 if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty())
1248 // Avoid instructions obviously unsafe for remat.
1249 if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable())
1252 // If the instruction accesses memory and the memory could be non-constant,
1253 // assume the instruction is not rematerializable.
1254 for (std::list<MachineMemOperand>::const_iterator
1255 I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){
1256 const MachineMemOperand &MMO = *I;
1257 if (MMO.isVolatile() || MMO.isStore())
1259 const Value *V = MMO.getValue();
1262 if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
1263 if (!PSV->isConstant(mf_->getFrameInfo()))
1265 } else if (!aa_->pointsToConstantMemory(V))
1269 // If any of the registers accessed are non-constant, conservatively assume
1270 // the instruction is not rematerializable.
1271 unsigned ImpUse = 0;
1272 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1273 const MachineOperand &MO = MI->getOperand(i);
1275 unsigned Reg = MO.getReg();
1278 if (TargetRegisterInfo::isPhysicalRegister(Reg))
1281 // Only allow one def, and that in the first operand.
1282 if (MO.isDef() != (i == 0))
1285 // Only allow constant-valued registers.
1286 bool IsLiveIn = mri_->isLiveIn(Reg);
1287 MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg),
1288 E = mri_->def_end();
1290 // For the def, it should be the only def of that register.
1291 if (MO.isDef() && (next(I) != E || IsLiveIn))
1295 // Only allow one use other register use, as that's all the
1296 // remat mechanisms support currently.
1297 if (Reg != li.reg) {
1300 else if (Reg != ImpUse)
1303 // For the use, there should be only one associated def.
1304 if (I != E && (next(I) != E || IsLiveIn))
1311 unsigned ImpUse = getReMatImplicitUse(li, MI);
1313 const LiveInterval &ImpLi = getInterval(ImpUse);
1314 for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg),
1315 re = mri_->use_end(); ri != re; ++ri) {
1316 MachineInstr *UseMI = &*ri;
1317 unsigned UseIdx = getInstructionIndex(UseMI);
1318 if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
1320 if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
1324 // If a register operand of the re-materialized instruction is going to
1325 // be spilled next, then it's not legal to re-materialize this instruction.
1326 for (unsigned i = 0, e = SpillIs.size(); i != e; ++i)
1327 if (ImpUse == SpillIs[i]->reg)
1333 /// isReMaterializable - Returns true if the definition MI of the specified
1334 /// val# of the specified interval is re-materializable.
1335 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1336 const VNInfo *ValNo, MachineInstr *MI) {
1337 SmallVector<LiveInterval*, 4> Dummy1;
1339 return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2);
1342 /// isReMaterializable - Returns true if every definition of MI of every
1343 /// val# of the specified interval is re-materializable.
1344 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1345 SmallVectorImpl<LiveInterval*> &SpillIs,
1348 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1350 const VNInfo *VNI = *i;
1351 if (VNI->isUnused())
1352 continue; // Dead val#.
1353 // Is the def for the val# rematerializable?
1354 if (!VNI->isDefAccurate())
1356 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1357 bool DefIsLoad = false;
1359 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
1361 isLoad |= DefIsLoad;
1366 /// FilterFoldedOps - Filter out two-address use operands. Return
1367 /// true if it finds any issue with the operands that ought to prevent
1369 static bool FilterFoldedOps(MachineInstr *MI,
1370 SmallVector<unsigned, 2> &Ops,
1372 SmallVector<unsigned, 2> &FoldOps) {
1374 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1375 unsigned OpIdx = Ops[i];
1376 MachineOperand &MO = MI->getOperand(OpIdx);
1377 // FIXME: fold subreg use.
1381 MRInfo |= (unsigned)VirtRegMap::isMod;
1383 // Filter out two-address use operand(s).
1384 if (MI->isRegTiedToDefOperand(OpIdx)) {
1385 MRInfo = VirtRegMap::isModRef;
1388 MRInfo |= (unsigned)VirtRegMap::isRef;
1390 FoldOps.push_back(OpIdx);
1396 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
1397 /// slot / to reg or any rematerialized load into ith operand of specified
1398 /// MI. If it is successul, MI is updated with the newly created MI and
1400 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
1401 VirtRegMap &vrm, MachineInstr *DefMI,
1403 SmallVector<unsigned, 2> &Ops,
1404 bool isSS, int Slot, unsigned Reg) {
1405 // If it is an implicit def instruction, just delete it.
1406 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
1407 RemoveMachineInstrFromMaps(MI);
1408 vrm.RemoveMachineInstrFromMaps(MI);
1409 MI->eraseFromParent();
1414 // Filter the list of operand indexes that are to be folded. Abort if
1415 // any operand will prevent folding.
1416 unsigned MRInfo = 0;
1417 SmallVector<unsigned, 2> FoldOps;
1418 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1421 // The only time it's safe to fold into a two address instruction is when
1422 // it's folding reload and spill from / into a spill stack slot.
1423 if (DefMI && (MRInfo & VirtRegMap::isMod))
1426 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
1427 : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
1429 // Remember this instruction uses the spill slot.
1430 if (isSS) vrm.addSpillSlotUse(Slot, fmi);
1432 // Attempt to fold the memory reference into the instruction. If
1433 // we can do this, we don't need to insert spill code.
1434 MachineBasicBlock &MBB = *MI->getParent();
1435 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
1436 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
1437 vrm.transferSpillPts(MI, fmi);
1438 vrm.transferRestorePts(MI, fmi);
1439 vrm.transferEmergencySpills(MI, fmi);
1441 i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
1442 mi2iMap_[fmi] = InstrIdx;
1443 MI = MBB.insert(MBB.erase(MI), fmi);
1450 /// canFoldMemoryOperand - Returns true if the specified load / store
1451 /// folding is possible.
1452 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
1453 SmallVector<unsigned, 2> &Ops,
1455 // Filter the list of operand indexes that are to be folded. Abort if
1456 // any operand will prevent folding.
1457 unsigned MRInfo = 0;
1458 SmallVector<unsigned, 2> FoldOps;
1459 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1462 // It's only legal to remat for a use, not a def.
1463 if (ReMat && (MRInfo & VirtRegMap::isMod))
1466 return tii_->canFoldMemoryOperand(MI, FoldOps);
1469 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
1470 SmallPtrSet<MachineBasicBlock*, 4> MBBs;
1471 for (LiveInterval::Ranges::const_iterator
1472 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1473 std::vector<IdxMBBPair>::const_iterator II =
1474 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
1475 if (II == Idx2MBBMap.end())
1477 if (I->end > II->first) // crossing a MBB.
1479 MBBs.insert(II->second);
1480 if (MBBs.size() > 1)
1486 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
1487 /// interval on to-be re-materialized operands of MI) with new register.
1488 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
1489 MachineInstr *MI, unsigned NewVReg,
1491 // There is an implicit use. That means one of the other operand is
1492 // being remat'ed and the remat'ed instruction has li.reg as an
1493 // use operand. Make sure we rewrite that as well.
1494 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1495 MachineOperand &MO = MI->getOperand(i);
1498 unsigned Reg = MO.getReg();
1499 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
1501 if (!vrm.isReMaterialized(Reg))
1503 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
1504 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
1506 UseMO->setReg(NewVReg);
1510 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
1511 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
1512 bool LiveIntervals::
1513 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
1514 bool TrySplit, unsigned index, unsigned end, MachineInstr *MI,
1515 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1516 unsigned Slot, int LdSlot,
1517 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1519 const TargetRegisterClass* rc,
1520 SmallVector<int, 4> &ReMatIds,
1521 const MachineLoopInfo *loopInfo,
1522 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
1523 DenseMap<unsigned,unsigned> &MBBVRegsMap,
1524 std::vector<LiveInterval*> &NewLIs) {
1525 bool CanFold = false;
1527 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1528 MachineOperand& mop = MI->getOperand(i);
1531 unsigned Reg = mop.getReg();
1532 unsigned RegI = Reg;
1533 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
1538 bool TryFold = !DefIsReMat;
1539 bool FoldSS = true; // Default behavior unless it's a remat.
1540 int FoldSlot = Slot;
1542 // If this is the rematerializable definition MI itself and
1543 // all of its uses are rematerialized, simply delete it.
1544 if (MI == ReMatOrigDefMI && CanDelete) {
1545 DEBUG(errs() << "\t\t\t\tErasing re-materlizable def: "
1547 RemoveMachineInstrFromMaps(MI);
1548 vrm.RemoveMachineInstrFromMaps(MI);
1549 MI->eraseFromParent();
1553 // If def for this use can't be rematerialized, then try folding.
1554 // If def is rematerializable and it's a load, also try folding.
1555 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1557 // Try fold loads (from stack slot, constant pool, etc.) into uses.
1563 // Scan all of the operands of this instruction rewriting operands
1564 // to use NewVReg instead of li.reg as appropriate. We do this for
1567 // 1. If the instr reads the same spilled vreg multiple times, we
1568 // want to reuse the NewVReg.
1569 // 2. If the instr is a two-addr instruction, we are required to
1570 // keep the src/dst regs pinned.
1572 // Keep track of whether we replace a use and/or def so that we can
1573 // create the spill interval with the appropriate range.
1575 HasUse = mop.isUse();
1576 HasDef = mop.isDef();
1577 SmallVector<unsigned, 2> Ops;
1579 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
1580 const MachineOperand &MOj = MI->getOperand(j);
1583 unsigned RegJ = MOj.getReg();
1584 if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
1588 if (!MOj.isUndef()) {
1589 HasUse |= MOj.isUse();
1590 HasDef |= MOj.isDef();
1595 // Create a new virtual register for the spill interval.
1596 // Create the new register now so we can map the fold instruction
1597 // to the new register so when it is unfolded we get the correct
1599 bool CreatedNewVReg = false;
1601 NewVReg = mri_->createVirtualRegister(rc);
1603 CreatedNewVReg = true;
1609 // Do not fold load / store here if we are splitting. We'll find an
1610 // optimal point to insert a load / store later.
1612 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1613 Ops, FoldSS, FoldSlot, NewVReg)) {
1614 // Folding the load/store can completely change the instruction in
1615 // unpredictable ways, rescan it from the beginning.
1618 // We need to give the new vreg the same stack slot as the
1619 // spilled interval.
1620 vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
1626 if (isNotInMIMap(MI))
1628 goto RestartInstruction;
1631 // We'll try to fold it later if it's profitable.
1632 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1636 mop.setReg(NewVReg);
1637 if (mop.isImplicit())
1638 rewriteImplicitOps(li, MI, NewVReg, vrm);
1640 // Reuse NewVReg for other reads.
1641 for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1642 MachineOperand &mopj = MI->getOperand(Ops[j]);
1643 mopj.setReg(NewVReg);
1644 if (mopj.isImplicit())
1645 rewriteImplicitOps(li, MI, NewVReg, vrm);
1648 if (CreatedNewVReg) {
1650 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
1651 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1652 // Each valnum may have its own remat id.
1653 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1655 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1657 if (!CanDelete || (HasUse && HasDef)) {
1658 // If this is a two-addr instruction then its use operands are
1659 // rematerializable but its def is not. It should be assigned a
1661 vrm.assignVirt2StackSlot(NewVReg, Slot);
1664 vrm.assignVirt2StackSlot(NewVReg, Slot);
1666 } else if (HasUse && HasDef &&
1667 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1668 // If this interval hasn't been assigned a stack slot (because earlier
1669 // def is a deleted remat def), do it now.
1670 assert(Slot != VirtRegMap::NO_STACK_SLOT);
1671 vrm.assignVirt2StackSlot(NewVReg, Slot);
1674 // Re-matting an instruction with virtual register use. Add the
1675 // register as an implicit use on the use MI.
1676 if (DefIsReMat && ImpUse)
1677 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1679 // Create a new register interval for this spill / remat.
1680 LiveInterval &nI = getOrCreateInterval(NewVReg);
1681 if (CreatedNewVReg) {
1682 NewLIs.push_back(&nI);
1683 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1685 vrm.setIsSplitFromReg(NewVReg, li.reg);
1689 if (CreatedNewVReg) {
1690 LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
1691 nI.getNextValue(0, 0, false, VNInfoAllocator));
1692 DEBUG(errs() << " +" << LR);
1695 // Extend the split live interval to this def / use.
1696 unsigned End = getUseIndex(index)+1;
1697 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1698 nI.getValNumInfo(nI.getNumValNums()-1));
1699 DEBUG(errs() << " +" << LR);
1704 LiveRange LR(getDefIndex(index), getStoreIndex(index),
1705 nI.getNextValue(0, 0, false, VNInfoAllocator));
1706 DEBUG(errs() << " +" << LR);
1711 errs() << "\t\t\t\tAdded new interval: ";
1712 nI.print(errs(), tri_);
1718 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1720 MachineBasicBlock *MBB, unsigned Idx) const {
1721 unsigned End = getMBBEndIdx(MBB);
1722 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
1723 if (VNI->kills[j].isPHIKill)
1726 unsigned KillIdx = VNI->kills[j].killIdx;
1727 if (KillIdx > Idx && KillIdx < End)
1733 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1734 /// during spilling.
1736 struct RewriteInfo {
1741 RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
1742 : Index(i), MI(mi), HasUse(u), HasDef(d) {}
1745 struct RewriteInfoCompare {
1746 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1747 return LHS.Index < RHS.Index;
1752 void LiveIntervals::
1753 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1754 LiveInterval::Ranges::const_iterator &I,
1755 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1756 unsigned Slot, int LdSlot,
1757 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1759 const TargetRegisterClass* rc,
1760 SmallVector<int, 4> &ReMatIds,
1761 const MachineLoopInfo *loopInfo,
1762 BitVector &SpillMBBs,
1763 DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
1764 BitVector &RestoreMBBs,
1765 DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1766 DenseMap<unsigned,unsigned> &MBBVRegsMap,
1767 std::vector<LiveInterval*> &NewLIs) {
1768 bool AllCanFold = true;
1769 unsigned NewVReg = 0;
1770 unsigned start = getBaseIndex(I->start);
1771 unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
1773 // First collect all the def / use in this live range that will be rewritten.
1774 // Make sure they are sorted according to instruction index.
1775 std::vector<RewriteInfo> RewriteMIs;
1776 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1777 re = mri_->reg_end(); ri != re; ) {
1778 MachineInstr *MI = &*ri;
1779 MachineOperand &O = ri.getOperand();
1781 assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
1782 unsigned index = getInstructionIndex(MI);
1783 if (index < start || index >= end)
1787 // Must be defined by an implicit def. It should not be spilled. Note,
1788 // this is for correctness reason. e.g.
1789 // 8 %reg1024<def> = IMPLICIT_DEF
1790 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1791 // The live range [12, 14) are not part of the r1024 live interval since
1792 // it's defined by an implicit def. It will not conflicts with live
1793 // interval of r1025. Now suppose both registers are spilled, you can
1794 // easily see a situation where both registers are reloaded before
1795 // the INSERT_SUBREG and both target registers that would overlap.
1797 RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
1799 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1801 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1802 // Now rewrite the defs and uses.
1803 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1804 RewriteInfo &rwi = RewriteMIs[i];
1806 unsigned index = rwi.Index;
1807 bool MIHasUse = rwi.HasUse;
1808 bool MIHasDef = rwi.HasDef;
1809 MachineInstr *MI = rwi.MI;
1810 // If MI def and/or use the same register multiple times, then there
1811 // are multiple entries.
1812 unsigned NumUses = MIHasUse;
1813 while (i != e && RewriteMIs[i].MI == MI) {
1814 assert(RewriteMIs[i].Index == index);
1815 bool isUse = RewriteMIs[i].HasUse;
1816 if (isUse) ++NumUses;
1818 MIHasDef |= RewriteMIs[i].HasDef;
1821 MachineBasicBlock *MBB = MI->getParent();
1823 if (ImpUse && MI != ReMatDefMI) {
1824 // Re-matting an instruction with virtual register use. Update the
1825 // register interval's spill weight to HUGE_VALF to prevent it from
1827 LiveInterval &ImpLi = getInterval(ImpUse);
1828 ImpLi.weight = HUGE_VALF;
1831 unsigned MBBId = MBB->getNumber();
1832 unsigned ThisVReg = 0;
1834 DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
1835 if (NVI != MBBVRegsMap.end()) {
1836 ThisVReg = NVI->second;
1843 // It's better to start a new interval to avoid artifically
1844 // extend the new interval.
1845 if (MIHasDef && !MIHasUse) {
1846 MBBVRegsMap.erase(MBB->getNumber());
1852 bool IsNew = ThisVReg == 0;
1854 // This ends the previous live interval. If all of its def / use
1855 // can be folded, give it a low spill weight.
1856 if (NewVReg && TrySplit && AllCanFold) {
1857 LiveInterval &nI = getOrCreateInterval(NewVReg);
1864 bool HasDef = false;
1865 bool HasUse = false;
1866 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1867 index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1868 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1869 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1870 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
1871 if (!HasDef && !HasUse)
1874 AllCanFold &= CanFold;
1876 // Update weight of spill interval.
1877 LiveInterval &nI = getOrCreateInterval(NewVReg);
1879 // The spill weight is now infinity as it cannot be spilled again.
1880 nI.weight = HUGE_VALF;
1884 // Keep track of the last def and first use in each MBB.
1886 if (MI != ReMatOrigDefMI || !CanDelete) {
1887 bool HasKill = false;
1889 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
1891 // If this is a two-address code, then this index starts a new VNInfo.
1892 const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index));
1894 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
1896 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1897 SpillIdxes.find(MBBId);
1899 if (SII == SpillIdxes.end()) {
1900 std::vector<SRInfo> S;
1901 S.push_back(SRInfo(index, NewVReg, true));
1902 SpillIdxes.insert(std::make_pair(MBBId, S));
1903 } else if (SII->second.back().vreg != NewVReg) {
1904 SII->second.push_back(SRInfo(index, NewVReg, true));
1905 } else if ((int)index > SII->second.back().index) {
1906 // If there is an earlier def and this is a two-address
1907 // instruction, then it's not possible to fold the store (which
1908 // would also fold the load).
1909 SRInfo &Info = SII->second.back();
1911 Info.canFold = !HasUse;
1913 SpillMBBs.set(MBBId);
1914 } else if (SII != SpillIdxes.end() &&
1915 SII->second.back().vreg == NewVReg &&
1916 (int)index > SII->second.back().index) {
1917 // There is an earlier def that's not killed (must be two-address).
1918 // The spill is no longer needed.
1919 SII->second.pop_back();
1920 if (SII->second.empty()) {
1921 SpillIdxes.erase(MBBId);
1922 SpillMBBs.reset(MBBId);
1929 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1930 SpillIdxes.find(MBBId);
1931 if (SII != SpillIdxes.end() &&
1932 SII->second.back().vreg == NewVReg &&
1933 (int)index > SII->second.back().index)
1934 // Use(s) following the last def, it's not safe to fold the spill.
1935 SII->second.back().canFold = false;
1936 DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
1937 RestoreIdxes.find(MBBId);
1938 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1939 // If we are splitting live intervals, only fold if it's the first
1940 // use and there isn't another use later in the MBB.
1941 RII->second.back().canFold = false;
1943 // Only need a reload if there isn't an earlier def / use.
1944 if (RII == RestoreIdxes.end()) {
1945 std::vector<SRInfo> Infos;
1946 Infos.push_back(SRInfo(index, NewVReg, true));
1947 RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1949 RII->second.push_back(SRInfo(index, NewVReg, true));
1951 RestoreMBBs.set(MBBId);
1955 // Update spill weight.
1956 unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1957 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1960 if (NewVReg && TrySplit && AllCanFold) {
1961 // If all of its def / use can be folded, give it a low spill weight.
1962 LiveInterval &nI = getOrCreateInterval(NewVReg);
1967 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1968 BitVector &RestoreMBBs,
1969 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1970 if (!RestoreMBBs[Id])
1972 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1973 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1974 if (Restores[i].index == index &&
1975 Restores[i].vreg == vr &&
1976 Restores[i].canFold)
1981 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1982 BitVector &RestoreMBBs,
1983 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1984 if (!RestoreMBBs[Id])
1986 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1987 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1988 if (Restores[i].index == index && Restores[i].vreg)
1989 Restores[i].index = -1;
1992 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1993 /// spilled and create empty intervals for their uses.
1995 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1996 const TargetRegisterClass* rc,
1997 std::vector<LiveInterval*> &NewLIs) {
1998 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1999 re = mri_->reg_end(); ri != re; ) {
2000 MachineOperand &O = ri.getOperand();
2001 MachineInstr *MI = &*ri;
2004 assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
2005 "Register def was not rewritten?");
2006 RemoveMachineInstrFromMaps(MI);
2007 vrm.RemoveMachineInstrFromMaps(MI);
2008 MI->eraseFromParent();
2010 // This must be an use of an implicit_def so it's not part of the live
2011 // interval. Create a new empty live interval for it.
2012 // FIXME: Can we simply erase some of the instructions? e.g. Stores?
2013 unsigned NewVReg = mri_->createVirtualRegister(rc);
2015 vrm.setIsImplicitlyDefined(NewVReg);
2016 NewLIs.push_back(&getOrCreateInterval(NewVReg));
2017 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2018 MachineOperand &MO = MI->getOperand(i);
2019 if (MO.isReg() && MO.getReg() == li.reg) {
2028 std::vector<LiveInterval*> LiveIntervals::
2029 addIntervalsForSpillsFast(const LiveInterval &li,
2030 const MachineLoopInfo *loopInfo,
2032 unsigned slot = vrm.assignVirt2StackSlot(li.reg);
2034 std::vector<LiveInterval*> added;
2036 assert(li.weight != HUGE_VALF &&
2037 "attempt to spill already spilled interval!");
2040 errs() << "\t\t\t\tadding intervals for spills for interval: ";
2045 const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
2047 MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg);
2048 while (RI != mri_->reg_end()) {
2049 MachineInstr* MI = &*RI;
2051 SmallVector<unsigned, 2> Indices;
2052 bool HasUse = false;
2053 bool HasDef = false;
2055 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
2056 MachineOperand& mop = MI->getOperand(i);
2057 if (!mop.isReg() || mop.getReg() != li.reg) continue;
2059 HasUse |= MI->getOperand(i).isUse();
2060 HasDef |= MI->getOperand(i).isDef();
2062 Indices.push_back(i);
2065 if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI),
2066 Indices, true, slot, li.reg)) {
2067 unsigned NewVReg = mri_->createVirtualRegister(rc);
2069 vrm.assignVirt2StackSlot(NewVReg, slot);
2071 // create a new register for this spill
2072 LiveInterval &nI = getOrCreateInterval(NewVReg);
2074 // the spill weight is now infinity as it
2075 // cannot be spilled again
2076 nI.weight = HUGE_VALF;
2078 // Rewrite register operands to use the new vreg.
2079 for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(),
2080 E = Indices.end(); I != E; ++I) {
2081 MI->getOperand(*I).setReg(NewVReg);
2083 if (MI->getOperand(*I).isUse())
2084 MI->getOperand(*I).setIsKill(true);
2087 // Fill in the new live interval.
2088 unsigned index = getInstructionIndex(MI);
2090 LiveRange LR(getLoadIndex(index), getUseIndex(index),
2091 nI.getNextValue(0, 0, false, getVNInfoAllocator()));
2092 DEBUG(errs() << " +" << LR);
2094 vrm.addRestorePoint(NewVReg, MI);
2097 LiveRange LR(getDefIndex(index), getStoreIndex(index),
2098 nI.getNextValue(0, 0, false, getVNInfoAllocator()));
2099 DEBUG(errs() << " +" << LR);
2101 vrm.addSpillPoint(NewVReg, true, MI);
2104 added.push_back(&nI);
2107 errs() << "\t\t\t\tadded new interval: ";
2114 RI = mri_->reg_begin(li.reg);
2120 std::vector<LiveInterval*> LiveIntervals::
2121 addIntervalsForSpills(const LiveInterval &li,
2122 SmallVectorImpl<LiveInterval*> &SpillIs,
2123 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
2125 if (EnableFastSpilling)
2126 return addIntervalsForSpillsFast(li, loopInfo, vrm);
2128 assert(li.weight != HUGE_VALF &&
2129 "attempt to spill already spilled interval!");
2132 errs() << "\t\t\t\tadding intervals for spills for interval: ";
2133 li.print(errs(), tri_);
2137 // Each bit specify whether a spill is required in the MBB.
2138 BitVector SpillMBBs(mf_->getNumBlockIDs());
2139 DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
2140 BitVector RestoreMBBs(mf_->getNumBlockIDs());
2141 DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
2142 DenseMap<unsigned,unsigned> MBBVRegsMap;
2143 std::vector<LiveInterval*> NewLIs;
2144 const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
2146 unsigned NumValNums = li.getNumValNums();
2147 SmallVector<MachineInstr*, 4> ReMatDefs;
2148 ReMatDefs.resize(NumValNums, NULL);
2149 SmallVector<MachineInstr*, 4> ReMatOrigDefs;
2150 ReMatOrigDefs.resize(NumValNums, NULL);
2151 SmallVector<int, 4> ReMatIds;
2152 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
2153 BitVector ReMatDelete(NumValNums);
2154 unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
2156 // Spilling a split live interval. It cannot be split any further. Also,
2157 // it's also guaranteed to be a single val# / range interval.
2158 if (vrm.getPreSplitReg(li.reg)) {
2159 vrm.setIsSplitFromReg(li.reg, 0);
2160 // Unset the split kill marker on the last use.
2161 unsigned KillIdx = vrm.getKillPoint(li.reg);
2163 MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
2164 assert(KillMI && "Last use disappeared?");
2165 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
2166 assert(KillOp != -1 && "Last use disappeared?");
2167 KillMI->getOperand(KillOp).setIsKill(false);
2169 vrm.removeKillPoint(li.reg);
2170 bool DefIsReMat = vrm.isReMaterialized(li.reg);
2171 Slot = vrm.getStackSlot(li.reg);
2172 assert(Slot != VirtRegMap::MAX_STACK_SLOT);
2173 MachineInstr *ReMatDefMI = DefIsReMat ?
2174 vrm.getReMaterializedMI(li.reg) : NULL;
2176 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
2177 bool isLoad = isLoadSS ||
2178 (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
2179 bool IsFirstRange = true;
2180 for (LiveInterval::Ranges::const_iterator
2181 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
2182 // If this is a split live interval with multiple ranges, it means there
2183 // are two-address instructions that re-defined the value. Only the
2184 // first def can be rematerialized!
2186 // Note ReMatOrigDefMI has already been deleted.
2187 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
2188 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
2189 false, vrm, rc, ReMatIds, loopInfo,
2190 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
2191 MBBVRegsMap, NewLIs);
2193 rewriteInstructionsForSpills(li, false, I, NULL, 0,
2194 Slot, 0, false, false, false,
2195 false, vrm, rc, ReMatIds, loopInfo,
2196 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
2197 MBBVRegsMap, NewLIs);
2199 IsFirstRange = false;
2202 handleSpilledImpDefs(li, vrm, rc, NewLIs);
2206 bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
2207 if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
2211 bool NeedStackSlot = false;
2212 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
2214 const VNInfo *VNI = *i;
2215 unsigned VN = VNI->id;
2216 if (VNI->isUnused())
2217 continue; // Dead val#.
2218 // Is the def for the val# rematerializable?
2219 MachineInstr *ReMatDefMI = VNI->isDefAccurate()
2220 ? getInstructionFromIndex(VNI->def) : 0;
2222 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
2223 // Remember how to remat the def of this val#.
2224 ReMatOrigDefs[VN] = ReMatDefMI;
2225 // Original def may be modified so we have to make a copy here.
2226 MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
2227 ClonedMIs.push_back(Clone);
2228 ReMatDefs[VN] = Clone;
2230 bool CanDelete = true;
2231 if (VNI->hasPHIKill()) {
2232 // A kill is a phi node, not all of its uses can be rematerialized.
2233 // It must not be deleted.
2235 // Need a stack slot if there is any live range where uses cannot be
2237 NeedStackSlot = true;
2240 ReMatDelete.set(VN);
2242 // Need a stack slot if there is any live range where uses cannot be
2244 NeedStackSlot = true;
2248 // One stack slot per live interval.
2249 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
2250 if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
2251 Slot = vrm.assignVirt2StackSlot(li.reg);
2253 // This case only occurs when the prealloc splitter has already assigned
2254 // a stack slot to this vreg.
2256 Slot = vrm.getStackSlot(li.reg);
2259 // Create new intervals and rewrite defs and uses.
2260 for (LiveInterval::Ranges::const_iterator
2261 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
2262 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
2263 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
2264 bool DefIsReMat = ReMatDefMI != NULL;
2265 bool CanDelete = ReMatDelete[I->valno->id];
2267 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
2268 bool isLoad = isLoadSS ||
2269 (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
2270 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
2271 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
2272 CanDelete, vrm, rc, ReMatIds, loopInfo,
2273 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
2274 MBBVRegsMap, NewLIs);
2277 // Insert spills / restores if we are splitting.
2279 handleSpilledImpDefs(li, vrm, rc, NewLIs);
2283 SmallPtrSet<LiveInterval*, 4> AddedKill;
2284 SmallVector<unsigned, 2> Ops;
2285 if (NeedStackSlot) {
2286 int Id = SpillMBBs.find_first();
2288 std::vector<SRInfo> &spills = SpillIdxes[Id];
2289 for (unsigned i = 0, e = spills.size(); i != e; ++i) {
2290 int index = spills[i].index;
2291 unsigned VReg = spills[i].vreg;
2292 LiveInterval &nI = getOrCreateInterval(VReg);
2293 bool isReMat = vrm.isReMaterialized(VReg);
2294 MachineInstr *MI = getInstructionFromIndex(index);
2295 bool CanFold = false;
2296 bool FoundUse = false;
2298 if (spills[i].canFold) {
2300 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
2301 MachineOperand &MO = MI->getOperand(j);
2302 if (!MO.isReg() || MO.getReg() != VReg)
2309 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
2310 RestoreMBBs, RestoreIdxes))) {
2311 // MI has two-address uses of the same register. If the use
2312 // isn't the first and only use in the BB, then we can't fold
2313 // it. FIXME: Move this to rewriteInstructionsForSpills.
2320 // Fold the store into the def if possible.
2321 bool Folded = false;
2322 if (CanFold && !Ops.empty()) {
2323 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
2326 // Also folded uses, do not issue a load.
2327 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
2328 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
2330 nI.removeRange(getDefIndex(index), getStoreIndex(index));
2334 // Otherwise tell the spiller to issue a spill.
2336 LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
2337 bool isKill = LR->end == getStoreIndex(index);
2338 if (!MI->registerDefIsDead(nI.reg))
2339 // No need to spill a dead def.
2340 vrm.addSpillPoint(VReg, isKill, MI);
2342 AddedKill.insert(&nI);
2345 Id = SpillMBBs.find_next(Id);
2349 int Id = RestoreMBBs.find_first();
2351 std::vector<SRInfo> &restores = RestoreIdxes[Id];
2352 for (unsigned i = 0, e = restores.size(); i != e; ++i) {
2353 int index = restores[i].index;
2356 unsigned VReg = restores[i].vreg;
2357 LiveInterval &nI = getOrCreateInterval(VReg);
2358 bool isReMat = vrm.isReMaterialized(VReg);
2359 MachineInstr *MI = getInstructionFromIndex(index);
2360 bool CanFold = false;
2362 if (restores[i].canFold) {
2364 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
2365 MachineOperand &MO = MI->getOperand(j);
2366 if (!MO.isReg() || MO.getReg() != VReg)
2370 // If this restore were to be folded, it would have been folded
2379 // Fold the load into the use if possible.
2380 bool Folded = false;
2381 if (CanFold && !Ops.empty()) {
2383 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
2385 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
2387 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
2388 // If the rematerializable def is a load, also try to fold it.
2389 if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
2390 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
2391 Ops, isLoadSS, LdSlot, VReg);
2393 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
2395 // Re-matting an instruction with virtual register use. Add the
2396 // register as an implicit use on the use MI and update the register
2397 // interval's spill weight to HUGE_VALF to prevent it from being
2399 LiveInterval &ImpLi = getInterval(ImpUse);
2400 ImpLi.weight = HUGE_VALF;
2401 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
2406 // If folding is not possible / failed, then tell the spiller to issue a
2407 // load / rematerialization for us.
2409 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
2411 vrm.addRestorePoint(VReg, MI);
2413 Id = RestoreMBBs.find_next(Id);
2416 // Finalize intervals: add kills, finalize spill weights, and filter out
2418 std::vector<LiveInterval*> RetNewLIs;
2419 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
2420 LiveInterval *LI = NewLIs[i];
2422 LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI);
2423 if (!AddedKill.count(LI)) {
2424 LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
2425 unsigned LastUseIdx = getBaseIndex(LR->end);
2426 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
2427 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
2428 assert(UseIdx != -1);
2429 if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
2430 LastUse->getOperand(UseIdx).setIsKill();
2431 vrm.addKillPoint(LI->reg, LastUseIdx);
2434 RetNewLIs.push_back(LI);
2438 handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
2442 /// hasAllocatableSuperReg - Return true if the specified physical register has
2443 /// any super register that's allocatable.
2444 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
2445 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
2446 if (allocatableRegs_[*AS] && hasInterval(*AS))
2451 /// getRepresentativeReg - Find the largest super register of the specified
2452 /// physical register.
2453 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
2454 // Find the largest super-register that is allocatable.
2455 unsigned BestReg = Reg;
2456 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
2457 unsigned SuperReg = *AS;
2458 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
2466 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
2467 /// specified interval that conflicts with the specified physical register.
2468 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
2469 unsigned PhysReg) const {
2470 unsigned NumConflicts = 0;
2471 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
2472 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2473 E = mri_->reg_end(); I != E; ++I) {
2474 MachineOperand &O = I.getOperand();
2475 MachineInstr *MI = O.getParent();
2476 unsigned Index = getInstructionIndex(MI);
2477 if (pli.liveAt(Index))
2480 return NumConflicts;
2483 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
2484 /// around all defs and uses of the specified interval. Return true if it
2485 /// was able to cut its interval.
2486 bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
2487 unsigned PhysReg, VirtRegMap &vrm) {
2488 unsigned SpillReg = getRepresentativeReg(PhysReg);
2490 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
2491 // If there are registers which alias PhysReg, but which are not a
2492 // sub-register of the chosen representative super register. Assert
2493 // since we can't handle it yet.
2494 assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
2495 tri_->isSuperRegister(*AS, SpillReg));
2498 LiveInterval &pli = getInterval(SpillReg);
2499 SmallPtrSet<MachineInstr*, 8> SeenMIs;
2500 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2501 E = mri_->reg_end(); I != E; ++I) {
2502 MachineOperand &O = I.getOperand();
2503 MachineInstr *MI = O.getParent();
2504 if (SeenMIs.count(MI))
2507 unsigned Index = getInstructionIndex(MI);
2508 if (pli.liveAt(Index)) {
2509 vrm.addEmergencySpill(SpillReg, MI);
2510 unsigned StartIdx = getLoadIndex(Index);
2511 unsigned EndIdx = getStoreIndex(Index)+1;
2512 if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
2513 pli.removeRange(StartIdx, EndIdx);
2517 raw_string_ostream Msg(msg);
2518 Msg << "Ran out of registers during register allocation!";
2519 if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {
2520 Msg << "\nPlease check your inline asm statement for invalid "
2521 << "constraints:\n";
2522 MI->print(Msg, tm_);
2524 llvm_report_error(Msg.str());
2526 for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
2527 if (!hasInterval(*AS))
2529 LiveInterval &spli = getInterval(*AS);
2530 if (spli.liveAt(Index))
2531 spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
2538 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
2539 MachineInstr* startInst) {
2540 LiveInterval& Interval = getOrCreateInterval(reg);
2541 VNInfo* VN = Interval.getNextValue(
2542 getInstructionIndex(startInst) + InstrSlots::DEF,
2543 startInst, true, getVNInfoAllocator());
2544 VN->setHasPHIKill(true);
2545 VN->kills.push_back(
2546 VNInfo::KillInfo(terminatorGaps[startInst->getParent()], true));
2547 LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
2548 getMBBEndIdx(startInst->getParent()) + 1, VN);
2549 Interval.addRange(LR);