aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Transforms/Utils
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Utils')
-rw-r--r--lib/Transforms/Utils/BasicBlockUtils.cpp92
-rw-r--r--lib/Transforms/Utils/BreakCriticalEdges.cpp65
-rw-r--r--lib/Transforms/Utils/LCSSA.cpp19
-rw-r--r--lib/Transforms/Utils/LoopSimplify.cpp40
4 files changed, 62 insertions, 154 deletions
diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp
index 736d26e..c165e04 100644
--- a/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -24,7 +24,6 @@
#include "llvm/Analysis/Dominators.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/Local.h"
-#include "llvm/Transforms/Scalar.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/ValueHandle.h"
#include <algorithm>
@@ -320,8 +319,7 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) {
++SplitIt;
BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
- // The new block lives in whichever loop the old one did. This preserves
- // LCSSA as well, because we force the split point to be after any PHI nodes.
+ // The new block lives in whichever loop the old one did.
if (LoopInfo* LI = P->getAnalysisIfAvailable<LoopInfo>())
if (Loop *L = LI->getLoopFor(Old))
L->addBasicBlockToLoop(New, LI->getBase());
@@ -355,12 +353,8 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) {
/// Preds array, which has NumPreds elements in it. The new block is given a
/// suffix of 'Suffix'.
///
-/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
-/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses.
-/// In particular, it does not preserve LoopSimplify (because it's
-/// complicated to handle the case where one of the edges being split
-/// is an exit of a loop with other exits).
-///
+/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and
+/// DominanceFrontier, but no other analyses.
BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
BasicBlock *const *Preds,
unsigned NumPreds, const char *Suffix,
@@ -372,44 +366,19 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
// The new block unconditionally branches to the old block.
BranchInst *BI = BranchInst::Create(BB, NewBB);
- LoopInfo *LI = P ? P->getAnalysisIfAvailable<LoopInfo>() : 0;
- Loop *L = LI ? LI->getLoopFor(BB) : 0;
- bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID);
-
// Move the edges from Preds to point to NewBB instead of BB.
- // While here, if we need to preserve loop analyses, collect
- // some information about how this split will affect loops.
- bool HasLoopExit = false;
- bool IsLoopEntry = !!L;
- bool SplitMakesNewLoopHeader = false;
- for (unsigned i = 0; i != NumPreds; ++i) {
+ for (unsigned i = 0; i != NumPreds; ++i)
Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
-
- if (LI) {
- // If we need to preserve LCSSA, determine if any of
- // the preds is a loop exit.
- if (PreserveLCSSA)
- if (Loop *PL = LI->getLoopFor(Preds[i]))
- if (!PL->contains(BB))
- HasLoopExit = true;
- // If we need to preserve LoopInfo, note whether any of the
- // preds crosses an interesting loop boundary.
- if (L) {
- if (L->contains(Preds[i]))
- IsLoopEntry = false;
- else
- SplitMakesNewLoopHeader = true;
- }
- }
- }
-
+
// Update dominator tree and dominator frontier if available.
DominatorTree *DT = P ? P->getAnalysisIfAvailable<DominatorTree>() : 0;
if (DT)
DT->splitBlock(NewBB);
if (DominanceFrontier *DF = P ? P->getAnalysisIfAvailable<DominanceFrontier>():0)
DF->splitBlock(NewBB);
-
+ AliasAnalysis *AA = P ? P->getAnalysisIfAvailable<AliasAnalysis>() : 0;
+
+
// Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
// node becomes an incoming value for BB's phi node. However, if the Preds
// list is empty, we need to insert dummy entries into the PHI nodes in BB to
@@ -420,42 +389,20 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
return NewBB;
}
-
- AliasAnalysis *AA = P ? P->getAnalysisIfAvailable<AliasAnalysis>() : 0;
-
- if (L) {
- if (IsLoopEntry) {
- if (Loop *PredLoop = LI->getLoopFor(Preds[0])) {
- // Add the new block to the nearest enclosing loop (and not an
- // adjacent loop).
- while (PredLoop && !PredLoop->contains(BB))
- PredLoop = PredLoop->getParentLoop();
- if (PredLoop)
- PredLoop->addBasicBlockToLoop(NewBB, LI->getBase());
- }
- } else {
- L->addBasicBlockToLoop(NewBB, LI->getBase());
- if (SplitMakesNewLoopHeader)
- L->moveToHeader(NewBB);
- }
- }
// Otherwise, create a new PHI node in NewBB for each PHI node in BB.
for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) {
PHINode *PN = cast<PHINode>(I++);
// Check to see if all of the values coming in are the same. If so, we
- // don't need to create a new PHI node, unless it's needed for LCSSA.
- Value *InVal = 0;
- if (!HasLoopExit) {
- InVal = PN->getIncomingValueForBlock(Preds[0]);
- for (unsigned i = 1; i != NumPreds; ++i)
- if (InVal != PN->getIncomingValueForBlock(Preds[i])) {
- InVal = 0;
- break;
- }
- }
-
+ // don't need to create a new PHI node.
+ Value *InVal = PN->getIncomingValueForBlock(Preds[0]);
+ for (unsigned i = 1; i != NumPreds; ++i)
+ if (InVal != PN->getIncomingValueForBlock(Preds[i])) {
+ InVal = 0;
+ break;
+ }
+
if (InVal) {
// If all incoming values for the new PHI would be the same, just don't
// make a new PHI. Instead, just remove the incoming values from the old
@@ -480,6 +427,13 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
// Add an incoming value to the PHI node in the loop for the preheader
// edge.
PN->addIncoming(InVal, NewBB);
+
+ // Check to see if we can eliminate this phi node.
+ if (Value *V = PN->hasConstantValue(DT)) {
+ PN->replaceAllUsesWith(V);
+ if (AA) AA->deleteValue(PN);
+ PN->eraseFromParent();
+ }
}
return NewBB;
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index f5a1366..632aa2b 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -122,9 +122,9 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
/// false otherwise. This ensures that all edges to that dest go to one block
/// instead of each going to a different block.
//
-BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
- Pass *P, bool MergeIdenticalEdges) {
- if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0;
+bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P,
+ bool MergeIdenticalEdges) {
+ if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return false;
BasicBlock *TIBB = TI->getParent();
BasicBlock *DestBB = TI->getSuccessor(SuccNum);
@@ -172,7 +172,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
// If we don't have a pass object, we can't update anything...
- if (P == 0) return NewBB;
+ if (P == 0) return true;
// Now update analysis information. Since the only predecessor of NewBB is
// the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate
@@ -254,9 +254,9 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
// Update LoopInfo if it is around.
if (LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>()) {
- if (Loop *TIL = LI->getLoopFor(TIBB)) {
- // If one or the other blocks were not in a loop, the new block is not
- // either, and thus LI doesn't need to be updated.
+ // If one or the other blocks were not in a loop, the new block is not
+ // either, and thus LI doesn't need to be updated.
+ if (Loop *TIL = LI->getLoopFor(TIBB))
if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
if (TIL == DestLoop) {
// Both in the same loop, the NewBB joins loop.
@@ -278,55 +278,6 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
P->addBasicBlockToLoop(NewBB, LI->getBase());
}
}
- // If TIBB is in a loop and DestBB is outside of that loop, split the
- // other exit blocks of the loop that also have predecessors outside
- // the loop, to maintain a LoopSimplify guarantee.
- if (!TIL->contains(DestBB) &&
- P->mustPreserveAnalysisID(LoopSimplifyID)) {
- // For each unique exit block...
- SmallVector<BasicBlock *, 4> ExitBlocks;
- TIL->getExitBlocks(ExitBlocks);
- for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
- // Collect all the preds that are inside the loop, and note
- // whether there are any preds outside the loop.
- SmallVector<BasicBlock *, 4> Preds;
- bool AllPredsInLoop = false;
- BasicBlock *Exit = ExitBlocks[i];
- for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit);
- I != E; ++I)
- if (TIL->contains(*I))
- Preds.push_back(*I);
- else
- AllPredsInLoop = true;
- // If there are any preds not in the loop, we'll need to split
- // the edges. The Preds.empty() check is needed because a block
- // may appear multiple times in the list. We can't use
- // getUniqueExitBlocks above because that depends on LoopSimplify
- // form, which we're in the process of restoring!
- if (Preds.empty() || !AllPredsInLoop) continue;
- BasicBlock *NewBB = SplitBlockPredecessors(Exit,
- Preds.data(), Preds.size(),
- "split", P);
- // Update LCSSA form. This is fairly simple in LoopSimplify form:
- // just move the existing LCSSA-mandated PHI nodes from the old exit
- // block to the new one.
- if (P->mustPreserveAnalysisID(LCSSAID))
- for (BasicBlock::iterator I = Exit->begin();
- PHINode *PN = dyn_cast<PHINode>(I); ++I)
- PN->moveBefore(NewBB->getTerminator());
- }
- }
- // LCSSA form was updated above for the case where LoopSimplify is
- // available, which means that all predecessors of loop exit blocks
- // are within the loop. Without LoopSimplify form, it would be
- // necessary to insert a new phi.
- assert((!P->mustPreserveAnalysisID(LCSSAID) ||
- P->mustPreserveAnalysisID(LoopSimplifyID)) &&
- "SplitCriticalEdge doesn't know how to update LCCSA form "
- "without LoopSimplify!");
- }
-
}
-
- return NewBB;
+ return true;
}
diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index e0251f8..84fcc64 100644
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -58,7 +58,6 @@ namespace {
DominatorTree *DT;
std::vector<BasicBlock*> LoopBlocks;
PredIteratorCache PredCache;
- Loop *L;
virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
@@ -73,9 +72,9 @@ namespace {
AU.setPreservesCFG();
AU.addRequiredID(LoopSimplifyID);
AU.addPreservedID(LoopSimplifyID);
- AU.addRequiredTransitive<LoopInfo>();
+ AU.addRequired<LoopInfo>();
AU.addPreserved<LoopInfo>();
- AU.addRequiredTransitive<DominatorTree>();
+ AU.addRequired<DominatorTree>();
AU.addPreserved<ScalarEvolution>();
AU.addPreserved<DominatorTree>();
@@ -87,17 +86,6 @@ namespace {
AU.addPreserved<DominanceFrontier>();
}
private:
-
- /// verifyAnalysis() - Verify loop nest.
- virtual void verifyAnalysis() const {
-#ifndef NDEBUG
- // Sanity check: Check basic loop invariants.
- L->verifyLoop();
- // Check the special guarantees that LCSSA makes.
- assert(L->isLCSSAForm());
-#endif
- }
-
void getLoopValuesUsedOutsideLoop(Loop *L,
SetVector<Instruction*> &AffectedValues,
const SmallVector<BasicBlock*, 8>& exitBlocks);
@@ -119,8 +107,7 @@ Pass *llvm::createLCSSAPass() { return new LCSSA(); }
const PassInfo *const llvm::LCSSAID = &X;
/// runOnFunction - Process all loops in the function, inner-most out.
-bool LCSSA::runOnLoop(Loop *l, LPPassManager &LPM) {
- L = l;
+bool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) {
PredCache.clear();
LI = &LPM.getAnalysis<LoopInfo>();
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 36709f7..56e5a46 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -69,8 +69,8 @@ namespace {
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
// We need loop information to identify the loops...
- AU.addRequiredTransitive<LoopInfo>();
- AU.addRequiredTransitive<DominatorTree>();
+ AU.addRequired<LoopInfo>();
+ AU.addRequired<DominatorTree>();
AU.addPreserved<LoopInfo>();
AU.addPreserved<DominatorTree>();
@@ -83,13 +83,9 @@ namespace {
void verifyAnalysis() const {
#ifndef NDEBUG
LoopInfo *NLI = &getAnalysis<LoopInfo>();
- for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I) {
- // Sanity check: Check basic loop invariants.
+ for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I)
(*I)->verifyLoop();
- // Check the special guarantees that LoopSimplify makes.
- assert((*I)->isLoopSimplifyForm());
- }
-#endif
+#endif
}
private:
@@ -350,6 +346,15 @@ BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) {
BasicBlock *NewBB =
SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(),
".preheader", this);
+
+
+ //===--------------------------------------------------------------------===//
+ // Update analysis results now that we have performed the transformation
+ //
+
+ // We know that we have loop information to update... update it now.
+ if (Loop *Parent = L->getParentLoop())
+ Parent->addBasicBlockToLoop(NewBB, LI->getBase());
// Make sure that NewBB is put someplace intelligent, which doesn't mess up
// code layout too horribly.
@@ -372,6 +377,17 @@ BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
LoopBlocks.size(), ".loopexit",
this);
+ // Update Loop Information - we know that the new block will be in whichever
+ // loop the Exit block is in. Note that it may not be in that immediate loop,
+ // if the successor is some other loop header. In that case, we continue
+ // walking up the loop tree to find a loop that contains both the successor
+ // block and the predecessor block.
+ Loop *SuccLoop = LI->getLoopFor(Exit);
+ while (SuccLoop && !SuccLoop->contains(L->getHeader()))
+ SuccLoop = SuccLoop->getParentLoop();
+ if (SuccLoop)
+ SuccLoop->addBasicBlockToLoop(NewBB, LI->getBase());
+
return NewBB;
}
@@ -505,6 +521,10 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
else
LI->changeTopLevelLoop(L, NewOuter);
+ // This block is going to be our new header block: add it to this loop and all
+ // parent loops.
+ NewOuter->addBasicBlockToLoop(NewBB, LI->getBase());
+
// L is now a subloop of our outer loop.
NewOuter->addChildLoop(L);
@@ -512,10 +532,6 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
I != E; ++I)
NewOuter->addBlockEntry(*I);
- // Now reset the header in L, which had been moved by
- // SplitBlockPredecessors for the outer loop.
- L->moveToHeader(Header);
-
// Determine which blocks should stay in L and which should be moved out to
// the Outer loop now.
std::set<BasicBlock*> BlocksInL;
generated by cgit v1.1 at 2025-05-21 01:22:53 +0000