[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.
