#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin();
I != E;) {
--I;
- if (I->getDesc().isCall()) {
+ if (I->isCall()) {
LSP.second = LIS.getInstructionIndex(I);
break;
}
I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E;
++I)
if (!I.getOperand().isUndef())
- UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex());
+ UseSlots.push_back(LIS.getInstructionIndex(&*I).getRegSlot());
array_pod_sort(UseSlots.begin(), UseSlots.end());
RegAssign.clear();
Values.clear();
- // We don't need to clear LiveOutCache, only LiveOutSeen entries are read.
- LiveOutSeen.clear();
+ // Reset the LiveRangeCalc instances needed for this spill mode.
+ LRCalc[0].reset(&VRM.getMachineFunction());
+ if (SpillMode)
+ LRCalc[1].reset(&VRM.getMachineFunction());
// We don't need an AliasAnalysis since we will only be performing
// cheap-as-a-copy remats anyway.
// Use insert for lookup, so we can add missing values with a second lookup.
std::pair<ValueMap::iterator, bool> InsP =
- Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI));
+ Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id),
+ ValueForcePair(VNI, false)));
// This was the first time (RegIdx, ParentVNI) was mapped.
// Keep it as a simple def without any liveness.
return VNI;
// If the previous value was a simple mapping, add liveness for it now.
- if (VNInfo *OldVNI = InsP.first->second) {
+ if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
SlotIndex Def = OldVNI->def;
- LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
- // No longer a simple mapping.
- InsP.first->second = 0;
+ LI->addRange(LiveRange(Def, Def.getDeadSlot(), OldVNI));
+ // No longer a simple mapping. Switch to a complex, non-forced mapping.
+ InsP.first->second = ValueForcePair();
}
// This is a complex mapping, add liveness for VNI
SlotIndex Def = VNI->def;
- LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
+ LI->addRange(LiveRange(Def, Def.getDeadSlot(), VNI));
return VNI;
}
-void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
+void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
assert(ParentVNI && "Mapping NULL value");
- VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
+ ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
+ VNInfo *VNI = VFP.getPointer();
- // ParentVNI was either unmapped or already complex mapped. Either way.
- if (!VNI)
+ // ParentVNI was either unmapped or already complex mapped. Either way, just
+ // set the force bit.
+ if (!VNI) {
+ VFP.setInt(true);
return;
+ }
// This was previously a single mapping. Make sure the old def is represented
// by a trivial live range.
SlotIndex Def = VNI->def;
- Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
- VNI = 0;
-}
-
-// extendRange - Extend the live range to reach Idx.
-// Potentially create phi-def values.
-void SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) {
- assert(Idx.isValid() && "Invalid SlotIndex");
- MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx);
- assert(IdxMBB && "No MBB at Idx");
- LiveInterval *LI = Edit->get(RegIdx);
-
- // Is there a def in the same MBB we can extend?
- if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx))
- return;
-
- // Now for the fun part. We know that ParentVNI potentially has multiple defs,
- // and we may need to create even more phi-defs to preserve VNInfo SSA form.
- // Perform a search for all predecessor blocks where we know the dominating
- // VNInfo.
- VNInfo *VNI = findReachingDefs(LI, IdxMBB, Idx.getNextSlot());
-
- // When there were multiple different values, we may need new PHIs.
- if (!VNI)
- return updateSSA();
-
- // Poor man's SSA update for the single-value case.
- LiveOutPair LOP(VNI, MDT[LIS.getMBBFromIndex(VNI->def)]);
- for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(),
- E = LiveInBlocks.end(); I != E; ++I) {
- MachineBasicBlock *MBB = I->DomNode->getBlock();
- SlotIndex Start = LIS.getMBBStartIdx(MBB);
- if (I->Kill.isValid())
- LI->addRange(LiveRange(Start, I->Kill, VNI));
- else {
- LiveOutCache[MBB] = LOP;
- LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
- }
- }
-}
-
-/// findReachingDefs - Search the CFG for known live-out values.
-/// Add required live-in blocks to LiveInBlocks.
-VNInfo *SplitEditor::findReachingDefs(LiveInterval *LI,
- MachineBasicBlock *KillMBB,
- SlotIndex Kill) {
- // Initialize the live-out cache the first time it is needed.
- if (LiveOutSeen.empty()) {
- unsigned N = VRM.getMachineFunction().getNumBlockIDs();
- LiveOutSeen.resize(N);
- LiveOutCache.resize(N);
- }
-
- // Blocks where LI should be live-in.
- SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB);
-
- // Remember if we have seen more than one value.
- bool UniqueVNI = true;
- VNInfo *TheVNI = 0;
-
- // Using LiveOutCache as a visited set, perform a BFS for all reaching defs.
- for (unsigned i = 0; i != WorkList.size(); ++i) {
- MachineBasicBlock *MBB = WorkList[i];
- assert(!MBB->pred_empty() && "Value live-in to entry block?");
- for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
- PE = MBB->pred_end(); PI != PE; ++PI) {
- MachineBasicBlock *Pred = *PI;
- LiveOutPair &LOP = LiveOutCache[Pred];
-
- // Is this a known live-out block?
- if (LiveOutSeen.test(Pred->getNumber())) {
- if (VNInfo *VNI = LOP.first) {
- if (TheVNI && TheVNI != VNI)
- UniqueVNI = false;
- TheVNI = VNI;
- }
- continue;
- }
-
- // First time. LOP is garbage and must be cleared below.
- LiveOutSeen.set(Pred->getNumber());
-
- // Does Pred provide a live-out value?
- SlotIndex Start, Last;
- tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred);
- Last = Last.getPrevSlot();
- VNInfo *VNI = LI->extendInBlock(Start, Last);
- LOP.first = VNI;
- if (VNI) {
- LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)];
- if (TheVNI && TheVNI != VNI)
- UniqueVNI = false;
- TheVNI = VNI;
- continue;
- }
- LOP.second = 0;
-
- // No, we need a live-in value for Pred as well
- if (Pred != KillMBB)
- WorkList.push_back(Pred);
- else
- // Loopback to KillMBB, so value is really live through.
- Kill = SlotIndex();
- }
- }
-
- // Transfer WorkList to LiveInBlocks in reverse order.
- // This ordering works best with updateSSA().
- LiveInBlocks.clear();
- LiveInBlocks.reserve(WorkList.size());
- while(!WorkList.empty())
- LiveInBlocks.push_back(MDT[WorkList.pop_back_val()]);
-
- // The kill block may not be live-through.
- assert(LiveInBlocks.back().DomNode->getBlock() == KillMBB);
- LiveInBlocks.back().Kill = Kill;
-
- return UniqueVNI ? TheVNI : 0;
-}
-
-void SplitEditor::updateSSA() {
- // This is essentially the same iterative algorithm that SSAUpdater uses,
- // except we already have a dominator tree, so we don't have to recompute it.
- unsigned Changes;
- do {
- Changes = 0;
- // Propagate live-out values down the dominator tree, inserting phi-defs
- // when necessary.
- for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(),
- E = LiveInBlocks.end(); I != E; ++I) {
- MachineDomTreeNode *Node = I->DomNode;
- // Skip block if the live-in value has already been determined.
- if (!Node)
- continue;
- MachineBasicBlock *MBB = Node->getBlock();
- MachineDomTreeNode *IDom = Node->getIDom();
- LiveOutPair IDomValue;
-
- // We need a live-in value to a block with no immediate dominator?
- // This is probably an unreachable block that has survived somehow.
- bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber());
-
- // IDom dominates all of our predecessors, but it may not be their
- // immediate dominator. Check if any of them have live-out values that are
- // properly dominated by IDom. If so, we need a phi-def here.
- if (!needPHI) {
- IDomValue = LiveOutCache[IDom->getBlock()];
- for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
- PE = MBB->pred_end(); PI != PE; ++PI) {
- LiveOutPair Value = LiveOutCache[*PI];
- if (!Value.first || Value.first == IDomValue.first)
- continue;
- // This predecessor is carrying something other than IDomValue.
- // It could be because IDomValue hasn't propagated yet, or it could be
- // because MBB is in the dominance frontier of that value.
- if (MDT.dominates(IDom, Value.second)) {
- needPHI = true;
- break;
- }
- }
- }
-
- // The value may be live-through even if Kill is set, as can happen when
- // we are called from extendRange. In that case LiveOutSeen is true, and
- // LiveOutCache indicates a foreign or missing value.
- LiveOutPair &LOP = LiveOutCache[MBB];
-
- // Create a phi-def if required.
- if (needPHI) {
- ++Changes;
- SlotIndex Start = LIS.getMBBStartIdx(MBB);
- unsigned RegIdx = RegAssign.lookup(Start);
- LiveInterval *LI = Edit->get(RegIdx);
- VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator());
- VNI->setIsPHIDef(true);
- I->Value = VNI;
- // This block is done, we know the final value.
- I->DomNode = 0;
- if (I->Kill.isValid())
- LI->addRange(LiveRange(Start, I->Kill, VNI));
- else {
- LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
- LOP = LiveOutPair(VNI, Node);
- }
- } else if (IDomValue.first) {
- // No phi-def here. Remember incoming value.
- I->Value = IDomValue.first;
- if (I->Kill.isValid())
- continue;
- // Propagate IDomValue if needed:
- // MBB is live-out and doesn't define its own value.
- if (LOP.second != Node && LOP.first != IDomValue.first) {
- ++Changes;
- LOP = IDomValue;
- }
- }
- }
- } while (Changes);
-
- // The values in LiveInBlocks are now accurate. No more phi-defs are needed
- // for these blocks, so we can color the live ranges.
- for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(),
- E = LiveInBlocks.end(); I != E; ++I) {
- if (!I->DomNode)
- continue;
- assert(I->Value && "No live-in value found");
- MachineBasicBlock *MBB = I->DomNode->getBlock();
- SlotIndex Start = LIS.getMBBStartIdx(MBB);
- unsigned RegIdx = RegAssign.lookup(Start);
- LiveInterval *LI = Edit->get(RegIdx);
- LI->addRange(LiveRange(Start, I->Kill.isValid() ?
- I->Kill : LIS.getMBBEndIdx(MBB), I->Value));
- }
+ Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getDeadSlot(), VNI));
+ // Mark as complex mapped, forced.
+ VFP = ValueForcePair(0, true);
}
VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
.addReg(Edit->getReg());
Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late)
- .getDefIndex();
+ .getRegSlot();
++NumCopies;
}
DEBUG(dbgs() << " leaveIntvAfter " << Idx);
// The interval must be live beyond the instruction at Idx.
- Idx = Idx.getBoundaryIndex();
- VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
+ SlotIndex Boundary = Idx.getBoundaryIndex();
+ VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
if (!ParentVNI) {
DEBUG(dbgs() << ": not live\n");
- return Idx.getNextSlot();
+ return Boundary.getNextSlot();
}
DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
-
- MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
+ MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
assert(MI && "No instruction at index");
- VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(),
+
+ // In spill mode, make live ranges as short as possible by inserting the copy
+ // before MI. This is only possible if that instruction doesn't redefine the
+ // value. The inserted COPY is not a kill, and we don't need to recompute
+ // the source live range. The spiller also won't try to hoist this copy.
+ if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
+ MI->readsVirtualRegister(Edit->getReg())) {
+ forceRecompute(0, ParentVNI);
+ defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
+ return Idx;
+ }
+
+ VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
llvm::next(MachineBasicBlock::iterator(MI)));
return VNI->def;
}
void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
assert(OpenIdx && "openIntv not called before overlapIntv");
const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
- assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) &&
+ assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
"Parent changes value in extended range");
assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
"Range cannot span basic blocks");
- // The complement interval will be extended as needed by extendRange().
+ // The complement interval will be extended as needed by LRCalc.extend().
if (ParentVNI)
- markComplexMapped(0, ParentVNI);
+ forceRecompute(0, ParentVNI);
DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
RegAssign.insert(Start, End, OpenIdx);
DEBUG(dump());
}
+//===----------------------------------------------------------------------===//
+// Spill modes
+//===----------------------------------------------------------------------===//
+
+void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
+ LiveInterval *LI = Edit->get(0);
+ DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
+ RegAssignMap::iterator AssignI;
+ AssignI.setMap(RegAssign);
+
+ for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
+ VNInfo *VNI = Copies[i];
+ SlotIndex Def = VNI->def;
+ MachineInstr *MI = LIS.getInstructionFromIndex(Def);
+ assert(MI && "No instruction for back-copy");
+
+ MachineBasicBlock *MBB = MI->getParent();
+ MachineBasicBlock::iterator MBBI(MI);
+ bool AtBegin;
+ do AtBegin = MBBI == MBB->begin();
+ while (!AtBegin && (--MBBI)->isDebugValue());
+
+ DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
+ LI->removeValNo(VNI);
+ LIS.RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+
+ // Adjust RegAssign if a register assignment is killed at VNI->def. We
+ // want to avoid calculating the live range of the source register if
+ // possible.
+ AssignI.find(VNI->def.getPrevSlot());
+ if (!AssignI.valid() || AssignI.start() >= Def)
+ continue;
+ // If MI doesn't kill the assigned register, just leave it.
+ if (AssignI.stop() != Def)
+ continue;
+ unsigned RegIdx = AssignI.value();
+ if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
+ DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx << '\n');
+ forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def));
+ } else {
+ SlotIndex Kill = LIS.getInstructionIndex(MBBI).getRegSlot();
+ DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI);
+ AssignI.setStop(Kill);
+ }
+ }
+}
+
+MachineBasicBlock*
+SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
+ MachineBasicBlock *DefMBB) {
+ if (MBB == DefMBB)
+ return MBB;
+ assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
+
+ const MachineLoopInfo &Loops = SA.Loops;
+ const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
+ MachineDomTreeNode *DefDomNode = MDT[DefMBB];
+
+ // Best candidate so far.
+ MachineBasicBlock *BestMBB = MBB;
+ unsigned BestDepth = UINT_MAX;
+
+ for (;;) {
+ const MachineLoop *Loop = Loops.getLoopFor(MBB);
+
+ // MBB isn't in a loop, it doesn't get any better. All dominators have a
+ // higher frequency by definition.
+ if (!Loop) {
+ DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
+ << MBB->getNumber() << " at depth 0\n");
+ return MBB;
+ }
+
+ // We'll never be able to exit the DefLoop.
+ if (Loop == DefLoop) {
+ DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
+ << MBB->getNumber() << " in the same loop\n");
+ return MBB;
+ }
+
+ // Least busy dominator seen so far.
+ unsigned Depth = Loop->getLoopDepth();
+ if (Depth < BestDepth) {
+ BestMBB = MBB;
+ BestDepth = Depth;
+ DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
+ << MBB->getNumber() << " at depth " << Depth << '\n');
+ }
+
+ // Leave loop by going to the immediate dominator of the loop header.
+ // This is a bigger stride than simply walking up the dominator tree.
+ MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
+
+ // Too far up the dominator tree?
+ if (!IDom || !MDT.dominates(DefDomNode, IDom))
+ return BestMBB;
+
+ MBB = IDom->getBlock();
+ }
+}
+
+void SplitEditor::hoistCopiesForSize() {
+ // Get the complement interval, always RegIdx 0.
+ LiveInterval *LI = Edit->get(0);
+ LiveInterval *Parent = &Edit->getParent();
+
+ // Track the nearest common dominator for all back-copies for each ParentVNI,
+ // indexed by ParentVNI->id.
+ typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair;
+ SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
+
+ // Find the nearest common dominator for parent values with multiple
+ // back-copies. If a single back-copy dominates, put it in DomPair.second.
+ for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end();
+ VI != VE; ++VI) {
+ VNInfo *VNI = *VI;
+ VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
+ assert(ParentVNI && "Parent not live at complement def");
+
+ // Don't hoist remats. The complement is probably going to disappear
+ // completely anyway.
+ if (Edit->didRematerialize(ParentVNI))
+ continue;
+
+ MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
+ DomPair &Dom = NearestDom[ParentVNI->id];
+
+ // Keep directly defined parent values. This is either a PHI or an
+ // instruction in the complement range. All other copies of ParentVNI
+ // should be eliminated.
+ if (VNI->def == ParentVNI->def) {
+ DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
+ Dom = DomPair(ValMBB, VNI->def);
+ continue;
+ }
+ // Skip the singly mapped values. There is nothing to gain from hoisting a
+ // single back-copy.
+ if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
+ DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
+ continue;
+ }
+
+ if (!Dom.first) {
+ // First time we see ParentVNI. VNI dominates itself.
+ Dom = DomPair(ValMBB, VNI->def);
+ } else if (Dom.first == ValMBB) {
+ // Two defs in the same block. Pick the earlier def.
+ if (!Dom.second.isValid() || VNI->def < Dom.second)
+ Dom.second = VNI->def;
+ } else {
+ // Different basic blocks. Check if one dominates.
+ MachineBasicBlock *Near =
+ MDT.findNearestCommonDominator(Dom.first, ValMBB);
+ if (Near == ValMBB)
+ // Def ValMBB dominates.
+ Dom = DomPair(ValMBB, VNI->def);
+ else if (Near != Dom.first)
+ // None dominate. Hoist to common dominator, need new def.
+ Dom = DomPair(Near, SlotIndex());
+ }
+
+ DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def
+ << " for parent " << ParentVNI->id << '@' << ParentVNI->def
+ << " hoist to BB#" << Dom.first->getNumber() << ' '
+ << Dom.second << '\n');
+ }
+
+ // Insert the hoisted copies.
+ for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
+ DomPair &Dom = NearestDom[i];
+ if (!Dom.first || Dom.second.isValid())
+ continue;
+ // This value needs a hoisted copy inserted at the end of Dom.first.
+ VNInfo *ParentVNI = Parent->getValNumInfo(i);
+ MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
+ // Get a less loopy dominator than Dom.first.
+ Dom.first = findShallowDominator(Dom.first, DefMBB);
+ SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
+ Dom.second =
+ defFromParent(0, ParentVNI, Last, *Dom.first,
+ LIS.getLastSplitPoint(Edit->getParent(), Dom.first))->def;
+ }
+
+ // Remove redundant back-copies that are now known to be dominated by another
+ // def with the same value.
+ SmallVector<VNInfo*, 8> BackCopies;
+ for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end();
+ VI != VE; ++VI) {
+ VNInfo *VNI = *VI;
+ VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
+ const DomPair &Dom = NearestDom[ParentVNI->id];
+ if (!Dom.first || Dom.second == VNI->def)
+ continue;
+ BackCopies.push_back(VNI);
+ forceRecompute(0, ParentVNI);
+ }
+ removeBackCopies(BackCopies);
+}
+
+
/// transferValues - Transfer all possible values to the new live ranges.
-/// Values that were rematerialized are left alone, they need extendRange().
+/// Values that were rematerialized are left alone, they need LRCalc.extend().
bool SplitEditor::transferValues() {
bool Skipped = false;
- LiveInBlocks.clear();
RegAssignMap::const_iterator AssignI = RegAssign.begin();
for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(),
ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) {
LiveInterval *LI = Edit->get(RegIdx);
// Check for a simply defined value that can be blitted directly.
- if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) {
+ ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
+ if (VNInfo *VNI = VFP.getPointer()) {
DEBUG(dbgs() << ':' << VNI->id);
LI->addRange(LiveRange(Start, End, VNI));
Start = End;
continue;
}
- // Skip rematerialized values, we need to use extendRange() and
- // extendPHIKillRanges() to completely recompute the live ranges.
- if (Edit->didRematerialize(ParentVNI)) {
- DEBUG(dbgs() << "(remat)");
+ // Skip values with forced recomputation.
+ if (VFP.getInt()) {
+ DEBUG(dbgs() << "(recalc)");
Skipped = true;
Start = End;
continue;
}
- // Initialize the live-out cache the first time it is needed.
- if (LiveOutSeen.empty()) {
- unsigned N = VRM.getMachineFunction().getNumBlockIDs();
- LiveOutSeen.resize(N);
- LiveOutCache.resize(N);
- }
+ LiveRangeCalc &LRC = getLRCalc(RegIdx);
// This value has multiple defs in RegIdx, but it wasn't rematerialized,
// so the live range is accurate. Add live-in blocks in [Start;End) to the
// The first block may be live-in, or it may have its own def.
if (Start != BlockStart) {
- VNInfo *VNI = LI->extendInBlock(BlockStart,
- std::min(BlockEnd, End).getPrevSlot());
+ VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End));
assert(VNI && "Missing def for complex mapped value");
DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
// MBB has its own def. Is it also live-out?
- if (BlockEnd <= End) {
- LiveOutSeen.set(MBB->getNumber());
- LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]);
- }
+ if (BlockEnd <= End)
+ LRC.setLiveOutValue(MBB, VNI);
+
// Skip to the next block for live-in.
++MBB;
BlockStart = BlockEnd;
if (BlockStart == ParentVNI->def) {
// This block has the def of a parent PHI, so it isn't live-in.
assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
- VNInfo *VNI = LI->extendInBlock(BlockStart,
- std::min(BlockEnd, End).getPrevSlot());
+ VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End));
assert(VNI && "Missing def for complex mapped parent PHI");
- if (End >= BlockEnd) {
- // Live-out as well.
- LiveOutSeen.set(MBB->getNumber());
- LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]);
- }
+ if (End >= BlockEnd)
+ LRC.setLiveOutValue(MBB, VNI); // Live-out as well.
} else {
- // This block needs a live-in value.
- LiveInBlocks.push_back(MDT[MBB]);
- // The last block covered may not be live-out.
+ // This block needs a live-in value. The last block covered may not
+ // be live-out.
if (End < BlockEnd)
- LiveInBlocks.back().Kill = End;
+ LRC.addLiveInBlock(LI, MDT[MBB], End);
else {
- // Live-out, but we need updateSSA to tell us the value.
- LiveOutSeen.set(MBB->getNumber());
- LiveOutCache[MBB] = LiveOutPair((VNInfo*)0,
- (MachineDomTreeNode*)0);
+ // Live-through, and we don't know the value.
+ LRC.addLiveInBlock(LI, MDT[MBB]);
+ LRC.setLiveOutValue(MBB, 0);
}
}
BlockStart = BlockEnd;
DEBUG(dbgs() << '\n');
}
- if (!LiveInBlocks.empty())
- updateSSA();
+ LRCalc[0].calculateValues(LIS.getSlotIndexes(), &MDT,
+ &LIS.getVNInfoAllocator());
+ if (SpillMode)
+ LRCalc[1].calculateValues(LIS.getSlotIndexes(), &MDT,
+ &LIS.getVNInfoAllocator());
return Skipped;
}
if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
continue;
unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
+ LiveInterval *LI = Edit->get(RegIdx);
+ LiveRangeCalc &LRC = getLRCalc(RegIdx);
MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) {
- SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot();
+ SlotIndex End = LIS.getMBBEndIdx(*PI);
+ SlotIndex LastUse = End.getPrevSlot();
// The predecessor may not have a live-out value. That is OK, like an
// undef PHI operand.
- if (Edit->getParent().liveAt(End)) {
- assert(RegAssign.lookup(End) == RegIdx &&
+ if (Edit->getParent().liveAt(LastUse)) {
+ assert(RegAssign.lookup(LastUse) == RegIdx &&
"Different register assignment in phi predecessor");
- extendRange(RegIdx, End);
+ LRC.extend(LI, End,
+ LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator());
}
}
}
// use the same register as the def, so just do that always.
SlotIndex Idx = LIS.getInstructionIndex(MI);
if (MO.isDef() || MO.isUndef())
- Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex();
+ Idx = Idx.getRegSlot(MO.isEarlyClobber());
// Rewrite to the mapped register at Idx.
unsigned RegIdx = RegAssign.lookup(Idx);
- MO.setReg(Edit->get(RegIdx)->reg);
+ LiveInterval *LI = Edit->get(RegIdx);
+ MO.setReg(LI->reg);
DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
<< Idx << ':' << RegIdx << '\t' << *MI);
if (!Edit->getParent().liveAt(Idx))
continue;
} else
- Idx = Idx.getUseIndex();
+ Idx = Idx.getRegSlot(true);
- extendRange(RegIdx, Idx);
+ getLRCalc(RegIdx).extend(LI, Idx.getNextSlot(), LIS.getSlotIndexes(),
+ &MDT, &LIS.getVNInfoAllocator());
}
}
LiveInterval *LI = *I;
for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end();
LII != LIE; ++LII) {
- // Dead defs end at the store slot.
- if (LII->end != LII->valno->def.getNextSlot())
+ // Dead defs end at the dead slot.
+ if (LII->end != LII->valno->def.getDeadSlot())
continue;
MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def);
assert(MI && "Missing instruction for dead def");
VNI->setIsPHIDef(ParentVNI->isPHIDef());
VNI->setCopy(ParentVNI->getCopy());
- // Mark rematted values as complex everywhere to force liveness computation.
+ // Force rematted values to be recomputed everywhere.
// The new live ranges may be truncated.
if (Edit->didRematerialize(ParentVNI))
for (unsigned i = 0, e = Edit->size(); i != e; ++i)
- markComplexMapped(i, ParentVNI);
+ forceRecompute(i, ParentVNI);
+ }
+
+ // Hoist back-copies to the complement interval when in spill mode.
+ switch (SpillMode) {
+ case SM_Partition:
+ // Leave all back-copies as is.
+ break;
+ case SM_Size:
+ hoistCopiesForSize();
+ break;
+ case SM_Speed:
+ llvm_unreachable("Spill mode 'speed' not implemented yet");
+ break;
}
// Transfer the simply mapped values, check if any are skipped.