From 8f5149e002b28568a87c591e82a9371fc0a7dd47 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Sat, 7 Jul 2007 16:23:34 +0000 Subject: Back out Devang's fix for PR1320 because it causes PR1542. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37966 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopRotation.cpp | 112 ++++++--------------------------- 1 file changed, 19 insertions(+), 93 deletions(-) (limited to 'lib/Transforms/Scalar/LoopRotation.cpp') diff --git a/lib/Transforms/Scalar/LoopRotation.cpp b/lib/Transforms/Scalar/LoopRotation.cpp index 2a7b06c..6c44a9d 100644 --- a/lib/Transforms/Scalar/LoopRotation.cpp +++ b/lib/Transforms/Scalar/LoopRotation.cpp @@ -18,10 +18,7 @@ #include "llvm/Instructions.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Transforms/Utils/Local.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/ADT/Statistic.h" @@ -58,17 +55,6 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequiredID(LCSSAID); AU.addPreservedID(LCSSAID); - AU.addPreserved(); - AU.addPreserved(); - AU.addRequiredID(LoopSimplifyID); - AU.addPreservedID(LoopSimplifyID); - AU.addPreserved(); - // 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(); - AU.addPreserved(); } // Helper functions @@ -104,7 +90,7 @@ namespace { BasicBlock *OrigLatch; BasicBlock *NewHeader; BasicBlock *Exit; - LPPassManager *LPM_Ptr; + SmallVector LoopHeaderInfo; }; @@ -120,7 +106,6 @@ bool LoopRotate::runOnLoop(Loop *Lp, LPPassManager &LPM) { bool RotatedOneLoop = false; initialize(); - LPM_Ptr = &LPM; // One loop can be rotated multiple times. while (rotateLoop(Lp,LPM)) { @@ -167,13 +152,6 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { if (ExitBlocks.size() > 1) return false; - // Check size of original header and reject - // loop if it is very big. - if (OrigHeader->getInstList().size() > MAX_HEADER_SIZE) - return false; - - // Now, this loop is suitable for rotation. - // Find new Loop header. NewHeader is a Header's one and only successor // that is inside loop. Header's other successor is out side the // loop. Otherwise loop is not suitable for rotation. @@ -185,6 +163,13 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { assert(L->contains(NewHeader) && !L->contains(Exit) && "Unable to determine loop header and exit blocks"); + // Check size of original header and reject + // loop if it is very big. + if (OrigHeader->getInstList().size() > MAX_HEADER_SIZE) + return false; + + // Now, this loop is suitable for rotation. + // Copy PHI nodes and other instructions from original header // into original pre-header. Unlike original header, original pre-header is // not a member of loop. @@ -329,24 +314,18 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { U->replaceUsesOfWith(OldPhi, NewPhi); continue; } - + // Used inside Exit Block. Since we are in LCSSA form, U must be PHINode. - if (U->getParent() == Exit) { - assert (isa(U) && "Use in Exit Block that is not PHINode"); - - PHINode *UPhi = cast(U); - // UPhi already has one incoming argument from original header. - // Add second incoming argument from new Pre header. - UPhi->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader); - } else { - // Used outside Exit block. Create a new PHI node from exit block - // to receive value from ne new header ane pre header. - PHINode *PN = new PHINode(U->getType(), U->getName()); - PN->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader); - PN->addIncoming(OldPhi, OrigHeader); - Exit->getInstList().push_front(PN); - U->replaceUsesOfWith(OldPhi, PN); - } + assert (U->getParent() == Exit + && "Need to propagate new PHI into Exit blocks"); + assert (isa(U) && "Use in Exit Block that is not PHINode"); + + PHINode *UPhi = cast(U); + + // UPhi already has one incoming argument from original header. + // Add second incoming argument from new Pre header. + + UPhi->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader); } } @@ -482,63 +461,10 @@ void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) { "Expected only one incoming value from Original PreHeader"); } - SplitEdge(L->getLoopLatch(), Exit, this); - - if (DominatorTree *DT = getAnalysisToUpdate()) { - DT->addNewBlock(NewPreHeader, OrigPreHeader); - DT->changeImmediateDominator(L->getHeader(), NewPreHeader); - DT->changeImmediateDominator(Exit, OrigPreHeader); - for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); - BI != BE; ++BI) { - BasicBlock *B = *BI; - if (L->getHeader() != B) { - DomTreeNode *Node = DT->getNode(B); - if (Node && Node->getBlock() == OrigHeader) - DT->changeImmediateDominator(*BI, L->getHeader()); - } - } - DT->changeImmediateDominator(OrigHeader, OrigLatch); - } - - if(DominanceFrontier *DF = getAnalysisToUpdate()) { - - // 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); - } - } - - // 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); - } - } - } - assert (NewHeader && L->getHeader() == NewHeader && "Invalid loop header after loop rotation"); assert (NewPreHeader && L->getLoopPreheader() == NewPreHeader && "Invalid loop preheader after loop rotation"); assert (L->getLoopLatch() && "Invalid loop latch after loop rotation"); - } -- cgit v1.1