summaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils/LoopSimplify.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Utils/LoopSimplify.cpp')
-rw-r--r--lib/Transforms/Utils/LoopSimplify.cpp218
1 files changed, 80 insertions, 138 deletions
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index d6b167f8b848b..c22708a92b7a6 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -37,10 +37,12 @@
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
+#include "llvm/LLVMContext.h"
#include "llvm/Type.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
-#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CFG.h"
@@ -55,44 +57,42 @@ STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted");
STATISTIC(NumNested , "Number of nested loops split out");
namespace {
- struct VISIBILITY_HIDDEN LoopSimplify : public FunctionPass {
+ struct VISIBILITY_HIDDEN LoopSimplify : public LoopPass {
static char ID; // Pass identification, replacement for typeid
- LoopSimplify() : FunctionPass(&ID) {}
+ LoopSimplify() : LoopPass(&ID) {}
// AA - If we have an alias analysis object to update, this is it, otherwise
// this is null.
AliasAnalysis *AA;
LoopInfo *LI;
DominatorTree *DT;
- virtual bool runOnFunction(Function &F);
+ Loop *L;
+ virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
// We need loop information to identify the loops...
- AU.addRequired<LoopInfo>();
- AU.addRequired<DominatorTree>();
+ AU.addRequiredTransitive<LoopInfo>();
+ AU.addRequiredTransitive<DominatorTree>();
AU.addPreserved<LoopInfo>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<DominanceFrontier>();
AU.addPreserved<AliasAnalysis>();
+ AU.addPreserved<ScalarEvolution>();
AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added.
}
/// verifyAnalysis() - Verify loop nest.
void verifyAnalysis() const {
-#ifndef NDEBUG
- LoopInfo *NLI = &getAnalysis<LoopInfo>();
- for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I)
- (*I)->verifyLoop();
-#endif
+ assert(L->isLoopSimplifyForm() && "LoopSimplify form not preserved!");
}
private:
- bool ProcessLoop(Loop *L);
+ bool ProcessLoop(Loop *L, LPPassManager &LPM);
BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
- void InsertPreheaderForLoop(Loop *L);
- Loop *SeparateNestedLoop(Loop *L);
- void InsertUniqueBackedgeBlock(Loop *L);
+ BasicBlock *InsertPreheaderForLoop(Loop *L);
+ Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM);
+ void InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader);
void PlaceSplitBlockCarefully(BasicBlock *NewBB,
SmallVectorImpl<BasicBlock*> &SplitPreds,
Loop *L);
@@ -105,73 +105,19 @@ X("loopsimplify", "Canonicalize natural loops", true);
// Publically exposed interface to pass...
const PassInfo *const llvm::LoopSimplifyID = &X;
-FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
+Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
/// runOnFunction - Run down all loops in the CFG (recursively, but we could do
/// it in any convenient order) inserting preheaders...
///
-bool LoopSimplify::runOnFunction(Function &F) {
+bool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) {
+ L = l;
bool Changed = false;
LI = &getAnalysis<LoopInfo>();
AA = getAnalysisIfAvailable<AliasAnalysis>();
DT = &getAnalysis<DominatorTree>();
- // Check to see that no blocks (other than the header) in loops have
- // predecessors that are not in loops. This is not valid for natural loops,
- // but can occur if the blocks are unreachable. Since they are unreachable we
- // can just shamelessly destroy their terminators to make them not branch into
- // the loop!
- for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
- // This case can only occur for unreachable blocks. Blocks that are
- // unreachable can't be in loops, so filter those blocks out.
- if (LI->getLoopFor(BB)) continue;
-
- bool BlockUnreachable = false;
- TerminatorInst *TI = BB->getTerminator();
-
- // Check to see if any successors of this block are non-loop-header loops
- // that are not the header.
- for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
- // If this successor is not in a loop, BB is clearly ok.
- Loop *L = LI->getLoopFor(TI->getSuccessor(i));
- if (!L) continue;
-
- // If the succ is the loop header, and if L is a top-level loop, then this
- // is an entrance into a loop through the header, which is also ok.
- if (L->getHeader() == TI->getSuccessor(i) && L->getParentLoop() == 0)
- continue;
-
- // Otherwise, this is an entrance into a loop from some place invalid.
- // Either the loop structure is invalid and this is not a natural loop (in
- // which case the compiler is buggy somewhere else) or BB is unreachable.
- BlockUnreachable = true;
- break;
- }
-
- // If this block is ok, check the next one.
- if (!BlockUnreachable) continue;
-
- // Otherwise, this block is dead. To clean up the CFG and to allow later
- // loop transformations to ignore this case, we delete the edges into the
- // loop by replacing the terminator.
-
- // Remove PHI entries from the successors.
- for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
- TI->getSuccessor(i)->removePredecessor(BB);
-
- // Add a new unreachable instruction before the old terminator.
- new UnreachableInst(TI);
-
- // Delete the dead terminator.
- if (AA) AA->deleteValue(TI);
- if (!TI->use_empty())
- TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
- TI->eraseFromParent();
- Changed |= true;
- }
-
- for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
- Changed |= ProcessLoop(*I);
+ Changed |= ProcessLoop(L, LPM);
return Changed;
}
@@ -179,21 +125,42 @@ bool LoopSimplify::runOnFunction(Function &F) {
/// ProcessLoop - Walk the loop structure in depth first order, ensuring that
/// all loops have preheaders.
///
-bool LoopSimplify::ProcessLoop(Loop *L) {
+bool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) {
bool Changed = false;
ReprocessLoop:
-
- // Canonicalize inner loops before outer loops. Inner loop canonicalization
- // can provide work for the outer loop to canonicalize.
- for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
- Changed |= ProcessLoop(*I);
-
- assert(L->getBlocks()[0] == L->getHeader() &&
- "Header isn't first block in loop?");
+
+ // Check to see that no blocks (other than the header) in this loop that has
+ // predecessors that are not in the loop. This is not valid for natural
+ // loops, but can occur if the blocks are unreachable. Since they are
+ // unreachable we can just shamelessly delete those CFG edges!
+ for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
+ BB != E; ++BB) {
+ if (*BB == L->getHeader()) continue;
+
+ SmallPtrSet<BasicBlock *, 4> BadPreds;
+ for (pred_iterator PI = pred_begin(*BB), PE = pred_end(*BB); PI != PE; ++PI)
+ if (!L->contains(*PI))
+ BadPreds.insert(*PI);
+
+ // Delete each unique out-of-loop (and thus dead) predecessor.
+ for (SmallPtrSet<BasicBlock *, 4>::iterator I = BadPreds.begin(),
+ E = BadPreds.end(); I != E; ++I) {
+ // Inform each successor of each dead pred.
+ for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI)
+ (*SI)->removePredecessor(*I);
+ // Zap the dead pred's terminator and replace it with unreachable.
+ TerminatorInst *TI = (*I)->getTerminator();
+ TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
+ (*I)->getTerminator()->eraseFromParent();
+ new UnreachableInst((*I)->getContext(), *I);
+ Changed = true;
+ }
+ }
// Does the loop already have a preheader? If so, don't insert one.
- if (L->getLoopPreheader() == 0) {
- InsertPreheaderForLoop(L);
+ BasicBlock *Preheader = L->getLoopPreheader();
+ if (!Preheader) {
+ Preheader = InsertPreheaderForLoop(L);
NumInserted++;
Changed = true;
}
@@ -229,10 +196,9 @@ ReprocessLoop:
// this for loops with a giant number of backedges, just factor them into a
// common backedge instead.
if (NumBackedges < 8) {
- if (Loop *NL = SeparateNestedLoop(L)) {
+ if (SeparateNestedLoop(L, LPM)) {
++NumNested;
// This is a big restructuring change, reprocess the whole loop.
- ProcessLoop(NL);
Changed = true;
// GCC doesn't tail recursion eliminate this.
goto ReprocessLoop;
@@ -242,7 +208,7 @@ ReprocessLoop:
// If we either couldn't, or didn't want to, identify nesting of the loops,
// insert a new block that all backedges target, then make it jump to the
// loop header.
- InsertUniqueBackedgeBlock(L);
+ InsertUniqueBackedgeBlock(L, Preheader);
NumInserted++;
Changed = true;
}
@@ -253,7 +219,7 @@ ReprocessLoop:
PHINode *PN;
for (BasicBlock::iterator I = L->getHeader()->begin();
(PN = dyn_cast<PHINode>(I++)); )
- if (Value *V = PN->hasConstantValue()) {
+ if (Value *V = PN->hasConstantValue(DT)) {
if (AA) AA->deleteValue(PN);
PN->replaceAllUsesWith(V);
PN->eraseFromParent();
@@ -286,19 +252,10 @@ ReprocessLoop:
Instruction *Inst = I++;
if (Inst == CI)
continue;
- if (Inst->isTrapping()) {
+ if (!L->makeLoopInvariant(Inst, Changed, Preheader->getTerminator())) {
AllInvariant = false;
break;
}
- for (unsigned j = 0, f = Inst->getNumOperands(); j != f; ++j)
- if (!L->isLoopInvariant(Inst->getOperand(j))) {
- AllInvariant = false;
- break;
- }
- if (!AllInvariant)
- break;
- // Hoist.
- Inst->moveBefore(L->getLoopPreheader()->getTerminator());
}
if (!AllInvariant) continue;
@@ -317,9 +274,10 @@ ReprocessLoop:
DomTreeNode *Node = DT->getNode(ExitingBlock);
const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
Node->getChildren();
- for (unsigned k = 0, g = Children.size(); k != g; ++k) {
- DT->changeImmediateDominator(Children[k], Node->getIDom());
- if (DF) DF->changeImmediateDominator(Children[k]->getBlock(),
+ while (!Children.empty()) {
+ DomTreeNode *Child = Children.front();
+ DT->changeImmediateDominator(Child, Node->getIDom());
+ if (DF) DF->changeImmediateDominator(Child->getBlock(),
Node->getIDom()->getBlock(),
DT);
}
@@ -339,7 +297,7 @@ ReprocessLoop:
/// preheader, this method is called to insert one. This method has two phases:
/// preheader insertion and analysis updating.
///
-void LoopSimplify::InsertPreheaderForLoop(Loop *L) {
+BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) {
BasicBlock *Header = L->getHeader();
// Compute the set of predecessors of the loop that are not in the loop.
@@ -353,19 +311,12 @@ void 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.
PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L);
+
+ return NewBB;
}
/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit
@@ -382,17 +333,6 @@ 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;
}
@@ -422,14 +362,13 @@ static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT,
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
PHINode *PN = cast<PHINode>(I);
++I;
- if (Value *V = PN->hasConstantValue())
- if (!isa<Instruction>(V) || DT->dominates(cast<Instruction>(V), PN)) {
- // This is a degenerate PHI already, don't modify it!
- PN->replaceAllUsesWith(V);
- if (AA) AA->deleteValue(PN);
- PN->eraseFromParent();
- continue;
- }
+ if (Value *V = PN->hasConstantValue(DT)) {
+ // This is a degenerate PHI already, don't modify it!
+ PN->replaceAllUsesWith(V);
+ if (AA) AA->deleteValue(PN);
+ PN->eraseFromParent();
+ continue;
+ }
// Scan this PHI node looking for a use of the PHI node by itself.
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
@@ -496,7 +435,7 @@ void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB,
/// If we are able to separate out a loop, return the new outer loop that was
/// created.
///
-Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
+Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) {
PHINode *PN = FindPHIToPartitionLoops(L, DT, AA);
if (PN == 0) return 0; // No known way to partition.
@@ -527,17 +466,20 @@ 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);
+ // Add the new loop to the pass manager queue.
+ LPM.insertLoopIntoQueue(NewOuter);
+
for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
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;
@@ -578,11 +520,10 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
/// backedges to target a new basic block and have that block branch to the loop
/// header. This ensures that loops have exactly one backedge.
///
-void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) {
+void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) {
assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
// Get information about the loop
- BasicBlock *Preheader = L->getLoopPreheader();
BasicBlock *Header = L->getHeader();
Function *F = Header->getParent();
@@ -592,7 +533,8 @@ void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) {
if (*I != Preheader) BackedgeBlocks.push_back(*I);
// Create and insert the new backedge block...
- BasicBlock *BEBlock = BasicBlock::Create(Header->getName()+".backedge", F);
+ BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(),
+ Header->getName()+".backedge", F);
BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
// Move the new backedge block to right after the last backedge block.
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-31 15:25:55 +0000