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.
308 mi->addRegisterDefined(interval.reg);
310 MachineInstr *CopyMI = NULL;
311 if (mi->isCopyLike()) {
315 VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
316 assert(ValNo->id == 0 && "First value in interval is not 0?");
318 // Loop over all of the blocks that the vreg is defined in. There are
319 // two cases we have to handle here. The most common case is a vreg
320 // whose lifetime is contained within a basic block. In this case there
321 // will be a single kill, in MBB, which comes after the definition.
322 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
323 // FIXME: what about dead vars?
325 if (vi.Kills[0] != mi)
326 killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex();
328 killIdx = defIndex.getStoreIndex();
330 // If the kill happens after the definition, we have an intra-block
332 if (killIdx > defIndex) {
333 assert(vi.AliveBlocks.empty() &&
334 "Shouldn't be alive across any blocks!");
335 LiveRange LR(defIndex, killIdx, ValNo);
336 interval.addRange(LR);
337 DEBUG(dbgs() << " +" << LR << "\n");
342 // The other case we handle is when a virtual register lives to the end
343 // of the defining block, potentially live across some blocks, then is
344 // live into some number of blocks, but gets killed. Start by adding a
345 // range that goes from this definition to the end of the defining block.
346 LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
347 DEBUG(dbgs() << " +" << NewLR);
348 interval.addRange(NewLR);
350 bool PHIJoin = lv_->isPHIJoin(interval.reg);
353 // A phi join register is killed at the end of the MBB and revived as a new
354 // valno in the killing blocks.
355 assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
356 DEBUG(dbgs() << " phi-join");
357 ValNo->setHasPHIKill(true);
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 (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
363 E = vi.AliveBlocks.end(); I != E; ++I) {
364 MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
365 LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
366 interval.addRange(LR);
367 DEBUG(dbgs() << " +" << LR);
371 // Finally, this virtual register is live from the start of any killing
372 // block to the 'use' slot of the killing instruction.
373 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
374 MachineInstr *Kill = vi.Kills[i];
375 SlotIndex Start = getMBBStartIdx(Kill->getParent());
376 SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex();
378 // Create interval with one of a NEW value number. Note that this value
379 // number isn't actually defined by an instruction, weird huh? :)
381 assert(getInstructionFromIndex(Start) == 0 &&
382 "PHI def index points at actual instruction.");
383 ValNo = interval.getNextValue(Start, 0, VNInfoAllocator);
384 ValNo->setIsPHIDef(true);
386 LiveRange LR(Start, killIdx, ValNo);
387 interval.addRange(LR);
388 DEBUG(dbgs() << " +" << LR);
392 if (MultipleDefsBySameMI(*mi, MOIdx))
393 // Multiple defs of the same virtual register by the same instruction.
394 // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
395 // This is likely due to elimination of REG_SEQUENCE instructions. Return
396 // here since there is nothing to do.
399 // If this is the second time we see a virtual register definition, it
400 // must be due to phi elimination or two addr elimination. If this is
401 // the result of two address elimination, then the vreg is one of the
402 // def-and-use register operand.
404 // It may also be partial redef like this:
405 // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
406 // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0
407 bool PartReDef = isPartialRedef(MIIdx, MO, interval);
408 if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) {
409 // If this is a two-address definition, then we have already processed
410 // the live range. The only problem is that we didn't realize there
411 // are actually two values in the live interval. Because of this we
412 // need to take the LiveRegion that defines this register and split it
414 SlotIndex RedefIndex = MIIdx.getDefIndex();
415 if (MO.isEarlyClobber())
416 RedefIndex = MIIdx.getUseIndex();
418 const LiveRange *OldLR =
419 interval.getLiveRangeContaining(RedefIndex.getUseIndex());
420 VNInfo *OldValNo = OldLR->valno;
421 SlotIndex DefIndex = OldValNo->def.getDefIndex();
423 // Delete the previous value, which should be short and continuous,
424 // because the 2-addr copy must be in the same MBB as the redef.
425 interval.removeRange(DefIndex, RedefIndex);
427 // The new value number (#1) is defined by the instruction we claimed
429 VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
431 // Value#0 is now defined by the 2-addr instruction.
432 OldValNo->def = RedefIndex;
433 OldValNo->setCopy(0);
435 // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ...
436 if (PartReDef && mi->isCopyLike())
437 OldValNo->setCopy(&*mi);
439 // Add the new live interval which replaces the range for the input copy.
440 LiveRange LR(DefIndex, RedefIndex, ValNo);
441 DEBUG(dbgs() << " replace range with " << LR);
442 interval.addRange(LR);
444 // If this redefinition is dead, we need to add a dummy unit live
445 // range covering the def slot.
447 interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(),
451 dbgs() << " RESULT: ";
452 interval.print(dbgs(), tri_);
454 } else if (lv_->isPHIJoin(interval.reg)) {
455 // In the case of PHI elimination, each variable definition is only
456 // live until the end of the block. We've already taken care of the
457 // rest of the live range.
459 SlotIndex defIndex = MIIdx.getDefIndex();
460 if (MO.isEarlyClobber())
461 defIndex = MIIdx.getUseIndex();
464 MachineInstr *CopyMI = NULL;
465 if (mi->isCopyLike())
467 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
469 SlotIndex killIndex = getMBBEndIdx(mbb);
470 LiveRange LR(defIndex, killIndex, ValNo);
471 interval.addRange(LR);
472 ValNo->setHasPHIKill(true);
473 DEBUG(dbgs() << " phi-join +" << LR);
475 llvm_unreachable("Multiply defined register");
479 DEBUG(dbgs() << '\n');
482 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
483 MachineBasicBlock::iterator mi,
486 LiveInterval &interval,
487 MachineInstr *CopyMI) {
488 // A physical register cannot be live across basic block, so its
489 // lifetime must end somewhere in its defining basic block.
490 DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
492 SlotIndex baseIndex = MIIdx;
493 SlotIndex start = baseIndex.getDefIndex();
494 // Earlyclobbers move back one.
495 if (MO.isEarlyClobber())
496 start = MIIdx.getUseIndex();
497 SlotIndex end = start;
499 // If it is not used after definition, it is considered dead at
500 // the instruction defining it. Hence its interval is:
501 // [defSlot(def), defSlot(def)+1)
502 // For earlyclobbers, the defSlot was pushed back one; the extra
503 // advance below compensates.
505 DEBUG(dbgs() << " dead");
506 end = start.getStoreIndex();
510 // If it is not dead on definition, it must be killed by a
511 // subsequent instruction. Hence its interval is:
512 // [defSlot(def), useSlot(kill)+1)
513 baseIndex = baseIndex.getNextIndex();
514 while (++mi != MBB->end()) {
516 if (mi->isDebugValue())
518 if (getInstructionFromIndex(baseIndex) == 0)
519 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
521 if (mi->killsRegister(interval.reg, tri_)) {
522 DEBUG(dbgs() << " killed");
523 end = baseIndex.getDefIndex();
526 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
528 if (mi->isRegTiedToUseOperand(DefIdx)) {
529 // Two-address instruction.
530 end = baseIndex.getDefIndex();
532 // Another instruction redefines the register before it is ever read.
533 // Then the register is essentially dead at the instruction that
534 // defines it. Hence its interval is:
535 // [defSlot(def), defSlot(def)+1)
536 DEBUG(dbgs() << " dead");
537 end = start.getStoreIndex();
543 baseIndex = baseIndex.getNextIndex();
546 // The only case we should have a dead physreg here without a killing or
547 // instruction where we know it's dead is if it is live-in to the function
548 // and never used. Another possible case is the implicit use of the
549 // physical register has been deleted by two-address pass.
550 end = start.getStoreIndex();
553 assert(start < end && "did not find end of interval?");
555 // Already exists? Extend old live interval.
556 VNInfo *ValNo = interval.getVNInfoAt(start);
557 bool Extend = ValNo != 0;
559 ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator);
560 if (Extend && MO.isEarlyClobber())
561 ValNo->setHasRedefByEC(true);
562 LiveRange LR(start, end, ValNo);
563 interval.addRange(LR);
564 DEBUG(dbgs() << " +" << LR << '\n');
567 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
568 MachineBasicBlock::iterator MI,
572 if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
573 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
574 getOrCreateInterval(MO.getReg()));
575 else if (allocatableRegs_[MO.getReg()]) {
576 MachineInstr *CopyMI = NULL;
577 if (MI->isCopyLike())
579 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
580 getOrCreateInterval(MO.getReg()), CopyMI);
581 // Def of a register also defines its sub-registers.
582 for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS)
583 // If MI also modifies the sub-register explicitly, avoid processing it
584 // more than once. Do not pass in TRI here so it checks for exact match.
585 if (!MI->definesRegister(*AS))
586 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
587 getOrCreateInterval(*AS), 0);
591 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
593 LiveInterval &interval, bool isAlias) {
594 DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_));
596 // Look for kills, if it reaches a def before it's killed, then it shouldn't
597 // be considered a livein.
598 MachineBasicBlock::iterator mi = MBB->begin();
599 MachineBasicBlock::iterator E = MBB->end();
600 // Skip over DBG_VALUE at the start of the MBB.
601 if (mi != E && mi->isDebugValue()) {
602 while (++mi != E && mi->isDebugValue())
605 // MBB is empty except for DBG_VALUE's.
609 SlotIndex baseIndex = MIIdx;
610 SlotIndex start = baseIndex;
611 if (getInstructionFromIndex(baseIndex) == 0)
612 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
614 SlotIndex end = baseIndex;
615 bool SeenDefUse = false;
618 if (mi->killsRegister(interval.reg, tri_)) {
619 DEBUG(dbgs() << " killed");
620 end = baseIndex.getDefIndex();
623 } else if (mi->definesRegister(interval.reg, tri_)) {
624 // Another instruction redefines the register before it is ever read.
625 // Then the register is essentially dead at the instruction that defines
626 // it. Hence its interval is:
627 // [defSlot(def), defSlot(def)+1)
628 DEBUG(dbgs() << " dead");
629 end = start.getStoreIndex();
634 while (++mi != E && mi->isDebugValue())
635 // Skip over DBG_VALUE.
638 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
641 // Live-in register might not be used at all.
644 DEBUG(dbgs() << " dead");
645 end = MIIdx.getStoreIndex();
647 DEBUG(dbgs() << " live through");
652 SlotIndex defIdx = getMBBStartIdx(MBB);
653 assert(getInstructionFromIndex(defIdx) == 0 &&
654 "PHI def index points at actual instruction.");
656 interval.getNextValue(defIdx, 0, VNInfoAllocator);
657 vni->setIsPHIDef(true);
658 LiveRange LR(start, end, vni);
660 interval.addRange(LR);
661 DEBUG(dbgs() << " +" << LR << '\n');
664 /// computeIntervals - computes the live intervals for virtual
665 /// registers. for some ordering of the machine instructions [1,N] a
666 /// live interval is an interval [i, j) where 1 <= i <= j < N for
667 /// which a variable is live
668 void LiveIntervals::computeIntervals() {
669 DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
670 << "********** Function: "
671 << ((Value*)mf_->getFunction())->getName() << '\n');
673 SmallVector<unsigned, 8> UndefUses;
674 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
676 MachineBasicBlock *MBB = MBBI;
680 // Track the index of the current machine instr.
681 SlotIndex MIIndex = getMBBStartIdx(MBB);
682 DEBUG(dbgs() << "BB#" << MBB->getNumber()
683 << ":\t\t# derived from " << MBB->getName() << "\n");
685 // Create intervals for live-ins to this BB first.
686 for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
687 LE = MBB->livein_end(); LI != LE; ++LI) {
688 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
689 // Multiple live-ins can alias the same register.
690 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
691 if (!hasInterval(*AS))
692 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
696 // Skip over empty initial indices.
697 if (getInstructionFromIndex(MIIndex) == 0)
698 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
700 for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
702 DEBUG(dbgs() << MIIndex << "\t" << *MI);
703 if (MI->isDebugValue())
707 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
708 MachineOperand &MO = MI->getOperand(i);
709 if (!MO.isReg() || !MO.getReg())
712 // handle register defs - build intervals
714 handleRegisterDef(MBB, MI, MIIndex, MO, i);
715 else if (MO.isUndef())
716 UndefUses.push_back(MO.getReg());
719 // Move to the next instr slot.
720 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
724 // Create empty intervals for registers defined by implicit_def's (except
725 // for those implicit_def that define values which are liveout of their
727 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
728 unsigned UndefReg = UndefUses[i];
729 (void)getOrCreateInterval(UndefReg);
733 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
734 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
735 return new LiveInterval(reg, Weight);
738 /// dupInterval - Duplicate a live interval. The caller is responsible for
739 /// managing the allocated memory.
740 LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
741 LiveInterval *NewLI = createInterval(li->reg);
742 NewLI->Copy(*li, mri_, getVNInfoAllocator());
746 /// shrinkToUses - After removing some uses of a register, shrink its live
747 /// range to just the remaining uses. This method does not compute reaching
748 /// defs for new uses, and it doesn't remove dead defs.
749 bool LiveIntervals::shrinkToUses(LiveInterval *li,
750 SmallVectorImpl<MachineInstr*> *dead) {
751 DEBUG(dbgs() << "Shrink: " << *li << '\n');
752 assert(TargetRegisterInfo::isVirtualRegister(li->reg)
753 && "Can't only shrink physical registers");
754 // Find all the values used, including PHI kills.
755 SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
757 // Visit all instructions reading li->reg.
758 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg);
759 MachineInstr *UseMI = I.skipInstruction();) {
760 if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
762 SlotIndex Idx = getInstructionIndex(UseMI).getUseIndex();
763 VNInfo *VNI = li->getVNInfoAt(Idx);
765 // This shouldn't happen: readsVirtualRegister returns true, but there is
766 // no live value. It is likely caused by a target getting <undef> flags
768 DEBUG(dbgs() << Idx << '\t' << *UseMI
769 << "Warning: Instr claims to read non-existent value in "
773 if (VNI->def == Idx) {
774 // Special case: An early-clobber tied operand reads and writes the
775 // register one slot early.
776 Idx = Idx.getPrevSlot();
777 VNI = li->getVNInfoAt(Idx);
778 assert(VNI && "Early-clobber tied value not available");
780 WorkList.push_back(std::make_pair(Idx, VNI));
783 // Create a new live interval with only minimal live segments per def.
784 LiveInterval NewLI(li->reg, 0);
785 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
790 NewLI.addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), VNI));
792 // A use tied to an early-clobber def ends at the load slot and isn't caught
793 // above. Catch it here instead. This probably only ever happens for inline
795 if (VNI->def.isUse())
796 if (VNInfo *UVNI = li->getVNInfoAt(VNI->def.getLoadIndex()))
797 WorkList.push_back(std::make_pair(VNI->def.getLoadIndex(), UVNI));
800 // Keep track of the PHIs that are in use.
801 SmallPtrSet<VNInfo*, 8> UsedPHIs;
803 // Extend intervals to reach all uses in WorkList.
804 while (!WorkList.empty()) {
805 SlotIndex Idx = WorkList.back().first;
806 VNInfo *VNI = WorkList.back().second;
808 const MachineBasicBlock *MBB = getMBBFromIndex(Idx);
809 SlotIndex BlockStart = getMBBStartIdx(MBB);
811 // Extend the live range for VNI to be live at Idx.
812 if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
814 assert(ExtVNI == VNI && "Unexpected existing value number");
815 // Is this a PHIDef we haven't seen before?
816 if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
818 // The PHI is live, make sure the predecessors are live-out.
819 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
820 PE = MBB->pred_end(); PI != PE; ++PI) {
821 SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
822 VNInfo *PVNI = li->getVNInfoAt(Stop);
823 // A predecessor is not required to have a live-out value for a PHI.
825 assert(PVNI->hasPHIKill() && "Missing hasPHIKill flag");
826 WorkList.push_back(std::make_pair(Stop, PVNI));
832 // VNI is live-in to MBB.
833 DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
834 NewLI.addRange(LiveRange(BlockStart, Idx.getNextSlot(), VNI));
836 // Make sure VNI is live-out from the predecessors.
837 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
838 PE = MBB->pred_end(); PI != PE; ++PI) {
839 SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
840 assert(li->getVNInfoAt(Stop) == VNI && "Wrong value out of predecessor");
841 WorkList.push_back(std::make_pair(Stop, VNI));
845 // Handle dead values.
846 bool CanSeparate = false;
847 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
852 LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
853 assert(LII != NewLI.end() && "Missing live range for PHI");
854 if (LII->end != VNI->def.getNextSlot())
856 if (VNI->isPHIDef()) {
857 // This is a dead PHI. Remove it.
858 VNI->setIsUnused(true);
859 NewLI.removeRange(*LII);
860 DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
863 // This is a dead def. Make sure the instruction knows.
864 MachineInstr *MI = getInstructionFromIndex(VNI->def);
865 assert(MI && "No instruction defining live value");
866 MI->addRegisterDead(li->reg, tri_);
867 if (dead && MI->allDefsAreDead()) {
868 DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
874 // Move the trimmed ranges back.
875 li->ranges.swap(NewLI.ranges);
876 DEBUG(dbgs() << "Shrunk: " << *li << '\n');
881 //===----------------------------------------------------------------------===//
882 // Register allocator hooks.
885 MachineBasicBlock::iterator
886 LiveIntervals::getLastSplitPoint(const LiveInterval &li,
887 MachineBasicBlock *mbb) const {
888 const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor();
890 // If li is not live into a landing pad, we can insert spill code before the
892 if (!lpad || !isLiveInToMBB(li, lpad))
893 return mbb->getFirstTerminator();
895 // When there is a landing pad, spill code must go before the call instruction
897 MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin();
900 if (I->getDesc().isCall())
903 // The block contains no calls that can throw, so use the first terminator.
904 return mbb->getFirstTerminator();
907 void LiveIntervals::addKillFlags() {
908 for (iterator I = begin(), E = end(); I != E; ++I) {
909 unsigned Reg = I->first;
910 if (TargetRegisterInfo::isPhysicalRegister(Reg))
912 if (mri_->reg_nodbg_empty(Reg))
914 LiveInterval *LI = I->second;
916 // Every instruction that kills Reg corresponds to a live range end point.
917 for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
919 // A LOAD index indicates an MBB edge.
920 if (RI->end.isLoad())
922 MachineInstr *MI = getInstructionFromIndex(RI->end);
925 MI->addRegisterKilled(Reg, NULL);
930 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
931 /// allow one) virtual register operand, then its uses are implicitly using
932 /// the register. Returns the virtual register.
933 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
934 MachineInstr *MI) const {
936 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
937 MachineOperand &MO = MI->getOperand(i);
938 if (!MO.isReg() || !MO.isUse())
940 unsigned Reg = MO.getReg();
941 if (Reg == 0 || Reg == li.reg)
944 if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
945 !allocatableRegs_[Reg])
947 // FIXME: For now, only remat MI with at most one register operand.
949 "Can't rematerialize instruction with multiple register operand!");
958 /// isValNoAvailableAt - Return true if the val# of the specified interval
959 /// which reaches the given instruction also reaches the specified use index.
960 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
961 SlotIndex UseIdx) const {
962 VNInfo *UValNo = li.getVNInfoAt(UseIdx);
963 return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI));
966 /// isReMaterializable - Returns true if the definition MI of the specified
967 /// val# of the specified interval is re-materializable.
969 LiveIntervals::isReMaterializable(const LiveInterval &li,
970 const VNInfo *ValNo, MachineInstr *MI,
971 const SmallVectorImpl<LiveInterval*> *SpillIs,
976 if (!tii_->isTriviallyReMaterializable(MI, aa_))
979 // Target-specific code can mark an instruction as being rematerializable
980 // if it has one virtual reg use, though it had better be something like
981 // a PIC base register which is likely to be live everywhere.
982 unsigned ImpUse = getReMatImplicitUse(li, MI);
984 const LiveInterval &ImpLi = getInterval(ImpUse);
985 for (MachineRegisterInfo::use_nodbg_iterator
986 ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
988 MachineInstr *UseMI = &*ri;
989 SlotIndex UseIdx = getInstructionIndex(UseMI);
990 if (li.getVNInfoAt(UseIdx) != ValNo)
992 if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
996 // If a register operand of the re-materialized instruction is going to
997 // be spilled next, then it's not legal to re-materialize this instruction.
999 for (unsigned i = 0, e = SpillIs->size(); i != e; ++i)
1000 if (ImpUse == (*SpillIs)[i]->reg)
1006 /// isReMaterializable - Returns true if the definition MI of the specified
1007 /// val# of the specified interval is re-materializable.
1008 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1009 const VNInfo *ValNo, MachineInstr *MI) {
1011 return isReMaterializable(li, ValNo, MI, 0, Dummy2);
1014 /// isReMaterializable - Returns true if every definition of MI of every
1015 /// val# of the specified interval is re-materializable.
1017 LiveIntervals::isReMaterializable(const LiveInterval &li,
1018 const SmallVectorImpl<LiveInterval*> *SpillIs,
1021 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1023 const VNInfo *VNI = *i;
1024 if (VNI->isUnused())
1025 continue; // Dead val#.
1026 // Is the def for the val# rematerializable?
1027 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1030 bool DefIsLoad = false;
1032 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
1034 isLoad |= DefIsLoad;
1039 /// FilterFoldedOps - Filter out two-address use operands. Return
1040 /// true if it finds any issue with the operands that ought to prevent
1042 static bool FilterFoldedOps(MachineInstr *MI,
1043 SmallVector<unsigned, 2> &Ops,
1045 SmallVector<unsigned, 2> &FoldOps) {
1047 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1048 unsigned OpIdx = Ops[i];
1049 MachineOperand &MO = MI->getOperand(OpIdx);
1050 // FIXME: fold subreg use.
1054 MRInfo |= (unsigned)VirtRegMap::isMod;
1056 // Filter out two-address use operand(s).
1057 if (MI->isRegTiedToDefOperand(OpIdx)) {
1058 MRInfo = VirtRegMap::isModRef;
1061 MRInfo |= (unsigned)VirtRegMap::isRef;
1063 FoldOps.push_back(OpIdx);
1069 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
1070 /// slot / to reg or any rematerialized load into ith operand of specified
1071 /// MI. If it is successul, MI is updated with the newly created MI and
1073 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
1074 VirtRegMap &vrm, MachineInstr *DefMI,
1076 SmallVector<unsigned, 2> &Ops,
1077 bool isSS, int Slot, unsigned Reg) {
1078 // If it is an implicit def instruction, just delete it.
1079 if (MI->isImplicitDef()) {
1080 RemoveMachineInstrFromMaps(MI);
1081 vrm.RemoveMachineInstrFromMaps(MI);
1082 MI->eraseFromParent();
1087 // Filter the list of operand indexes that are to be folded. Abort if
1088 // any operand will prevent folding.
1089 unsigned MRInfo = 0;
1090 SmallVector<unsigned, 2> FoldOps;
1091 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1094 // The only time it's safe to fold into a two address instruction is when
1095 // it's folding reload and spill from / into a spill stack slot.
1096 if (DefMI && (MRInfo & VirtRegMap::isMod))
1099 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot)
1100 : tii_->foldMemoryOperand(MI, FoldOps, DefMI);
1102 // Remember this instruction uses the spill slot.
1103 if (isSS) vrm.addSpillSlotUse(Slot, fmi);
1105 // Attempt to fold the memory reference into the instruction. If
1106 // we can do this, we don't need to insert spill code.
1107 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
1108 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
1109 vrm.transferSpillPts(MI, fmi);
1110 vrm.transferRestorePts(MI, fmi);
1111 vrm.transferEmergencySpills(MI, fmi);
1112 ReplaceMachineInstrInMaps(MI, fmi);
1113 MI->eraseFromParent();
1121 /// canFoldMemoryOperand - Returns true if the specified load / store
1122 /// folding is possible.
1123 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
1124 SmallVector<unsigned, 2> &Ops,
1126 // Filter the list of operand indexes that are to be folded. Abort if
1127 // any operand will prevent folding.
1128 unsigned MRInfo = 0;
1129 SmallVector<unsigned, 2> FoldOps;
1130 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1133 // It's only legal to remat for a use, not a def.
1134 if (ReMat && (MRInfo & VirtRegMap::isMod))
1137 return tii_->canFoldMemoryOperand(MI, FoldOps);
1140 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
1141 LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
1143 MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end);
1148 for (++itr; itr != li.ranges.end(); ++itr) {
1149 MachineBasicBlock *mbb2 =
1150 indexes_->getMBBCoveringRange(itr->start, itr->end);
1159 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
1160 /// interval on to-be re-materialized operands of MI) with new register.
1161 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
1162 MachineInstr *MI, unsigned NewVReg,
1164 // There is an implicit use. That means one of the other operand is
1165 // being remat'ed and the remat'ed instruction has li.reg as an
1166 // use operand. Make sure we rewrite that as well.
1167 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1168 MachineOperand &MO = MI->getOperand(i);
1171 unsigned Reg = MO.getReg();
1172 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1174 if (!vrm.isReMaterialized(Reg))
1176 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
1177 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
1179 UseMO->setReg(NewVReg);
1183 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
1184 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
1185 bool LiveIntervals::
1186 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
1187 bool TrySplit, SlotIndex index, SlotIndex end,
1189 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1190 unsigned Slot, int LdSlot,
1191 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1193 const TargetRegisterClass* rc,
1194 SmallVector<int, 4> &ReMatIds,
1195 const MachineLoopInfo *loopInfo,
1196 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
1197 DenseMap<unsigned,unsigned> &MBBVRegsMap,
1198 std::vector<LiveInterval*> &NewLIs) {
1199 bool CanFold = false;
1201 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1202 MachineOperand& mop = MI->getOperand(i);
1205 unsigned Reg = mop.getReg();
1206 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1211 bool TryFold = !DefIsReMat;
1212 bool FoldSS = true; // Default behavior unless it's a remat.
1213 int FoldSlot = Slot;
1215 // If this is the rematerializable definition MI itself and
1216 // all of its uses are rematerialized, simply delete it.
1217 if (MI == ReMatOrigDefMI && CanDelete) {
1218 DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: "
1220 RemoveMachineInstrFromMaps(MI);
1221 vrm.RemoveMachineInstrFromMaps(MI);
1222 MI->eraseFromParent();
1226 // If def for this use can't be rematerialized, then try folding.
1227 // If def is rematerializable and it's a load, also try folding.
1228 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1230 // Try fold loads (from stack slot, constant pool, etc.) into uses.
1236 // Scan all of the operands of this instruction rewriting operands
1237 // to use NewVReg instead of li.reg as appropriate. We do this for
1240 // 1. If the instr reads the same spilled vreg multiple times, we
1241 // want to reuse the NewVReg.
1242 // 2. If the instr is a two-addr instruction, we are required to
1243 // keep the src/dst regs pinned.
1245 // Keep track of whether we replace a use and/or def so that we can
1246 // create the spill interval with the appropriate range.
1247 SmallVector<unsigned, 2> Ops;
1248 tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops);
1250 // Create a new virtual register for the spill interval.
1251 // Create the new register now so we can map the fold instruction
1252 // to the new register so when it is unfolded we get the correct
1254 bool CreatedNewVReg = false;
1256 NewVReg = mri_->createVirtualRegister(rc);
1258 CreatedNewVReg = true;
1260 // The new virtual register should get the same allocation hints as the
1262 std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg);
1263 if (Hint.first || Hint.second)
1264 mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second);
1270 // Do not fold load / store here if we are splitting. We'll find an
1271 // optimal point to insert a load / store later.
1273 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1274 Ops, FoldSS, FoldSlot, NewVReg)) {
1275 // Folding the load/store can completely change the instruction in
1276 // unpredictable ways, rescan it from the beginning.
1279 // We need to give the new vreg the same stack slot as the
1280 // spilled interval.
1281 vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
1287 if (isNotInMIMap(MI))
1289 goto RestartInstruction;
1292 // We'll try to fold it later if it's profitable.
1293 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1297 mop.setReg(NewVReg);
1298 if (mop.isImplicit())
1299 rewriteImplicitOps(li, MI, NewVReg, vrm);
1301 // Reuse NewVReg for other reads.
1302 bool HasEarlyClobber = false;
1303 for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1304 MachineOperand &mopj = MI->getOperand(Ops[j]);
1305 mopj.setReg(NewVReg);
1306 if (mopj.isImplicit())
1307 rewriteImplicitOps(li, MI, NewVReg, vrm);
1308 if (mopj.isEarlyClobber())
1309 HasEarlyClobber = true;
1312 if (CreatedNewVReg) {
1314 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
1315 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1316 // Each valnum may have its own remat id.
1317 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1319 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1321 if (!CanDelete || (HasUse && HasDef)) {
1322 // If this is a two-addr instruction then its use operands are
1323 // rematerializable but its def is not. It should be assigned a
1325 vrm.assignVirt2StackSlot(NewVReg, Slot);
1328 vrm.assignVirt2StackSlot(NewVReg, Slot);
1330 } else if (HasUse && HasDef &&
1331 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1332 // If this interval hasn't been assigned a stack slot (because earlier
1333 // def is a deleted remat def), do it now.
1334 assert(Slot != VirtRegMap::NO_STACK_SLOT);
1335 vrm.assignVirt2StackSlot(NewVReg, Slot);
1338 // Re-matting an instruction with virtual register use. Add the
1339 // register as an implicit use on the use MI.
1340 if (DefIsReMat && ImpUse)
1341 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1343 // Create a new register interval for this spill / remat.
1344 LiveInterval &nI = getOrCreateInterval(NewVReg);
1345 if (CreatedNewVReg) {
1346 NewLIs.push_back(&nI);
1347 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1349 vrm.setIsSplitFromReg(NewVReg, li.reg);
1353 if (CreatedNewVReg) {
1354 LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
1355 nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
1356 DEBUG(dbgs() << " +" << LR);
1359 // Extend the split live interval to this def / use.
1360 SlotIndex End = index.getDefIndex();
1361 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1362 nI.getValNumInfo(nI.getNumValNums()-1));
1363 DEBUG(dbgs() << " +" << LR);
1368 // An early clobber starts at the use slot, except for an early clobber
1369 // tied to a use operand (yes, that is a thing).
1370 LiveRange LR(HasEarlyClobber && !HasUse ?
1371 index.getUseIndex() : index.getDefIndex(),
1372 index.getStoreIndex(),
1373 nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
1374 DEBUG(dbgs() << " +" << LR);
1379 dbgs() << "\t\t\t\tAdded new interval: ";
1380 nI.print(dbgs(), tri_);
1386 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1388 MachineBasicBlock *MBB,
1389 SlotIndex Idx) const {
1390 return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB));
1393 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1394 /// during spilling.
1396 struct RewriteInfo {
1399 RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {}
1402 struct RewriteInfoCompare {
1403 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1404 return LHS.Index < RHS.Index;
1409 void LiveIntervals::
1410 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1411 LiveInterval::Ranges::const_iterator &I,
1412 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1413 unsigned Slot, int LdSlot,
1414 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1416 const TargetRegisterClass* rc,
1417 SmallVector<int, 4> &ReMatIds,
1418 const MachineLoopInfo *loopInfo,
1419 BitVector &SpillMBBs,
1420 DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
1421 BitVector &RestoreMBBs,
1422 DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1423 DenseMap<unsigned,unsigned> &MBBVRegsMap,
1424 std::vector<LiveInterval*> &NewLIs) {
1425 bool AllCanFold = true;
1426 unsigned NewVReg = 0;
1427 SlotIndex start = I->start.getBaseIndex();
1428 SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
1430 // First collect all the def / use in this live range that will be rewritten.
1431 // Make sure they are sorted according to instruction index.
1432 std::vector<RewriteInfo> RewriteMIs;
1433 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1434 re = mri_->reg_end(); ri != re; ) {
1435 MachineInstr *MI = &*ri;
1436 MachineOperand &O = ri.getOperand();
1438 if (MI->isDebugValue()) {
1439 // Modify DBG_VALUE now that the value is in a spill slot.
1440 if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) {
1441 uint64_t Offset = MI->getOperand(1).getImm();
1442 const MDNode *MDPtr = MI->getOperand(2).getMetadata();
1443 DebugLoc DL = MI->getDebugLoc();
1444 int FI = isLoadSS ? LdSlot : (int)Slot;
1445 if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI,
1446 Offset, MDPtr, DL)) {
1447 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
1448 ReplaceMachineInstrInMaps(MI, NewDV);
1449 MachineBasicBlock *MBB = MI->getParent();
1450 MBB->insert(MBB->erase(MI), NewDV);
1455 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1456 RemoveMachineInstrFromMaps(MI);
1457 vrm.RemoveMachineInstrFromMaps(MI);
1458 MI->eraseFromParent();
1461 assert(!(O.isImplicit() && O.isUse()) &&
1462 "Spilling register that's used as implicit use?");
1463 SlotIndex index = getInstructionIndex(MI);
1464 if (index < start || index >= end)
1468 // Must be defined by an implicit def. It should not be spilled. Note,
1469 // this is for correctness reason. e.g.
1470 // 8 %reg1024<def> = IMPLICIT_DEF
1471 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1472 // The live range [12, 14) are not part of the r1024 live interval since
1473 // it's defined by an implicit def. It will not conflicts with live
1474 // interval of r1025. Now suppose both registers are spilled, you can
1475 // easily see a situation where both registers are reloaded before
1476 // the INSERT_SUBREG and both target registers that would overlap.
1478 RewriteMIs.push_back(RewriteInfo(index, MI));
1480 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1482 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1483 // Now rewrite the defs and uses.
1484 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1485 RewriteInfo &rwi = RewriteMIs[i];
1487 SlotIndex index = rwi.Index;
1488 MachineInstr *MI = rwi.MI;
1489 // If MI def and/or use the same register multiple times, then there
1490 // are multiple entries.
1491 while (i != e && RewriteMIs[i].MI == MI) {
1492 assert(RewriteMIs[i].Index == index);
1495 MachineBasicBlock *MBB = MI->getParent();
1497 if (ImpUse && MI != ReMatDefMI) {
1498 // Re-matting an instruction with virtual register use. Prevent interval
1499 // from being spilled.
1500 getInterval(ImpUse).markNotSpillable();
1503 unsigned MBBId = MBB->getNumber();
1504 unsigned ThisVReg = 0;
1506 DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
1507 if (NVI != MBBVRegsMap.end()) {
1508 ThisVReg = NVI->second;
1515 // It's better to start a new interval to avoid artifically
1516 // extend the new interval.
1517 if (MI->readsWritesVirtualRegister(li.reg) ==
1518 std::make_pair(false,true)) {
1519 MBBVRegsMap.erase(MBB->getNumber());
1525 bool IsNew = ThisVReg == 0;
1527 // This ends the previous live interval. If all of its def / use
1528 // can be folded, give it a low spill weight.
1529 if (NewVReg && TrySplit && AllCanFold) {
1530 LiveInterval &nI = getOrCreateInterval(NewVReg);
1537 bool HasDef = false;
1538 bool HasUse = false;
1539 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1540 index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1541 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1542 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1543 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
1544 if (!HasDef && !HasUse)
1547 AllCanFold &= CanFold;
1549 // Update weight of spill interval.
1550 LiveInterval &nI = getOrCreateInterval(NewVReg);
1552 // The spill weight is now infinity as it cannot be spilled again.
1553 nI.markNotSpillable();
1557 // Keep track of the last def and first use in each MBB.
1559 if (MI != ReMatOrigDefMI || !CanDelete) {
1560 bool HasKill = false;
1562 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex());
1564 // If this is a two-address code, then this index starts a new VNInfo.
1565 const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex());
1567 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex());
1569 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1570 SpillIdxes.find(MBBId);
1572 if (SII == SpillIdxes.end()) {
1573 std::vector<SRInfo> S;
1574 S.push_back(SRInfo(index, NewVReg, true));
1575 SpillIdxes.insert(std::make_pair(MBBId, S));
1576 } else if (SII->second.back().vreg != NewVReg) {
1577 SII->second.push_back(SRInfo(index, NewVReg, true));
1578 } else if (index > SII->second.back().index) {
1579 // If there is an earlier def and this is a two-address
1580 // instruction, then it's not possible to fold the store (which
1581 // would also fold the load).
1582 SRInfo &Info = SII->second.back();
1584 Info.canFold = !HasUse;
1586 SpillMBBs.set(MBBId);
1587 } else if (SII != SpillIdxes.end() &&
1588 SII->second.back().vreg == NewVReg &&
1589 index > SII->second.back().index) {
1590 // There is an earlier def that's not killed (must be two-address).
1591 // The spill is no longer needed.
1592 SII->second.pop_back();
1593 if (SII->second.empty()) {
1594 SpillIdxes.erase(MBBId);
1595 SpillMBBs.reset(MBBId);
1602 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1603 SpillIdxes.find(MBBId);
1604 if (SII != SpillIdxes.end() &&
1605 SII->second.back().vreg == NewVReg &&
1606 index > SII->second.back().index)
1607 // Use(s) following the last def, it's not safe to fold the spill.
1608 SII->second.back().canFold = false;
1609 DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
1610 RestoreIdxes.find(MBBId);
1611 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1612 // If we are splitting live intervals, only fold if it's the first
1613 // use and there isn't another use later in the MBB.
1614 RII->second.back().canFold = false;
1616 // Only need a reload if there isn't an earlier def / use.
1617 if (RII == RestoreIdxes.end()) {
1618 std::vector<SRInfo> Infos;
1619 Infos.push_back(SRInfo(index, NewVReg, true));
1620 RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1622 RII->second.push_back(SRInfo(index, NewVReg, true));
1624 RestoreMBBs.set(MBBId);
1628 // Update spill weight.
1629 unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1630 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1633 if (NewVReg && TrySplit && AllCanFold) {
1634 // If all of its def / use can be folded, give it a low spill weight.
1635 LiveInterval &nI = getOrCreateInterval(NewVReg);
1640 bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index,
1641 unsigned vr, BitVector &RestoreMBBs,
1642 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1643 if (!RestoreMBBs[Id])
1645 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1646 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1647 if (Restores[i].index == index &&
1648 Restores[i].vreg == vr &&
1649 Restores[i].canFold)
1654 void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index,
1655 unsigned vr, BitVector &RestoreMBBs,
1656 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1657 if (!RestoreMBBs[Id])
1659 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1660 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1661 if (Restores[i].index == index && Restores[i].vreg)
1662 Restores[i].index = SlotIndex();
1665 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1666 /// spilled and create empty intervals for their uses.
1668 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1669 const TargetRegisterClass* rc,
1670 std::vector<LiveInterval*> &NewLIs) {
1671 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1672 re = mri_->reg_end(); ri != re; ) {
1673 MachineOperand &O = ri.getOperand();
1674 MachineInstr *MI = &*ri;
1676 if (MI->isDebugValue()) {
1677 // Remove debug info for now.
1679 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1683 assert(MI->isImplicitDef() &&
1684 "Register def was not rewritten?");
1685 RemoveMachineInstrFromMaps(MI);
1686 vrm.RemoveMachineInstrFromMaps(MI);
1687 MI->eraseFromParent();
1689 // This must be an use of an implicit_def so it's not part of the live
1690 // interval. Create a new empty live interval for it.
1691 // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1692 unsigned NewVReg = mri_->createVirtualRegister(rc);
1694 vrm.setIsImplicitlyDefined(NewVReg);
1695 NewLIs.push_back(&getOrCreateInterval(NewVReg));
1696 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1697 MachineOperand &MO = MI->getOperand(i);
1698 if (MO.isReg() && MO.getReg() == li.reg) {
1708 LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
1709 // Limit the loop depth ridiculousness.
1710 if (loopDepth > 200)
1713 // The loop depth is used to roughly estimate the number of times the
1714 // instruction is executed. Something like 10^d is simple, but will quickly
1715 // overflow a float. This expression behaves like 10^d for small d, but is
1716 // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
1717 // headroom before overflow.
1718 // By the way, powf() might be unavailable here. For consistency,
1719 // We may take pow(double,double).
1720 float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
1722 return (isDef + isUse) * lc;
1725 static void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) {
1726 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
1728 normalizeSpillWeight(NewLIs[i]->weight, NewLIs[i]->getSize());
1731 std::vector<LiveInterval*> LiveIntervals::
1732 addIntervalsForSpills(const LiveInterval &li,
1733 const SmallVectorImpl<LiveInterval*> *SpillIs,
1734 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
1735 assert(li.isSpillable() && "attempt to spill already spilled interval!");
1738 dbgs() << "\t\t\t\tadding intervals for spills for interval: ";
1739 li.print(dbgs(), tri_);
1743 // Each bit specify whether a spill is required in the MBB.
1744 BitVector SpillMBBs(mf_->getNumBlockIDs());
1745 DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
1746 BitVector RestoreMBBs(mf_->getNumBlockIDs());
1747 DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
1748 DenseMap<unsigned,unsigned> MBBVRegsMap;
1749 std::vector<LiveInterval*> NewLIs;
1750 const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
1752 unsigned NumValNums = li.getNumValNums();
1753 SmallVector<MachineInstr*, 4> ReMatDefs;
1754 ReMatDefs.resize(NumValNums, NULL);
1755 SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1756 ReMatOrigDefs.resize(NumValNums, NULL);
1757 SmallVector<int, 4> ReMatIds;
1758 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1759 BitVector ReMatDelete(NumValNums);
1760 unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1762 // Spilling a split live interval. It cannot be split any further. Also,
1763 // it's also guaranteed to be a single val# / range interval.
1764 if (vrm.getPreSplitReg(li.reg)) {
1765 vrm.setIsSplitFromReg(li.reg, 0);
1766 // Unset the split kill marker on the last use.
1767 SlotIndex KillIdx = vrm.getKillPoint(li.reg);
1768 if (KillIdx != SlotIndex()) {
1769 MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1770 assert(KillMI && "Last use disappeared?");
1771 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1772 assert(KillOp != -1 && "Last use disappeared?");
1773 KillMI->getOperand(KillOp).setIsKill(false);
1775 vrm.removeKillPoint(li.reg);
1776 bool DefIsReMat = vrm.isReMaterialized(li.reg);
1777 Slot = vrm.getStackSlot(li.reg);
1778 assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1779 MachineInstr *ReMatDefMI = DefIsReMat ?
1780 vrm.getReMaterializedMI(li.reg) : NULL;
1782 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1783 bool isLoad = isLoadSS ||
1784 (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
1785 bool IsFirstRange = true;
1786 for (LiveInterval::Ranges::const_iterator
1787 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1788 // If this is a split live interval with multiple ranges, it means there
1789 // are two-address instructions that re-defined the value. Only the
1790 // first def can be rematerialized!
1792 // Note ReMatOrigDefMI has already been deleted.
1793 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1794 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1795 false, vrm, rc, ReMatIds, loopInfo,
1796 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1797 MBBVRegsMap, NewLIs);
1799 rewriteInstructionsForSpills(li, false, I, NULL, 0,
1800 Slot, 0, false, false, false,
1801 false, vrm, rc, ReMatIds, loopInfo,
1802 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1803 MBBVRegsMap, NewLIs);
1805 IsFirstRange = false;
1808 handleSpilledImpDefs(li, vrm, rc, NewLIs);
1809 normalizeSpillWeights(NewLIs);
1813 bool TrySplit = !intervalIsInOneMBB(li);
1816 bool NeedStackSlot = false;
1817 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1819 const VNInfo *VNI = *i;
1820 unsigned VN = VNI->id;
1821 if (VNI->isUnused())
1822 continue; // Dead val#.
1823 // Is the def for the val# rematerializable?
1824 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1826 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
1827 // Remember how to remat the def of this val#.
1828 ReMatOrigDefs[VN] = ReMatDefMI;
1829 // Original def may be modified so we have to make a copy here.
1830 MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
1831 CloneMIs.push_back(Clone);
1832 ReMatDefs[VN] = Clone;
1834 bool CanDelete = true;
1835 if (VNI->hasPHIKill()) {
1836 // A kill is a phi node, not all of its uses can be rematerialized.
1837 // It must not be deleted.
1839 // Need a stack slot if there is any live range where uses cannot be
1841 NeedStackSlot = true;
1844 ReMatDelete.set(VN);
1846 // Need a stack slot if there is any live range where uses cannot be
1848 NeedStackSlot = true;
1852 // One stack slot per live interval.
1853 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
1854 if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
1855 Slot = vrm.assignVirt2StackSlot(li.reg);
1857 // This case only occurs when the prealloc splitter has already assigned
1858 // a stack slot to this vreg.
1860 Slot = vrm.getStackSlot(li.reg);
1863 // Create new intervals and rewrite defs and uses.
1864 for (LiveInterval::Ranges::const_iterator
1865 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1866 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1867 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1868 bool DefIsReMat = ReMatDefMI != NULL;
1869 bool CanDelete = ReMatDelete[I->valno->id];
1871 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1872 bool isLoad = isLoadSS ||
1873 (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
1874 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1875 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1876 CanDelete, vrm, rc, ReMatIds, loopInfo,
1877 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1878 MBBVRegsMap, NewLIs);
1881 // Insert spills / restores if we are splitting.
1883 handleSpilledImpDefs(li, vrm, rc, NewLIs);
1884 normalizeSpillWeights(NewLIs);
1888 SmallPtrSet<LiveInterval*, 4> AddedKill;
1889 SmallVector<unsigned, 2> Ops;
1890 if (NeedStackSlot) {
1891 int Id = SpillMBBs.find_first();
1893 std::vector<SRInfo> &spills = SpillIdxes[Id];
1894 for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1895 SlotIndex index = spills[i].index;
1896 unsigned VReg = spills[i].vreg;
1897 LiveInterval &nI = getOrCreateInterval(VReg);
1898 bool isReMat = vrm.isReMaterialized(VReg);
1899 MachineInstr *MI = getInstructionFromIndex(index);
1900 bool CanFold = false;
1901 bool FoundUse = false;
1903 if (spills[i].canFold) {
1905 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1906 MachineOperand &MO = MI->getOperand(j);
1907 if (!MO.isReg() || MO.getReg() != VReg)
1914 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1915 RestoreMBBs, RestoreIdxes))) {
1916 // MI has two-address uses of the same register. If the use
1917 // isn't the first and only use in the BB, then we can't fold
1918 // it. FIXME: Move this to rewriteInstructionsForSpills.
1925 // Fold the store into the def if possible.
1926 bool Folded = false;
1927 if (CanFold && !Ops.empty()) {
1928 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1931 // Also folded uses, do not issue a load.
1932 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1933 nI.removeRange(index.getLoadIndex(), index.getDefIndex());
1935 nI.removeRange(index.getDefIndex(), index.getStoreIndex());
1939 // Otherwise tell the spiller to issue a spill.
1941 LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1942 bool isKill = LR->end == index.getStoreIndex();
1943 if (!MI->registerDefIsDead(nI.reg))
1944 // No need to spill a dead def.
1945 vrm.addSpillPoint(VReg, isKill, MI);
1947 AddedKill.insert(&nI);
1950 Id = SpillMBBs.find_next(Id);
1954 int Id = RestoreMBBs.find_first();
1956 std::vector<SRInfo> &restores = RestoreIdxes[Id];
1957 for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1958 SlotIndex index = restores[i].index;
1959 if (index == SlotIndex())
1961 unsigned VReg = restores[i].vreg;
1962 LiveInterval &nI = getOrCreateInterval(VReg);
1963 bool isReMat = vrm.isReMaterialized(VReg);
1964 MachineInstr *MI = getInstructionFromIndex(index);
1965 bool CanFold = false;
1967 if (restores[i].canFold) {
1969 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1970 MachineOperand &MO = MI->getOperand(j);
1971 if (!MO.isReg() || MO.getReg() != VReg)
1975 // If this restore were to be folded, it would have been folded
1984 // Fold the load into the use if possible.
1985 bool Folded = false;
1986 if (CanFold && !Ops.empty()) {
1988 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1990 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1992 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1993 // If the rematerializable def is a load, also try to fold it.
1994 if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
1995 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1996 Ops, isLoadSS, LdSlot, VReg);
1998 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
2000 // Re-matting an instruction with virtual register use. Add the
2001 // register as an implicit use on the use MI and mark the register
2002 // interval as unspillable.
2003 LiveInterval &ImpLi = getInterval(ImpUse);
2004 ImpLi.markNotSpillable();
2005 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
2010 // If folding is not possible / failed, then tell the spiller to issue a
2011 // load / rematerialization for us.
2013 nI.removeRange(index.getLoadIndex(), index.getDefIndex());
2015 vrm.addRestorePoint(VReg, MI);
2017 Id = RestoreMBBs.find_next(Id);
2020 // Finalize intervals: add kills, finalize spill weights, and filter out
2022 std::vector<LiveInterval*> RetNewLIs;
2023 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
2024 LiveInterval *LI = NewLIs[i];
2026 if (!AddedKill.count(LI)) {
2027 LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
2028 SlotIndex LastUseIdx = LR->end.getBaseIndex();
2029 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
2030 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
2031 assert(UseIdx != -1);
2032 if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
2033 LastUse->getOperand(UseIdx).setIsKill();
2034 vrm.addKillPoint(LI->reg, LastUseIdx);
2037 RetNewLIs.push_back(LI);
2041 handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
2042 normalizeSpillWeights(RetNewLIs);
2046 /// hasAllocatableSuperReg - Return true if the specified physical register has
2047 /// any super register that's allocatable.
2048 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
2049 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
2050 if (allocatableRegs_[*AS] && hasInterval(*AS))
2055 /// getRepresentativeReg - Find the largest super register of the specified
2056 /// physical register.
2057 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
2058 // Find the largest super-register that is allocatable.
2059 unsigned BestReg = Reg;
2060 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
2061 unsigned SuperReg = *AS;
2062 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
2070 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
2071 /// specified interval that conflicts with the specified physical register.
2072 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
2073 unsigned PhysReg) const {
2074 unsigned NumConflicts = 0;
2075 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
2076 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2077 E = mri_->reg_end(); I != E; ++I) {
2078 MachineOperand &O = I.getOperand();
2079 MachineInstr *MI = O.getParent();
2080 if (MI->isDebugValue())
2082 SlotIndex Index = getInstructionIndex(MI);
2083 if (pli.liveAt(Index))
2086 return NumConflicts;
2089 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
2090 /// around all defs and uses of the specified interval. Return true if it
2091 /// was able to cut its interval.
2092 bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
2093 unsigned PhysReg, VirtRegMap &vrm) {
2094 unsigned SpillReg = getRepresentativeReg(PhysReg);
2096 DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg)
2097 << " represented by " << tri_->getName(SpillReg) << '\n');
2099 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
2100 // If there are registers which alias PhysReg, but which are not a
2101 // sub-register of the chosen representative super register. Assert
2102 // since we can't handle it yet.
2103 assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
2104 tri_->isSuperRegister(*AS, SpillReg));
2107 SmallVector<unsigned, 4> PRegs;
2108 if (hasInterval(SpillReg))
2109 PRegs.push_back(SpillReg);
2110 for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR)
2111 if (hasInterval(*SR))
2112 PRegs.push_back(*SR);
2115 dbgs() << "Trying to spill:";
2116 for (unsigned i = 0, e = PRegs.size(); i != e; ++i)
2117 dbgs() << ' ' << tri_->getName(PRegs[i]);
2121 SmallPtrSet<MachineInstr*, 8> SeenMIs;
2122 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2123 E = mri_->reg_end(); I != E; ++I) {
2124 MachineOperand &O = I.getOperand();
2125 MachineInstr *MI = O.getParent();
2126 if (MI->isDebugValue() || SeenMIs.count(MI))
2129 SlotIndex Index = getInstructionIndex(MI);
2130 bool LiveReg = false;
2131 for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
2132 unsigned PReg = PRegs[i];
2133 LiveInterval &pli = getInterval(PReg);
2134 if (!pli.liveAt(Index))
2137 SlotIndex StartIdx = Index.getLoadIndex();
2138 SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
2139 if (!pli.isInOneLiveRange(StartIdx, EndIdx)) {
2141 raw_string_ostream Msg(msg);
2142 Msg << "Ran out of registers during register allocation!";
2143 if (MI->isInlineAsm()) {
2144 Msg << "\nPlease check your inline asm statement for invalid "
2145 << "constraints:\n";
2146 MI->print(Msg, tm_);
2148 report_fatal_error(Msg.str());
2150 pli.removeRange(StartIdx, EndIdx);
2155 DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI);
2156 vrm.addEmergencySpill(SpillReg, MI);
2162 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
2163 MachineInstr* startInst) {
2164 LiveInterval& Interval = getOrCreateInterval(reg);
2165 VNInfo* VN = Interval.getNextValue(
2166 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
2167 startInst, getVNInfoAllocator());
2168 VN->setHasPHIKill(true);
2170 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
2171 getMBBEndIdx(startInst->getParent()), VN);
2172 Interval.addRange(LR);