//
// The LLVM Compiler Infrastructure
//
-// This file was developed by Devang Patel and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// LCSSA form makes instruction renaming easier.
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequiredID(LoopSimplifyID);
+ AU.addPreservedID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addPreservedID(LCSSAID);
AU.addPreserved<ScalarEvolution>();
AU.addPreserved<LoopInfo>();
- AU.addRequiredID(LoopSimplifyID);
- AU.addPreservedID(LoopSimplifyID);
AU.addPreserved<DominatorTree>();
- // Request DominanceFrontier now, even though Loop Rotate does
- // not use it. This allows Pass Manager to schedule Dominance
- // Frontier early enough such that one LPPassManager can handle
- // loop rotate as well as licm pass.
- AU.addRequired<DominanceFrontier>();
AU.addPreserved<DominanceFrontier>();
}
/// Rotate Loop L as many times as possible. Return true if
/// loop is rotated at least once.
bool LoopRotate::runOnLoop(Loop *Lp, LPPassManager &LPM) {
-
+
bool RotatedOneLoop = false;
initialize();
LPM_Ptr = &LPM;
BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
if (!BI)
return false;
- assert (BI->isConditional() && "Branch Instruction is not condiitional");
+ assert (BI->isConditional() && "Branch Instruction is not conditional");
// Updating PHInodes in loops with multiple exits adds complexity.
// Keep it simple, and restrict loop rotation to loops with one exit only.
// In future, lift this restriction and support for multiple exits if
// required.
- std::vector<BasicBlock *> ExitBlocks;
+ SmallVector<BasicBlock*, 8> ExitBlocks;
L->getExitBlocks(ExitBlocks);
if (ExitBlocks.size() > 1)
return false;
NewHeader);
LoopInfo &LI = LPM.getAnalysis<LoopInfo>();
if (Loop *PL = LI.getLoopFor(OrigPreHeader))
- PL->addBasicBlockToLoop(NewPreHeader, LI);
+ PL->addBasicBlockToLoop(NewPreHeader, LI.getBase());
new BranchInst(NewHeader, NewPreHeader);
BranchInst *OrigPH_BI = cast<BranchInst>(OrigPreHeader->getTerminator());
"Expected only one incoming value from Original PreHeader");
}
- SplitEdge(L->getLoopLatch(), Exit, this);
-
if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
DT->addNewBlock(NewPreHeader, OrigPreHeader);
DT->changeImmediateDominator(L->getHeader(), NewPreHeader);
if(DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
- // New Preheader's dominance frontier is same as original preheader.
- DominanceFrontier::iterator DFI = DF->find(OrigPreHeader);
- if (DFI != DF->end()) {
- DominanceFrontier::DomSetType NPHSet(DFI->second), NHSet(DFI->second);
- // NPHSet.insert(DFI->second.begin(), DFI->second.end(), NPHSet.begin());
- DF->addBasicBlock(NewPreHeader, NPHSet);
-
- DominanceFrontier::iterator DHI = DF->find(L->getHeader());
- if (DHI != DF->end()) {
- DominanceFrontier::DomSetType DHSet = DHI->second;
- DHSet.clear();
- DHSet.insert(DFI->second.begin(), DFI->second.end());
- } else {
- DominanceFrontier::DomSetType NHSet(DFI->second);
- // NHSet.insert(DFI->second.begin(), DFI->second.end(), NHSet.begin());
- DF->addBasicBlock(L->getHeader(), NHSet);
- }
+ // New Preheader's dominance frontier is Exit block.
+ DominanceFrontier::DomSetType NewPHSet;
+ NewPHSet.insert(Exit);
+ DF->addBasicBlock(NewPreHeader, NewPHSet);
+
+ // New Header's dominance frontier now includes itself and Exit block
+ DominanceFrontier::iterator HeadI = DF->find(L->getHeader());
+ if (HeadI != DF->end()) {
+ DominanceFrontier::DomSetType & HeaderSet = HeadI->second;
+ HeaderSet.clear();
+ HeaderSet.insert(L->getHeader());
+ HeaderSet.insert(Exit);
+ } else {
+ DominanceFrontier::DomSetType HeaderSet;
+ HeaderSet.insert(L->getHeader());
+ HeaderSet.insert(Exit);
+ DF->addBasicBlock(L->getHeader(), HeaderSet);
+ }
+
+ // Original header (new Loop Latch)'s dominance frontier is Exit.
+ DominanceFrontier::iterator LatchI = DF->find(L->getLoopLatch());
+ if (LatchI != DF->end()) {
+ DominanceFrontier::DomSetType &LatchSet = LatchI->second;
+ LatchSet = LatchI->second;
+ LatchSet.clear();
+ LatchSet.insert(Exit);
+ } else {
+ DominanceFrontier::DomSetType LatchSet;
+ LatchSet.insert(Exit);
+ DF->addBasicBlock(L->getHeader(), LatchSet);
}
- // Original header no longer dominates Exit
- DFI = DF->find(OrigHeader);
- if (DFI != DF->end()) {
- for (succ_iterator SI = succ_begin(Exit), SE = succ_end(Exit);
- SI != SE; ++SI) {
- BasicBlock *Succ = *SI;
- DominanceFrontier::DomSetType::iterator DSI = DFI->second.find(Succ);
- if (DSI != DFI->second.end())
- DFI->second.erase(DSI);
+ // If a loop block dominates new loop latch then its frontier is
+ // new header and Exit.
+ BasicBlock *NewLatch = L->getLoopLatch();
+ DominatorTree *DT = getAnalysisToUpdate<DominatorTree>();
+ for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end();
+ BI != BE; ++BI) {
+ BasicBlock *B = *BI;
+ if (DT->dominates(B, NewLatch)) {
+ DominanceFrontier::iterator BDFI = DF->find(B);
+ if (BDFI != DF->end()) {
+ DominanceFrontier::DomSetType &BSet = BDFI->second;
+ BSet = BDFI->second;
+ BSet.clear();
+ BSet.insert(L->getHeader());
+ BSet.insert(Exit);
+ } else {
+ DominanceFrontier::DomSetType BSet;
+ BSet.insert(L->getHeader());
+ BSet.insert(Exit);
+ DF->addBasicBlock(B, BSet);
+ }
}
}
}
+ // Preserve canonical loop form, which means Exit block should
+ // have only one predecessor.
+ BasicBlock *NExit = SplitEdge(L->getLoopLatch(), Exit, this);
+
+ // Preserve LCSSA.
+ BasicBlock::iterator I = Exit->begin(), E = Exit->end();
+ PHINode *PN = NULL;
+ for (; (PN = dyn_cast<PHINode>(I)); ++I) {
+ PHINode *NewPN = new PHINode(PN->getType(), PN->getName());
+ unsigned N = PN->getNumIncomingValues();
+ for (unsigned index = 0; index < N; ++index)
+ if (PN->getIncomingBlock(index) == NExit) {
+ NewPN->addIncoming(PN->getIncomingValue(index), L->getLoopLatch());
+ PN->setIncomingValue(index, NewPN);
+ PN->setIncomingBlock(index, NExit);
+ NExit->getInstList().push_front(NewPN);
+ }
+ }
+
assert (NewHeader && L->getHeader() == NewHeader
&& "Invalid loop header after loop rotation");
assert (NewPreHeader && L->getLoopPreheader() == NewPreHeader
projects / oota-llvm.git / blobdiff