Move PHIElimination's SplitCriticalEdge for MachineBasicBlocks out
into a utility routine, teach it how to update MachineLoopInfo, and
make use of it in MachineLICM to split critical edges on demand.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106555 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp
index d9623ab..9b24a9a 100644
--- a/lib/CodeGen/MachineLICM.cpp
+++ b/lib/CodeGen/MachineLICM.cpp
@@ -83,7 +83,6 @@
const char *getPassName() const { return "Machine Instruction LICM"; }
- // FIXME: Loop preheaders?
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<MachineLoopInfo>();
@@ -182,6 +181,10 @@
/// current loop preheader that may become duplicates of instructions that
/// are hoisted out of the loop.
void InitCSEMap(MachineBasicBlock *BB);
+
+ /// getCurPreheader - Get the preheader for the current loop, splitting
+ /// a critical edge if needed.
+ MachineBasicBlock *getCurPreheader();
};
} // end anonymous namespace
@@ -193,11 +196,11 @@
return new MachineLICM(PreRegAlloc);
}
-/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most
-/// loop that has a preheader.
-static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) {
+/// LoopIsOuterMostWithPredecessor - Test if the given loop is the outer-most
+/// loop that has a unique predecessor.
+static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) {
for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop())
- if (L->getLoopPreheader())
+ if (L->getLoopPredecessor())
return false;
return true;
}
@@ -223,20 +226,11 @@
for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I){
CurLoop = *I;
+ CurPreheader = 0;
// If this is done before regalloc, only visit outer-most preheader-sporting
// loops.
- if (PreRegAlloc && !LoopIsOuterMostWithPreheader(CurLoop))
- continue;
-
- // Determine the block to which to hoist instructions. If we can't find a
- // suitable loop preheader, we can't do any hoisting.
- //
- // FIXME: We are only hoisting if the basic block coming into this loop
- // has only one successor. This isn't the case in general because we haven't
- // broken critical edges or added preheaders.
- CurPreheader = CurLoop->getLoopPreheader();
- if (!CurPreheader)
+ if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop))
continue;
if (!PreRegAlloc)
@@ -438,13 +432,16 @@
/// operands that is safe to hoist, this instruction is called to do the
/// dirty work.
void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) {
+ MachineBasicBlock *Preheader = getCurPreheader();
+ if (!Preheader) return;
+
// Now move the instructions to the predecessor, inserting it before any
// terminator instructions.
DEBUG({
dbgs() << "Hoisting " << *MI;
- if (CurPreheader->getBasicBlock())
+ if (Preheader->getBasicBlock())
dbgs() << " to MachineBasicBlock "
- << CurPreheader->getName();
+ << Preheader->getName();
if (MI->getParent()->getBasicBlock())
dbgs() << " from MachineBasicBlock "
<< MI->getParent()->getName();
@@ -453,7 +450,7 @@
// Splice the instruction to the preheader.
MachineBasicBlock *MBB = MI->getParent();
- CurPreheader->splice(CurPreheader->getFirstTerminator(), MBB, MI);
+ Preheader->splice(Preheader->getFirstTerminator(), MBB, MI);
// Add register to livein list to all the BBs in the current loop since a
// loop invariant must be kept live throughout the whole loop. This is
@@ -756,6 +753,9 @@
/// that are safe to hoist, this instruction is called to do the dirty work.
///
void MachineLICM::Hoist(MachineInstr *MI) {
+ MachineBasicBlock *Preheader = getCurPreheader();
+ if (!Preheader) return;
+
// First check whether we should hoist this instruction.
if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
// If not, try unfolding a hoistable load.
@@ -767,9 +767,9 @@
// terminator instructions.
DEBUG({
dbgs() << "Hoisting " << *MI;
- if (CurPreheader->getBasicBlock())
+ if (Preheader->getBasicBlock())
dbgs() << " to MachineBasicBlock "
- << CurPreheader->getName();
+ << Preheader->getName();
if (MI->getParent()->getBasicBlock())
dbgs() << " from MachineBasicBlock "
<< MI->getParent()->getName();
@@ -779,7 +779,7 @@
// If this is the first instruction being hoisted to the preheader,
// initialize the CSE map with potential common expressions.
if (FirstInLoop) {
- InitCSEMap(CurPreheader);
+ InitCSEMap(Preheader);
FirstInLoop = false;
}
@@ -789,7 +789,7 @@
CI = CSEMap.find(Opcode);
if (!EliminateCSE(MI, CI)) {
// Otherwise, splice the instruction to the preheader.
- CurPreheader->splice(CurPreheader->getFirstTerminator(),MI->getParent(),MI);
+ Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
// Clear the kill flags of any register this instruction defines,
// since they may need to be live throughout the entire loop
@@ -813,3 +813,30 @@
++NumHoisted;
Changed = true;
}
+
+MachineBasicBlock *MachineLICM::getCurPreheader() {
+ // Determine the block to which to hoist instructions. If we can't find a
+ // suitable loop predecessor, we can't do any hoisting.
+
+ // If we've tried to get a preheader and failed, don't try again.
+ if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1))
+ return 0;
+
+ if (!CurPreheader) {
+ CurPreheader = CurLoop->getLoopPreheader();
+ if (!CurPreheader) {
+ MachineBasicBlock *Pred = CurLoop->getLoopPredecessor();
+ if (!Pred) {
+ CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
+ return 0;
+ }
+
+ CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), this);
+ if (!CurPreheader) {
+ CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
+ return 0;
+ }
+ }
+ }
+ return CurPreheader;
+}