bool ProcessLoop(Loop *L);
BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix,
const std::vector<BasicBlock*> &Preds);
- void RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
+ BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
void InsertPreheaderForLoop(Loop *L);
Loop *SeparateNestedLoop(Loop *L);
void InsertUniqueBackedgeBlock(Loop *L);
// predecessors that are inside of the loop. This check guarantees that the
// loop preheader/header will dominate the exit blocks. If the exit block has
// predecessors from outside of the loop, split the edge now.
- for (unsigned i = 0, e = L->getExitBlocks().size(); i != e; ++i) {
- BasicBlock *ExitBlock = L->getExitBlocks()[i];
+ std::vector<BasicBlock*> ExitBlocks;
+ L->getExitBlocks(ExitBlocks);
+ for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
+ BasicBlock *ExitBlock = ExitBlocks[i];
for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
PI != PE; ++PI)
if (!L->contains(*PI)) {
- RewriteLoopExitBlock(L, ExitBlock);
+ BasicBlock *NewBB = RewriteLoopExitBlock(L, ExitBlock);
+ for (unsigned j = i; j != ExitBlocks.size(); ++j)
+ if (ExitBlocks[j] == ExitBlock)
+ ExitBlocks[j] = NewBB;
+
NumInserted++;
Changed = true;
break;
return NewBB;
}
-// ChangeExitBlock - This recursive function is used to change any exit blocks
-// that use OldExit to use NewExit instead. This is recursive because children
-// may need to be processed as well.
-//
-static void ChangeExitBlock(Loop *L, BasicBlock *OldExit, BasicBlock *NewExit) {
- if (L->hasExitBlock(OldExit)) {
- L->changeExitBlock(OldExit, NewExit);
- for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
- ChangeExitBlock(*I, OldExit, NewExit);
- }
-}
-
-
/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
/// preheader, this method is called to insert one. This method has two phases:
/// preheader insertion and analysis updating.
ParentLoopsE = getAnalysis<LoopInfo>().end();
}
- // Loop over all sibling loops, performing the substitution (recursively to
- // include child loops)...
- for (; ParentLoops != ParentLoopsE; ++ParentLoops)
- ChangeExitBlock(*ParentLoops, Header, NewBB);
-
DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info
DominatorTree &DT = getAnalysis<DominatorTree>();
/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit
/// blocks. This method is used to split exit blocks that have predecessors
/// outside of the loop.
-void LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
+BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
DominatorSet &DS = getAnalysis<DominatorSet>();
- assert(std::find(L->getExitBlocks().begin(), L->getExitBlocks().end(), Exit)
- != L->getExitBlocks().end() && "Not a current exit block!");
std::vector<BasicBlock*> LoopBlocks;
for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I)
if (Loop *Parent = L->getParentLoop())
Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>());
- // Replace any instances of Exit with NewBB in this and any nested loops...
- for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I)
- if (I->hasExitBlock(Exit))
- I->changeExitBlock(Exit, NewBB); // Update exit block information
-
// Update dominator information (set, immdom, domtree, and domfrontier)
UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks);
+ return NewBB;
}
/// AddBlockAndPredsToSet - Add the specified block, and all of its
AddBlockAndPredsToSet(*I, StopBlock, Blocks);
}
-static void ReplaceExitBlocksOfLoopAndParents(Loop *L, BasicBlock *Old,
- BasicBlock *New) {
- if (!L->hasExitBlock(Old)) return;
- L->changeExitBlock(Old, New);
- ReplaceExitBlocksOfLoopAndParents(L->getParentLoop(), Old, New);
-}
-
-/// VerifyExitBlocks - This is a function which can be useful for hacking on the
-/// LoopSimplify Code.
-static void VerifyExitBlocks(Loop *L) {
- std::vector<BasicBlock*> ExitBlocks;
- for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) {
- BasicBlock *BB = L->getBlocks()[i];
- for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
- if (!L->contains(*SI))
- ExitBlocks.push_back(*SI);
+/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
+/// PHI node that tells us how to partition the loops.
+static PHINode *FindPHIToPartitionLoops(Loop *L) {
+ for (BasicBlock::iterator I = L->getHeader()->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ) {
+ ++I;
+ if (Value *V = hasConstantValue(PN)) {
+ // This is a degenerate PHI already, don't modify it!
+ PN->replaceAllUsesWith(V);
+ PN->getParent()->getInstList().erase(PN);
+ } else {
+ // Scan this PHI node looking for a use of the PHI node by itself.
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+ if (PN->getIncomingValue(i) == PN &&
+ L->contains(PN->getIncomingBlock(i)))
+ // We found something tasty to remove.
+ return PN;
+ }
}
-
- std::vector<BasicBlock*> EB = L->getExitBlocks();
- std::sort(EB.begin(), EB.end());
- std::sort(ExitBlocks.begin(), ExitBlocks.end());
- assert(EB == ExitBlocks && "Exit blocks were incorrectly updated!");
-
- for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
- VerifyExitBlocks(*I);
+ return 0;
}
/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of
/// created.
///
Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
- BasicBlock *Header = L->getHeader();
+ PHINode *PN = FindPHIToPartitionLoops(L);
+ if (PN == 0) return 0; // No known way to partition.
+ // Pull out all predecessors that have varying values in the loop. This
+ // handles the case when a PHI node has multiple instances of itself as
+ // arguments.
std::vector<BasicBlock*> OuterLoopPreds;
- for (BasicBlock::iterator I = Header->begin();
- PHINode *PN = dyn_cast<PHINode>(I); ) {
- ++I;
- if (Value *V = hasConstantValue(PN)) {
- // This is a degenerate PHI already, don't modify it!
- PN->replaceAllUsesWith(V);
- Header->getInstList().erase(PN);
- 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)
- if (PN->getIncomingValue(i) == PN &&
- L->contains(PN->getIncomingBlock(i))) {
- // Wow, we found something tasty to remove. Pull out all predecessors
- // that have varying values in the loop. This handles the case when a
- // PHI node has multiple instances of itself as arguments.
- for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
- if (PN->getIncomingValue(i) != PN ||
- !L->contains(PN->getIncomingBlock(i)))
- OuterLoopPreds.push_back(PN->getIncomingBlock(i));
- goto FoundExtraction;
- }
- }
-
- return 0; // Nothing looks appetizing to separate out
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+ if (PN->getIncomingValue(i) != PN ||
+ !L->contains(PN->getIncomingBlock(i)))
+ OuterLoopPreds.push_back(PN->getIncomingBlock(i));
-FoundExtraction:
+ BasicBlock *Header = L->getHeader();
BasicBlock *NewBB = SplitBlockPredecessors(Header, ".outer", OuterLoopPreds);
// Update dominator information (set, immdom, domtree, and domfrontier)
// L is now a subloop of our outer loop.
NewOuter->addChildLoop(L);
- // Add all of L's exit blocks to the outer loop.
- for (unsigned i = 0, e = L->getExitBlocks().size(); i != e; ++i)
- NewOuter->addExitBlock(L->getExitBlocks()[i]);
-
- // Add temporary exit block entries for NewBB. Add one for each edge in L
- // that goes to NewBB.
- for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); PI != E; ++PI)
- if (L->contains(*PI))
- L->addExitBlock(NewBB);
-
for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i)
NewOuter->addBlockEntry(L->getBlocks()[i]);
}
}
- // Check all subloops of this loop, replacing any exit blocks that got
- // revectored with the new basic block.
- for (pred_iterator I = pred_begin(NewBB), E = pred_end(NewBB); I != E; ++I)
- if (NewOuter->contains(*I)) {
- // Change any exit blocks that used to go to Header to go to NewBB
- // instead.
- ReplaceExitBlocksOfLoopAndParents((Loop*)LI[*I], Header, NewBB);
- }
-
- //VerifyExitBlocks(NewOuter);
return NewOuter;
}
// loop and all parent loops.
L->addBasicBlockToLoop(BEBlock, getAnalysis<LoopInfo>());
- // Replace any instances of Exit with NewBB in this and any nested loops...
- for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I)
- if (I->hasExitBlock(Header))
- I->changeExitBlock(Header, BEBlock); // Update exit block information
-
// Update dominator information (set, immdom, domtree, and domfrontier)
UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks);
}
// Update dominance frontier information...
if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
- // If NewBB dominates NewBBSucc, then the global dominance frontiers are not
- // changed. DF(NewBB) is now going to be the DF(PredBlocks[0]) without the
- // stuff that the new block does not dominate a predecessor of.
+ // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
+ // DF(PredBlocks[0]) without the stuff that the new block does not dominate
+ // a predecessor of.
if (NewBBDominatesNewBBSucc) {
DominanceFrontier::iterator DFI = DF->find(PredBlocks[0]);
if (DFI != DF->end()) {
DominanceFrontier::DomSetType NewDFSet;
NewDFSet.insert(NewBBSucc);
DF->addBasicBlock(NewBB, NewDFSet);
-
- // Now we must loop over all of the dominance frontiers in the function,
- // replacing occurrences of NewBBSucc with NewBB in some cases. All
- // blocks that dominate a block in PredBlocks and contained NewBBSucc in
- // their dominance frontier must be updated to contain NewBB instead.
- //
- for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) {
- BasicBlock *Pred = PredBlocks[i];
- // Get all of the dominators of the predecessor...
- const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred);
- for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(),
- PDE = PredDoms.end(); PDI != PDE; ++PDI) {
- BasicBlock *PredDom = *PDI;
-
- // If the NewBBSucc node is in DF(PredDom), then PredDom didn't
- // dominate NewBBSucc but did dominate a predecessor of it. Now we
- // change this entry to include NewBB in the DF instead of NewBBSucc.
- DominanceFrontier::iterator DFI = DF->find(PredDom);
- assert(DFI != DF->end() && "No dominance frontier for node?");
- if (DFI->second.count(NewBBSucc)) {
- DF->removeFromFrontier(DFI, NewBBSucc);
- DF->addToFrontier(DFI, NewBB);
+ }
+
+ // Now we must loop over all of the dominance frontiers in the function,
+ // replacing occurrences of NewBBSucc with NewBB in some cases. All
+ // blocks that dominate a block in PredBlocks and contained NewBBSucc in
+ // their dominance frontier must be updated to contain NewBB instead.
+ //
+ for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) {
+ BasicBlock *Pred = PredBlocks[i];
+ // Get all of the dominators of the predecessor...
+ const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred);
+ for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(),
+ PDE = PredDoms.end(); PDI != PDE; ++PDI) {
+ BasicBlock *PredDom = *PDI;
+
+ // If the NewBBSucc node is in DF(PredDom), then PredDom didn't
+ // dominate NewBBSucc but did dominate a predecessor of it. Now we
+ // change this entry to include NewBB in the DF instead of NewBBSucc.
+ DominanceFrontier::iterator DFI = DF->find(PredDom);
+ assert(DFI != DF->end() && "No dominance frontier for node?");
+ if (DFI->second.count(NewBBSucc)) {
+ // If NewBBSucc should not stay in our dominator frontier, remove it.
+ // We remove it unless there is a predecessor of NewBBSucc that we
+ // dominate, but we don't strictly dominate NewBBSucc.
+ bool ShouldRemove = true;
+ if (PredDom == NewBBSucc || !DS.dominates(PredDom, NewBBSucc)) {
+ // Okay, we know that PredDom does not strictly dominate NewBBSucc.
+ // Check to see if it dominates any predecessors of NewBBSucc.
+ for (pred_iterator PI = pred_begin(NewBBSucc),
+ E = pred_end(NewBBSucc); PI != E; ++PI)
+ if (DS.dominates(PredDom, *PI)) {
+ ShouldRemove = false;
+ break;
+ }
}
+
+ if (ShouldRemove)
+ DF->removeFromFrontier(DFI, NewBBSucc);
+ DF->addToFrontier(DFI, NewBB);
}
}
}
projects / oota-llvm.git / blobdiff