//===----------------------------------------------------------------------===//
-// LiveIntervalMap
+// Split Editor
//===----------------------------------------------------------------------===//
-// Work around the fact that the std::pair constructors are broken for pointer
-// pairs in some implementations. makeVV(x, 0) works.
-static inline std::pair<const VNInfo*, VNInfo*>
-makeVV(const VNInfo *a, VNInfo *b) {
- return std::make_pair(a, b);
+/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
+SplitEditor::SplitEditor(SplitAnalysis &sa,
+ LiveIntervals &lis,
+ VirtRegMap &vrm,
+ MachineDominatorTree &mdt,
+ LiveRangeEdit &edit)
+ : SA(sa), LIS(lis), VRM(vrm),
+ MRI(vrm.getMachineFunction().getRegInfo()),
+ MDT(mdt),
+ TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
+ TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
+ Edit(edit),
+ OpenIdx(0),
+ RegAssign(Allocator)
+{
+ // We don't need an AliasAnalysis since we will only be performing
+ // cheap-as-a-copy remats anyway.
+ Edit.anyRematerializable(LIS, TII, 0);
+}
+
+void SplitEditor::dump() const {
+ if (RegAssign.empty()) {
+ dbgs() << " empty\n";
+ return;
+ }
+
+ for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
+ dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
+ dbgs() << '\n';
}
-void LiveIntervalMap::reset(LiveInterval *li) {
- LI = li;
- LiveOutCache.clear();
+VNInfo *SplitEditor::defValue(unsigned RegIdx,
+ const VNInfo *ParentVNI,
+ SlotIndex Idx) {
+ assert(ParentVNI && "Mapping NULL value");
+ assert(Idx.isValid() && "Invalid SlotIndex");
+ assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
+ LiveInterval *LI = Edit.get(RegIdx);
+
+ // Create a new value.
+ VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
+
+ // Preserve the PHIDef bit.
+ if (ParentVNI->isPHIDef() && Idx == ParentVNI->def)
+ VNI->setIsPHIDef(true);
+
+ // 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));
+
+ // This was the first time (RegIdx, ParentVNI) was mapped.
+ // Keep it as a simple def without any liveness.
+ if (InsP.second)
+ return VNI;
+
+ // If the previous value was a simple mapping, add liveness for it now.
+ if (VNInfo *OldVNI = InsP.first->second) {
+ SlotIndex Def = OldVNI->def;
+ LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
+ // No longer a simple mapping.
+ InsP.first->second = 0;
+ }
+
+ // This is a complex mapping, add liveness for VNI
+ SlotIndex Def = VNI->def;
+ LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
+
+ return VNI;
}
+void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
+ assert(ParentVNI && "Mapping NULL value");
+ VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
+
+ // ParentVNI was either unmapped or already complex mapped. Either way.
+ if (!VNI)
+ 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 LiveIntervalMap::extendRange(SlotIndex Idx) {
- assert(LI && "call reset first");
+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))
std::pair<LiveOutMap::iterator,bool> LOIP =
LiveOutCache.insert(std::make_pair(Pred, LiveOutPair()));
// Yes, we have been here before.
- if (!LOIP.second) {
- DEBUG(if (VNInfo *VNI = LOIP.first->second.first)
- dbgs() << " known valno #" << VNI->id
- << " at BB#" << Pred->getNumber() << '\n');
+ if (!LOIP.second)
continue;
- }
// Does Pred provide a live-out value?
SlotIndex Start, Last;
Last = Last.getPrevSlot();
if (VNInfo *VNI = LI->extendInBlock(Start, Last)) {
MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def);
- DEBUG(dbgs() << " found valno #" << VNI->id
- << " from BB#" << DefMBB->getNumber()
- << " at BB#" << Pred->getNumber() << '\n');
LiveOutPair &LOP = LOIP.first->second;
LOP.first = VNI;
LOP.second = MDT[DefMBB];
}
// We may need to add phi-def values to preserve the SSA form.
+ VNInfo *IdxVNI = updateSSA(RegIdx, LiveIn, Idx, IdxMBB);
+
+#ifndef NDEBUG
+ // Check the LiveOutCache invariants.
+ for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
+ I != E; ++I) {
+ assert(I->first && "Null MBB entry in cache");
+ assert(I->second.first && "Null VNInfo in cache");
+ assert(I->second.second && "Null DomTreeNode in cache");
+ if (I->second.second->getBlock() == I->first)
+ continue;
+ for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
+ PE = I->first->pred_end(); PI != PE; ++PI)
+ assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant");
+ }
+#endif
+
+ // Since we went through the trouble of a full BFS visiting all reaching defs,
+ // the values in LiveIn are now accurate. No more phi-defs are needed
+ // for these blocks, so we can color the live ranges.
+ for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
+ MachineBasicBlock *MBB = LiveIn[i]->getBlock();
+ SlotIndex Start = LIS.getMBBStartIdx(MBB);
+ VNInfo *VNI = LiveOutCache.lookup(MBB).first;
+
+ // Anything in LiveIn other than IdxMBB is live-through.
+ // In IdxMBB, we should stop at Idx unless the same value is live-out.
+ if (MBB == IdxMBB && IdxVNI != VNI)
+ LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
+ else
+ LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
+ }
+}
+
+VNInfo *SplitEditor::updateSSA(unsigned RegIdx,
+ SmallVectorImpl<MachineDomTreeNode*> &LiveIn,
+ SlotIndex Idx,
+ const MachineBasicBlock *IdxMBB) {
// 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.
+ LiveInterval *LI = Edit.get(RegIdx);
VNInfo *IdxVNI = 0;
unsigned Changes;
do {
Changes = 0;
DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n");
- // Propagate live-out values down the dominator tree, inserting phi-defs when
- // necessary. Since LiveIn was created by a BFS, going backwards makes it more
- // likely for us to visit immediate dominators before their children.
+ // Propagate live-out values down the dominator tree, inserting phi-defs
+ // when necessary. Since LiveIn was created by a BFS, going backwards makes
+ // it more likely for us to visit immediate dominators before their
+ // children.
for (unsigned i = LiveIn.size(); i; --i) {
MachineDomTreeNode *Node = LiveIn[i-1];
MachineBasicBlock *MBB = Node->getBlock();
} while (Changes);
assert(IdxVNI && "Didn't find value for Idx");
-
-#ifndef NDEBUG
- // Check the LiveOutCache invariants.
- for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
- I != E; ++I) {
- assert(I->first && "Null MBB entry in cache");
- assert(I->second.first && "Null VNInfo in cache");
- assert(I->second.second && "Null DomTreeNode in cache");
- if (I->second.second->getBlock() == I->first)
- continue;
- for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
- PE = I->first->pred_end(); PI != PE; ++PI)
- assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant");
- }
-#endif
-
- // Since we went through the trouble of a full BFS visiting all reaching defs,
- // the values in LiveIn are now accurate. No more phi-defs are needed
- // for these blocks, so we can color the live ranges.
- for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
- MachineBasicBlock *MBB = LiveIn[i]->getBlock();
- SlotIndex Start = LIS.getMBBStartIdx(MBB);
- VNInfo *VNI = LiveOutCache.lookup(MBB).first;
-
- // Anything in LiveIn other than IdxMBB is live-through.
- // In IdxMBB, we should stop at Idx unless the same value is live-out.
- if (MBB == IdxMBB && IdxVNI != VNI)
- LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
- else
- LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
- }
-}
-
-#ifndef NDEBUG
-void LiveIntervalMap::dumpCache() {
- for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
- I != E; ++I) {
- assert(I->first && "Null MBB entry in cache");
- assert(I->second.first && "Null VNInfo in cache");
- assert(I->second.second && "Null DomTreeNode in cache");
- dbgs() << " cache: BB#" << I->first->getNumber()
- << " has valno #" << I->second.first->id << " from BB#"
- << I->second.second->getBlock()->getNumber() << ", preds";
- for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
- PE = I->first->pred_end(); PI != PE; ++PI)
- dbgs() << " BB#" << (*PI)->getNumber();
- dbgs() << '\n';
- }
- dbgs() << " cache: " << LiveOutCache.size() << " entries.\n";
-}
-#endif
-
-
-//===----------------------------------------------------------------------===//
-// Split Editor
-//===----------------------------------------------------------------------===//
-
-/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
-SplitEditor::SplitEditor(SplitAnalysis &sa,
- LiveIntervals &lis,
- VirtRegMap &vrm,
- MachineDominatorTree &mdt,
- LiveRangeEdit &edit)
- : SA(sa), LIS(lis), VRM(vrm),
- MRI(vrm.getMachineFunction().getRegInfo()),
- MDT(mdt),
- TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
- TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
- Edit(edit),
- OpenIdx(0),
- RegAssign(Allocator)
-{
- // We don't need an AliasAnalysis since we will only be performing
- // cheap-as-a-copy remats anyway.
- Edit.anyRematerializable(LIS, TII, 0);
-}
-
-void SplitEditor::dump() const {
- if (RegAssign.empty()) {
- dbgs() << " empty\n";
- return;
- }
-
- for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
- dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
- dbgs() << '\n';
-}
-
-VNInfo *SplitEditor::defValue(unsigned RegIdx,
- const VNInfo *ParentVNI,
- SlotIndex Idx) {
- assert(ParentVNI && "Mapping NULL value");
- assert(Idx.isValid() && "Invalid SlotIndex");
- assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
- LiveInterval *LI = Edit.get(RegIdx);
-
- // Create a new value.
- VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
-
- // Preserve the PHIDef bit.
- if (ParentVNI->isPHIDef() && Idx == ParentVNI->def)
- VNI->setIsPHIDef(true);
-
- // 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));
-
- // This was the first time (RegIdx, ParentVNI) was mapped.
- // Keep it as a simple def without any liveness.
- if (InsP.second)
- return VNI;
-
- // If the previous value was a simple mapping, add liveness for it now.
- if (VNInfo *OldVNI = InsP.first->second) {
- SlotIndex Def = OldVNI->def;
- LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
- // No longer a simple mapping.
- InsP.first->second = 0;
- }
-
- // This is a complex mapping, add liveness for VNI
- SlotIndex Def = VNI->def;
- LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
-
- return VNI;
-}
-
-void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
- assert(ParentVNI && "Mapping NULL value");
- VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
-
- // ParentVNI was either unmapped or already complex mapped. Either way.
- if (!VNI)
- 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;
+ return IdxVNI;
}
VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
assert(!OpenIdx && "Previous LI not closed before openIntv");
// Create the complement as index 0.
- if (Edit.empty()) {
+ if (Edit.empty())
Edit.create(MRI, LIS, VRM);
- LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
- LIMappers.back().reset(Edit.get(0));
- }
// Create the open interval.
OpenIdx = Edit.size();
Edit.create(MRI, LIS, VRM);
- LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
- LIMappers[OpenIdx].reset(Edit.get(OpenIdx));
}
SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
<< Idx << ':' << RegIdx << '\t' << *MI);
// Extend liveness to Idx.
- LIMappers[RegIdx].extendRange(Idx);
+ extendRange(RegIdx, Idx);
}
}
if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
continue;
unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
- LiveIntervalMap &LIM = LIMappers[RegIdx];
MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def
<< " -> " << RegIdx << '\n');
DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End);
// The predecessor may not have a live-out value. That is OK, like an
// undef PHI operand.
- if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) {
- DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n");
+ if (Edit.getParent().liveAt(End)) {
+ DEBUG(dbgs() << " has parent live out\n");
assert(RegAssign.lookup(End) == RegIdx &&
"Different register assignment in phi predecessor");
- LIM.extendRange(End);
- }
- else
+ extendRange(RegIdx, End);
+ } else
DEBUG(dbgs() << " is not live-out\n");
}
- DEBUG(dbgs() << " " << *LIM.getLI() << '\n');
+ DEBUG(dbgs() << " " << *Edit.get(RegIdx) << '\n');
}
// Rewrite instructions.
};
-/// LiveIntervalMap - Map values from a large LiveInterval into a small
-/// interval that is a subset. Insert phi-def values as needed. This class is
-/// used by SplitEditor to create new smaller LiveIntervals.
-///
-/// ParentLI is the larger interval, LI is the subset interval. Every value
-/// in LI corresponds to exactly one value in ParentLI, and the live range
-/// of the value is contained within the live range of the ParentLI value.
-/// Values in ParentLI may map to any number of OpenLI values, including 0.
-class LiveIntervalMap {
- LiveIntervals &LIS;
- MachineDominatorTree &MDT;
-
- // The parent interval is never changed.
- const LiveInterval &ParentLI;
-
- // The child interval's values are fully contained inside ParentLI values.
- LiveInterval *LI;
-
- typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair;
- typedef DenseMap<MachineBasicBlock*,LiveOutPair> LiveOutMap;
-
- // LiveOutCache - Map each basic block where LI is live out to the live-out
- // value and its defining block. One of these conditions shall be true:
- //
- // 1. !LiveOutCache.count(MBB)
- // 2. LiveOutCache[MBB].second.getNode() == MBB
- // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB]
- //
- // This is only a cache, the values can be computed as:
- //
- // VNI = LI->getVNInfoAt(LIS.getMBBEndIdx(MBB))
- // Node = mbt_[LIS.getMBBFromIndex(VNI->def)]
- //
- // The cache is also used as a visiteed set by mapValue().
- LiveOutMap LiveOutCache;
-
- // Dump the live-out cache to dbgs().
- void dumpCache();
-
-public:
- LiveIntervalMap(LiveIntervals &lis,
- MachineDominatorTree &mdt,
- const LiveInterval &parentli)
- : LIS(lis), MDT(mdt), ParentLI(parentli), LI(0) {}
-
- /// reset - clear all data structures and start a new live interval.
- void reset(LiveInterval *);
-
- /// getLI - return the current live interval.
- LiveInterval *getLI() const { return LI; }
-
- /// extendRange - Extend the live range of LI so it reaches Idx.
- /// Insert PHIDefs as needed to preserve SSA form.
- void extendRange(SlotIndex Idx);
-};
-
-
/// SplitEditor - Edit machine code and LiveIntervals for live range
/// splitting.
///
/// Idx.
RegAssignMap RegAssign;
- /// LIMappers - One LiveIntervalMap or each interval in Edit.
- SmallVector<LiveIntervalMap, 4> LIMappers;
-
typedef DenseMap<std::pair<unsigned, unsigned>, VNInfo*> ValueMap;
/// Values - keep track of the mapping from parent values to values in the new
/// The new value has no live ranges anywhere.
ValueMap Values;
+ typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair;
+ typedef DenseMap<MachineBasicBlock*,LiveOutPair> LiveOutMap;
+
+ // LiveOutCache - Map each basic block where a new register is live out to the
+ // live-out value and its defining block.
+ // One of these conditions shall be true:
+ //
+ // 1. !LiveOutCache.count(MBB)
+ // 2. LiveOutCache[MBB].second.getNode() == MBB
+ // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB]
+ //
+ // This is only a cache, the values can be computed as:
+ //
+ // VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB))
+ // Node = mbt_[LIS.getMBBFromIndex(VNI->def)]
+ //
+ // The cache is also used as a visited set by extendRange(). It can be shared
+ // by all the new registers because at most one is live out of each block.
+ LiveOutMap LiveOutCache;
+
/// defValue - define a value in RegIdx from ParentVNI at Idx.
/// Idx does not have to be ParentVNI->def, but it must be contained within
/// ParentVNI's live range in ParentLI. The new value is added to the value
MachineBasicBlock &MBB,
MachineBasicBlock::iterator I);
+ /// extendRange - Extend the live range of Edit.get(RegIdx) so it reaches Idx.
+ /// Insert PHIDefs as needed to preserve SSA form.
+ void extendRange(unsigned RegIdx, SlotIndex Idx);
+
+ /// updateSSA - Insert PHIDefs as necessary and update LiveOutCache such that
+ /// Edit.get(RegIdx) is live-in to all the blocks in LiveIn.
+ /// Return the value that is eventually live-in to IdxMBB.
+ VNInfo *updateSSA(unsigned RegIdx,
+ SmallVectorImpl<MachineDomTreeNode*> &LiveIn,
+ SlotIndex Idx,
+ const MachineBasicBlock *IdxMBB);
+
/// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers.
void rewriteAssigned();
projects / oota-llvm.git / commitdiff