[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.47 - 1.48
---
Log message:
Correct a few comments.
---
Diffs of the changes: (+5 -5)
LoopUnroll.cpp | 10 +-
1 files changed, 5 insertions(+), 5 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.47
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.48
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.47 Fri May 11 15:53:41 2007
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Mon May 14 09:31:17 2007
@@ -168,7 +168,7 @@
LI-removeBlock(BB);
BB-eraseFromParent();
- // Inherit predecessors name if it exists...
+ // Inherit predecessor's name if it exists...
if (!OldName.empty() !OnlyPred-hasName())
OnlyPred-setName(OldName);
@@ -191,10 +191,10 @@
}
/// Unroll the given loop by UnrollCount, or by a heuristically-determined
-/// value if Count is zero. If Threshold is non-NULL, it points to
-/// a Threshold value to limit code size expansion. If the loop size would
-/// expand beyond the threshold value, unrolling is suppressed. The return
-/// value is false if no transformations are performed.
+/// value if Count is zero. If Threshold is not NoThreshold, it is a value
+/// to limit code size expansion. If the loop size would expand beyond the
+/// threshold value, unrolling is suppressed. The return value is true if
+/// any transformations are performed.
///
bool LoopUnroll::unrollLoop(Loop *L, unsigned Count, unsigned Threshold) {
assert(L-isLCSSAForm());
___
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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.46 - 1.47
---
Log message:
This patch extends the LoopUnroll pass to be able to unroll loops
with unknown trip counts. This is left off by default, and a
command-line option enables it. It also begins to separate loop
unrolling into a utility routine; eventually it might be made usable
from other passes.
It currently works by inserting conditional branches between each
unrolled iteration, unless it proves that the trip count is a
multiple of a constant integer 1, which it currently only does in
the rare case that the trip count expression is a Mul operator with
a ConstantInt operand. Eventually this information might be provided
by other sources, for example by a pass that peels/splits the loop
for this purpose.
---
Diffs of the changes: (+193 -58)
LoopUnroll.cpp | 251 +++--
1 files changed, 193 insertions(+), 58 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.46
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.47
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.46 Tue May 8 10:19:19 2007
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Fri May 11 15:53:41 2007
@@ -31,6 +31,7 @@
#include llvm/Support/Compiler.h
#include llvm/Support/CommandLine.h
#include llvm/Support/Debug.h
+#include llvm/Support/MathExtras.h
#include llvm/ADT/Statistic.h
#include llvm/ADT/STLExtras.h
#include llvm/ADT/SmallPtrSet.h
@@ -39,12 +40,19 @@
#include algorithm
using namespace llvm;
-STATISTIC(NumUnrolled, Number of loops completely unrolled);
+STATISTIC(NumCompletelyUnrolled, Number of loops completely unrolled);
+STATISTIC(NumUnrolled, Number of loops unrolled (completely or
otherwise));
namespace {
cl::optunsigned
- UnrollThreshold(unroll-threshold, cl::init(100), cl::Hidden,
- cl::desc(The cut-off point for loop unrolling));
+ UnrollThreshold
+(unroll-threshold, cl::init(100), cl::Hidden,
+ cl::desc(The cut-off point for automatic loop unrolling));
+
+ cl::optunsigned
+ UnrollCount
+(unroll-count, cl::init(0), cl::Hidden,
+ cl::desc(Use this unroll count for all loops, for testing purposes));
class VISIBILITY_HIDDEN LoopUnroll : public LoopPass {
LoopInfo *LI; // The current loop information
@@ -52,7 +60,13 @@
static char ID; // Pass ID, replacement for typeid
LoopUnroll() : LoopPass((intptr_t)ID) {}
+/// A magic value for use with the Threshold parameter to indicate
+/// that the loop unroll should be performed regardless of how much
+/// code expansion would result.
+static const unsigned NoThreshold = UINT_MAX;
+
bool runOnLoop(Loop *L, LPPassManager LPM);
+bool unrollLoop(Loop *L, unsigned Count, unsigned Threshold);
BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB);
/// This transformation requires natural loop information requires that
@@ -162,43 +176,137 @@
}
bool LoopUnroll::runOnLoop(Loop *L, LPPassManager LPM) {
- bool Changed = false;
LI = getAnalysisLoopInfo();
+ // Unroll the loop.
+ if (!unrollLoop(L, UnrollCount, UnrollThreshold))
+return false;
+
+ // Update the loop information for this loop.
+ // If we completely unrolled the loop, remove it from the parent.
+ if (L-getNumBackEdges() == 0)
+LPM.deleteLoopFromQueue(L);
+
+ return true;
+}
+
+/// Unroll the given loop by UnrollCount, or by a heuristically-determined
+/// value if Count is zero. If Threshold is non-NULL, it points to
+/// a Threshold value to limit code size expansion. If the loop size would
+/// expand beyond the threshold value, unrolling is suppressed. The return
+/// value is false if no transformations are performed.
+///
+bool LoopUnroll::unrollLoop(Loop *L, unsigned Count, unsigned Threshold) {
+ assert(L-isLCSSAForm());
+
BasicBlock *Header = L-getHeader();
BasicBlock *LatchBlock = L-getLoopLatch();
-
BranchInst *BI = dyn_castBranchInst(LatchBlock-getTerminator());
- if (BI == 0) return Changed; // Must end in a conditional branch
- ConstantInt *TripCountC = dyn_cast_or_nullConstantInt(L-getTripCount());
- if (!TripCountC) return Changed; // Must have constant trip count!
+ DOUT Loop Unroll: F[ Header-getParent()-getName()
+] Loop % Header-getName() \n;
- // Guard against huge trip counts. This also guards against assertions in
- // APInt from the use of getZExtValue, below.
- if (TripCountC-getValue().getActiveBits() 32)
-return Changed; // More than 2^32 iterations???
+ if (!BI || BI-isUnconditional()) {
+// The loop-rorate pass can be helpful to avoid this in many cases.
+DOUTCan't unroll; loop not terminated by a conditional branch.\n;
+return false;
+ }
- uint64_t TripCountFull = TripCountC-getZExtValue();
- if (TripCountFull == 0)
-return Changed; // Zero iteraitons?
+ // Determine the trip count and/or trip
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.44 - 1.45
---
Log message:
Correct the comment for ApproximateLoopSize to reflect what it actually does.
---
Diffs of the changes: (+1 -2)
LoopUnroll.cpp |3 +--
1 files changed, 1 insertion(+), 2 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.44
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.45
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.44 Sat May 5 13:49:57 2007
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Tue May 8 10:14:19 2007
@@ -72,8 +72,7 @@
LoopPass *llvm::createLoopUnrollPass() { return new LoopUnroll(); }
-/// ApproximateLoopSize - Approximate the size of the loop after it has been
-/// unrolled.
+/// ApproximateLoopSize - Approximate the size of the loop.
static unsigned ApproximateLoopSize(const Loop *L) {
unsigned Size = 0;
for (unsigned i = 0, e = L-getBlocks().size(); i != e; ++i) {
___
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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.45 - 1.46
---
Log message:
Fix various whitespace inconsistencies.
---
Diffs of the changes: (+10 -10)
LoopUnroll.cpp | 20 ++--
1 files changed, 10 insertions(+), 10 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.45
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.46
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.45 Tue May 8 10:14:19 2007
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Tue May 8 10:19:19 2007
@@ -50,10 +50,10 @@
LoopInfo *LI; // The current loop information
public:
static char ID; // Pass ID, replacement for typeid
-LoopUnroll() : LoopPass((intptr_t)ID) {}
+LoopUnroll() : LoopPass((intptr_t)ID) {}
bool runOnLoop(Loop *L, LPPassManager LPM);
-BasicBlock* FoldBlockIntoPredecessor(BasicBlock* BB);
+BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB);
/// This transformation requires natural loop information requires that
/// loop preheaders be inserted into the CFG...
@@ -114,7 +114,7 @@
// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it
// only has one predecessor, and that predecessor only has one successor.
// Returns the new combined block.
-BasicBlock* LoopUnroll::FoldBlockIntoPredecessor(BasicBlock* BB) {
+BasicBlock *LoopUnroll::FoldBlockIntoPredecessor(BasicBlock *BB) {
// Merge basic blocks into their predecessor if there is only one distinct
// pred, and if there is only one distinct successor of the predecessor, and
// if there are no PHI nodes.
@@ -165,8 +165,8 @@
bool Changed = false;
LI = getAnalysisLoopInfo();
- BasicBlock* Header = L-getHeader();
- BasicBlock* LatchBlock = L-getLoopLatch();
+ BasicBlock *Header = L-getHeader();
+ BasicBlock *LatchBlock = L-getLoopLatch();
BranchInst *BI = dyn_castBranchInst(LatchBlock-getTerminator());
if (BI == 0) return Changed; // Must end in a conditional branch
@@ -262,10 +262,10 @@
if (*BB != LatchBlock)
for (Value::use_iterator UI = (*BB)-use_begin(), UE =
(*BB)-use_end();
UI != UE; ++UI) {
- Instruction* UseInst = castInstruction(*UI);
+ Instruction *UseInst = castInstruction(*UI);
if (isaPHINode(UseInst) !L-contains(UseInst-getParent())) {
-PHINode* phi = castPHINode(UseInst);
-Value* Incoming = phi-getIncomingValueForBlock(*BB);
+PHINode *phi = castPHINode(UseInst);
+Value *Incoming = phi-getIncomingValueForBlock(*BB);
if (isaInstruction(Incoming))
Incoming = LastValueMap[Incoming];
@@ -298,7 +298,7 @@
SmallPtrSetPHINode*, 8 Users;
for (Value::use_iterator UI = LatchBlock-use_begin(),
UE = LatchBlock-use_end(); UI != UE; ++UI)
- if (PHINode* phi = dyn_castPHINode(*UI))
+ if (PHINode *phi = dyn_castPHINode(*UI))
Users.insert(phi);
BasicBlock *LastIterationBB = castBasicBlock(LastValueMap[LatchBlock]);
@@ -328,7 +328,7 @@
// Insert the branches that link the different iterations together
for (unsigned i = 0; i Latches.size()-1; ++i) {
new BranchInst(Headers[i+1], Latches[i]);
-if(BasicBlock* Fold = FoldBlockIntoPredecessor(Headers[i+1])) {
+if (BasicBlock *Fold = FoldBlockIntoPredecessor(Headers[i+1])) {
std::replace(Latches.begin(), Latches.end(), Headers[i+1], Fold);
std::replace(Headers.begin(), Headers.end(), Headers[i+1], Fold);
}
___
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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.42 - 1.43
---
Log message:
make a temporary for *SI, no functionality change.
---
Diffs of the changes: (+7 -6)
LoopUnroll.cpp | 13 +++--
1 files changed, 7 insertions(+), 6 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.42
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.43
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.42 Wed May 2 20:11:54 2007
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Sat May 5 13:36:36 2007
@@ -302,17 +302,18 @@
for (SmallPtrSetPHINode*,8::iterator SI = Users.begin(), SE =
Users.end();
SI != SE; ++SI) {
- Value* InVal = (*SI)-getIncomingValueForBlock(LatchBlock);
+ PHINode *PN = *SI;
+ Value* InVal = PN-getIncomingValueForBlock(LatchBlock);
if (isaInstruction(InVal))
InVal = LastValueMap[InVal];
- (*SI)-removeIncomingValue(LatchBlock, false);
+ PN-removeIncomingValue(LatchBlock, false);
if (InVal)
-(*SI)-addIncoming(InVal, castBasicBlock(LastValueMap[LatchBlock]));
- if ((*SI)-getNumIncomingValues() == 0) {
+PN-addIncoming(InVal, castBasicBlock(LastValueMap[LatchBlock]));
+ if (PN-getNumIncomingValues() == 0) {
// Remove this phi node.
// If anyone is using this PHI, make them use a dummy value instead...
-(*SI)-replaceAllUsesWith(UndefValue::get((*SI)-getType()));
-(*SI)-eraseFromParent();
+PN-replaceAllUsesWith(UndefValue::get(PN-getType()));
+PN-eraseFromParent();
}
}
}
___
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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.43 - 1.44
---
Log message:
Fix Transforms/LoopUnroll/2007-05-05-UnrollMiscomp.ll and PR1385:
http://llvm.org/PR1385 .
If we have a LCSSA, only modify the input value if the inval was defined
by an instruction in the loop. If defined by something before the loop,
it is still valid.
---
Diffs of the changes: (+17 -18)
LoopUnroll.cpp | 35 +--
1 files changed, 17 insertions(+), 18 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.43
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.44
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.43 Sat May 5 13:36:36 2007
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Sat May 5 13:49:57 2007
@@ -203,7 +203,8 @@
// For the first iteration of the loop, we should use the precloned values
for
// PHI nodes. Insert associations now.
- DenseMapconst Value*, Value* LastValueMap;
+ typedef DenseMapconst Value*, Value* ValueMapTy;
+ ValueMapTy LastValueMap;
std::vectorPHINode* OrigPHINode;
for (BasicBlock::iterator I = Header-begin(); isaPHINode(I); ++I) {
PHINode *PN = castPHINode(I);
@@ -231,7 +232,7 @@
for (std::vectorBasicBlock*::iterator BB = LoopBlocks.begin(),
E = LoopBlocks.end(); BB != E; ++BB) {
- DenseMapconst Value*, Value* ValueMap;
+ ValueMapTy ValueMap;
BasicBlock *New = CloneBasicBlock(*BB, ValueMap, SuffixBuffer);
Header-getParent()-getBasicBlockList().push_back(New);
@@ -250,8 +251,8 @@
// Update our running map of newest clones
LastValueMap[*BB] = New;
- for (DenseMapconst Value*, Value*::iterator VI = ValueMap.begin(),
- VE = ValueMap.end(); VI != VE; ++VI)
+ for (ValueMapTy::iterator VI = ValueMap.begin(), VE = ValueMap.end();
+ VI != VE; ++VI)
LastValueMap[VI-first] = VI-second;
L-addBasicBlockToLoop(New, *LI);
@@ -291,30 +292,28 @@
}
-
- // Update PHI nodes that reference the final latch block
+ // The latch block exits the loop. If there are any PHI nodes in the
+ // successor blocks, update them to use the appropriate values computed as
the
+ // last iteration of the loop.
if (TripCount 1) {
SmallPtrSetPHINode*, 8 Users;
for (Value::use_iterator UI = LatchBlock-use_begin(),
UE = LatchBlock-use_end(); UI != UE; ++UI)
if (PHINode* phi = dyn_castPHINode(*UI))
Users.insert(phi);
-
+
+BasicBlock *LastIterationBB = castBasicBlock(LastValueMap[LatchBlock]);
for (SmallPtrSetPHINode*,8::iterator SI = Users.begin(), SE =
Users.end();
SI != SE; ++SI) {
PHINode *PN = *SI;
- Value* InVal = PN-getIncomingValueForBlock(LatchBlock);
- if (isaInstruction(InVal))
-InVal = LastValueMap[InVal];
- PN-removeIncomingValue(LatchBlock, false);
- if (InVal)
-PN-addIncoming(InVal, castBasicBlock(LastValueMap[LatchBlock]));
- if (PN-getNumIncomingValues() == 0) {
-// Remove this phi node.
-// If anyone is using this PHI, make them use a dummy value instead...
-PN-replaceAllUsesWith(UndefValue::get(PN-getType()));
-PN-eraseFromParent();
+ Value *InVal = PN-removeIncomingValue(LatchBlock, false);
+ // If this value was defined in the loop, take the value defined by the
+ // last iteration of the loop.
+ if (Instruction *InValI = dyn_castInstruction(InVal)) {
+if (L-contains(InValI-getParent()))
+ InVal = LastValueMap[InVal];
}
+ PN-addIncoming(InVal, LastIterationBB);
}
}
___
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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.38 - 1.39
---
Log message:
Fix
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070416/047888.html
---
Diffs of the changes: (+6 -0)
LoopUnroll.cpp |6 ++
1 files changed, 6 insertions(+)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.38
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.39
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.38 Tue Mar 6 19:38:05 2007
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Mon Apr 16 18:03:45 2007
@@ -304,6 +304,12 @@
(*SI)-removeIncomingValue(LatchBlock, false);
if (InVal)
(*SI)-addIncoming(InVal, castBasicBlock(LastValueMap[LatchBlock]));
+ if ((*SI)-getNumIncomingValues() == 0) {
+// Remove this phi node.
+// If anyone is using this PHI, make them use a dummy value instead...
+(*SI)-replaceAllUsesWith(UndefValue::get((*SI)-getType()));
+(*SI)-eraseFromParent();
+ }
}
}
___
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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.37 - 1.38
---
Log message:
Now LoopUnroll is a LoopPass.
---
Diffs of the changes: (+7 -36)
LoopUnroll.cpp | 43 +++
1 files changed, 7 insertions(+), 36 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.37
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.38
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.37 Fri Mar 2 17:31:34 2007
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Tue Mar 6 19:38:05 2007
@@ -24,6 +24,7 @@
#include llvm/Instructions.h
#include llvm/Analysis/ConstantFolding.h
#include llvm/Analysis/LoopInfo.h
+#include llvm/Analysis/LoopPass.h
#include llvm/Transforms/Utils/Cloning.h
#include llvm/Transforms/Utils/Local.h
#include llvm/Support/CFG.h
@@ -45,11 +46,10 @@
UnrollThreshold(unroll-threshold, cl::init(100), cl::Hidden,
cl::desc(The cut-off point for loop unrolling));
- class VISIBILITY_HIDDEN LoopUnroll : public FunctionPass {
+ class VISIBILITY_HIDDEN LoopUnroll : public LoopPass {
LoopInfo *LI; // The current loop information
public:
-virtual bool runOnFunction(Function F);
-bool visitLoop(Loop *L);
+bool runOnLoop(Loop *L, LPPassManager LPM);
BasicBlock* FoldBlockIntoPredecessor(BasicBlock* BB);
/// This transformation requires natural loop information requires that
@@ -66,20 +66,7 @@
RegisterPassLoopUnroll X(loop-unroll, Unroll loops);
}
-FunctionPass *llvm::createLoopUnrollPass() { return new LoopUnroll(); }
-
-bool LoopUnroll::runOnFunction(Function F) {
- bool Changed = false;
- LI = getAnalysisLoopInfo();
-
- // Transform all the top-level loops. Copy the loop list so that the child
- // can update the loop tree if it needs to delete the loop.
- std::vectorLoop* SubLoops(LI-begin(), LI-end());
- for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
-Changed |= visitLoop(SubLoops[i]);
-
- return Changed;
-}
+LoopPass *llvm::createLoopUnrollPass() { return new LoopUnroll(); }
/// ApproximateLoopSize - Approximate the size of the loop after it has been
/// unrolled.
@@ -171,15 +158,9 @@
return OnlyPred;
}
-bool LoopUnroll::visitLoop(Loop *L) {
+bool LoopUnroll::runOnLoop(Loop *L, LPPassManager LPM) {
bool Changed = false;
-
- // Recurse through all subloops before we process this loop. Copy the loop
- // list so that the child can update the loop tree if it needs to delete the
- // loop.
- std::vectorLoop* SubLoops(L-begin(), L-end());
- for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
-Changed |= visitLoop(SubLoops[i]);
+ LI = getAnalysisLoopInfo();
BasicBlock* Header = L-getHeader();
BasicBlock* LatchBlock = L-getLoopLatch();
@@ -367,18 +348,8 @@
}
// Update the loop information for this loop.
- Loop *Parent = L-getParentLoop();
-
- // Move all of the basic blocks in the loop into the parent loop.
- for (std::vectorBasicBlock*::const_iterator BB = NewLoopBlocks.begin(),
- E = NewLoopBlocks.end(); BB != E; ++BB)
-LI-changeLoopFor(*BB, Parent);
-
// Remove the loop from the parent.
- if (Parent)
-delete Parent-removeChildLoop(std::find(Parent-begin(),
Parent-end(),L));
- else
-delete LI-removeLoop(std::find(LI-begin(), LI-end(), L));
+ LPM.deleteLoopFromQueue(L);
++NumUnrolled;
return true;
___
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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopUnroll.cpp updated: 1.36 - 1.37 --- Log message: Guard against huge loop trip counts in an APInt safe way. --- Diffs of the changes: (+7 -2) LoopUnroll.cpp |9 +++-- 1 files changed, 7 insertions(+), 2 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.36 llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.37 --- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.36 Mon Feb 5 17:32:05 2007 +++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Fri Mar 2 17:31:34 2007 @@ -190,10 +190,15 @@ ConstantInt *TripCountC = dyn_cast_or_nullConstantInt(L-getTripCount()); if (!TripCountC) return Changed; // Must have constant trip count! - uint64_t TripCountFull = TripCountC-getZExtValue(); - if (TripCountFull != TripCountC-getZExtValue() || TripCountFull == 0) + // Guard against huge trip counts. This also guards against assertions in + // APInt from the use of getZExtValue, below. + if (TripCountC-getValue().getActiveBits() 32) return Changed; // More than 2^32 iterations??? + uint64_t TripCountFull = TripCountC-getZExtValue(); + if (TripCountFull == 0) +return Changed; // Zero iteraitons? + unsigned LoopSize = ApproximateLoopSize(L); DOUT Loop Unroll: F[ Header-getParent()-getName() ] Loop % Header-getName() Loop Size = ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
On Mar 2, 2007, at 3:31 PM, Reid Spencer wrote: + // Guard against huge trip counts. This also guards against assertions in + // APInt from the use of getZExtValue, below. + if (TripCountC-getValue().getActiveBits() 32) return Changed; // More than 2^32 iterations??? + uint64_t TripCountFull = TripCountC-getZExtValue(); + if (TripCountFull == 0) +return Changed; // Zero iteraitons? + Won't this still assert on 'i128 16' ? -Chris ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
On Fri, 2007-03-02 at 15:35 -0800, Chris Lattner wrote: On Mar 2, 2007, at 3:31 PM, Reid Spencer wrote: + // Guard against huge trip counts. This also guards against assertions in + // APInt from the use of getZExtValue, below. + if (TripCountC-getValue().getActiveBits() 32) return Changed; // More than 2^32 iterations??? + uint64_t TripCountFull = TripCountC-getZExtValue(); + if (TripCountFull == 0) +return Changed; // Zero iteraitons? + Won't this still assert on 'i128 16' ? No. getZExtValue() doesn't look at the bit width, it looks at the precision of the value. Regardless of the bit width, if the value fits in 64 bits, it allows it. If not, it asserts. Which is why I check getActiveBits() 32 to limit trip counts to 2^32. This makes the getZExtValue() safe. That precision check is another reason why I'm changing things like: if (CI-getZExtValue() == 1) into if (CI-isOne()) because its cheaper :) Reid. -Chris ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
On Mar 2, 2007, at 3:40 PM, Reid Spencer wrote: On Fri, 2007-03-02 at 15:35 -0800, Chris Lattner wrote: On Mar 2, 2007, at 3:31 PM, Reid Spencer wrote: + // Guard against huge trip counts. This also guards against assertions in + // APInt from the use of getZExtValue, below. + if (TripCountC-getValue().getActiveBits() 32) return Changed; // More than 2^32 iterations??? + uint64_t TripCountFull = TripCountC-getZExtValue(); + if (TripCountFull == 0) +return Changed; // Zero iteraitons? + Won't this still assert on 'i128 16' ? No. getZExtValue() doesn't look at the bit width, it looks at the precision of the value. Regardless of the bit width, if the value fits in 64 bits, it allows it. If not, it asserts. Which is why I check getActiveBits() 32 to limit trip counts to 2^32. This makes the getZExtValue() safe. Ok, nifty. That precision check is another reason why I'm changing things like: if (CI-getZExtValue() == 1) into if (CI-isOne()) because its cheaper :) Woot! -Chris ___ 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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.26 - 1.27
---
Log message:
Make LoopUnroll fold excessive BasicBlocks. This results in a significant
speedup of
gccas on 252.eon
---
Diffs of the changes: (+89 -9)
LoopUnroll.cpp | 98 +++--
1 files changed, 89 insertions(+), 9 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.26
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.27
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.26 Sun Aug 27 17:42:52 2006
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Sun Aug 27 21:09:46 2006
@@ -25,6 +25,7 @@
#include llvm/Analysis/LoopInfo.h
#include llvm/Transforms/Utils/Cloning.h
#include llvm/Transforms/Utils/Local.h
+#include llvm/Support/CFG.h
#include llvm/Support/CommandLine.h
#include llvm/Support/Debug.h
#include llvm/ADT/Statistic.h
@@ -48,6 +49,7 @@
public:
virtual bool runOnFunction(Function F);
bool visitLoop(Loop *L);
+BasicBlock* FoldBlockIntoPredecessor(BasicBlock* BB);
/// This transformation requires natural loop information requires that
/// loop preheaders be inserted into the CFG...
@@ -118,6 +120,76 @@
}
}
+// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it
+// only has one predecessor, and that predecessor only has one successor.
+// Returns the new combined block.
+BasicBlock* LoopUnroll::FoldBlockIntoPredecessor(BasicBlock* BB) {
+ // Merge basic blocks into their predecessor if there is only one distinct
+ // pred, and if there is only one distinct successor of the predecessor, and
+ // if there are no PHI nodes.
+ //
+ pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
+ BasicBlock *OnlyPred = *PI++;
+ for (; PI != PE; ++PI) // Search all predecessors, see if they are all same
+if (*PI != OnlyPred) {
+ OnlyPred = 0; // There are multiple different predecessors...
+ break;
+}
+
+ BasicBlock *OnlySucc = 0;
+ if (OnlyPred OnlyPred != BB // Don't break self loops
+ OnlyPred-getTerminator()-getOpcode() != Instruction::Invoke) {
+// Check to see if there is only one distinct successor...
+succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred));
+OnlySucc = BB;
+for (; SI != SE; ++SI)
+ if (*SI != OnlySucc) {
+OnlySucc = 0; // There are multiple distinct successors!
+break;
+ }
+ }
+
+ if (OnlySucc) {
+DEBUG(std::cerr Merging: *BB into: *OnlyPred);
+TerminatorInst *Term = OnlyPred-getTerminator();
+
+// Resolve any PHI nodes at the start of the block. They are all
+// guaranteed to have exactly one entry if they exist, unless there are
+// multiple duplicate (but guaranteed to be equal) entries for the
+// incoming edges. This occurs when there are multiple edges from
+// OnlyPred to OnlySucc.
+//
+while (PHINode *PN = dyn_castPHINode(BB-front())) {
+ PN-replaceAllUsesWith(PN-getIncomingValue(0));
+ BB-getInstList().pop_front(); // Delete the phi node...
+}
+
+// Delete the unconditional branch from the predecessor...
+OnlyPred-getInstList().pop_back();
+
+// Move all definitions in the successor to the predecessor...
+OnlyPred-getInstList().splice(OnlyPred-end(), BB-getInstList());
+
+// Make all PHI nodes that referred to BB now refer to Pred as their
+// source...
+BB-replaceAllUsesWith(OnlyPred);
+
+std::string OldName = BB-getName();
+
+// Erase basic block from the function...
+LI-removeBlock(BB);
+BB-eraseFromParent();
+
+// Inherit predecessors name if it exists...
+if (!OldName.empty() !OnlyPred-hasName())
+ OnlyPred-setName(OldName);
+
+return OnlyPred;
+ }
+
+ return 0;
+}
+
bool LoopUnroll::visitLoop(Loop *L) {
bool Changed = false;
@@ -247,13 +319,7 @@
RemapInstruction(I, LastValueMap);
}
- // Insert the branches that link the different iterations together
- for (unsigned i = 0; i Latches.size()-1; ++i)
-new BranchInst(Headers[i+1], Latches[i]);
- // Finally, add an unconditional branch to the block to continue into the
exit
- // block.
- new BranchInst(LoopExit, Latches[Latches.size()-1]);
// Update PHI nodes that reference the final latch block
if (TripCount 1) {
@@ -281,14 +347,28 @@
PHINode *PN = OrigPHINode[i];
PN-replaceAllUsesWith(PN-getIncomingValueForBlock(Preheader));
Header-getInstList().erase(PN);
- }
-
+ }
+
+ // Insert the branches that link the different iterations together
+ for (unsigned i = 0; i Latches.size()-1; ++i) {
+new BranchInst(Headers[i+1], Latches[i]);
+if(BasicBlock* Fold = FoldBlockIntoPredecessor(Headers[i+1])) {
+ std::replace(Latches.begin(), Latches.end(), Headers[i+1], Fold);
+ std::replace(Headers.begin(), Headers.end(), Headers[i+1], Fold);
+}
+ }
+
+ // Finally,
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopUnroll.cpp updated: 1.24 - 1.25 --- Log message: Fix a crash related to updating Phi nodes in the original header block. This was causing a crash in 175.vpr --- Diffs of the changes: (+2 -1) LoopUnroll.cpp |3 ++- 1 files changed, 2 insertions(+), 1 deletion(-) Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.24 llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.25 --- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.24 Thu Aug 24 16:28:19 2006 +++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Fri Aug 25 17:13:55 2006 @@ -269,7 +269,8 @@ if (isaInstruction(InVal)) InVal = LastValueMap[InVal]; (*SI)-removeIncomingValue(LatchBlock, false); - (*SI)-addIncoming(InVal, castBasicBlock(LastValueMap[LatchBlock])); + if (InVal) +(*SI)-addIncoming(InVal, castBasicBlock(LastValueMap[LatchBlock])); } } ___ 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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.20 - 1.21
---
Log message:
Make LoopUnroll not die on LCSSA Phis. This makes lencod work again.
---
Diffs of the changes: (+6 -0)
LoopUnroll.cpp |6 ++
1 files changed, 6 insertions(+)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.20
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.21
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.20 Wed Jun 7 16:24:10 2006
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Wed Jul 19 00:45:14 2006
@@ -269,6 +269,12 @@
// FIXME: Should update dominator analyses
+ // Remove LCSSA Phis from the exit block
+ for (BasicBlock::iterator ExitInstr = LoopExit-begin();
+ PHINode* PN = dyn_castPHINode(ExitInstr); ++ExitInstr) {
+PN-replaceAllUsesWith(PN-getOperand(0));
+PN-eraseFromParent();
+ }
// Now that everything is up-to-date that will be, we fold the loop block
into
// the preheader and exit block, updating our analyses as we go.
___
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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.21 - 1.22
---
Log message:
Add an assertion.
---
Diffs of the changes: (+2 -0)
LoopUnroll.cpp |2 ++
1 files changed, 2 insertions(+)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.21
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.22
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.21 Wed Jul 19 00:45:14 2006
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Wed Jul 19 00:48:45 2006
@@ -272,6 +272,8 @@
// Remove LCSSA Phis from the exit block
for (BasicBlock::iterator ExitInstr = LoopExit-begin();
PHINode* PN = dyn_castPHINode(ExitInstr); ++ExitInstr) {
+assert(PN-getNumIncomingValues() == 1
+Block should only have one pred, so Phi's must be LCSSA);
PN-replaceAllUsesWith(PN-getOperand(0));
PN-eraseFromParent();
}
___
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/LoopUnroll.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopUnroll.cpp updated: 1.19 - 1.20
---
Log message:
Fix a spello in a comment.
---
Diffs of the changes: (+1 -1)
LoopUnroll.cpp |2 +-
1 files changed, 1 insertion(+), 1 deletion(-)
Index: llvm/lib/Transforms/Scalar/LoopUnroll.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.19
llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.20
--- llvm/lib/Transforms/Scalar/LoopUnroll.cpp:1.19 Sun Jan 22 17:32:06 2006
+++ llvm/lib/Transforms/Scalar/LoopUnroll.cpp Wed Jun 7 16:24:10 2006
@@ -213,7 +213,7 @@
// We don't want to reprocess entries with PHI nodes in them. For this
// reason, we look at each operand of each user exactly once, performing
the
-// stubstitution exactly once.
+// substitution exactly once.
for (std::setUser*::iterator UI = Users.begin(), E = Users.end(); UI !=
E;
++UI) {
Instruction *I = castInstruction(*UI);
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
