[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopRotation.cpp updated: 1.1 - 1.2 --- Log message: Only cosmetic changes. Zero functionality Change. --- Diffs of the changes: (+100 -97) LoopRotation.cpp | 197 +++ 1 files changed, 100 insertions(+), 97 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.1 llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.2 --- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.1 Fri Apr 6 20:20:26 2007 +++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr 9 11:11:48 2007 @@ -11,7 +11,7 @@ // //===--===// -#define DEBUG_TYPE loop-rotation +#define DEBUG_TYPE loop-rotate #include llvm/Transforms/Scalar.h #include llvm/Function.h @@ -23,7 +23,6 @@ #include llvm/Support/Debug.h #include llvm/ADT/Statistic.h #include llvm/ADT/SmallVector.h -#include map using namespace llvm; @@ -32,29 +31,28 @@ STATISTIC(NumRotated, Number of loops rotated); namespace { - cl::optunsigned - RotateThreshold(rotate-threshold, cl::init(200), cl::Hidden, - cl::desc(The cut-off point for loop rotating)); - - class VISIBILITY_HIDDEN InsnReplacementData { + class VISIBILITY_HIDDEN RenameData { public: -InsnReplacementData(Instruction *O, Instruction *P, Instruction *H) - : Original(O), PreHeader(P), Header(H) {} +RenameData(Instruction *O, Instruction *P, Instruction *H) + : Original(O), PreHeader(P), Header(H) { } public: Instruction *Original; // Original instruction Instruction *PreHeader; // New pre-header replacement Instruction *Header; // New header replacement }; - + class VISIBILITY_HIDDEN LoopRotate : public LoopPass { public: + +// Rotate Loop L as many times as possible. Return true if +// loop is rotated at least once. bool runOnLoop(Loop *L, LPPassManager LPM); + +// LCSSA form makes instruction renaming easier. virtual void getAnalysisUsage(AnalysisUsage AU) const { AU.addRequiredID(LCSSAID); AU.addPreservedID(LCSSAID); - //AU.addRequiredLoopInfo(); - //AU.addPreservedLoopInfo(); } // Helper functions @@ -75,7 +73,7 @@ /// Find Replacement information for instruction. Return NULL if it is /// not available. -InsnReplacementData *findReplacementData(Instruction *I); +RenameData *findReplacementData(Instruction *I); private: @@ -87,7 +85,7 @@ BasicBlock *NewPreHeader; BasicBlock *Exit; -SmallVectorInsnReplacementData, MAX_HEADER_SIZE RD; +SmallVectorRenameData, MAX_HEADER_SIZE LoopHeaderInfo; }; RegisterPassLoopRotate X (loop-rotate, Rotate Loops); @@ -95,6 +93,8 @@ LoopPass *llvm::createLoopRotatePass() { return new LoopRotate(); } +/// 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; @@ -109,18 +109,17 @@ return RotatedOneLoop; } +/// Rotate loop LP. Return true if it loop is rotated. bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager LPM) { L = Lp; - if ( NumRotated = RotateThreshold) -return false; OrigHeader = L-getHeader(); OrigPreHeader = L-getLoopPreheader(); OrigLatch = L-getLoopLatch(); // If loop has only one block then there is not much to rotate. - if (L-getBlocks().size() = 1) + if (L-getBlocks().size() == 1) return false; if (!OrigHeader || !OrigLatch || !OrigPreHeader) @@ -135,33 +134,27 @@ BranchInst *BI = dyn_castBranchInst(OrigHeader-getTerminator()); if (!BI) return false; + assert (BI-isConditional() Branch Instruction is not condiitional); + // 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::vectorBasicBlock * ExitBlocks; L-getExitBlocks(ExitBlocks); if (ExitBlocks.size() 1) return false; // Find new Loop header. NewHeader is a Header's one and only successor - // that is inside loop. Header's all other successors are out side the + // that is inside loop. Header's other successor is out side the // loop. Otherwise loop is not suitable for rotation. - for (unsigned index = 0; index BI-getNumSuccessors(); ++index) { -BasicBlock *S = BI-getSuccessor(index); -if (L-contains(S)) { - if (!NewHeader) -NewHeader = S; - else -// Loop Header has two successors inside loop. This loop is -// not suitable for rotation. -return false; -} else { - if (!Exit) -Exit = S; - else -// Loop has multiple exits. -return false; -} - } + Exit = BI-getSuccessor(0); +
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopRotation.cpp updated: 1.2 - 1.3 --- Log message: More cosmetic changes. --- Diffs of the changes: (+18 -14) LoopRotation.cpp | 32 ++-- 1 files changed, 18 insertions(+), 14 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.2 llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.3 --- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.2 Mon Apr 9 11:11:48 2007 +++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr 9 11:21:29 2007 @@ -238,10 +238,12 @@ for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) { -RenameData ILoopHeaderInfo = (*I); +const RenameData ILoopHeaderInfo = *I; Instruction *In = ILoopHeaderInfo.Original; Instruction *C = ILoopHeaderInfo.PreHeader; - + +// If this instruction is not from new pre-header then is not new +// pre-header then this instruction is not handled here. if (C-getParent() != NewPreHeader) continue; @@ -249,7 +251,7 @@ if (isaPHINode(In)) continue; -for (unsigned opi = 0; opi In-getNumOperands(); ++opi) { +for (unsigned opi = 0, e = In-getNumOperands(); opi != e; ++opi) { if (Instruction *OpPhi = dyn_castPHINode(In-getOperand(opi))) { if (RenameData *D = findReplacementData(OpPhi)) C-setOperand(opi, D-PreHeader); @@ -283,7 +285,7 @@ for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) { -RenameData ILoopHeaderInfo = (*I); +const RenameData ILoopHeaderInfo = *I; if (!ILoopHeaderInfo.Header) continue; @@ -294,7 +296,7 @@ // not invalidated. SmallVectorInstruction *, 16 AllUses; for (Value::use_iterator UI = OldPhi-use_begin(), UE = OldPhi-use_end(); - UI != UE; ++UI ) { + UI != UE; ++UI) { Instruction *U = castInstruction(UI); AllUses.push_back(U); } @@ -307,9 +309,10 @@ // Used inside original header if (Parent == OrigHeader) { // Do not rename uses inside original header non-phi instructions. -if (!isaPHINode(U)) - continue; PHINode *PU = dyn_castPHINode(U); +if (!PU) + continue; + // Do not rename uses inside original header phi nodes, if the // incoming value is for new header. if (PU-getBasicBlockIndex(NewHeader) != -1 @@ -322,13 +325,14 @@ // Used inside loop, but not in original header. if (L-contains(U-getParent())) { -if (U != NewPhi ) +if (U != NewPhi) U-replaceUsesOfWith(OldPhi, NewPhi); continue; } // Used inside Exit Block. Since we are in LCSSA form, U must be PHINode. - assert ( U-getParent() == Exit Need to propagate new PHI into Exit blocks); + assert (U-getParent() == Exit + Need to propagate new PHI into Exit blocks); assert (isaPHINode(U) Use in Exit Block that is not PHINode); PHINode *UPhi = castPHINode(U); @@ -374,10 +378,9 @@ for (BasicBlock::iterator I = Exit-begin(), E = Exit-end(); I != E; ++I) { -if (!isaPHINode(I)) - break; - PHINode *PN = dyn_castPHINode(I); +if (!PN) + break; if (PN-getBasicBlockIndex(NewPreHeader) == -1) { Value *V = PN-getIncomingValueForBlock(OrigHeader); @@ -405,7 +408,8 @@ LoopHeaderInfo.clear(); } -/// Return true if this instruction is used outside original header. +/// Return true if this instruction is used by any instructions in the loop that +/// aren't in original header. bool LoopRotate::usedOutsideOriginalHeader(Instruction *In) { for (Value::use_iterator UI = In-use_begin(), UE = In-use_end(); @@ -427,7 +431,7 @@ // Since LoopHeaderInfo is small, linear walk is OK. for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) -if ((*I).Original == In) +if (I-Original == In) return (*I); return NULL; ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopRotation.cpp updated: 1.3 - 1.4 --- Log message: Fix future bug. Of course, Chris spotted this. Handle Argument or Undef as an incoming PHI value. --- Diffs of the changes: (+12 -11) LoopRotation.cpp | 23 --- 1 files changed, 12 insertions(+), 11 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.3 llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.4 --- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.3 Mon Apr 9 11:21:29 2007 +++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr 9 11:41:46 2007 @@ -369,7 +369,6 @@ return true; } - /// Make sure all Exit block PHINodes have required incoming values. /// If incoming value is constant or defined outside the loop then /// PHINode may not have an entry for new pre-header. @@ -382,20 +381,22 @@ if (!PN) break; -if (PN-getBasicBlockIndex(NewPreHeader) == -1) { - Value *V = PN-getIncomingValueForBlock(OrigHeader); - if (isaConstant(V)) -PN-addIncoming(V, NewPreHeader); - else { -RenameData *ILoopHeaderInfo = findReplacementData(castInstruction(V)); -assert (ILoopHeaderInfo ILoopHeaderInfo-PreHeader Missing New Preheader Instruction); -PN-addIncoming(ILoopHeaderInfo-PreHeader, NewPreHeader); - } +// There is already one incoming value from new pre-header block. +if (PN-getBasicBlockIndex(NewPreHeader) != -1) + return; + +RenameData *ILoopHeaderInfo; +Value *V = PN-getIncomingValueForBlock(OrigHeader); +if (isaInstruction(V) +(ILoopHeaderInfo = findReplacementData(castInstruction(V { + assert (ILoopHeaderInfo-PreHeader Missing New Preheader Instruction); + PN-addIncoming(ILoopHeaderInfo-PreHeader, NewPreHeader); +} else { + PN-addIncoming(V, NewPreHeader); } } } - /// Initialize local data void LoopRotate::initialize() { L = NULL; ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopRotation.cpp updated: 1.4 - 1.5 --- Log message: Simpler for() loops. --- Diffs of the changes: (+17 -23) LoopRotation.cpp | 40 +--- 1 files changed, 17 insertions(+), 23 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.4 llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.5 --- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.4 Mon Apr 9 11:41:46 2007 +++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr 9 12:09:13 2007 @@ -73,7 +73,7 @@ /// Find Replacement information for instruction. Return NULL if it is /// not available. -RenameData *findReplacementData(Instruction *I); +const RenameData *findReplacementData(Instruction *I); private: @@ -179,13 +179,10 @@ NewPreHeader = new BasicBlock(bb.nph, OrigHeader-getParent(), OrigHeader); BasicBlock::iterator I = OrigHeader-begin(), E = OrigHeader-end(); - for (; I != E; ++I) { + PHINode *PN = NULL; + for (; (PN = dyn_castPHINode(I)); ++I) { Instruction *In = I; -PHINode *PN = dyn_castPHINode(I); -if (!PN) - break; - // Create new PHI node with one value incoming from OrigPreHeader. // NewPreHeader has only one predecessor, OrigPreHeader. PHINode *NPH = new PHINode(In-getType(), In-getName()); @@ -235,10 +232,8 @@ // Update new pre-header. // Rename values that are defined in original header to reflects values // defined in new pre-header. - for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator - I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) { - -const RenameData ILoopHeaderInfo = *I; + for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) { +const RenameData ILoopHeaderInfo = LoopHeaderInfo[LHI]; Instruction *In = ILoopHeaderInfo.Original; Instruction *C = ILoopHeaderInfo.PreHeader; @@ -253,12 +248,12 @@ for (unsigned opi = 0, e = In-getNumOperands(); opi != e; ++opi) { if (Instruction *OpPhi = dyn_castPHINode(In-getOperand(opi))) { -if (RenameData *D = findReplacementData(OpPhi)) +if (const RenameData *D = findReplacementData(OpPhi)) C-setOperand(opi, D-PreHeader); } else if (Instruction *OpInsn = dyn_castInstruction(In-getOperand(opi))) { -if (RenameData *D = findReplacementData(OpInsn)) +if (const RenameData *D = findReplacementData(OpInsn)) C-setOperand(opi, D-PreHeader); } } @@ -282,10 +277,9 @@ // 2) Inside loop but not in original header // //Replace this use to reflect definition from new header. - for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator - I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) { + for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) { +const RenameData ILoopHeaderInfo = LoopHeaderInfo[LHI]; -const RenameData ILoopHeaderInfo = *I; if (!ILoopHeaderInfo.Header) continue; @@ -318,7 +312,7 @@ if (PU-getBasicBlockIndex(NewHeader) != -1 PU-getIncomingValueForBlock(NewHeader) == U) continue; - + U-replaceUsesOfWith(OldPhi, NewPhi); continue; } @@ -385,7 +379,7 @@ if (PN-getBasicBlockIndex(NewPreHeader) != -1) return; -RenameData *ILoopHeaderInfo; +const RenameData *ILoopHeaderInfo; Value *V = PN-getIncomingValueForBlock(OrigHeader); if (isaInstruction(V) (ILoopHeaderInfo = findReplacementData(castInstruction(V { @@ -427,13 +421,13 @@ /// Find Replacement information for instruction. Return NULL if it is /// not available. -RenameData *LoopRotate::findReplacementData(Instruction *In) { +const RenameData *LoopRotate::findReplacementData(Instruction *In) { // Since LoopHeaderInfo is small, linear walk is OK. - for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator - I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) -if (I-Original == In) - return (*I); - + for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) { +const RenameData ILoopHeaderInfo = LoopHeaderInfo[LHI]; +if (ILoopHeaderInfo.Original == In) + return ILoopHeaderInfo; + } return NULL; } ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopRotation.cpp updated: 1.5 - 1.6 --- Log message: Do not create new pre-header. Reuse original pre-header. --- Diffs of the changes: (+57 -73) LoopRotation.cpp | 130 --- 1 files changed, 57 insertions(+), 73 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.5 llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.6 --- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.5 Mon Apr 9 12:09:13 2007 +++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr 9 14:04:21 2007 @@ -33,11 +33,11 @@ class VISIBILITY_HIDDEN RenameData { public: -RenameData(Instruction *O, Instruction *P, Instruction *H) +RenameData(Instruction *O, Value *P, Instruction *H) : Original(O), PreHeader(P), Header(H) { } public: Instruction *Original; // Original instruction -Instruction *PreHeader; // New pre-header replacement +Value *PreHeader; // Original pre-header replacement Instruction *Header; // New header replacement }; @@ -65,7 +65,7 @@ /// Make sure all Exit block PHINodes have required incoming values. /// If incoming value is constant or defined outside the loop then -/// PHINode may not have an entry for new pre-header. +/// PHINode may not have an entry for original pre-header. void updateExitBlock(); /// Return true if this instruction is used outside original header. @@ -82,7 +82,6 @@ BasicBlock *OrigPreHeader; BasicBlock *OrigLatch; BasicBlock *NewHeader; -BasicBlock *NewPreHeader; BasicBlock *Exit; SmallVectorRenameData, MAX_HEADER_SIZE LoopHeaderInfo; @@ -125,6 +124,9 @@ if (!OrigHeader || !OrigLatch || !OrigPreHeader) return false; + if (!OrigHeader || !OrigLatch || !OrigPreHeader) +return false; + // If loop header is not one of the loop exit block then // either this loop is already rotated or it is not // suitable for loop rotation transformations. @@ -164,42 +166,40 @@ // Now, this loop is suitable for rotation. // Copy PHI nodes and other instructions from original header - // into new pre-header. Unlike original header, new pre-header is - // not a member of loop. New pre-header has only one predecessor, - // that is original loop pre-header. + // into original pre-header. Unlike original header, original pre-header is + // not a member of loop. // // New loop header is one and only successor of original header that // is inside the loop. All other original header successors are outside // the loop. Copy PHI Nodes from original header into new loop header. - // Add second incoming value, from new loop pre-header into these phi + // Add second incoming value, from original loop pre-header into these phi // nodes. If a value defined in original header is used outside original // header then new loop header will need new phi nodes with two incoming // values, one definition from original header and second definition is - // from new loop pre-header (which is a clone of original header definition). + // from original loop pre-header. - NewPreHeader = new BasicBlock(bb.nph, OrigHeader-getParent(), OrigHeader); + // Remove terminator from Original pre-header. Original pre-header will + // receive a clone of original header terminator as a new terminator. + OrigPreHeader-getInstList().pop_back(); BasicBlock::iterator I = OrigHeader-begin(), E = OrigHeader-end(); PHINode *PN = NULL; for (; (PN = dyn_castPHINode(I)); ++I) { Instruction *In = I; -// Create new PHI node with one value incoming from OrigPreHeader. -// NewPreHeader has only one predecessor, OrigPreHeader. -PHINode *NPH = new PHINode(In-getType(), In-getName()); -NPH-addIncoming(PN-getIncomingValueForBlock(OrigPreHeader), - OrigPreHeader); -NewPreHeader-getInstList().push_back(NPH); - +// PHI nodes are not copied into original pre-header. Instead their values +// are directly propagated. +Value * NPV = PN-getIncomingValueForBlock(OrigPreHeader); + // Create new PHI node with two incoming values for NewHeader. // One incoming value is from OrigLatch (through OrigHeader) and -// second incoming value is from NewPreHeader. +// second incoming value is from original pre-header. PHINode *NH = new PHINode(In-getType(), In-getName()); NH-addIncoming(PN-getIncomingValueForBlock(OrigLatch), OrigHeader); -NH-addIncoming(NPH, NewPreHeader); +NH-addIncoming(NPV, OrigPreHeader); NewHeader-getInstList().push_front(NH); -// In can be replaced by NPH or NH at various places. -LoopHeaderInfo.push_back(RenameData(In, NPH, NH)); +// In can be replaced by NH at various places. +LoopHeaderInfo.push_back(RenameData(In, NPV, NH)); } // Now, handle non-phi instructions. @@
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopRotation.cpp updated: 1.6 - 1.7 --- Log message: Preserve canonical loop form. --- Diffs of the changes: (+55 -5) LoopRotation.cpp | 60 ++- 1 files changed, 55 insertions(+), 5 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.6 llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.7 --- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.6 Mon Apr 9 14:04:21 2007 +++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr 9 15:19:46 2007 @@ -75,6 +75,11 @@ /// not available. const RenameData *findReplacementData(Instruction *I); +/// After loop rotation, loop pre-header has multiple sucessors. +/// Insert one forwarding basic block to ensure that loop pre-header +/// has only one successor. +void preserveCanonicalLoopForm(LPPassManager LPM); + private: Loop *L; @@ -121,11 +126,8 @@ if (L-getBlocks().size() == 1) return false; - if (!OrigHeader || !OrigLatch || !OrigPreHeader) -return false; - - if (!OrigHeader || !OrigLatch || !OrigPreHeader) -return false; + assert (OrigHeader OrigLatch OrigPreHeader + Loop is not in cannocial form); // If loop header is not one of the loop exit block then // either this loop is already rotated or it is not @@ -344,6 +346,8 @@ // Make NewHeader as the new header for the loop. L-moveToHeader(NewHeader); + preserveCanonicalLoopForm(LPM); + NumRotated++; return true; } @@ -415,3 +419,49 @@ } return NULL; } + +/// After loop rotation, loop pre-header has multiple sucessors. +/// Insert one forwarding basic block to ensure that loop pre-header +/// has only one successor. +void LoopRotate::preserveCanonicalLoopForm(LPPassManager LPM) { + + // Right now original pre-header has two successors, new header and + // exit block. Insert new block between original pre-header and + // new header such that loop's new pre-header has only one successor. + BasicBlock *NewPreHeader = new BasicBlock(bb.nph, OrigHeader-getParent(), +OrigPreHeader); + LoopInfo LI = LPM.getAnalysisLoopInfo(); + if (Loop *PL = LI.getLoopFor(OrigPreHeader)) +PL-addBasicBlockToLoop(NewPreHeader, LI); + new BranchInst(NewHeader, NewPreHeader); + + BranchInst *OrigPH_BI = castBranchInst(OrigPreHeader-getTerminator()); + if (OrigPH_BI-getSuccessor(0) == NewHeader) +OrigPH_BI-setSuccessor(0, NewPreHeader); + else { +assert (OrigPH_BI-getSuccessor(1) == NewPreHeader +Unexpected original pre-header terminator); +OrigPH_BI-setSuccessor(1, NewPreHeader); + } + + for (BasicBlock::iterator I = NewHeader-begin(), E = NewHeader-end(); + I != E; ++I) { +Instruction *In = I; +PHINode *PN = dyn_castPHINode(In); +if (!PN) + break; + +int index = PN-getBasicBlockIndex(OrigPreHeader); +assert (index != -1 Expected incoming value from Original PreHeader); +PN-setIncomingBlock(index, NewPreHeader); +assert (PN-getBasicBlockIndex(OrigPreHeader) == -1 +Expected only one incoming value from Original PreHeader); + } + + 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); +} ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopRotation.cpp updated: 1.8 - 1.9 --- Log message: Check _all_ PHINodes. --- Diffs of the changes: (+1 -1) LoopRotation.cpp |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.8 llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.9 --- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.8 Mon Apr 9 16:40:43 2007 +++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr 9 17:20:10 2007 @@ -366,7 +366,7 @@ // There is already one incoming value from original pre-header block. if (PN-getBasicBlockIndex(OrigPreHeader) != -1) - return; + continue; const RenameData *ILoopHeaderInfo; Value *V = PN-getIncomingValueForBlock(OrigHeader); ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopRotation.cpp added (r1.1) --- Log message: Add loop rotation pass. --- Diffs of the changes: (+431 -0) LoopRotation.cpp | 431 +++ 1 files changed, 431 insertions(+) Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp diff -c /dev/null llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.1 *** /dev/null Fri Apr 6 20:20:36 2007 --- llvm/lib/Transforms/Scalar/LoopRotation.cpp Fri Apr 6 20:20:26 2007 *** *** 0 --- 1,431 + //===- LoopRotation.cpp - Loop Rotation Pass --===// + // + // 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 implements Loop Rotation Pass. + // + //===--===// + + #define DEBUG_TYPE loop-rotation + + #include llvm/Transforms/Scalar.h + #include llvm/Function.h + #include llvm/Instructions.h + #include llvm/Analysis/LoopInfo.h + #include llvm/Analysis/LoopPass.h + #include llvm/Transforms/Utils/Local.h + #include llvm/Support/CommandLine.h + #include llvm/Support/Debug.h + #include llvm/ADT/Statistic.h + #include llvm/ADT/SmallVector.h + #include map + + using namespace llvm; + + #define MAX_HEADER_SIZE 16 + + STATISTIC(NumRotated, Number of loops rotated); + namespace { + + cl::optunsigned + RotateThreshold(rotate-threshold, cl::init(200), cl::Hidden, + cl::desc(The cut-off point for loop rotating)); + + class VISIBILITY_HIDDEN InsnReplacementData { + public: + InsnReplacementData(Instruction *O, Instruction *P, Instruction *H) + : Original(O), PreHeader(P), Header(H) {} + public: + Instruction *Original; // Original instruction + Instruction *PreHeader; // New pre-header replacement + Instruction *Header; // New header replacement + }; + + class VISIBILITY_HIDDEN LoopRotate : public LoopPass { + + public: + bool runOnLoop(Loop *L, LPPassManager LPM); + virtual void getAnalysisUsage(AnalysisUsage AU) const { + AU.addRequiredID(LCSSAID); + AU.addPreservedID(LCSSAID); + //AU.addRequiredLoopInfo(); + //AU.addPreservedLoopInfo(); + } + + // Helper functions + + /// Do actual work + bool rotateLoop(Loop *L, LPPassManager LPM); + + /// Initialize local data + void initialize(); + + /// Make sure all Exit block PHINodes have required incoming values. + /// If incoming value is constant or defined outside the loop then + /// PHINode may not have an entry for new pre-header. + void updateExitBlock(); + + /// Return true if this instruction is used outside original header. + bool usedOutsideOriginalHeader(Instruction *In); + + /// Find Replacement information for instruction. Return NULL if it is + /// not available. + InsnReplacementData *findReplacementData(Instruction *I); + + private: + + Loop *L; + BasicBlock *OrigHeader; + BasicBlock *OrigPreHeader; + BasicBlock *OrigLatch; + BasicBlock *NewHeader; + BasicBlock *NewPreHeader; + BasicBlock *Exit; + + SmallVectorInsnReplacementData, MAX_HEADER_SIZE RD; + }; + + RegisterPassLoopRotate X (loop-rotate, Rotate Loops); + } + + LoopPass *llvm::createLoopRotatePass() { return new LoopRotate(); } + + bool LoopRotate::runOnLoop(Loop *Lp, LPPassManager LPM) { + + bool RotatedOneLoop = false; + initialize(); + + // One loop can be rotated multiple times. + while (rotateLoop(Lp,LPM)) { + RotatedOneLoop = true; + initialize(); + } + + return RotatedOneLoop; + } + + bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager LPM) { + + L = Lp; + if ( NumRotated = RotateThreshold) + return false; + + OrigHeader = L-getHeader(); + OrigPreHeader = L-getLoopPreheader(); + OrigLatch = L-getLoopLatch(); + + // If loop has only one block then there is not much to rotate. + if (L-getBlocks().size() = 1) + return false; + + if (!OrigHeader || !OrigLatch || !OrigPreHeader) + return false; + + // If loop header is not one of the loop exit block then + // either this loop is already rotated or it is not + // suitable for loop rotation transformations. + if (!L-isLoopExit(OrigHeader)) + return false; + + BranchInst *BI = dyn_castBranchInst(OrigHeader-getTerminator()); + if (!BI) + return false; + + std::vectorBasicBlock * ExitBlocks; + L-getExitBlocks(ExitBlocks); + if (ExitBlocks.size() 1) + return false; + + // Find new Loop header. NewHeader is a Header's one and only successor + // that is inside loop. Header's all other successors are out side the + // loop.