aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/SplitKit.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/SplitKit.cpp')
-rw-r--r--lib/CodeGen/SplitKit.cpp311
1 files changed, 135 insertions, 176 deletions
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index a2214bb3be..4c2a7bda0f 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -198,29 +198,101 @@ void SplitAnalysis::analyze(const LiveInterval *li) {
//===----------------------------------------------------------------------===//
-// 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))
@@ -247,12 +319,8 @@ void LiveIntervalMap::extendRange(SlotIndex 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;
@@ -260,9 +328,6 @@ void LiveIntervalMap::extendRange(SlotIndex Idx) {
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];
@@ -275,16 +340,56 @@ void LiveIntervalMap::extendRange(SlotIndex Idx) {
}
// 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();
@@ -369,146 +474,7 @@ void LiveIntervalMap::extendRange(SlotIndex Idx) {
} 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,
@@ -545,17 +511,12 @@ void SplitEditor::openIntv() {
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) {
@@ -716,7 +677,7 @@ void SplitEditor::rewriteAssigned() {
<< Idx << ':' << RegIdx << '\t' << *MI);
// Extend liveness to Idx.
- LIMappers[RegIdx].extendRange(Idx);
+ extendRange(RegIdx, Idx);
}
}
@@ -783,7 +744,6 @@ void SplitEditor::finish() {
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');
@@ -793,16 +753,15 @@ void SplitEditor::finish() {
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.
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-01 01:40:37 +0000