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/CodeGen/LiveVariables.h"
23 #include "llvm/CodeGen/MachineFrameInfo.h"
24 #include "llvm/CodeGen/MachineInstr.h"
25 #include "llvm/CodeGen/MachineLoopInfo.h"
26 #include "llvm/CodeGen/MachineRegisterInfo.h"
27 #include "llvm/CodeGen/Passes.h"
28 #include "llvm/Target/TargetRegisterInfo.h"
29 #include "llvm/Target/TargetInstrInfo.h"
30 #include "llvm/Target/TargetMachine.h"
31 #include "llvm/Support/CommandLine.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/ADT/STLExtras.h"
39 // Hidden options for help debugging.
40 static cl::opt<bool> DisableReMat("disable-rematerialization",
41 cl::init(false), cl::Hidden);
43 static cl::opt<bool> SplitAtBB("split-intervals-at-bb",
44 cl::init(true), cl::Hidden);
45 static cl::opt<int> SplitLimit("split-limit",
46 cl::init(-1), cl::Hidden);
48 STATISTIC(numIntervals, "Number of original intervals");
49 STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
50 STATISTIC(numFolds , "Number of loads/stores folded into instructions");
51 STATISTIC(numSplits , "Number of intervals split");
53 char LiveIntervals::ID = 0;
54 static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
56 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
57 AU.addPreserved<LiveVariables>();
58 AU.addRequired<LiveVariables>();
59 AU.addPreservedID(MachineLoopInfoID);
60 AU.addPreservedID(MachineDominatorsID);
61 AU.addPreservedID(PHIEliminationID);
62 AU.addRequiredID(PHIEliminationID);
63 AU.addRequiredID(TwoAddressInstructionPassID);
64 MachineFunctionPass::getAnalysisUsage(AU);
67 void LiveIntervals::releaseMemory() {
72 // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
73 VNInfoAllocator.Reset();
74 for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i)
78 void LiveIntervals::computeNumbering() {
79 Index2MiMap OldI2MI = i2miMap_;
86 // Number MachineInstrs and MachineBasicBlocks.
87 // Initialize MBB indexes to a sentinal.
88 MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
91 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
93 unsigned StartIdx = MIIndex;
95 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
97 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
98 assert(inserted && "multiple MachineInstr -> index mappings");
99 i2miMap_.push_back(I);
100 MIIndex += InstrSlots::NUM;
103 // Set the MBB2IdxMap entry for this MBB.
104 MBB2IdxMap[MBB->getNumber()] = (StartIdx == MIIndex)
105 ? std::make_pair(StartIdx, StartIdx) // Empty MBB
106 : std::make_pair(StartIdx, MIIndex - 1);
107 Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
109 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
111 if (!OldI2MI.empty())
112 for (iterator I = begin(), E = end(); I != E; ++I)
113 for (LiveInterval::iterator LI = I->second.begin(), LE = I->second.end();
116 // Remap the start index of the live range to the corresponding new
117 // number, or our best guess at what it _should_ correspond to if the
118 // original instruction has been erased. This is either the following
119 // instruction or its predecessor.
120 unsigned offset = LI->start % InstrSlots::NUM;
121 if (OldI2MI[LI->start / InstrSlots::NUM])
122 LI->start = mi2iMap_[OldI2MI[LI->start / InstrSlots::NUM]] + offset;
125 MachineInstr* newInstr = 0;
127 newInstr = OldI2MI[LI->start / InstrSlots::NUM + i];
131 if (mi2iMap_[newInstr] ==
132 MBB2IdxMap[newInstr->getParent()->getNumber()].first)
133 LI->start = mi2iMap_[newInstr];
135 LI->start = mi2iMap_[newInstr] - InstrSlots::NUM + offset;
138 // Remap the ending index in the same way that we remapped the start,
139 // except for the final step where we always map to the immediately
140 // following instruction.
141 if (LI->end / InstrSlots::NUM < OldI2MI.size()) {
142 offset = LI->end % InstrSlots::NUM;
143 if (OldI2MI[LI->end / InstrSlots::NUM])
144 LI->end = mi2iMap_[OldI2MI[LI->end / InstrSlots::NUM]] + offset;
147 MachineInstr* newInstr = 0;
149 newInstr = OldI2MI[LI->end / InstrSlots::NUM + i];
153 LI->end = mi2iMap_[newInstr];
156 LI->end = i2miMap_.size() * InstrSlots::NUM;
159 // Remap the VNInfo def index, which works the same as the
160 // start indices above.
161 VNInfo* vni = LI->valno;
162 offset = vni->def % InstrSlots::NUM;
163 if (OldI2MI[vni->def / InstrSlots::NUM])
164 vni->def = mi2iMap_[OldI2MI[vni->def / InstrSlots::NUM]] + offset;
167 MachineInstr* newInstr = 0;
169 newInstr = OldI2MI[vni->def / InstrSlots::NUM + i];
173 if (mi2iMap_[newInstr] ==
174 MBB2IdxMap[newInstr->getParent()->getNumber()].first)
175 vni->def = mi2iMap_[newInstr];
177 vni->def = mi2iMap_[newInstr] - InstrSlots::NUM + offset;
180 // Remap the VNInfo kill indices, which works the same as
181 // the end indices above.
182 for (size_t i = 0; i < vni->kills.size(); ++i) {
183 offset = vni->kills[i] % InstrSlots::NUM;
184 if (OldI2MI[vni->kills[i] / InstrSlots::NUM])
185 vni->kills[i] = mi2iMap_[OldI2MI[vni->kills[i] / InstrSlots::NUM]] +
189 MachineInstr* newInstr = 0;
191 newInstr = OldI2MI[vni->kills[i] / InstrSlots::NUM + e];
195 vni->kills[i] = mi2iMap_[newInstr];
201 /// runOnMachineFunction - Register allocate the whole function
203 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
205 mri_ = &mf_->getRegInfo();
206 tm_ = &fn.getTarget();
207 tri_ = tm_->getRegisterInfo();
208 tii_ = tm_->getInstrInfo();
209 lv_ = &getAnalysis<LiveVariables>();
210 allocatableRegs_ = tri_->getAllocatableSet(fn);
215 numIntervals += getNumIntervals();
217 DOUT << "********** INTERVALS **********\n";
218 for (iterator I = begin(), E = end(); I != E; ++I) {
219 I->second.print(DOUT, tri_);
223 numIntervalsAfter += getNumIntervals();
228 /// print - Implement the dump method.
229 void LiveIntervals::print(std::ostream &O, const Module* ) const {
230 O << "********** INTERVALS **********\n";
231 for (const_iterator I = begin(), E = end(); I != E; ++I) {
232 I->second.print(DOUT, tri_);
236 O << "********** MACHINEINSTRS **********\n";
237 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
238 mbbi != mbbe; ++mbbi) {
239 O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
240 for (MachineBasicBlock::iterator mii = mbbi->begin(),
241 mie = mbbi->end(); mii != mie; ++mii) {
242 O << getInstructionIndex(mii) << '\t' << *mii;
247 /// conflictsWithPhysRegDef - Returns true if the specified register
248 /// is defined during the duration of the specified interval.
249 bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
250 VirtRegMap &vrm, unsigned reg) {
251 for (LiveInterval::Ranges::const_iterator
252 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
253 for (unsigned index = getBaseIndex(I->start),
254 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
255 index += InstrSlots::NUM) {
256 // skip deleted instructions
257 while (index != end && !getInstructionFromIndex(index))
258 index += InstrSlots::NUM;
259 if (index == end) break;
261 MachineInstr *MI = getInstructionFromIndex(index);
262 unsigned SrcReg, DstReg;
263 if (tii_->isMoveInstr(*MI, SrcReg, DstReg))
264 if (SrcReg == li.reg || DstReg == li.reg)
266 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
267 MachineOperand& mop = MI->getOperand(i);
268 if (!mop.isRegister())
270 unsigned PhysReg = mop.getReg();
271 if (PhysReg == 0 || PhysReg == li.reg)
273 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
274 if (!vrm.hasPhys(PhysReg))
276 PhysReg = vrm.getPhys(PhysReg);
278 if (PhysReg && tri_->regsOverlap(PhysReg, reg))
287 void LiveIntervals::printRegName(unsigned reg) const {
288 if (TargetRegisterInfo::isPhysicalRegister(reg))
289 cerr << tri_->getName(reg);
291 cerr << "%reg" << reg;
294 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
295 MachineBasicBlock::iterator mi,
297 LiveInterval &interval) {
298 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
299 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
301 if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
302 DOUT << "is a implicit_def\n";
306 // Virtual registers may be defined multiple times (due to phi
307 // elimination and 2-addr elimination). Much of what we do only has to be
308 // done once for the vreg. We use an empty interval to detect the first
309 // time we see a vreg.
310 if (interval.empty()) {
311 // Get the Idx of the defining instructions.
312 unsigned defIndex = getDefIndex(MIIdx);
314 MachineInstr *CopyMI = NULL;
315 unsigned SrcReg, DstReg;
316 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
317 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
318 tii_->isMoveInstr(*mi, SrcReg, DstReg))
320 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
322 assert(ValNo->id == 0 && "First value in interval is not 0?");
324 // Loop over all of the blocks that the vreg is defined in. There are
325 // two cases we have to handle here. The most common case is a vreg
326 // whose lifetime is contained within a basic block. In this case there
327 // will be a single kill, in MBB, which comes after the definition.
328 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
329 // FIXME: what about dead vars?
331 if (vi.Kills[0] != mi)
332 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
334 killIdx = defIndex+1;
336 // If the kill happens after the definition, we have an intra-block
338 if (killIdx > defIndex) {
339 assert(vi.AliveBlocks.none() &&
340 "Shouldn't be alive across any blocks!");
341 LiveRange LR(defIndex, killIdx, ValNo);
342 interval.addRange(LR);
343 DOUT << " +" << LR << "\n";
344 interval.addKill(ValNo, killIdx);
349 // The other case we handle is when a virtual register lives to the end
350 // of the defining block, potentially live across some blocks, then is
351 // live into some number of blocks, but gets killed. Start by adding a
352 // range that goes from this definition to the end of the defining block.
353 LiveRange NewLR(defIndex,
354 getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
356 DOUT << " +" << NewLR;
357 interval.addRange(NewLR);
359 // Iterate over all of the blocks that the variable is completely
360 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
362 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
363 if (vi.AliveBlocks[i]) {
364 MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
366 LiveRange LR(getMBBStartIdx(i),
367 getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
369 interval.addRange(LR);
375 // Finally, this virtual register is live from the start of any killing
376 // block to the 'use' slot of the killing instruction.
377 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
378 MachineInstr *Kill = vi.Kills[i];
379 unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
380 LiveRange LR(getMBBStartIdx(Kill->getParent()),
382 interval.addRange(LR);
383 interval.addKill(ValNo, killIdx);
388 // If this is the second time we see a virtual register definition, it
389 // must be due to phi elimination or two addr elimination. If this is
390 // the result of two address elimination, then the vreg is one of the
391 // def-and-use register operand.
392 if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
393 // If this is a two-address definition, then we have already processed
394 // the live range. The only problem is that we didn't realize there
395 // are actually two values in the live interval. Because of this we
396 // need to take the LiveRegion that defines this register and split it
398 assert(interval.containsOneValue());
399 unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
400 unsigned RedefIndex = getDefIndex(MIIdx);
402 const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
403 VNInfo *OldValNo = OldLR->valno;
405 // Delete the initial value, which should be short and continuous,
406 // because the 2-addr copy must be in the same MBB as the redef.
407 interval.removeRange(DefIndex, RedefIndex);
409 // Two-address vregs should always only be redefined once. This means
410 // that at this point, there should be exactly one value number in it.
411 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
413 // The new value number (#1) is defined by the instruction we claimed
415 VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy,
418 // Value#0 is now defined by the 2-addr instruction.
419 OldValNo->def = RedefIndex;
422 // Add the new live interval which replaces the range for the input copy.
423 LiveRange LR(DefIndex, RedefIndex, ValNo);
424 DOUT << " replace range with " << LR;
425 interval.addRange(LR);
426 interval.addKill(ValNo, RedefIndex);
428 // If this redefinition is dead, we need to add a dummy unit live
429 // range covering the def slot.
430 if (mi->registerDefIsDead(interval.reg, tri_))
431 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
434 interval.print(DOUT, tri_);
437 // Otherwise, this must be because of phi elimination. If this is the
438 // first redefinition of the vreg that we have seen, go back and change
439 // the live range in the PHI block to be a different value number.
440 if (interval.containsOneValue()) {
441 assert(vi.Kills.size() == 1 &&
442 "PHI elimination vreg should have one kill, the PHI itself!");
444 // Remove the old range that we now know has an incorrect number.
445 VNInfo *VNI = interval.getValNumInfo(0);
446 MachineInstr *Killer = vi.Kills[0];
447 unsigned Start = getMBBStartIdx(Killer->getParent());
448 unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
449 DOUT << " Removing [" << Start << "," << End << "] from: ";
450 interval.print(DOUT, tri_); DOUT << "\n";
451 interval.removeRange(Start, End);
452 VNI->hasPHIKill = true;
453 DOUT << " RESULT: "; interval.print(DOUT, tri_);
455 // Replace the interval with one of a NEW value number. Note that this
456 // value number isn't actually defined by an instruction, weird huh? :)
457 LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
458 DOUT << " replace range with " << LR;
459 interval.addRange(LR);
460 interval.addKill(LR.valno, End);
461 DOUT << " RESULT: "; interval.print(DOUT, tri_);
464 // In the case of PHI elimination, each variable definition is only
465 // live until the end of the block. We've already taken care of the
466 // rest of the live range.
467 unsigned defIndex = getDefIndex(MIIdx);
470 MachineInstr *CopyMI = NULL;
471 unsigned SrcReg, DstReg;
472 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
473 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
474 tii_->isMoveInstr(*mi, SrcReg, DstReg))
476 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
478 unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
479 LiveRange LR(defIndex, killIndex, ValNo);
480 interval.addRange(LR);
481 interval.addKill(ValNo, killIndex);
482 ValNo->hasPHIKill = true;
490 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
491 MachineBasicBlock::iterator mi,
493 LiveInterval &interval,
494 MachineInstr *CopyMI) {
495 // A physical register cannot be live across basic block, so its
496 // lifetime must end somewhere in its defining basic block.
497 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
499 unsigned baseIndex = MIIdx;
500 unsigned start = getDefIndex(baseIndex);
501 unsigned end = start;
503 // If it is not used after definition, it is considered dead at
504 // the instruction defining it. Hence its interval is:
505 // [defSlot(def), defSlot(def)+1)
506 if (mi->registerDefIsDead(interval.reg, tri_)) {
508 end = getDefIndex(start) + 1;
512 // If it is not dead on definition, it must be killed by a
513 // subsequent instruction. Hence its interval is:
514 // [defSlot(def), useSlot(kill)+1)
515 while (++mi != MBB->end()) {
516 baseIndex += InstrSlots::NUM;
517 if (mi->killsRegister(interval.reg, tri_)) {
519 end = getUseIndex(baseIndex) + 1;
521 } else if (mi->modifiesRegister(interval.reg, tri_)) {
522 // Another instruction redefines the register before it is ever read.
523 // Then the register is essentially dead at the instruction that defines
524 // it. Hence its interval is:
525 // [defSlot(def), defSlot(def)+1)
527 end = getDefIndex(start) + 1;
532 // The only case we should have a dead physreg here without a killing or
533 // instruction where we know it's dead is if it is live-in to the function
535 assert(!CopyMI && "physreg was not killed in defining block!");
536 end = getDefIndex(start) + 1; // It's dead.
539 assert(start < end && "did not find end of interval?");
541 // Already exists? Extend old live interval.
542 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
543 VNInfo *ValNo = (OldLR != interval.end())
544 ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator);
545 LiveRange LR(start, end, ValNo);
546 interval.addRange(LR);
547 interval.addKill(LR.valno, end);
548 DOUT << " +" << LR << '\n';
551 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
552 MachineBasicBlock::iterator MI,
555 if (TargetRegisterInfo::isVirtualRegister(reg))
556 handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
557 else if (allocatableRegs_[reg]) {
558 MachineInstr *CopyMI = NULL;
559 unsigned SrcReg, DstReg;
560 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
561 MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
562 tii_->isMoveInstr(*MI, SrcReg, DstReg))
564 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI);
565 // Def of a register also defines its sub-registers.
566 for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS)
567 // If MI also modifies the sub-register explicitly, avoid processing it
568 // more than once. Do not pass in TRI here so it checks for exact match.
569 if (!MI->modifiesRegister(*AS))
570 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
574 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
576 LiveInterval &interval, bool isAlias) {
577 DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
579 // Look for kills, if it reaches a def before it's killed, then it shouldn't
580 // be considered a livein.
581 MachineBasicBlock::iterator mi = MBB->begin();
582 unsigned baseIndex = MIIdx;
583 unsigned start = baseIndex;
584 unsigned end = start;
585 while (mi != MBB->end()) {
586 if (mi->killsRegister(interval.reg, tri_)) {
588 end = getUseIndex(baseIndex) + 1;
590 } else if (mi->modifiesRegister(interval.reg, tri_)) {
591 // Another instruction redefines the register before it is ever read.
592 // Then the register is essentially dead at the instruction that defines
593 // it. Hence its interval is:
594 // [defSlot(def), defSlot(def)+1)
596 end = getDefIndex(start) + 1;
600 baseIndex += InstrSlots::NUM;
605 // Live-in register might not be used at all.
609 end = getDefIndex(MIIdx) + 1;
611 DOUT << " live through";
616 LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
617 interval.addRange(LR);
618 interval.addKill(LR.valno, end);
619 DOUT << " +" << LR << '\n';
622 /// computeIntervals - computes the live intervals for virtual
623 /// registers. for some ordering of the machine instructions [1,N] a
624 /// live interval is an interval [i, j) where 1 <= i <= j < N for
625 /// which a variable is live
626 void LiveIntervals::computeIntervals() {
627 DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
628 << "********** Function: "
629 << ((Value*)mf_->getFunction())->getName() << '\n';
630 // Track the index of the current machine instr.
631 unsigned MIIndex = 0;
632 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
634 MachineBasicBlock *MBB = MBBI;
635 DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
637 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
639 // Create intervals for live-ins to this BB first.
640 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
641 LE = MBB->livein_end(); LI != LE; ++LI) {
642 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
643 // Multiple live-ins can alias the same register.
644 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
645 if (!hasInterval(*AS))
646 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
650 for (; MI != miEnd; ++MI) {
651 DOUT << MIIndex << "\t" << *MI;
654 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
655 MachineOperand &MO = MI->getOperand(i);
656 // handle register defs - build intervals
657 if (MO.isRegister() && MO.getReg() && MO.isDef())
658 handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
661 MIIndex += InstrSlots::NUM;
666 bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
667 SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
668 std::vector<IdxMBBPair>::const_iterator I =
669 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);
672 while (I != Idx2MBBMap.end()) {
673 if (LR.end <= I->first)
675 MBBs.push_back(I->second);
683 LiveInterval LiveIntervals::createInterval(unsigned reg) {
684 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ?
686 return LiveInterval(reg, Weight);
689 /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
690 /// copy field and returns the source register that defines it.
691 unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const {
695 if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
696 return VNI->copy->getOperand(1).getReg();
697 if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
698 return VNI->copy->getOperand(2).getReg();
699 unsigned SrcReg, DstReg;
700 if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg))
702 assert(0 && "Unrecognized copy instruction!");
706 //===----------------------------------------------------------------------===//
707 // Register allocator hooks.
710 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
711 /// allow one) virtual register operand, then its uses are implicitly using
712 /// the register. Returns the virtual register.
713 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
714 MachineInstr *MI) const {
716 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
717 MachineOperand &MO = MI->getOperand(i);
718 if (!MO.isRegister() || !MO.isUse())
720 unsigned Reg = MO.getReg();
721 if (Reg == 0 || Reg == li.reg)
723 // FIXME: For now, only remat MI with at most one register operand.
725 "Can't rematerialize instruction with multiple register operand!");
732 /// isValNoAvailableAt - Return true if the val# of the specified interval
733 /// which reaches the given instruction also reaches the specified use index.
734 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
735 unsigned UseIdx) const {
736 unsigned Index = getInstructionIndex(MI);
737 VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
738 LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
739 return UI != li.end() && UI->valno == ValNo;
742 /// isReMaterializable - Returns true if the definition MI of the specified
743 /// val# of the specified interval is re-materializable.
744 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
745 const VNInfo *ValNo, MachineInstr *MI,
751 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
755 if (tii_->isLoadFromStackSlot(MI, FrameIdx) &&
756 mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
757 // FIXME: Let target specific isReallyTriviallyReMaterializable determines
758 // this but remember this is not safe to fold into a two-address
760 // This is a load from fixed stack slot. It can be rematerialized.
763 if (tii_->isTriviallyReMaterializable(MI)) {
764 const TargetInstrDesc &TID = MI->getDesc();
765 isLoad = TID.isSimpleLoad();
767 unsigned ImpUse = getReMatImplicitUse(li, MI);
769 const LiveInterval &ImpLi = getInterval(ImpUse);
770 for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg),
771 re = mri_->use_end(); ri != re; ++ri) {
772 MachineInstr *UseMI = &*ri;
773 unsigned UseIdx = getInstructionIndex(UseMI);
774 if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
776 if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
786 /// isReMaterializable - Returns true if every definition of MI of every
787 /// val# of the specified interval is re-materializable.
788 bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) {
790 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
792 const VNInfo *VNI = *i;
793 unsigned DefIdx = VNI->def;
795 continue; // Dead val#.
796 // Is the def for the val# rematerializable?
799 MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx);
800 bool DefIsLoad = false;
802 !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad))
809 /// FilterFoldedOps - Filter out two-address use operands. Return
810 /// true if it finds any issue with the operands that ought to prevent
812 static bool FilterFoldedOps(MachineInstr *MI,
813 SmallVector<unsigned, 2> &Ops,
815 SmallVector<unsigned, 2> &FoldOps) {
816 const TargetInstrDesc &TID = MI->getDesc();
819 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
820 unsigned OpIdx = Ops[i];
821 MachineOperand &MO = MI->getOperand(OpIdx);
822 // FIXME: fold subreg use.
826 MRInfo |= (unsigned)VirtRegMap::isMod;
828 // Filter out two-address use operand(s).
829 if (!MO.isImplicit() &&
830 TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) {
831 MRInfo = VirtRegMap::isModRef;
834 MRInfo |= (unsigned)VirtRegMap::isRef;
836 FoldOps.push_back(OpIdx);
842 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
843 /// slot / to reg or any rematerialized load into ith operand of specified
844 /// MI. If it is successul, MI is updated with the newly created MI and
846 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
847 VirtRegMap &vrm, MachineInstr *DefMI,
849 SmallVector<unsigned, 2> &Ops,
850 bool isSS, int Slot, unsigned Reg) {
851 // If it is an implicit def instruction, just delete it.
852 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
853 RemoveMachineInstrFromMaps(MI);
854 vrm.RemoveMachineInstrFromMaps(MI);
855 MI->eraseFromParent();
860 // Filter the list of operand indexes that are to be folded. Abort if
861 // any operand will prevent folding.
863 SmallVector<unsigned, 2> FoldOps;
864 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
867 // The only time it's safe to fold into a two address instruction is when
868 // it's folding reload and spill from / into a spill stack slot.
869 if (DefMI && (MRInfo & VirtRegMap::isMod))
872 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
873 : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
875 // Remember this instruction uses the spill slot.
876 if (isSS) vrm.addSpillSlotUse(Slot, fmi);
878 // Attempt to fold the memory reference into the instruction. If
879 // we can do this, we don't need to insert spill code.
881 lv_->instructionChanged(MI, fmi);
883 fmi->copyKillDeadInfo(MI, tri_);
884 MachineBasicBlock &MBB = *MI->getParent();
885 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
886 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
887 vrm.transferSpillPts(MI, fmi);
888 vrm.transferRestorePts(MI, fmi);
889 vrm.transferEmergencySpills(MI, fmi);
891 i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
892 mi2iMap_[fmi] = InstrIdx;
893 MI = MBB.insert(MBB.erase(MI), fmi);
900 /// canFoldMemoryOperand - Returns true if the specified load / store
901 /// folding is possible.
902 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
903 SmallVector<unsigned, 2> &Ops,
905 // Filter the list of operand indexes that are to be folded. Abort if
906 // any operand will prevent folding.
908 SmallVector<unsigned, 2> FoldOps;
909 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
912 // It's only legal to remat for a use, not a def.
913 if (ReMat && (MRInfo & VirtRegMap::isMod))
916 return tii_->canFoldMemoryOperand(MI, FoldOps);
919 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
920 SmallPtrSet<MachineBasicBlock*, 4> MBBs;
921 for (LiveInterval::Ranges::const_iterator
922 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
923 std::vector<IdxMBBPair>::const_iterator II =
924 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
925 if (II == Idx2MBBMap.end())
927 if (I->end > II->first) // crossing a MBB.
929 MBBs.insert(II->second);
936 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
937 /// interval on to-be re-materialized operands of MI) with new register.
938 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
939 MachineInstr *MI, unsigned NewVReg,
941 // There is an implicit use. That means one of the other operand is
942 // being remat'ed and the remat'ed instruction has li.reg as an
943 // use operand. Make sure we rewrite that as well.
944 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
945 MachineOperand &MO = MI->getOperand(i);
946 if (!MO.isRegister())
948 unsigned Reg = MO.getReg();
949 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
951 if (!vrm.isReMaterialized(Reg))
953 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
954 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
956 UseMO->setReg(NewVReg);
960 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
961 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
963 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
964 bool TrySplit, unsigned index, unsigned end, MachineInstr *MI,
965 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
966 unsigned Slot, int LdSlot,
967 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
969 const TargetRegisterClass* rc,
970 SmallVector<int, 4> &ReMatIds,
971 const MachineLoopInfo *loopInfo,
972 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
973 std::map<unsigned,unsigned> &MBBVRegsMap,
974 std::vector<LiveInterval*> &NewLIs) {
975 bool CanFold = false;
977 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
978 MachineOperand& mop = MI->getOperand(i);
979 if (!mop.isRegister())
981 unsigned Reg = mop.getReg();
983 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
988 bool TryFold = !DefIsReMat;
989 bool FoldSS = true; // Default behavior unless it's a remat.
992 // If this is the rematerializable definition MI itself and
993 // all of its uses are rematerialized, simply delete it.
994 if (MI == ReMatOrigDefMI && CanDelete) {
995 DOUT << "\t\t\t\tErasing re-materlizable def: ";
997 RemoveMachineInstrFromMaps(MI);
998 vrm.RemoveMachineInstrFromMaps(MI);
999 MI->eraseFromParent();
1003 // If def for this use can't be rematerialized, then try folding.
1004 // If def is rematerializable and it's a load, also try folding.
1005 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1007 // Try fold loads (from stack slot, constant pool, etc.) into uses.
1013 // Scan all of the operands of this instruction rewriting operands
1014 // to use NewVReg instead of li.reg as appropriate. We do this for
1017 // 1. If the instr reads the same spilled vreg multiple times, we
1018 // want to reuse the NewVReg.
1019 // 2. If the instr is a two-addr instruction, we are required to
1020 // keep the src/dst regs pinned.
1022 // Keep track of whether we replace a use and/or def so that we can
1023 // create the spill interval with the appropriate range.
1025 HasUse = mop.isUse();
1026 HasDef = mop.isDef();
1027 SmallVector<unsigned, 2> Ops;
1029 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
1030 const MachineOperand &MOj = MI->getOperand(j);
1031 if (!MOj.isRegister())
1033 unsigned RegJ = MOj.getReg();
1034 if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
1038 HasUse |= MOj.isUse();
1039 HasDef |= MOj.isDef();
1044 // Do not fold load / store here if we are splitting. We'll find an
1045 // optimal point to insert a load / store later.
1047 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1048 Ops, FoldSS, FoldSlot, Reg)) {
1049 // Folding the load/store can completely change the instruction in
1050 // unpredictable ways, rescan it from the beginning.
1056 goto RestartInstruction;
1059 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1064 // Create a new virtual register for the spill interval.
1065 bool CreatedNewVReg = false;
1067 NewVReg = mri_->createVirtualRegister(rc);
1069 CreatedNewVReg = true;
1071 mop.setReg(NewVReg);
1072 if (mop.isImplicit())
1073 rewriteImplicitOps(li, MI, NewVReg, vrm);
1075 // Reuse NewVReg for other reads.
1076 for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1077 MachineOperand &mopj = MI->getOperand(Ops[j]);
1078 mopj.setReg(NewVReg);
1079 if (mopj.isImplicit())
1080 rewriteImplicitOps(li, MI, NewVReg, vrm);
1083 if (CreatedNewVReg) {
1085 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
1086 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1087 // Each valnum may have its own remat id.
1088 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1090 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1092 if (!CanDelete || (HasUse && HasDef)) {
1093 // If this is a two-addr instruction then its use operands are
1094 // rematerializable but its def is not. It should be assigned a
1096 vrm.assignVirt2StackSlot(NewVReg, Slot);
1099 vrm.assignVirt2StackSlot(NewVReg, Slot);
1101 } else if (HasUse && HasDef &&
1102 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1103 // If this interval hasn't been assigned a stack slot (because earlier
1104 // def is a deleted remat def), do it now.
1105 assert(Slot != VirtRegMap::NO_STACK_SLOT);
1106 vrm.assignVirt2StackSlot(NewVReg, Slot);
1109 // Re-matting an instruction with virtual register use. Add the
1110 // register as an implicit use on the use MI.
1111 if (DefIsReMat && ImpUse)
1112 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1114 // create a new register interval for this spill / remat.
1115 LiveInterval &nI = getOrCreateInterval(NewVReg);
1116 if (CreatedNewVReg) {
1117 NewLIs.push_back(&nI);
1118 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1120 vrm.setIsSplitFromReg(NewVReg, li.reg);
1124 if (CreatedNewVReg) {
1125 LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
1126 nI.getNextValue(~0U, 0, VNInfoAllocator));
1130 // Extend the split live interval to this def / use.
1131 unsigned End = getUseIndex(index)+1;
1132 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1133 nI.getValNumInfo(nI.getNumValNums()-1));
1139 LiveRange LR(getDefIndex(index), getStoreIndex(index),
1140 nI.getNextValue(~0U, 0, VNInfoAllocator));
1145 DOUT << "\t\t\t\tAdded new interval: ";
1146 nI.print(DOUT, tri_);
1151 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1153 MachineBasicBlock *MBB, unsigned Idx) const {
1154 unsigned End = getMBBEndIdx(MBB);
1155 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
1156 unsigned KillIdx = VNI->kills[j];
1157 if (KillIdx > Idx && KillIdx < End)
1163 static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) {
1164 const VNInfo *VNI = NULL;
1165 for (LiveInterval::const_vni_iterator i = li.vni_begin(),
1166 e = li.vni_end(); i != e; ++i)
1167 if ((*i)->def == DefIdx) {
1174 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1175 /// during spilling.
1177 struct RewriteInfo {
1182 RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
1183 : Index(i), MI(mi), HasUse(u), HasDef(d) {}
1186 struct RewriteInfoCompare {
1187 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1188 return LHS.Index < RHS.Index;
1193 void LiveIntervals::
1194 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1195 LiveInterval::Ranges::const_iterator &I,
1196 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1197 unsigned Slot, int LdSlot,
1198 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1200 const TargetRegisterClass* rc,
1201 SmallVector<int, 4> &ReMatIds,
1202 const MachineLoopInfo *loopInfo,
1203 BitVector &SpillMBBs,
1204 std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
1205 BitVector &RestoreMBBs,
1206 std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1207 std::map<unsigned,unsigned> &MBBVRegsMap,
1208 std::vector<LiveInterval*> &NewLIs) {
1209 bool AllCanFold = true;
1210 unsigned NewVReg = 0;
1211 unsigned start = getBaseIndex(I->start);
1212 unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
1214 // First collect all the def / use in this live range that will be rewritten.
1215 // Make sure they are sorted according to instruction index.
1216 std::vector<RewriteInfo> RewriteMIs;
1217 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1218 re = mri_->reg_end(); ri != re; ) {
1219 MachineInstr *MI = &*ri;
1220 MachineOperand &O = ri.getOperand();
1222 assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
1223 unsigned index = getInstructionIndex(MI);
1224 if (index < start || index >= end)
1226 RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
1228 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1230 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1231 // Now rewrite the defs and uses.
1232 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1233 RewriteInfo &rwi = RewriteMIs[i];
1235 unsigned index = rwi.Index;
1236 bool MIHasUse = rwi.HasUse;
1237 bool MIHasDef = rwi.HasDef;
1238 MachineInstr *MI = rwi.MI;
1239 // If MI def and/or use the same register multiple times, then there
1240 // are multiple entries.
1241 unsigned NumUses = MIHasUse;
1242 while (i != e && RewriteMIs[i].MI == MI) {
1243 assert(RewriteMIs[i].Index == index);
1244 bool isUse = RewriteMIs[i].HasUse;
1245 if (isUse) ++NumUses;
1247 MIHasDef |= RewriteMIs[i].HasDef;
1250 MachineBasicBlock *MBB = MI->getParent();
1252 if (ImpUse && MI != ReMatDefMI) {
1253 // Re-matting an instruction with virtual register use. Update the
1254 // register interval's spill weight to HUGE_VALF to prevent it from
1256 LiveInterval &ImpLi = getInterval(ImpUse);
1257 ImpLi.weight = HUGE_VALF;
1260 unsigned MBBId = MBB->getNumber();
1261 unsigned ThisVReg = 0;
1263 std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId);
1264 if (NVI != MBBVRegsMap.end()) {
1265 ThisVReg = NVI->second;
1272 // It's better to start a new interval to avoid artifically
1273 // extend the new interval.
1274 if (MIHasDef && !MIHasUse) {
1275 MBBVRegsMap.erase(MBB->getNumber());
1281 bool IsNew = ThisVReg == 0;
1283 // This ends the previous live interval. If all of its def / use
1284 // can be folded, give it a low spill weight.
1285 if (NewVReg && TrySplit && AllCanFold) {
1286 LiveInterval &nI = getOrCreateInterval(NewVReg);
1293 bool HasDef = false;
1294 bool HasUse = false;
1295 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1296 index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1297 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1298 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1299 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
1300 if (!HasDef && !HasUse)
1303 AllCanFold &= CanFold;
1305 // Update weight of spill interval.
1306 LiveInterval &nI = getOrCreateInterval(NewVReg);
1308 // The spill weight is now infinity as it cannot be spilled again.
1309 nI.weight = HUGE_VALF;
1313 // Keep track of the last def and first use in each MBB.
1315 if (MI != ReMatOrigDefMI || !CanDelete) {
1316 bool HasKill = false;
1318 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
1320 // If this is a two-address code, then this index starts a new VNInfo.
1321 const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index));
1323 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
1325 std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1326 SpillIdxes.find(MBBId);
1328 if (SII == SpillIdxes.end()) {
1329 std::vector<SRInfo> S;
1330 S.push_back(SRInfo(index, NewVReg, true));
1331 SpillIdxes.insert(std::make_pair(MBBId, S));
1332 } else if (SII->second.back().vreg != NewVReg) {
1333 SII->second.push_back(SRInfo(index, NewVReg, true));
1334 } else if ((int)index > SII->second.back().index) {
1335 // If there is an earlier def and this is a two-address
1336 // instruction, then it's not possible to fold the store (which
1337 // would also fold the load).
1338 SRInfo &Info = SII->second.back();
1340 Info.canFold = !HasUse;
1342 SpillMBBs.set(MBBId);
1343 } else if (SII != SpillIdxes.end() &&
1344 SII->second.back().vreg == NewVReg &&
1345 (int)index > SII->second.back().index) {
1346 // There is an earlier def that's not killed (must be two-address).
1347 // The spill is no longer needed.
1348 SII->second.pop_back();
1349 if (SII->second.empty()) {
1350 SpillIdxes.erase(MBBId);
1351 SpillMBBs.reset(MBBId);
1358 std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1359 SpillIdxes.find(MBBId);
1360 if (SII != SpillIdxes.end() &&
1361 SII->second.back().vreg == NewVReg &&
1362 (int)index > SII->second.back().index)
1363 // Use(s) following the last def, it's not safe to fold the spill.
1364 SII->second.back().canFold = false;
1365 std::map<unsigned, std::vector<SRInfo> >::iterator RII =
1366 RestoreIdxes.find(MBBId);
1367 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1368 // If we are splitting live intervals, only fold if it's the first
1369 // use and there isn't another use later in the MBB.
1370 RII->second.back().canFold = false;
1372 // Only need a reload if there isn't an earlier def / use.
1373 if (RII == RestoreIdxes.end()) {
1374 std::vector<SRInfo> Infos;
1375 Infos.push_back(SRInfo(index, NewVReg, true));
1376 RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1378 RII->second.push_back(SRInfo(index, NewVReg, true));
1380 RestoreMBBs.set(MBBId);
1384 // Update spill weight.
1385 unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1386 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1389 if (NewVReg && TrySplit && AllCanFold) {
1390 // If all of its def / use can be folded, give it a low spill weight.
1391 LiveInterval &nI = getOrCreateInterval(NewVReg);
1396 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1397 BitVector &RestoreMBBs,
1398 std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1399 if (!RestoreMBBs[Id])
1401 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1402 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1403 if (Restores[i].index == index &&
1404 Restores[i].vreg == vr &&
1405 Restores[i].canFold)
1410 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1411 BitVector &RestoreMBBs,
1412 std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1413 if (!RestoreMBBs[Id])
1415 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1416 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1417 if (Restores[i].index == index && Restores[i].vreg)
1418 Restores[i].index = -1;
1421 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1422 /// spilled and create empty intervals for their uses.
1424 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1425 const TargetRegisterClass* rc,
1426 std::vector<LiveInterval*> &NewLIs) {
1427 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1428 re = mri_->reg_end(); ri != re; ) {
1429 MachineOperand &O = ri.getOperand();
1430 MachineInstr *MI = &*ri;
1433 assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
1434 "Register def was not rewritten?");
1435 RemoveMachineInstrFromMaps(MI);
1436 vrm.RemoveMachineInstrFromMaps(MI);
1437 MI->eraseFromParent();
1439 // This must be an use of an implicit_def so it's not part of the live
1440 // interval. Create a new empty live interval for it.
1441 // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1442 unsigned NewVReg = mri_->createVirtualRegister(rc);
1444 vrm.setIsImplicitlyDefined(NewVReg);
1445 NewLIs.push_back(&getOrCreateInterval(NewVReg));
1446 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1447 MachineOperand &MO = MI->getOperand(i);
1448 if (MO.isReg() && MO.getReg() == li.reg)
1456 std::vector<LiveInterval*> LiveIntervals::
1457 addIntervalsForSpills(const LiveInterval &li,
1458 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
1459 // Since this is called after the analysis is done we don't know if
1460 // LiveVariables is available
1461 lv_ = getAnalysisToUpdate<LiveVariables>();
1463 assert(li.weight != HUGE_VALF &&
1464 "attempt to spill already spilled interval!");
1466 DOUT << "\t\t\t\tadding intervals for spills for interval: ";
1467 li.print(DOUT, tri_);
1470 // Each bit specify whether it a spill is required in the MBB.
1471 BitVector SpillMBBs(mf_->getNumBlockIDs());
1472 std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
1473 BitVector RestoreMBBs(mf_->getNumBlockIDs());
1474 std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
1475 std::map<unsigned,unsigned> MBBVRegsMap;
1476 std::vector<LiveInterval*> NewLIs;
1477 const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
1479 unsigned NumValNums = li.getNumValNums();
1480 SmallVector<MachineInstr*, 4> ReMatDefs;
1481 ReMatDefs.resize(NumValNums, NULL);
1482 SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1483 ReMatOrigDefs.resize(NumValNums, NULL);
1484 SmallVector<int, 4> ReMatIds;
1485 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1486 BitVector ReMatDelete(NumValNums);
1487 unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1489 // Spilling a split live interval. It cannot be split any further. Also,
1490 // it's also guaranteed to be a single val# / range interval.
1491 if (vrm.getPreSplitReg(li.reg)) {
1492 vrm.setIsSplitFromReg(li.reg, 0);
1493 // Unset the split kill marker on the last use.
1494 unsigned KillIdx = vrm.getKillPoint(li.reg);
1496 MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1497 assert(KillMI && "Last use disappeared?");
1498 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1499 assert(KillOp != -1 && "Last use disappeared?");
1500 KillMI->getOperand(KillOp).setIsKill(false);
1502 vrm.removeKillPoint(li.reg);
1503 bool DefIsReMat = vrm.isReMaterialized(li.reg);
1504 Slot = vrm.getStackSlot(li.reg);
1505 assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1506 MachineInstr *ReMatDefMI = DefIsReMat ?
1507 vrm.getReMaterializedMI(li.reg) : NULL;
1509 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1510 bool isLoad = isLoadSS ||
1511 (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad()));
1512 bool IsFirstRange = true;
1513 for (LiveInterval::Ranges::const_iterator
1514 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1515 // If this is a split live interval with multiple ranges, it means there
1516 // are two-address instructions that re-defined the value. Only the
1517 // first def can be rematerialized!
1519 // Note ReMatOrigDefMI has already been deleted.
1520 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1521 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1522 false, vrm, rc, ReMatIds, loopInfo,
1523 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1524 MBBVRegsMap, NewLIs);
1526 rewriteInstructionsForSpills(li, false, I, NULL, 0,
1527 Slot, 0, false, false, false,
1528 false, vrm, rc, ReMatIds, loopInfo,
1529 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1530 MBBVRegsMap, NewLIs);
1532 IsFirstRange = false;
1535 handleSpilledImpDefs(li, vrm, rc, NewLIs);
1539 bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
1540 if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
1544 bool NeedStackSlot = false;
1545 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1547 const VNInfo *VNI = *i;
1548 unsigned VN = VNI->id;
1549 unsigned DefIdx = VNI->def;
1551 continue; // Dead val#.
1552 // Is the def for the val# rematerializable?
1553 MachineInstr *ReMatDefMI = (DefIdx == ~0u)
1554 ? 0 : getInstructionFromIndex(DefIdx);
1556 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) {
1557 // Remember how to remat the def of this val#.
1558 ReMatOrigDefs[VN] = ReMatDefMI;
1559 // Original def may be modified so we have to make a copy here. vrm must
1561 ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone();
1563 bool CanDelete = true;
1564 if (VNI->hasPHIKill) {
1565 // A kill is a phi node, not all of its uses can be rematerialized.
1566 // It must not be deleted.
1568 // Need a stack slot if there is any live range where uses cannot be
1570 NeedStackSlot = true;
1573 ReMatDelete.set(VN);
1575 // Need a stack slot if there is any live range where uses cannot be
1577 NeedStackSlot = true;
1581 // One stack slot per live interval.
1582 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
1583 Slot = vrm.assignVirt2StackSlot(li.reg);
1585 // Create new intervals and rewrite defs and uses.
1586 for (LiveInterval::Ranges::const_iterator
1587 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1588 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1589 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1590 bool DefIsReMat = ReMatDefMI != NULL;
1591 bool CanDelete = ReMatDelete[I->valno->id];
1593 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1594 bool isLoad = isLoadSS ||
1595 (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad());
1596 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1597 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1598 CanDelete, vrm, rc, ReMatIds, loopInfo,
1599 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1600 MBBVRegsMap, NewLIs);
1603 // Insert spills / restores if we are splitting.
1605 handleSpilledImpDefs(li, vrm, rc, NewLIs);
1609 SmallPtrSet<LiveInterval*, 4> AddedKill;
1610 SmallVector<unsigned, 2> Ops;
1611 if (NeedStackSlot) {
1612 int Id = SpillMBBs.find_first();
1614 std::vector<SRInfo> &spills = SpillIdxes[Id];
1615 for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1616 int index = spills[i].index;
1617 unsigned VReg = spills[i].vreg;
1618 LiveInterval &nI = getOrCreateInterval(VReg);
1619 bool isReMat = vrm.isReMaterialized(VReg);
1620 MachineInstr *MI = getInstructionFromIndex(index);
1621 bool CanFold = false;
1622 bool FoundUse = false;
1624 if (spills[i].canFold) {
1626 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1627 MachineOperand &MO = MI->getOperand(j);
1628 if (!MO.isRegister() || MO.getReg() != VReg)
1635 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1636 RestoreMBBs, RestoreIdxes))) {
1637 // MI has two-address uses of the same register. If the use
1638 // isn't the first and only use in the BB, then we can't fold
1639 // it. FIXME: Move this to rewriteInstructionsForSpills.
1646 // Fold the store into the def if possible.
1647 bool Folded = false;
1648 if (CanFold && !Ops.empty()) {
1649 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1652 // Also folded uses, do not issue a load.
1653 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1654 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1656 nI.removeRange(getDefIndex(index), getStoreIndex(index));
1660 // Otherwise tell the spiller to issue a spill.
1662 LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1663 bool isKill = LR->end == getStoreIndex(index);
1664 if (!MI->registerDefIsDead(nI.reg))
1665 // No need to spill a dead def.
1666 vrm.addSpillPoint(VReg, isKill, MI);
1668 AddedKill.insert(&nI);
1671 Id = SpillMBBs.find_next(Id);
1675 int Id = RestoreMBBs.find_first();
1677 std::vector<SRInfo> &restores = RestoreIdxes[Id];
1678 for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1679 int index = restores[i].index;
1682 unsigned VReg = restores[i].vreg;
1683 LiveInterval &nI = getOrCreateInterval(VReg);
1684 MachineInstr *MI = getInstructionFromIndex(index);
1685 bool CanFold = false;
1687 if (restores[i].canFold) {
1689 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1690 MachineOperand &MO = MI->getOperand(j);
1691 if (!MO.isRegister() || MO.getReg() != VReg)
1695 // If this restore were to be folded, it would have been folded
1704 // Fold the load into the use if possible.
1705 bool Folded = false;
1706 if (CanFold && !Ops.empty()) {
1707 if (!vrm.isReMaterialized(VReg))
1708 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1710 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1712 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1713 // If the rematerializable def is a load, also try to fold it.
1714 if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad())
1715 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1716 Ops, isLoadSS, LdSlot, VReg);
1717 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
1719 // Re-matting an instruction with virtual register use. Add the
1720 // register as an implicit use on the use MI and update the register
1721 // interval's spill weight to HUGE_VALF to prevent it from being
1723 LiveInterval &ImpLi = getInterval(ImpUse);
1724 ImpLi.weight = HUGE_VALF;
1725 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1729 // If folding is not possible / failed, then tell the spiller to issue a
1730 // load / rematerialization for us.
1732 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1734 vrm.addRestorePoint(VReg, MI);
1736 Id = RestoreMBBs.find_next(Id);
1739 // Finalize intervals: add kills, finalize spill weights, and filter out
1741 std::vector<LiveInterval*> RetNewLIs;
1742 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
1743 LiveInterval *LI = NewLIs[i];
1745 LI->weight /= LI->getSize();
1746 if (!AddedKill.count(LI)) {
1747 LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
1748 unsigned LastUseIdx = getBaseIndex(LR->end);
1749 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
1750 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
1751 assert(UseIdx != -1);
1752 if (LastUse->getOperand(UseIdx).isImplicit() ||
1753 LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){
1754 LastUse->getOperand(UseIdx).setIsKill();
1755 vrm.addKillPoint(LI->reg, LastUseIdx);
1758 RetNewLIs.push_back(LI);
1762 handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
1766 /// hasAllocatableSuperReg - Return true if the specified physical register has
1767 /// any super register that's allocatable.
1768 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
1769 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
1770 if (allocatableRegs_[*AS] && hasInterval(*AS))
1775 /// getRepresentativeReg - Find the largest super register of the specified
1776 /// physical register.
1777 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
1778 // Find the largest super-register that is allocatable.
1779 unsigned BestReg = Reg;
1780 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
1781 unsigned SuperReg = *AS;
1782 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
1790 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
1791 /// specified interval that conflicts with the specified physical register.
1792 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
1793 unsigned PhysReg) const {
1794 unsigned NumConflicts = 0;
1795 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
1796 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
1797 E = mri_->reg_end(); I != E; ++I) {
1798 MachineOperand &O = I.getOperand();
1799 MachineInstr *MI = O.getParent();
1800 unsigned Index = getInstructionIndex(MI);
1801 if (pli.liveAt(Index))
1804 return NumConflicts;
1807 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
1808 /// around all defs and uses of the specified interval.
1809 void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
1810 unsigned PhysReg, VirtRegMap &vrm) {
1811 unsigned SpillReg = getRepresentativeReg(PhysReg);
1813 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
1814 // If there are registers which alias PhysReg, but which are not a
1815 // sub-register of the chosen representative super register. Assert
1816 // since we can't handle it yet.
1817 assert(*AS == SpillReg || !allocatableRegs_[*AS] ||
1818 tri_->isSuperRegister(*AS, SpillReg));
1820 LiveInterval &pli = getInterval(SpillReg);
1821 SmallPtrSet<MachineInstr*, 8> SeenMIs;
1822 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
1823 E = mri_->reg_end(); I != E; ++I) {
1824 MachineOperand &O = I.getOperand();
1825 MachineInstr *MI = O.getParent();
1826 if (SeenMIs.count(MI))
1829 unsigned Index = getInstructionIndex(MI);
1830 if (pli.liveAt(Index)) {
1831 vrm.addEmergencySpill(SpillReg, MI);
1832 pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
1833 for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
1834 if (!hasInterval(*AS))
1836 LiveInterval &spli = getInterval(*AS);
1837 if (spli.liveAt(Index))
1838 spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);