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/CalcSpillWeights.h"
24 #include "llvm/CodeGen/LiveVariables.h"
25 #include "llvm/CodeGen/MachineFrameInfo.h"
26 #include "llvm/CodeGen/MachineInstr.h"
27 #include "llvm/CodeGen/MachineInstrBuilder.h"
28 #include "llvm/CodeGen/MachineLoopInfo.h"
29 #include "llvm/CodeGen/MachineMemOperand.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/Passes.h"
32 #include "llvm/CodeGen/ProcessImplicitDefs.h"
33 #include "llvm/Target/TargetRegisterInfo.h"
34 #include "llvm/Target/TargetInstrInfo.h"
35 #include "llvm/Target/TargetMachine.h"
36 #include "llvm/Target/TargetOptions.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/ErrorHandling.h"
40 #include "llvm/Support/raw_ostream.h"
41 #include "llvm/ADT/DepthFirstIterator.h"
42 #include "llvm/ADT/SmallSet.h"
43 #include "llvm/ADT/Statistic.h"
44 #include "llvm/ADT/STLExtras.h"
50 // Hidden options for help debugging.
51 static cl::opt<bool> DisableReMat("disable-rematerialization",
52 cl::init(false), cl::Hidden);
54 STATISTIC(numIntervals , "Number of original intervals");
55 STATISTIC(numFolds , "Number of loads/stores folded into instructions");
56 STATISTIC(numSplits , "Number of intervals split");
58 char LiveIntervals::ID = 0;
59 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
60 "Live Interval Analysis", false, false)
61 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
62 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
63 INITIALIZE_PASS_DEPENDENCY(PHIElimination)
64 INITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass)
65 INITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs)
66 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
67 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
68 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
69 "Live Interval Analysis", false, false)
71 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
73 AU.addRequired<AliasAnalysis>();
74 AU.addPreserved<AliasAnalysis>();
75 AU.addRequired<LiveVariables>();
76 AU.addPreserved<LiveVariables>();
77 AU.addRequired<MachineLoopInfo>();
78 AU.addPreserved<MachineLoopInfo>();
79 AU.addPreservedID(MachineDominatorsID);
82 AU.addPreservedID(PHIEliminationID);
83 AU.addRequiredID(PHIEliminationID);
86 AU.addRequiredID(TwoAddressInstructionPassID);
87 AU.addPreserved<ProcessImplicitDefs>();
88 AU.addRequired<ProcessImplicitDefs>();
89 AU.addPreserved<SlotIndexes>();
90 AU.addRequiredTransitive<SlotIndexes>();
91 MachineFunctionPass::getAnalysisUsage(AU);
94 void LiveIntervals::releaseMemory() {
95 // Free the live intervals themselves.
96 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
97 E = r2iMap_.end(); I != E; ++I)
102 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
103 VNInfoAllocator.Reset();
104 while (!CloneMIs.empty()) {
105 MachineInstr *MI = CloneMIs.back();
107 mf_->DeleteMachineInstr(MI);
111 /// runOnMachineFunction - Register allocate the whole function
113 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
115 mri_ = &mf_->getRegInfo();
116 tm_ = &fn.getTarget();
117 tri_ = tm_->getRegisterInfo();
118 tii_ = tm_->getInstrInfo();
119 aa_ = &getAnalysis<AliasAnalysis>();
120 lv_ = &getAnalysis<LiveVariables>();
121 indexes_ = &getAnalysis<SlotIndexes>();
122 allocatableRegs_ = tri_->getAllocatableSet(fn);
126 numIntervals += getNumIntervals();
132 /// print - Implement the dump method.
133 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
134 OS << "********** INTERVALS **********\n";
135 for (const_iterator I = begin(), E = end(); I != E; ++I) {
136 I->second->print(OS, tri_);
143 void LiveIntervals::printInstrs(raw_ostream &OS) const {
144 OS << "********** MACHINEINSTRS **********\n";
145 mf_->print(OS, indexes_);
148 void LiveIntervals::dumpInstrs() const {
152 bool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li,
153 VirtRegMap &vrm, unsigned reg) {
154 // We don't handle fancy stuff crossing basic block boundaries
155 if (li.ranges.size() != 1)
157 const LiveRange &range = li.ranges.front();
158 SlotIndex idx = range.start.getBaseIndex();
159 SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex();
161 // Skip deleted instructions
162 MachineInstr *firstMI = getInstructionFromIndex(idx);
163 while (!firstMI && idx != end) {
164 idx = idx.getNextIndex();
165 firstMI = getInstructionFromIndex(idx);
170 // Find last instruction in range
171 SlotIndex lastIdx = end.getPrevIndex();
172 MachineInstr *lastMI = getInstructionFromIndex(lastIdx);
173 while (!lastMI && lastIdx != idx) {
174 lastIdx = lastIdx.getPrevIndex();
175 lastMI = getInstructionFromIndex(lastIdx);
180 // Range cannot cross basic block boundaries or terminators
181 MachineBasicBlock *MBB = firstMI->getParent();
182 if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator())
185 MachineBasicBlock::const_iterator E = lastMI;
187 for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) {
188 const MachineInstr &MI = *I;
190 // Allow copies to and from li.reg
192 if (MI.getOperand(0).getReg() == li.reg ||
193 MI.getOperand(1).getReg() == li.reg)
196 // Check for operands using reg
197 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
198 const MachineOperand& mop = MI.getOperand(i);
201 unsigned PhysReg = mop.getReg();
202 if (PhysReg == 0 || PhysReg == li.reg)
204 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
205 if (!vrm.hasPhys(PhysReg))
207 PhysReg = vrm.getPhys(PhysReg);
209 if (PhysReg && tri_->regsOverlap(PhysReg, reg))
214 // No conflicts found.
218 bool LiveIntervals::conflictsWithAliasRef(LiveInterval &li, unsigned Reg,
219 SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
220 for (LiveInterval::Ranges::const_iterator
221 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
222 for (SlotIndex index = I->start.getBaseIndex(),
223 end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
225 index = index.getNextIndex()) {
226 MachineInstr *MI = getInstructionFromIndex(index);
228 continue; // skip deleted instructions
230 if (JoinedCopies.count(MI))
232 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
233 MachineOperand& MO = MI->getOperand(i);
236 unsigned PhysReg = MO.getReg();
237 if (PhysReg == 0 || PhysReg == Reg ||
238 TargetRegisterInfo::isVirtualRegister(PhysReg))
240 if (tri_->regsOverlap(Reg, PhysReg))
250 bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) {
251 unsigned Reg = MI.getOperand(MOIdx).getReg();
252 for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) {
253 const MachineOperand &MO = MI.getOperand(i);
256 if (MO.getReg() == Reg && MO.isDef()) {
257 assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() &&
258 MI.getOperand(MOIdx).getSubReg() &&
259 (MO.getSubReg() || MO.isImplicit()));
266 /// isPartialRedef - Return true if the specified def at the specific index is
267 /// partially re-defining the specified live interval. A common case of this is
268 /// a definition of the sub-register.
269 bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO,
270 LiveInterval &interval) {
271 if (!MO.getSubReg() || MO.isEarlyClobber())
274 SlotIndex RedefIndex = MIIdx.getDefIndex();
275 const LiveRange *OldLR =
276 interval.getLiveRangeContaining(RedefIndex.getUseIndex());
277 MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
279 return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
284 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
285 MachineBasicBlock::iterator mi,
289 LiveInterval &interval) {
290 DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
292 // Virtual registers may be defined multiple times (due to phi
293 // elimination and 2-addr elimination). Much of what we do only has to be
294 // done once for the vreg. We use an empty interval to detect the first
295 // time we see a vreg.
296 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
297 if (interval.empty()) {
298 // Get the Idx of the defining instructions.
299 SlotIndex defIndex = MIIdx.getDefIndex();
300 // Earlyclobbers move back one, so that they overlap the live range
302 if (MO.isEarlyClobber())
303 defIndex = MIIdx.getUseIndex();
305 // Make sure the first definition is not a partial redefinition. Add an
306 // <imp-def> of the full register.
307 // FIXME: LiveIntervals shouldn't modify the code like this. Whoever
308 // created the machine instruction should annotate it with <undef> flags
309 // as needed. Then we can simply assert here. The REG_SEQUENCE lowering
310 // is the main suspect.
311 if (MO.getSubReg()) {
312 mi->addRegisterDefined(interval.reg);
313 // Mark all defs of interval.reg on this instruction as reading <undef>.
314 for (unsigned i = MOIdx, e = mi->getNumOperands(); i != e; ++i) {
315 MachineOperand &MO2 = mi->getOperand(i);
316 if (MO2.isReg() && MO2.getReg() == interval.reg && MO2.getSubReg())
321 MachineInstr *CopyMI = NULL;
322 if (mi->isCopyLike()) {
326 VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
327 assert(ValNo->id == 0 && "First value in interval is not 0?");
329 // Loop over all of the blocks that the vreg is defined in. There are
330 // two cases we have to handle here. The most common case is a vreg
331 // whose lifetime is contained within a basic block. In this case there
332 // will be a single kill, in MBB, which comes after the definition.
333 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
334 // FIXME: what about dead vars?
336 if (vi.Kills[0] != mi)
337 killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex();
339 killIdx = defIndex.getStoreIndex();
341 // If the kill happens after the definition, we have an intra-block
343 if (killIdx > defIndex) {
344 assert(vi.AliveBlocks.empty() &&
345 "Shouldn't be alive across any blocks!");
346 LiveRange LR(defIndex, killIdx, ValNo);
347 interval.addRange(LR);
348 DEBUG(dbgs() << " +" << LR << "\n");
353 // The other case we handle is when a virtual register lives to the end
354 // of the defining block, potentially live across some blocks, then is
355 // live into some number of blocks, but gets killed. Start by adding a
356 // range that goes from this definition to the end of the defining block.
357 LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
358 DEBUG(dbgs() << " +" << NewLR);
359 interval.addRange(NewLR);
361 bool PHIJoin = lv_->isPHIJoin(interval.reg);
364 // A phi join register is killed at the end of the MBB and revived as a new
365 // valno in the killing blocks.
366 assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
367 DEBUG(dbgs() << " phi-join");
368 ValNo->setHasPHIKill(true);
370 // Iterate over all of the blocks that the variable is completely
371 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
373 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
374 E = vi.AliveBlocks.end(); I != E; ++I) {
375 MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
376 LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
377 interval.addRange(LR);
378 DEBUG(dbgs() << " +" << LR);
382 // Finally, this virtual register is live from the start of any killing
383 // block to the 'use' slot of the killing instruction.
384 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
385 MachineInstr *Kill = vi.Kills[i];
386 SlotIndex Start = getMBBStartIdx(Kill->getParent());
387 SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex();
389 // Create interval with one of a NEW value number. Note that this value
390 // number isn't actually defined by an instruction, weird huh? :)
392 assert(getInstructionFromIndex(Start) == 0 &&
393 "PHI def index points at actual instruction.");
394 ValNo = interval.getNextValue(Start, 0, VNInfoAllocator);
395 ValNo->setIsPHIDef(true);
397 LiveRange LR(Start, killIdx, ValNo);
398 interval.addRange(LR);
399 DEBUG(dbgs() << " +" << LR);
403 if (MultipleDefsBySameMI(*mi, MOIdx))
404 // Multiple defs of the same virtual register by the same instruction.
405 // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
406 // This is likely due to elimination of REG_SEQUENCE instructions. Return
407 // here since there is nothing to do.
410 // If this is the second time we see a virtual register definition, it
411 // must be due to phi elimination or two addr elimination. If this is
412 // the result of two address elimination, then the vreg is one of the
413 // def-and-use register operand.
415 // It may also be partial redef like this:
416 // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
417 // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0
418 bool PartReDef = isPartialRedef(MIIdx, MO, interval);
419 if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) {
420 // If this is a two-address definition, then we have already processed
421 // the live range. The only problem is that we didn't realize there
422 // are actually two values in the live interval. Because of this we
423 // need to take the LiveRegion that defines this register and split it
425 SlotIndex RedefIndex = MIIdx.getDefIndex();
426 if (MO.isEarlyClobber())
427 RedefIndex = MIIdx.getUseIndex();
429 const LiveRange *OldLR =
430 interval.getLiveRangeContaining(RedefIndex.getUseIndex());
431 VNInfo *OldValNo = OldLR->valno;
432 SlotIndex DefIndex = OldValNo->def.getDefIndex();
434 // Delete the previous value, which should be short and continuous,
435 // because the 2-addr copy must be in the same MBB as the redef.
436 interval.removeRange(DefIndex, RedefIndex);
438 // The new value number (#1) is defined by the instruction we claimed
440 VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
442 // Value#0 is now defined by the 2-addr instruction.
443 OldValNo->def = RedefIndex;
444 OldValNo->setCopy(0);
446 // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ...
447 if (PartReDef && mi->isCopyLike())
448 OldValNo->setCopy(&*mi);
450 // Add the new live interval which replaces the range for the input copy.
451 LiveRange LR(DefIndex, RedefIndex, ValNo);
452 DEBUG(dbgs() << " replace range with " << LR);
453 interval.addRange(LR);
455 // If this redefinition is dead, we need to add a dummy unit live
456 // range covering the def slot.
458 interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(),
462 dbgs() << " RESULT: ";
463 interval.print(dbgs(), tri_);
465 } else if (lv_->isPHIJoin(interval.reg)) {
466 // In the case of PHI elimination, each variable definition is only
467 // live until the end of the block. We've already taken care of the
468 // rest of the live range.
470 SlotIndex defIndex = MIIdx.getDefIndex();
471 if (MO.isEarlyClobber())
472 defIndex = MIIdx.getUseIndex();
475 MachineInstr *CopyMI = NULL;
476 if (mi->isCopyLike())
478 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
480 SlotIndex killIndex = getMBBEndIdx(mbb);
481 LiveRange LR(defIndex, killIndex, ValNo);
482 interval.addRange(LR);
483 ValNo->setHasPHIKill(true);
484 DEBUG(dbgs() << " phi-join +" << LR);
486 llvm_unreachable("Multiply defined register");
490 DEBUG(dbgs() << '\n');
493 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
494 MachineBasicBlock::iterator mi,
497 LiveInterval &interval,
498 MachineInstr *CopyMI) {
499 // A physical register cannot be live across basic block, so its
500 // lifetime must end somewhere in its defining basic block.
501 DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
503 SlotIndex baseIndex = MIIdx;
504 SlotIndex start = baseIndex.getDefIndex();
505 // Earlyclobbers move back one.
506 if (MO.isEarlyClobber())
507 start = MIIdx.getUseIndex();
508 SlotIndex end = start;
510 // If it is not used after definition, it is considered dead at
511 // the instruction defining it. Hence its interval is:
512 // [defSlot(def), defSlot(def)+1)
513 // For earlyclobbers, the defSlot was pushed back one; the extra
514 // advance below compensates.
516 DEBUG(dbgs() << " dead");
517 end = start.getStoreIndex();
521 // If it is not dead on definition, it must be killed by a
522 // subsequent instruction. Hence its interval is:
523 // [defSlot(def), useSlot(kill)+1)
524 baseIndex = baseIndex.getNextIndex();
525 while (++mi != MBB->end()) {
527 if (mi->isDebugValue())
529 if (getInstructionFromIndex(baseIndex) == 0)
530 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
532 if (mi->killsRegister(interval.reg, tri_)) {
533 DEBUG(dbgs() << " killed");
534 end = baseIndex.getDefIndex();
537 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
539 if (mi->isRegTiedToUseOperand(DefIdx)) {
540 // Two-address instruction.
541 end = baseIndex.getDefIndex();
543 // Another instruction redefines the register before it is ever read.
544 // Then the register is essentially dead at the instruction that
545 // defines it. Hence its interval is:
546 // [defSlot(def), defSlot(def)+1)
547 DEBUG(dbgs() << " dead");
548 end = start.getStoreIndex();
554 baseIndex = baseIndex.getNextIndex();
557 // The only case we should have a dead physreg here without a killing or
558 // instruction where we know it's dead is if it is live-in to the function
559 // and never used. Another possible case is the implicit use of the
560 // physical register has been deleted by two-address pass.
561 end = start.getStoreIndex();
564 assert(start < end && "did not find end of interval?");
566 // Already exists? Extend old live interval.
567 VNInfo *ValNo = interval.getVNInfoAt(start);
568 bool Extend = ValNo != 0;
570 ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator);
571 if (Extend && MO.isEarlyClobber())
572 ValNo->setHasRedefByEC(true);
573 LiveRange LR(start, end, ValNo);
574 interval.addRange(LR);
575 DEBUG(dbgs() << " +" << LR << '\n');
578 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
579 MachineBasicBlock::iterator MI,
583 if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
584 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
585 getOrCreateInterval(MO.getReg()));
587 MachineInstr *CopyMI = NULL;
588 if (MI->isCopyLike())
590 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
591 getOrCreateInterval(MO.getReg()), CopyMI);
595 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
597 LiveInterval &interval, bool isAlias) {
598 DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_));
600 // Look for kills, if it reaches a def before it's killed, then it shouldn't
601 // be considered a livein.
602 MachineBasicBlock::iterator mi = MBB->begin();
603 MachineBasicBlock::iterator E = MBB->end();
604 // Skip over DBG_VALUE at the start of the MBB.
605 if (mi != E && mi->isDebugValue()) {
606 while (++mi != E && mi->isDebugValue())
609 // MBB is empty except for DBG_VALUE's.
613 SlotIndex baseIndex = MIIdx;
614 SlotIndex start = baseIndex;
615 if (getInstructionFromIndex(baseIndex) == 0)
616 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
618 SlotIndex end = baseIndex;
619 bool SeenDefUse = false;
622 if (mi->killsRegister(interval.reg, tri_)) {
623 DEBUG(dbgs() << " killed");
624 end = baseIndex.getDefIndex();
627 } else if (mi->definesRegister(interval.reg, tri_)) {
628 // Another instruction redefines the register before it is ever read.
629 // Then the register is essentially dead at the instruction that defines
630 // it. Hence its interval is:
631 // [defSlot(def), defSlot(def)+1)
632 DEBUG(dbgs() << " dead");
633 end = start.getStoreIndex();
638 while (++mi != E && mi->isDebugValue())
639 // Skip over DBG_VALUE.
642 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
645 // Live-in register might not be used at all.
648 DEBUG(dbgs() << " dead");
649 end = MIIdx.getStoreIndex();
651 DEBUG(dbgs() << " live through");
652 end = getMBBEndIdx(MBB);
656 SlotIndex defIdx = getMBBStartIdx(MBB);
657 assert(getInstructionFromIndex(defIdx) == 0 &&
658 "PHI def index points at actual instruction.");
660 interval.getNextValue(defIdx, 0, VNInfoAllocator);
661 vni->setIsPHIDef(true);
662 LiveRange LR(start, end, vni);
664 interval.addRange(LR);
665 DEBUG(dbgs() << " +" << LR << '\n');
668 /// computeIntervals - computes the live intervals for virtual
669 /// registers. for some ordering of the machine instructions [1,N] a
670 /// live interval is an interval [i, j) where 1 <= i <= j < N for
671 /// which a variable is live
672 void LiveIntervals::computeIntervals() {
673 DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
674 << "********** Function: "
675 << ((Value*)mf_->getFunction())->getName() << '\n');
677 SmallVector<unsigned, 8> UndefUses;
678 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
680 MachineBasicBlock *MBB = MBBI;
684 // Track the index of the current machine instr.
685 SlotIndex MIIndex = getMBBStartIdx(MBB);
686 DEBUG(dbgs() << "BB#" << MBB->getNumber()
687 << ":\t\t# derived from " << MBB->getName() << "\n");
689 // Create intervals for live-ins to this BB first.
690 for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
691 LE = MBB->livein_end(); LI != LE; ++LI) {
692 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
693 // Multiple live-ins can alias the same register.
694 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
695 if (!hasInterval(*AS))
696 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
700 // Skip over empty initial indices.
701 if (getInstructionFromIndex(MIIndex) == 0)
702 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
704 for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
706 DEBUG(dbgs() << MIIndex << "\t" << *MI);
707 if (MI->isDebugValue())
711 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
712 MachineOperand &MO = MI->getOperand(i);
713 if (!MO.isReg() || !MO.getReg())
716 // handle register defs - build intervals
718 handleRegisterDef(MBB, MI, MIIndex, MO, i);
719 else if (MO.isUndef())
720 UndefUses.push_back(MO.getReg());
723 // Move to the next instr slot.
724 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
728 // Create empty intervals for registers defined by implicit_def's (except
729 // for those implicit_def that define values which are liveout of their
731 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
732 unsigned UndefReg = UndefUses[i];
733 (void)getOrCreateInterval(UndefReg);
737 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
738 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
739 return new LiveInterval(reg, Weight);
742 /// dupInterval - Duplicate a live interval. The caller is responsible for
743 /// managing the allocated memory.
744 LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
745 LiveInterval *NewLI = createInterval(li->reg);
746 NewLI->Copy(*li, mri_, getVNInfoAllocator());
750 /// shrinkToUses - After removing some uses of a register, shrink its live
751 /// range to just the remaining uses. This method does not compute reaching
752 /// defs for new uses, and it doesn't remove dead defs.
753 bool LiveIntervals::shrinkToUses(LiveInterval *li,
754 SmallVectorImpl<MachineInstr*> *dead) {
755 DEBUG(dbgs() << "Shrink: " << *li << '\n');
756 assert(TargetRegisterInfo::isVirtualRegister(li->reg)
757 && "Can't only shrink physical registers");
758 // Find all the values used, including PHI kills.
759 SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
761 // Blocks that have already been added to WorkList as live-out.
762 SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
764 // Visit all instructions reading li->reg.
765 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg);
766 MachineInstr *UseMI = I.skipInstruction();) {
767 if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
769 SlotIndex Idx = getInstructionIndex(UseMI).getUseIndex();
770 VNInfo *VNI = li->getVNInfoAt(Idx);
772 // This shouldn't happen: readsVirtualRegister returns true, but there is
773 // no live value. It is likely caused by a target getting <undef> flags
775 DEBUG(dbgs() << Idx << '\t' << *UseMI
776 << "Warning: Instr claims to read non-existent value in "
780 if (VNI->def == Idx) {
781 // Special case: An early-clobber tied operand reads and writes the
782 // register one slot early.
783 Idx = Idx.getPrevSlot();
784 VNI = li->getVNInfoAt(Idx);
785 assert(VNI && "Early-clobber tied value not available");
787 WorkList.push_back(std::make_pair(Idx, VNI));
790 // Create a new live interval with only minimal live segments per def.
791 LiveInterval NewLI(li->reg, 0);
792 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
797 NewLI.addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), VNI));
799 // A use tied to an early-clobber def ends at the load slot and isn't caught
800 // above. Catch it here instead. This probably only ever happens for inline
802 if (VNI->def.isUse())
803 if (VNInfo *UVNI = li->getVNInfoAt(VNI->def.getLoadIndex()))
804 WorkList.push_back(std::make_pair(VNI->def.getLoadIndex(), UVNI));
807 // Keep track of the PHIs that are in use.
808 SmallPtrSet<VNInfo*, 8> UsedPHIs;
810 // Extend intervals to reach all uses in WorkList.
811 while (!WorkList.empty()) {
812 SlotIndex Idx = WorkList.back().first;
813 VNInfo *VNI = WorkList.back().second;
815 const MachineBasicBlock *MBB = getMBBFromIndex(Idx);
816 SlotIndex BlockStart = getMBBStartIdx(MBB);
818 // Extend the live range for VNI to be live at Idx.
819 if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx.getNextSlot())) {
821 assert(ExtVNI == VNI && "Unexpected existing value number");
822 // Is this a PHIDef we haven't seen before?
823 if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
825 // The PHI is live, make sure the predecessors are live-out.
826 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
827 PE = MBB->pred_end(); PI != PE; ++PI) {
828 if (!LiveOut.insert(*PI))
830 SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
831 // A predecessor is not required to have a live-out value for a PHI.
832 if (VNInfo *PVNI = li->getVNInfoAt(Stop))
833 WorkList.push_back(std::make_pair(Stop, PVNI));
838 // VNI is live-in to MBB.
839 DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
840 NewLI.addRange(LiveRange(BlockStart, Idx.getNextSlot(), VNI));
842 // Make sure VNI is live-out from the predecessors.
843 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
844 PE = MBB->pred_end(); PI != PE; ++PI) {
845 if (!LiveOut.insert(*PI))
847 SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
848 assert(li->getVNInfoAt(Stop) == VNI && "Wrong value out of predecessor");
849 WorkList.push_back(std::make_pair(Stop, VNI));
853 // Handle dead values.
854 bool CanSeparate = false;
855 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
860 LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
861 assert(LII != NewLI.end() && "Missing live range for PHI");
862 if (LII->end != VNI->def.getNextSlot())
864 if (VNI->isPHIDef()) {
865 // This is a dead PHI. Remove it.
866 VNI->setIsUnused(true);
867 NewLI.removeRange(*LII);
868 DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
871 // This is a dead def. Make sure the instruction knows.
872 MachineInstr *MI = getInstructionFromIndex(VNI->def);
873 assert(MI && "No instruction defining live value");
874 MI->addRegisterDead(li->reg, tri_);
875 if (dead && MI->allDefsAreDead()) {
876 DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
882 // Move the trimmed ranges back.
883 li->ranges.swap(NewLI.ranges);
884 DEBUG(dbgs() << "Shrunk: " << *li << '\n');
889 //===----------------------------------------------------------------------===//
890 // Register allocator hooks.
893 MachineBasicBlock::iterator
894 LiveIntervals::getLastSplitPoint(const LiveInterval &li,
895 MachineBasicBlock *mbb) const {
896 const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor();
898 // If li is not live into a landing pad, we can insert spill code before the
900 if (!lpad || !isLiveInToMBB(li, lpad))
901 return mbb->getFirstTerminator();
903 // When there is a landing pad, spill code must go before the call instruction
905 MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin();
908 if (I->getDesc().isCall())
911 // The block contains no calls that can throw, so use the first terminator.
912 return mbb->getFirstTerminator();
915 void LiveIntervals::addKillFlags() {
916 for (iterator I = begin(), E = end(); I != E; ++I) {
917 unsigned Reg = I->first;
918 if (TargetRegisterInfo::isPhysicalRegister(Reg))
920 if (mri_->reg_nodbg_empty(Reg))
922 LiveInterval *LI = I->second;
924 // Every instruction that kills Reg corresponds to a live range end point.
925 for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
927 // A LOAD index indicates an MBB edge.
928 if (RI->end.isLoad())
930 MachineInstr *MI = getInstructionFromIndex(RI->end);
933 MI->addRegisterKilled(Reg, NULL);
938 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
939 /// allow one) virtual register operand, then its uses are implicitly using
940 /// the register. Returns the virtual register.
941 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
942 MachineInstr *MI) const {
944 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
945 MachineOperand &MO = MI->getOperand(i);
946 if (!MO.isReg() || !MO.isUse())
948 unsigned Reg = MO.getReg();
949 if (Reg == 0 || Reg == li.reg)
952 if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
953 !allocatableRegs_[Reg])
955 // FIXME: For now, only remat MI with at most one register operand.
957 "Can't rematerialize instruction with multiple register operand!");
966 /// isValNoAvailableAt - Return true if the val# of the specified interval
967 /// which reaches the given instruction also reaches the specified use index.
968 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
969 SlotIndex UseIdx) const {
970 VNInfo *UValNo = li.getVNInfoAt(UseIdx);
971 return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI));
974 /// isReMaterializable - Returns true if the definition MI of the specified
975 /// val# of the specified interval is re-materializable.
977 LiveIntervals::isReMaterializable(const LiveInterval &li,
978 const VNInfo *ValNo, MachineInstr *MI,
979 const SmallVectorImpl<LiveInterval*> *SpillIs,
984 if (!tii_->isTriviallyReMaterializable(MI, aa_))
987 // Target-specific code can mark an instruction as being rematerializable
988 // if it has one virtual reg use, though it had better be something like
989 // a PIC base register which is likely to be live everywhere.
990 unsigned ImpUse = getReMatImplicitUse(li, MI);
992 const LiveInterval &ImpLi = getInterval(ImpUse);
993 for (MachineRegisterInfo::use_nodbg_iterator
994 ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
996 MachineInstr *UseMI = &*ri;
997 SlotIndex UseIdx = getInstructionIndex(UseMI);
998 if (li.getVNInfoAt(UseIdx) != ValNo)
1000 if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
1004 // If a register operand of the re-materialized instruction is going to
1005 // be spilled next, then it's not legal to re-materialize this instruction.
1007 for (unsigned i = 0, e = SpillIs->size(); i != e; ++i)
1008 if (ImpUse == (*SpillIs)[i]->reg)
1014 /// isReMaterializable - Returns true if the definition MI of the specified
1015 /// val# of the specified interval is re-materializable.
1016 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1017 const VNInfo *ValNo, MachineInstr *MI) {
1019 return isReMaterializable(li, ValNo, MI, 0, Dummy2);
1022 /// isReMaterializable - Returns true if every definition of MI of every
1023 /// val# of the specified interval is re-materializable.
1025 LiveIntervals::isReMaterializable(const LiveInterval &li,
1026 const SmallVectorImpl<LiveInterval*> *SpillIs,
1029 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1031 const VNInfo *VNI = *i;
1032 if (VNI->isUnused())
1033 continue; // Dead val#.
1034 // Is the def for the val# rematerializable?
1035 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1038 bool DefIsLoad = false;
1040 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
1042 isLoad |= DefIsLoad;
1047 /// FilterFoldedOps - Filter out two-address use operands. Return
1048 /// true if it finds any issue with the operands that ought to prevent
1050 static bool FilterFoldedOps(MachineInstr *MI,
1051 SmallVector<unsigned, 2> &Ops,
1053 SmallVector<unsigned, 2> &FoldOps) {
1055 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1056 unsigned OpIdx = Ops[i];
1057 MachineOperand &MO = MI->getOperand(OpIdx);
1058 // FIXME: fold subreg use.
1062 MRInfo |= (unsigned)VirtRegMap::isMod;
1064 // Filter out two-address use operand(s).
1065 if (MI->isRegTiedToDefOperand(OpIdx)) {
1066 MRInfo = VirtRegMap::isModRef;
1069 MRInfo |= (unsigned)VirtRegMap::isRef;
1071 FoldOps.push_back(OpIdx);
1077 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
1078 /// slot / to reg or any rematerialized load into ith operand of specified
1079 /// MI. If it is successul, MI is updated with the newly created MI and
1081 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
1082 VirtRegMap &vrm, MachineInstr *DefMI,
1084 SmallVector<unsigned, 2> &Ops,
1085 bool isSS, int Slot, unsigned Reg) {
1086 // If it is an implicit def instruction, just delete it.
1087 if (MI->isImplicitDef()) {
1088 RemoveMachineInstrFromMaps(MI);
1089 vrm.RemoveMachineInstrFromMaps(MI);
1090 MI->eraseFromParent();
1095 // Filter the list of operand indexes that are to be folded. Abort if
1096 // any operand will prevent folding.
1097 unsigned MRInfo = 0;
1098 SmallVector<unsigned, 2> FoldOps;
1099 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1102 // The only time it's safe to fold into a two address instruction is when
1103 // it's folding reload and spill from / into a spill stack slot.
1104 if (DefMI && (MRInfo & VirtRegMap::isMod))
1107 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot)
1108 : tii_->foldMemoryOperand(MI, FoldOps, DefMI);
1110 // Remember this instruction uses the spill slot.
1111 if (isSS) vrm.addSpillSlotUse(Slot, fmi);
1113 // Attempt to fold the memory reference into the instruction. If
1114 // we can do this, we don't need to insert spill code.
1115 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
1116 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
1117 vrm.transferSpillPts(MI, fmi);
1118 vrm.transferRestorePts(MI, fmi);
1119 vrm.transferEmergencySpills(MI, fmi);
1120 ReplaceMachineInstrInMaps(MI, fmi);
1121 MI->eraseFromParent();
1129 /// canFoldMemoryOperand - Returns true if the specified load / store
1130 /// folding is possible.
1131 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
1132 SmallVector<unsigned, 2> &Ops,
1134 // Filter the list of operand indexes that are to be folded. Abort if
1135 // any operand will prevent folding.
1136 unsigned MRInfo = 0;
1137 SmallVector<unsigned, 2> FoldOps;
1138 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1141 // It's only legal to remat for a use, not a def.
1142 if (ReMat && (MRInfo & VirtRegMap::isMod))
1145 return tii_->canFoldMemoryOperand(MI, FoldOps);
1148 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
1149 LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
1151 MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end);
1156 for (++itr; itr != li.ranges.end(); ++itr) {
1157 MachineBasicBlock *mbb2 =
1158 indexes_->getMBBCoveringRange(itr->start, itr->end);
1167 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
1168 /// interval on to-be re-materialized operands of MI) with new register.
1169 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
1170 MachineInstr *MI, unsigned NewVReg,
1172 // There is an implicit use. That means one of the other operand is
1173 // being remat'ed and the remat'ed instruction has li.reg as an
1174 // use operand. Make sure we rewrite that as well.
1175 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1176 MachineOperand &MO = MI->getOperand(i);
1179 unsigned Reg = MO.getReg();
1180 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1182 if (!vrm.isReMaterialized(Reg))
1184 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
1185 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
1187 UseMO->setReg(NewVReg);
1191 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
1192 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
1193 bool LiveIntervals::
1194 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
1195 bool TrySplit, SlotIndex index, SlotIndex end,
1197 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1198 unsigned Slot, int LdSlot,
1199 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1201 const TargetRegisterClass* rc,
1202 SmallVector<int, 4> &ReMatIds,
1203 const MachineLoopInfo *loopInfo,
1204 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
1205 DenseMap<unsigned,unsigned> &MBBVRegsMap,
1206 std::vector<LiveInterval*> &NewLIs) {
1207 bool CanFold = false;
1209 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1210 MachineOperand& mop = MI->getOperand(i);
1213 unsigned Reg = mop.getReg();
1214 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1219 bool TryFold = !DefIsReMat;
1220 bool FoldSS = true; // Default behavior unless it's a remat.
1221 int FoldSlot = Slot;
1223 // If this is the rematerializable definition MI itself and
1224 // all of its uses are rematerialized, simply delete it.
1225 if (MI == ReMatOrigDefMI && CanDelete) {
1226 DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: "
1228 RemoveMachineInstrFromMaps(MI);
1229 vrm.RemoveMachineInstrFromMaps(MI);
1230 MI->eraseFromParent();
1234 // If def for this use can't be rematerialized, then try folding.
1235 // If def is rematerializable and it's a load, also try folding.
1236 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1238 // Try fold loads (from stack slot, constant pool, etc.) into uses.
1244 // Scan all of the operands of this instruction rewriting operands
1245 // to use NewVReg instead of li.reg as appropriate. We do this for
1248 // 1. If the instr reads the same spilled vreg multiple times, we
1249 // want to reuse the NewVReg.
1250 // 2. If the instr is a two-addr instruction, we are required to
1251 // keep the src/dst regs pinned.
1253 // Keep track of whether we replace a use and/or def so that we can
1254 // create the spill interval with the appropriate range.
1255 SmallVector<unsigned, 2> Ops;
1256 tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops);
1258 // Create a new virtual register for the spill interval.
1259 // Create the new register now so we can map the fold instruction
1260 // to the new register so when it is unfolded we get the correct
1262 bool CreatedNewVReg = false;
1264 NewVReg = mri_->createVirtualRegister(rc);
1266 CreatedNewVReg = true;
1268 // The new virtual register should get the same allocation hints as the
1270 std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg);
1271 if (Hint.first || Hint.second)
1272 mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second);
1278 // Do not fold load / store here if we are splitting. We'll find an
1279 // optimal point to insert a load / store later.
1281 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1282 Ops, FoldSS, FoldSlot, NewVReg)) {
1283 // Folding the load/store can completely change the instruction in
1284 // unpredictable ways, rescan it from the beginning.
1287 // We need to give the new vreg the same stack slot as the
1288 // spilled interval.
1289 vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
1295 if (isNotInMIMap(MI))
1297 goto RestartInstruction;
1300 // We'll try to fold it later if it's profitable.
1301 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1305 mop.setReg(NewVReg);
1306 if (mop.isImplicit())
1307 rewriteImplicitOps(li, MI, NewVReg, vrm);
1309 // Reuse NewVReg for other reads.
1310 bool HasEarlyClobber = false;
1311 for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1312 MachineOperand &mopj = MI->getOperand(Ops[j]);
1313 mopj.setReg(NewVReg);
1314 if (mopj.isImplicit())
1315 rewriteImplicitOps(li, MI, NewVReg, vrm);
1316 if (mopj.isEarlyClobber())
1317 HasEarlyClobber = true;
1320 if (CreatedNewVReg) {
1322 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
1323 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1324 // Each valnum may have its own remat id.
1325 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1327 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1329 if (!CanDelete || (HasUse && HasDef)) {
1330 // If this is a two-addr instruction then its use operands are
1331 // rematerializable but its def is not. It should be assigned a
1333 vrm.assignVirt2StackSlot(NewVReg, Slot);
1336 vrm.assignVirt2StackSlot(NewVReg, Slot);
1338 } else if (HasUse && HasDef &&
1339 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1340 // If this interval hasn't been assigned a stack slot (because earlier
1341 // def is a deleted remat def), do it now.
1342 assert(Slot != VirtRegMap::NO_STACK_SLOT);
1343 vrm.assignVirt2StackSlot(NewVReg, Slot);
1346 // Re-matting an instruction with virtual register use. Add the
1347 // register as an implicit use on the use MI.
1348 if (DefIsReMat && ImpUse)
1349 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1351 // Create a new register interval for this spill / remat.
1352 LiveInterval &nI = getOrCreateInterval(NewVReg);
1353 if (CreatedNewVReg) {
1354 NewLIs.push_back(&nI);
1355 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1357 vrm.setIsSplitFromReg(NewVReg, li.reg);
1361 if (CreatedNewVReg) {
1362 LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
1363 nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
1364 DEBUG(dbgs() << " +" << LR);
1367 // Extend the split live interval to this def / use.
1368 SlotIndex End = index.getDefIndex();
1369 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1370 nI.getValNumInfo(nI.getNumValNums()-1));
1371 DEBUG(dbgs() << " +" << LR);
1376 // An early clobber starts at the use slot, except for an early clobber
1377 // tied to a use operand (yes, that is a thing).
1378 LiveRange LR(HasEarlyClobber && !HasUse ?
1379 index.getUseIndex() : index.getDefIndex(),
1380 index.getStoreIndex(),
1381 nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
1382 DEBUG(dbgs() << " +" << LR);
1387 dbgs() << "\t\t\t\tAdded new interval: ";
1388 nI.print(dbgs(), tri_);
1394 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1396 MachineBasicBlock *MBB,
1397 SlotIndex Idx) const {
1398 return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB));
1401 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1402 /// during spilling.
1404 struct RewriteInfo {
1407 RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {}
1410 struct RewriteInfoCompare {
1411 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1412 return LHS.Index < RHS.Index;
1417 void LiveIntervals::
1418 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1419 LiveInterval::Ranges::const_iterator &I,
1420 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1421 unsigned Slot, int LdSlot,
1422 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1424 const TargetRegisterClass* rc,
1425 SmallVector<int, 4> &ReMatIds,
1426 const MachineLoopInfo *loopInfo,
1427 BitVector &SpillMBBs,
1428 DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
1429 BitVector &RestoreMBBs,
1430 DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1431 DenseMap<unsigned,unsigned> &MBBVRegsMap,
1432 std::vector<LiveInterval*> &NewLIs) {
1433 bool AllCanFold = true;
1434 unsigned NewVReg = 0;
1435 SlotIndex start = I->start.getBaseIndex();
1436 SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
1438 // First collect all the def / use in this live range that will be rewritten.
1439 // Make sure they are sorted according to instruction index.
1440 std::vector<RewriteInfo> RewriteMIs;
1441 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1442 re = mri_->reg_end(); ri != re; ) {
1443 MachineInstr *MI = &*ri;
1444 MachineOperand &O = ri.getOperand();
1446 if (MI->isDebugValue()) {
1447 // Modify DBG_VALUE now that the value is in a spill slot.
1448 if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) {
1449 uint64_t Offset = MI->getOperand(1).getImm();
1450 const MDNode *MDPtr = MI->getOperand(2).getMetadata();
1451 DebugLoc DL = MI->getDebugLoc();
1452 int FI = isLoadSS ? LdSlot : (int)Slot;
1453 if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI,
1454 Offset, MDPtr, DL)) {
1455 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
1456 ReplaceMachineInstrInMaps(MI, NewDV);
1457 MachineBasicBlock *MBB = MI->getParent();
1458 MBB->insert(MBB->erase(MI), NewDV);
1463 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1464 RemoveMachineInstrFromMaps(MI);
1465 vrm.RemoveMachineInstrFromMaps(MI);
1466 MI->eraseFromParent();
1469 assert(!(O.isImplicit() && O.isUse()) &&
1470 "Spilling register that's used as implicit use?");
1471 SlotIndex index = getInstructionIndex(MI);
1472 if (index < start || index >= end)
1476 // Must be defined by an implicit def. It should not be spilled. Note,
1477 // this is for correctness reason. e.g.
1478 // 8 %reg1024<def> = IMPLICIT_DEF
1479 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1480 // The live range [12, 14) are not part of the r1024 live interval since
1481 // it's defined by an implicit def. It will not conflicts with live
1482 // interval of r1025. Now suppose both registers are spilled, you can
1483 // easily see a situation where both registers are reloaded before
1484 // the INSERT_SUBREG and both target registers that would overlap.
1486 RewriteMIs.push_back(RewriteInfo(index, MI));
1488 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1490 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1491 // Now rewrite the defs and uses.
1492 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1493 RewriteInfo &rwi = RewriteMIs[i];
1495 SlotIndex index = rwi.Index;
1496 MachineInstr *MI = rwi.MI;
1497 // If MI def and/or use the same register multiple times, then there
1498 // are multiple entries.
1499 while (i != e && RewriteMIs[i].MI == MI) {
1500 assert(RewriteMIs[i].Index == index);
1503 MachineBasicBlock *MBB = MI->getParent();
1505 if (ImpUse && MI != ReMatDefMI) {
1506 // Re-matting an instruction with virtual register use. Prevent interval
1507 // from being spilled.
1508 getInterval(ImpUse).markNotSpillable();
1511 unsigned MBBId = MBB->getNumber();
1512 unsigned ThisVReg = 0;
1514 DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
1515 if (NVI != MBBVRegsMap.end()) {
1516 ThisVReg = NVI->second;
1523 // It's better to start a new interval to avoid artificially
1524 // extend the new interval.
1525 if (MI->readsWritesVirtualRegister(li.reg) ==
1526 std::make_pair(false,true)) {
1527 MBBVRegsMap.erase(MBB->getNumber());
1533 bool IsNew = ThisVReg == 0;
1535 // This ends the previous live interval. If all of its def / use
1536 // can be folded, give it a low spill weight.
1537 if (NewVReg && TrySplit && AllCanFold) {
1538 LiveInterval &nI = getOrCreateInterval(NewVReg);
1545 bool HasDef = false;
1546 bool HasUse = false;
1547 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1548 index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1549 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1550 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1551 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
1552 if (!HasDef && !HasUse)
1555 AllCanFold &= CanFold;
1557 // Update weight of spill interval.
1558 LiveInterval &nI = getOrCreateInterval(NewVReg);
1560 // The spill weight is now infinity as it cannot be spilled again.
1561 nI.markNotSpillable();
1565 // Keep track of the last def and first use in each MBB.
1567 if (MI != ReMatOrigDefMI || !CanDelete) {
1568 bool HasKill = false;
1570 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex());
1572 // If this is a two-address code, then this index starts a new VNInfo.
1573 const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex());
1575 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex());
1577 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1578 SpillIdxes.find(MBBId);
1580 if (SII == SpillIdxes.end()) {
1581 std::vector<SRInfo> S;
1582 S.push_back(SRInfo(index, NewVReg, true));
1583 SpillIdxes.insert(std::make_pair(MBBId, S));
1584 } else if (SII->second.back().vreg != NewVReg) {
1585 SII->second.push_back(SRInfo(index, NewVReg, true));
1586 } else if (index > SII->second.back().index) {
1587 // If there is an earlier def and this is a two-address
1588 // instruction, then it's not possible to fold the store (which
1589 // would also fold the load).
1590 SRInfo &Info = SII->second.back();
1592 Info.canFold = !HasUse;
1594 SpillMBBs.set(MBBId);
1595 } else if (SII != SpillIdxes.end() &&
1596 SII->second.back().vreg == NewVReg &&
1597 index > SII->second.back().index) {
1598 // There is an earlier def that's not killed (must be two-address).
1599 // The spill is no longer needed.
1600 SII->second.pop_back();
1601 if (SII->second.empty()) {
1602 SpillIdxes.erase(MBBId);
1603 SpillMBBs.reset(MBBId);
1610 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1611 SpillIdxes.find(MBBId);
1612 if (SII != SpillIdxes.end() &&
1613 SII->second.back().vreg == NewVReg &&
1614 index > SII->second.back().index)
1615 // Use(s) following the last def, it's not safe to fold the spill.
1616 SII->second.back().canFold = false;
1617 DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
1618 RestoreIdxes.find(MBBId);
1619 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1620 // If we are splitting live intervals, only fold if it's the first
1621 // use and there isn't another use later in the MBB.
1622 RII->second.back().canFold = false;
1624 // Only need a reload if there isn't an earlier def / use.
1625 if (RII == RestoreIdxes.end()) {
1626 std::vector<SRInfo> Infos;
1627 Infos.push_back(SRInfo(index, NewVReg, true));
1628 RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1630 RII->second.push_back(SRInfo(index, NewVReg, true));
1632 RestoreMBBs.set(MBBId);
1636 // Update spill weight.
1637 unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1638 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1641 if (NewVReg && TrySplit && AllCanFold) {
1642 // If all of its def / use can be folded, give it a low spill weight.
1643 LiveInterval &nI = getOrCreateInterval(NewVReg);
1648 bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index,
1649 unsigned vr, BitVector &RestoreMBBs,
1650 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1651 if (!RestoreMBBs[Id])
1653 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1654 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1655 if (Restores[i].index == index &&
1656 Restores[i].vreg == vr &&
1657 Restores[i].canFold)
1662 void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index,
1663 unsigned vr, BitVector &RestoreMBBs,
1664 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1665 if (!RestoreMBBs[Id])
1667 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1668 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1669 if (Restores[i].index == index && Restores[i].vreg)
1670 Restores[i].index = SlotIndex();
1673 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1674 /// spilled and create empty intervals for their uses.
1676 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1677 const TargetRegisterClass* rc,
1678 std::vector<LiveInterval*> &NewLIs) {
1679 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1680 re = mri_->reg_end(); ri != re; ) {
1681 MachineOperand &O = ri.getOperand();
1682 MachineInstr *MI = &*ri;
1684 if (MI->isDebugValue()) {
1685 // Remove debug info for now.
1687 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1691 assert(MI->isImplicitDef() &&
1692 "Register def was not rewritten?");
1693 RemoveMachineInstrFromMaps(MI);
1694 vrm.RemoveMachineInstrFromMaps(MI);
1695 MI->eraseFromParent();
1697 // This must be an use of an implicit_def so it's not part of the live
1698 // interval. Create a new empty live interval for it.
1699 // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1700 unsigned NewVReg = mri_->createVirtualRegister(rc);
1702 vrm.setIsImplicitlyDefined(NewVReg);
1703 NewLIs.push_back(&getOrCreateInterval(NewVReg));
1704 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1705 MachineOperand &MO = MI->getOperand(i);
1706 if (MO.isReg() && MO.getReg() == li.reg) {
1716 LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
1717 // Limit the loop depth ridiculousness.
1718 if (loopDepth > 200)
1721 // The loop depth is used to roughly estimate the number of times the
1722 // instruction is executed. Something like 10^d is simple, but will quickly
1723 // overflow a float. This expression behaves like 10^d for small d, but is
1724 // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
1725 // headroom before overflow.
1726 // By the way, powf() might be unavailable here. For consistency,
1727 // We may take pow(double,double).
1728 float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
1730 return (isDef + isUse) * lc;
1733 static void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) {
1734 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
1736 normalizeSpillWeight(NewLIs[i]->weight, NewLIs[i]->getSize());
1739 std::vector<LiveInterval*> LiveIntervals::
1740 addIntervalsForSpills(const LiveInterval &li,
1741 const SmallVectorImpl<LiveInterval*> *SpillIs,
1742 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
1743 assert(li.isSpillable() && "attempt to spill already spilled interval!");
1746 dbgs() << "\t\t\t\tadding intervals for spills for interval: ";
1747 li.print(dbgs(), tri_);
1751 // Each bit specify whether a spill is required in the MBB.
1752 BitVector SpillMBBs(mf_->getNumBlockIDs());
1753 DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
1754 BitVector RestoreMBBs(mf_->getNumBlockIDs());
1755 DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
1756 DenseMap<unsigned,unsigned> MBBVRegsMap;
1757 std::vector<LiveInterval*> NewLIs;
1758 const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
1760 unsigned NumValNums = li.getNumValNums();
1761 SmallVector<MachineInstr*, 4> ReMatDefs;
1762 ReMatDefs.resize(NumValNums, NULL);
1763 SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1764 ReMatOrigDefs.resize(NumValNums, NULL);
1765 SmallVector<int, 4> ReMatIds;
1766 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1767 BitVector ReMatDelete(NumValNums);
1768 unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1770 // Spilling a split live interval. It cannot be split any further. Also,
1771 // it's also guaranteed to be a single val# / range interval.
1772 if (vrm.getPreSplitReg(li.reg)) {
1773 vrm.setIsSplitFromReg(li.reg, 0);
1774 // Unset the split kill marker on the last use.
1775 SlotIndex KillIdx = vrm.getKillPoint(li.reg);
1776 if (KillIdx != SlotIndex()) {
1777 MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1778 assert(KillMI && "Last use disappeared?");
1779 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1780 assert(KillOp != -1 && "Last use disappeared?");
1781 KillMI->getOperand(KillOp).setIsKill(false);
1783 vrm.removeKillPoint(li.reg);
1784 bool DefIsReMat = vrm.isReMaterialized(li.reg);
1785 Slot = vrm.getStackSlot(li.reg);
1786 assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1787 MachineInstr *ReMatDefMI = DefIsReMat ?
1788 vrm.getReMaterializedMI(li.reg) : NULL;
1790 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1791 bool isLoad = isLoadSS ||
1792 (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
1793 bool IsFirstRange = true;
1794 for (LiveInterval::Ranges::const_iterator
1795 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1796 // If this is a split live interval with multiple ranges, it means there
1797 // are two-address instructions that re-defined the value. Only the
1798 // first def can be rematerialized!
1800 // Note ReMatOrigDefMI has already been deleted.
1801 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1802 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1803 false, vrm, rc, ReMatIds, loopInfo,
1804 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1805 MBBVRegsMap, NewLIs);
1807 rewriteInstructionsForSpills(li, false, I, NULL, 0,
1808 Slot, 0, false, false, false,
1809 false, vrm, rc, ReMatIds, loopInfo,
1810 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1811 MBBVRegsMap, NewLIs);
1813 IsFirstRange = false;
1816 handleSpilledImpDefs(li, vrm, rc, NewLIs);
1817 normalizeSpillWeights(NewLIs);
1821 bool TrySplit = !intervalIsInOneMBB(li);
1824 bool NeedStackSlot = false;
1825 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1827 const VNInfo *VNI = *i;
1828 unsigned VN = VNI->id;
1829 if (VNI->isUnused())
1830 continue; // Dead val#.
1831 // Is the def for the val# rematerializable?
1832 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1834 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
1835 // Remember how to remat the def of this val#.
1836 ReMatOrigDefs[VN] = ReMatDefMI;
1837 // Original def may be modified so we have to make a copy here.
1838 MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
1839 CloneMIs.push_back(Clone);
1840 ReMatDefs[VN] = Clone;
1842 bool CanDelete = true;
1843 if (VNI->hasPHIKill()) {
1844 // A kill is a phi node, not all of its uses can be rematerialized.
1845 // It must not be deleted.
1847 // Need a stack slot if there is any live range where uses cannot be
1849 NeedStackSlot = true;
1852 ReMatDelete.set(VN);
1854 // Need a stack slot if there is any live range where uses cannot be
1856 NeedStackSlot = true;
1860 // One stack slot per live interval.
1861 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
1862 if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
1863 Slot = vrm.assignVirt2StackSlot(li.reg);
1865 // This case only occurs when the prealloc splitter has already assigned
1866 // a stack slot to this vreg.
1868 Slot = vrm.getStackSlot(li.reg);
1871 // Create new intervals and rewrite defs and uses.
1872 for (LiveInterval::Ranges::const_iterator
1873 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1874 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1875 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1876 bool DefIsReMat = ReMatDefMI != NULL;
1877 bool CanDelete = ReMatDelete[I->valno->id];
1879 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1880 bool isLoad = isLoadSS ||
1881 (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
1882 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1883 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1884 CanDelete, vrm, rc, ReMatIds, loopInfo,
1885 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1886 MBBVRegsMap, NewLIs);
1889 // Insert spills / restores if we are splitting.
1891 handleSpilledImpDefs(li, vrm, rc, NewLIs);
1892 normalizeSpillWeights(NewLIs);
1896 SmallPtrSet<LiveInterval*, 4> AddedKill;
1897 SmallVector<unsigned, 2> Ops;
1898 if (NeedStackSlot) {
1899 int Id = SpillMBBs.find_first();
1901 std::vector<SRInfo> &spills = SpillIdxes[Id];
1902 for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1903 SlotIndex index = spills[i].index;
1904 unsigned VReg = spills[i].vreg;
1905 LiveInterval &nI = getOrCreateInterval(VReg);
1906 bool isReMat = vrm.isReMaterialized(VReg);
1907 MachineInstr *MI = getInstructionFromIndex(index);
1908 bool CanFold = false;
1909 bool FoundUse = false;
1911 if (spills[i].canFold) {
1913 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1914 MachineOperand &MO = MI->getOperand(j);
1915 if (!MO.isReg() || MO.getReg() != VReg)
1922 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1923 RestoreMBBs, RestoreIdxes))) {
1924 // MI has two-address uses of the same register. If the use
1925 // isn't the first and only use in the BB, then we can't fold
1926 // it. FIXME: Move this to rewriteInstructionsForSpills.
1933 // Fold the store into the def if possible.
1934 bool Folded = false;
1935 if (CanFold && !Ops.empty()) {
1936 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1939 // Also folded uses, do not issue a load.
1940 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1941 nI.removeRange(index.getLoadIndex(), index.getDefIndex());
1943 nI.removeRange(index.getDefIndex(), index.getStoreIndex());
1947 // Otherwise tell the spiller to issue a spill.
1949 LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1950 bool isKill = LR->end == index.getStoreIndex();
1951 if (!MI->registerDefIsDead(nI.reg))
1952 // No need to spill a dead def.
1953 vrm.addSpillPoint(VReg, isKill, MI);
1955 AddedKill.insert(&nI);
1958 Id = SpillMBBs.find_next(Id);
1962 int Id = RestoreMBBs.find_first();
1964 std::vector<SRInfo> &restores = RestoreIdxes[Id];
1965 for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1966 SlotIndex index = restores[i].index;
1967 if (index == SlotIndex())
1969 unsigned VReg = restores[i].vreg;
1970 LiveInterval &nI = getOrCreateInterval(VReg);
1971 bool isReMat = vrm.isReMaterialized(VReg);
1972 MachineInstr *MI = getInstructionFromIndex(index);
1973 bool CanFold = false;
1975 if (restores[i].canFold) {
1977 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1978 MachineOperand &MO = MI->getOperand(j);
1979 if (!MO.isReg() || MO.getReg() != VReg)
1983 // If this restore were to be folded, it would have been folded
1992 // Fold the load into the use if possible.
1993 bool Folded = false;
1994 if (CanFold && !Ops.empty()) {
1996 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1998 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
2000 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
2001 // If the rematerializable def is a load, also try to fold it.
2002 if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
2003 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
2004 Ops, isLoadSS, LdSlot, VReg);
2006 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
2008 // Re-matting an instruction with virtual register use. Add the
2009 // register as an implicit use on the use MI and mark the register
2010 // interval as unspillable.
2011 LiveInterval &ImpLi = getInterval(ImpUse);
2012 ImpLi.markNotSpillable();
2013 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
2018 // If folding is not possible / failed, then tell the spiller to issue a
2019 // load / rematerialization for us.
2021 nI.removeRange(index.getLoadIndex(), index.getDefIndex());
2023 vrm.addRestorePoint(VReg, MI);
2025 Id = RestoreMBBs.find_next(Id);
2028 // Finalize intervals: add kills, finalize spill weights, and filter out
2030 std::vector<LiveInterval*> RetNewLIs;
2031 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
2032 LiveInterval *LI = NewLIs[i];
2034 if (!AddedKill.count(LI)) {
2035 LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
2036 SlotIndex LastUseIdx = LR->end.getBaseIndex();
2037 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
2038 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
2039 assert(UseIdx != -1);
2040 if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
2041 LastUse->getOperand(UseIdx).setIsKill();
2042 vrm.addKillPoint(LI->reg, LastUseIdx);
2045 RetNewLIs.push_back(LI);
2049 handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
2050 normalizeSpillWeights(RetNewLIs);
2054 /// hasAllocatableSuperReg - Return true if the specified physical register has
2055 /// any super register that's allocatable.
2056 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
2057 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
2058 if (allocatableRegs_[*AS] && hasInterval(*AS))
2063 /// getRepresentativeReg - Find the largest super register of the specified
2064 /// physical register.
2065 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
2066 // Find the largest super-register that is allocatable.
2067 unsigned BestReg = Reg;
2068 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
2069 unsigned SuperReg = *AS;
2070 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
2078 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
2079 /// specified interval that conflicts with the specified physical register.
2080 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
2081 unsigned PhysReg) const {
2082 unsigned NumConflicts = 0;
2083 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
2084 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2085 E = mri_->reg_end(); I != E; ++I) {
2086 MachineOperand &O = I.getOperand();
2087 MachineInstr *MI = O.getParent();
2088 if (MI->isDebugValue())
2090 SlotIndex Index = getInstructionIndex(MI);
2091 if (pli.liveAt(Index))
2094 return NumConflicts;
2097 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
2098 /// around all defs and uses of the specified interval. Return true if it
2099 /// was able to cut its interval.
2100 bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
2101 unsigned PhysReg, VirtRegMap &vrm) {
2102 unsigned SpillReg = getRepresentativeReg(PhysReg);
2104 DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg)
2105 << " represented by " << tri_->getName(SpillReg) << '\n');
2107 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
2108 // If there are registers which alias PhysReg, but which are not a
2109 // sub-register of the chosen representative super register. Assert
2110 // since we can't handle it yet.
2111 assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
2112 tri_->isSuperRegister(*AS, SpillReg));
2115 SmallVector<unsigned, 4> PRegs;
2116 if (hasInterval(SpillReg))
2117 PRegs.push_back(SpillReg);
2118 for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR)
2119 if (hasInterval(*SR))
2120 PRegs.push_back(*SR);
2123 dbgs() << "Trying to spill:";
2124 for (unsigned i = 0, e = PRegs.size(); i != e; ++i)
2125 dbgs() << ' ' << tri_->getName(PRegs[i]);
2129 SmallPtrSet<MachineInstr*, 8> SeenMIs;
2130 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2131 E = mri_->reg_end(); I != E; ++I) {
2132 MachineOperand &O = I.getOperand();
2133 MachineInstr *MI = O.getParent();
2134 if (MI->isDebugValue() || SeenMIs.count(MI))
2137 SlotIndex Index = getInstructionIndex(MI);
2138 bool LiveReg = false;
2139 for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
2140 unsigned PReg = PRegs[i];
2141 LiveInterval &pli = getInterval(PReg);
2142 if (!pli.liveAt(Index))
2145 SlotIndex StartIdx = Index.getLoadIndex();
2146 SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
2147 if (!pli.isInOneLiveRange(StartIdx, EndIdx)) {
2149 raw_string_ostream Msg(msg);
2150 Msg << "Ran out of registers during register allocation!";
2151 if (MI->isInlineAsm()) {
2152 Msg << "\nPlease check your inline asm statement for invalid "
2153 << "constraints:\n";
2154 MI->print(Msg, tm_);
2156 report_fatal_error(Msg.str());
2158 pli.removeRange(StartIdx, EndIdx);
2163 DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI);
2164 vrm.addEmergencySpill(SpillReg, MI);
2170 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
2171 MachineInstr* startInst) {
2172 LiveInterval& Interval = getOrCreateInterval(reg);
2173 VNInfo* VN = Interval.getNextValue(
2174 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
2175 startInst, getVNInfoAllocator());
2176 VN->setHasPHIKill(true);
2178 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
2179 getMBBEndIdx(startInst->getParent()), VN);
2180 Interval.addRange(LR);