[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.139 - 1.140
---
Log message:
Use DominatorTree instead of ETForest.
---
Diffs of the changes: (+7 -8)
LoopStrengthReduce.cpp | 15 +++
1 files changed, 7 insertions(+), 8 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.139
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.140
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.139 Tue Jun 5
20:23:55 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Thu Jun 7 16:42:15 2007
@@ -111,7 +111,7 @@
class VISIBILITY_HIDDEN LoopStrengthReduce : public LoopPass {
LoopInfo *LI;
-ETForest *EF;
+DominatorTree *DT;
ScalarEvolution *SE;
const TargetData *TD;
const Type *UIntPtrTy;
@@ -156,13 +156,12 @@
// many analyses if they are around.
AU.addPreservedID(LoopSimplifyID);
AU.addPreservedLoopInfo();
- AU.addPreservedETForest();
AU.addPreservedDominanceFrontier();
AU.addPreservedDominatorTree();
AU.addRequiredID(LoopSimplifyID);
AU.addRequiredLoopInfo();
- AU.addRequiredETForest();
+ AU.addRequiredDominatorTree();
AU.addRequiredTargetData();
AU.addRequiredScalarEvolution();
}
@@ -353,7 +352,7 @@
/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
/// should use the post-inc value).
static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
- Loop *L, ETForest *EF, Pass *P) {
+ Loop *L, DominatorTree *DT, Pass *P) {
// If the user is in the loop, use the preinc value.
if (L-contains(User-getParent())) return false;
@@ -361,7 +360,7 @@
// Ok, the user is outside of the loop. If it is dominated by the latch
// block, use the post-inc value.
- if (EF-dominates(LatchBlock, User-getParent()))
+ if (DT-dominates(LatchBlock, User-getParent()))
return true;
// There is one case we have to be careful of: PHI nodes. These little guys
@@ -378,7 +377,7 @@
for (unsigned i = 0, e = PN-getNumIncomingValues(); i != e; ++i)
if (PN-getIncomingValue(i) == IV) {
++NumUses;
- if (!EF-dominates(LatchBlock, PN-getIncomingBlock(i)))
+ if (!DT-dominates(LatchBlock, PN-getIncomingBlock(i)))
return false;
}
@@ -456,7 +455,7 @@
// Okay, we found a user that we cannot reduce. Analyze the instruction
// and decide what to do with it. If we are a use inside of the loop,
use
// the value before incrementation, otherwise use it after
incrementation.
- if (IVUseShouldUsePostIncValue(User, I, L, EF, this)) {
+ if (IVUseShouldUsePostIncValue(User, I, L, DT, this)) {
// The value used will be incremented by the stride more than we are
// expecting, so subtract this off.
SCEVHandle NewStart = SCEV::getMinusSCEV(Start, Stride);
@@ -1400,7 +1399,7 @@
bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager LPM) {
LI = getAnalysisLoopInfo();
- EF = getAnalysisETForest();
+ DT = getAnalysisDominatorTree();
SE = getAnalysisScalarEvolution();
TD = getAnalysisTargetData();
UIntPtrTy = TD-getIntPtrType();
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopStrengthReduce.cpp updated: 1.138 - 1.139 --- Log message: Fix PR1495: http://llvm.org/PR1495 and CodeGen/X86/2007-06-05-LSR-Dominator.ll --- Diffs of the changes: (+6 -0) LoopStrengthReduce.cpp |6 ++ 1 files changed, 6 insertions(+) Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.138 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.139 --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.138 Fri May 18 20:22:21 2007 +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Tue Jun 5 20:23:55 2007 @@ -560,11 +560,17 @@ OperandValToReplace-getType()); Value *Base = Rewriter.expandCodeFor(NewBase, BaseInsertPt); + + // If we are inserting the base and imm values in the same block, make sure to + // adjust the IP position if insertion reused a result. + if (IP == BaseInsertPt) +IP = Rewriter.getInsertionPoint(); // Always emit the immediate (if non-zero) into the same block as the user. SCEVHandle NewValSCEV = SCEVAddExpr::get(SCEVUnknown::get(Base), Imm); return Rewriter.expandCodeFor(NewValSCEV, IP, OperandValToReplace-getType()); + } ___ 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.137 - 1.138
---
Log message:
Handle negative strides much more optimally. This compiles
X86/lsr-negative-stride.ll
into:
_t:
movl 8(%esp), %ecx
movl 4(%esp), %eax
cmpl %ecx, %eax
je LBB1_3 #bb17
LBB1_1: #bb
cmpl %ecx, %eax
jg LBB1_4 #cond_true
LBB1_2: #cond_false
subl %eax, %ecx
cmpl %ecx, %eax
jne LBB1_1 #bb
LBB1_3: #bb17
ret
LBB1_4: #cond_true
subl %ecx, %eax
cmpl %ecx, %eax
jne LBB1_1 #bb
jmp LBB1_3 #bb17
instead of:
_t:
subl $4, %esp
movl %esi, (%esp)
movl 12(%esp), %ecx
movl 8(%esp), %eax
cmpl %ecx, %eax
je LBB1_4 #bb17
LBB1_1: #bb.outer
movl %ecx, %edx
negl %edx
LBB1_2: #bb
cmpl %ecx, %eax
jle LBB1_5 #cond_false
LBB1_3: #cond_true
addl %edx, %eax
cmpl %ecx, %eax
jne LBB1_2 #bb
LBB1_4: #bb17
movl (%esp), %esi
addl $4, %esp
ret
LBB1_5: #cond_false
movl %ecx, %edx
subl %eax, %edx
movl %eax, %esi
addl %esi, %esi
cmpl %ecx, %esi
je LBB1_4 #bb17
LBB1_6: #cond_false.bb.outer_crit_edge
movl %edx, %ecx
jmp LBB1_1 #bb.outer
---
Diffs of the changes: (+26 -3)
LoopStrengthReduce.cpp | 29 ++---
1 files changed, 26 insertions(+), 3 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.137
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.138
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.137 Fri May 11
17:40:34 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri May 18 20:22:21 2007
@@ -987,6 +987,20 @@
return Val.isUseOfPostIncrementedValue;
}
+/// isNonConstantNegative - REturn true if the specified scev is negated, but
+/// not a constant.
+static bool isNonConstantNegative(const SCEVHandle Expr) {
+ SCEVMulExpr *Mul = dyn_castSCEVMulExpr(Expr);
+ if (!Mul) return false;
+
+ // If there is a constant factor, it will be first.
+ SCEVConstant *SC = dyn_castSCEVConstant(Mul-getOperand(0));
+ if (!SC) return false;
+
+ // Return true if the value is negative, this matches things like (-42 * V).
+ return SC-getValue()-getValue().isNegative();
+}
+
/// StrengthReduceStridedIVUsers - Strength reduce all of the users of a single
/// stride of IV. All of the users may have different starting values, and
this
/// may not be the only stride (we know it is if isOnlyStride is true).
@@ -1104,15 +1118,24 @@
// Add common base to the new Phi node.
NewPHI-addIncoming(CommonBaseV, Preheader);
+// If the stride is negative, insert a sub instead of an add for the
+// increment.
+bool isNegative = isNonConstantNegative(Stride);
+SCEVHandle IncAmount = Stride;
+if (isNegative)
+ IncAmount = SCEV::getNegativeSCEV(Stride);
+
// Insert the stride into the preheader.
-Value *StrideV = PreheaderRewriter.expandCodeFor(Stride, PreInsertPt,
+Value *StrideV = PreheaderRewriter.expandCodeFor(IncAmount, PreInsertPt,
ReplacedTy);
if (!isaConstantInt(StrideV)) ++NumVariable;
// Emit the increment of the base value before the terminator of the loop
// latch block, and add it to the Phi node.
-SCEVHandle IncExp = SCEVAddExpr::get(SCEVUnknown::get(NewPHI),
- SCEVUnknown::get(StrideV));
+SCEVHandle IncExp = SCEVUnknown::get(StrideV);
+if (isNegative)
+ IncExp = SCEV::getNegativeSCEV(IncExp);
+IncExp = SCEVAddExpr::get(SCEVUnknown::get(NewPHI), IncExp);
IncV = Rewriter.expandCodeFor(IncExp, LatchBlock-getTerminator(),
ReplacedTy);
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.136 - 1.137
---
Log message:
significantly improve debug output of lsr
---
Diffs of the changes: (+13 -6)
LoopStrengthReduce.cpp | 19 +--
1 files changed, 13 insertions(+), 6 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.136
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.137
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.136 Fri May 4
09:59:09 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri May 11 17:40:34 2007
@@ -592,11 +592,12 @@
while (isaPHINode(InsertPt)) ++InsertPt;
}
}
-
Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt,
L);
// Replace the use of the operand Value with the new Phi we just created.
Inst-replaceUsesOfWith(OperandValToReplace, NewVal);
-DOUT CHANGED: IMM = *ImmInst = *Inst;
+DOUT CHANGED: IMM = *Imm;
+DOUT\tNEWBASE = *NewBase;
+DOUT\tInst = *Inst;
return;
}
@@ -1078,7 +1079,7 @@
// Now that we know what we need to do, insert the PHI node itself.
//
DOUT INSERTING IV of TYPE *ReplacedTy of STRIDE
-*Stride and BASE *CommonExprs :\n;
+*Stride and BASE *CommonExprs : ;
SCEVExpander Rewriter(*SE, *LI);
SCEVExpander PreheaderRewriter(*SE, *LI);
@@ -1120,6 +1121,8 @@
// Remember this in case a later stride is multiple of this.
IVsByStride[Stride].addIV(Stride, CommonExprs, NewPHI, IncV);
+
+DOUT IV=% NewPHI-getNameStr() INC=% IncV-getNameStr();
} else {
Constant *C = dyn_castConstant(CommonBaseV);
if (!C ||
@@ -1130,6 +1133,7 @@
CommonBaseV = new BitCastInst(CommonBaseV, CommonBaseV-getType(),
commonbase, PreInsertPt);
}
+ DOUT \n;
// We want to emit code for users inside the loop first. To do this, we
// rearrange BasedUser so that the entries at the end have
@@ -1166,12 +1170,15 @@
while (!UsersToProcess.empty()) {
SCEVHandle Base = UsersToProcess.back().Base;
-DOUTINSERTING code for BASE = *Base :\n;
-
// Emit the code for Base into the preheader.
Value *BaseV = PreheaderRewriter.expandCodeFor(Base, PreInsertPt,
ReplacedTy);
-
+
+DOUTINSERTING code for BASE = *Base :;
+if (BaseV-hasName())
+ DOUT Result value name = % BaseV-getNameStr();
+DOUT \n;
+
// If BaseV is a constant other than 0, make sure that it gets inserted
into
// the preheader, instead of being forward substituted into the uses. We
do
// this by forcing a BitCast (noop cast) to be inserted into the preheader
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.135 - 1.136
---
Log message:
Use IntrinsicInst to test for prefetch instructions, which is ever so
slightly nicer than using CallInst with an extra check; thanks Chris.
---
Diffs of the changes: (+5 -6)
LoopStrengthReduce.cpp | 11 +--
1 files changed, 5 insertions(+), 6 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.135
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.136
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.135 Thu May 3
18:20:33 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri May 4 09:59:09 2007
@@ -19,7 +19,7 @@
#include llvm/Transforms/Scalar.h
#include llvm/Constants.h
#include llvm/Instructions.h
-#include llvm/Intrinsics.h
+#include llvm/IntrinsicInst.h
#include llvm/Type.h
#include llvm/DerivedTypes.h
#include llvm/Analysis/Dominators.h
@@ -1043,12 +1043,11 @@
if (StoreInst *SI = dyn_castStoreInst(UsersToProcess[i].Inst)) {
if (SI-getOperand(1) == UsersToProcess[i].OperandValToReplace)
isAddress = true;
- } else if (CallInst *CI = dyn_castCallInst(UsersToProcess[i].Inst)) {
+ } else if (IntrinsicInst *II =
+ dyn_castIntrinsicInst(UsersToProcess[i].Inst)) {
// Addressing modes can also be folded into prefetches.
-Function *CalledFunc = CI-getCalledFunction();
-if (CalledFunc != NULL
-CalledFunc-getIntrinsicID() == Intrinsic::prefetch
-CI-getOperand(1) == UsersToProcess[i].OperandValToReplace)
+if (II-getIntrinsicID() == Intrinsic::prefetch
+II-getOperand(1) == UsersToProcess[i].OperandValToReplace)
isAddress = 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.134 - 1.135
---
Log message:
Allow strength reduction to make use of addressing modes for the
address operand in a prefetch intrinsic.
---
Diffs of the changes: (+10 -1)
LoopStrengthReduce.cpp | 11 ++-
1 files changed, 10 insertions(+), 1 deletion(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.134
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.135
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.134 Wed May 2
20:11:54 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Thu May 3 18:20:33 2007
@@ -19,6 +19,7 @@
#include llvm/Transforms/Scalar.h
#include llvm/Constants.h
#include llvm/Instructions.h
+#include llvm/Intrinsics.h
#include llvm/Type.h
#include llvm/DerivedTypes.h
#include llvm/Analysis/Dominators.h
@@ -1039,9 +1040,17 @@
// Addressing modes can be folded into loads and stores. Be careful that
// the store is through the expression, not of the expression though.
bool isAddress = isaLoadInst(UsersToProcess[i].Inst);
- if (StoreInst *SI = dyn_castStoreInst(UsersToProcess[i].Inst))
+ if (StoreInst *SI = dyn_castStoreInst(UsersToProcess[i].Inst)) {
if (SI-getOperand(1) == UsersToProcess[i].OperandValToReplace)
isAddress = true;
+ } else if (CallInst *CI = dyn_castCallInst(UsersToProcess[i].Inst)) {
+// Addressing modes can also be folded into prefetches.
+Function *CalledFunc = CI-getCalledFunction();
+if (CalledFunc != NULL
+CalledFunc-getIntrinsicID() == Intrinsic::prefetch
+CI-getOperand(1) == UsersToProcess[i].OperandValToReplace)
+ isAddress = true;
+ }
MoveImmediateValues(TLI, UsersToProcess[i].Inst, UsersToProcess[i].Base,
UsersToProcess[i].Imm, isAddress, L);
___
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/LoopStrengthReduce.cpp
+ } else if (CallInst *CI = dyn_castCallInst(UsersToProcess
[i].Inst)) {
+// Addressing modes can also be folded into prefetches.
+Function *CalledFunc = CI-getCalledFunction();
+if (CalledFunc != NULL
+CalledFunc-getIntrinsicID() == Intrinsic::prefetch
+CI-getOperand(1) == UsersToProcess
[i].OperandValToReplace)
+ isAddress = true;
+ }
Cool. One easier way to do this is with llvm/IntrinsicInst.h. You
can do stuff like:
} else if (IntrinsicInst *II = dyn_castIntrinsicInst(UsersToProcess
[i].Inst)) {
if (II-getIntrinsicID() == Intrinsic::prefetch ...
Which is ever so slightly nicer :)
-Chris
MoveImmediateValues(TLI, UsersToProcess[i].Inst,
UsersToProcess[i].Base,
UsersToProcess[i].Imm, isAddress, L);
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.130 - 1.131
---
Log message:
Fix
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070423/048333.html
---
Diffs of the changes: (+9 -5)
LoopStrengthReduce.cpp | 14 +-
1 files changed, 9 insertions(+), 5 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.130
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.131
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.130 Sun Apr 15
03:47:27 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Mon Apr 23 17:42:03 2007
@@ -416,12 +416,16 @@
if (!getSCEVStartAndStride(ISE, L, Start, Stride))
return false; // Non-reducible symbolic expression, bail out.
- for (Value::use_iterator UI = I-use_begin(), E = I-use_end(); UI != E;) {
-Instruction *User = castInstruction(*UI);
+ std::vectorInstruction * IUsers;
+ // Collect all I uses now because IVUseShouldUsePostIncValue may
+ // invalidate use_iterator.
+ for (Value::use_iterator UI = I-use_begin(), E = I-use_end(); UI != E;
++UI)
+IUsers.push_back(castInstruction(*UI));
-// Increment iterator now because IVUseShouldUsePostIncValue may remove
-// User from the list of I users.
-++UI;
+ for (unsigned iused_index = 0, iused_size = IUsers.size();
+ iused_index != iused_size; ++iused_index) {
+
+Instruction *User = IUsers[iused_index];
// Do not infinitely recurse on PHI nodes.
if (isaPHINode(User) Processed.count(User))
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopStrengthReduce.cpp updated: 1.129 - 1.130 --- Log message: Remove ImmediateDominator analysis. The same information can be obtained from DomTree. A lot of code for constructing ImmediateDominator is now folded into DomTree construction. This is part of the ongoing work for PR217: http://llvm.org/PR217 . --- Diffs of the changes: (+0 -1) LoopStrengthReduce.cpp |1 - 1 files changed, 1 deletion(-) Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.129 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.130 --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.129 Fri Apr 13 15:42:26 2007 +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Sun Apr 15 03:47:27 2007 @@ -154,7 +154,6 @@ AU.addPreservedID(LoopSimplifyID); AU.addPreservedLoopInfo(); AU.addPreservedETForest(); - AU.addPreservedImmediateDominators(); AU.addPreservedDominanceFrontier(); AU.addPreservedDominatorTree(); ___ llvm-commits mailing list [EMAIL PROTECTED] http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.128 - 1.129
---
Log message:
Now that codegen prepare isn't defeating me, I can finally fix what I set
out to do! :)
This fixes a problem where LSR would insert a bunch of code into each MBB
that uses a particular subexpression (e.g. IV+base+C). The problem is that
this code cannot be CSE'd back together if inserted into different blocks.
This patch changes LSR to attempt to insert a single copy of this code and
share it, allowing codegenprepare to duplicate the code if it can be sunk
into various addressing modes. On CodeGen/ARM/lsr-code-insertion.ll,
for example, this gives us code like:
add r8, r0, r5
str r6, [r8, #+4]
..
ble LBB1_4 @cond_next
LBB1_3: @cond_true
str r10, [r8, #+4]
LBB1_4: @cond_next
...
LBB1_5: @cond_true55
ldr r6, LCPI1_1
str r6, [r8, #+4]
instead of:
add r10, r0, r6
str r8, [r10, #+4]
...
ble LBB1_4 @cond_next
LBB1_3: @cond_true
add r8, r0, r6
str r10, [r8, #+4]
LBB1_4: @cond_next
...
LBB1_5: @cond_true55
add r8, r0, r6
ldr r10, LCPI1_1
str r10, [r8, #+4]
Besides being smaller and more efficient, this makes it immediately
obvious that it is profitable to predicate LBB1_3 now :)
---
Diffs of the changes: (+19 -1)
LoopStrengthReduce.cpp | 20 +++-
1 files changed, 19 insertions(+), 1 deletion(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.128
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.129
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.128 Mon Apr 9
17:20:14 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri Apr 13 15:42:26 2007
@@ -568,7 +568,25 @@
SCEVExpander Rewriter,
Loop *L, Pass *P) {
if (!isaPHINode(Inst)) {
-Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, Inst, L);
+// By default, insert code at the user instruction.
+BasicBlock::iterator InsertPt = Inst;
+
+// However, if the Operand is itself an instruction, the (potentially
+// complex) inserted code may be shared by many users. Because of this, we
+// want to emit code for the computation of the operand right before its
old
+// computation. This is usually safe, because we obviously used to use the
+// computation when it was computed in its current block. However, in some
+// cases (e.g. use of a post-incremented induction variable) the NewBase
+// value will be pinned to live somewhere after the original computation.
+// In this case, we have to back off.
+if (!isUseOfPostIncrementedValue) {
+ if (Instruction *OpInst = dyn_castInstruction(OperandValToReplace)) {
+InsertPt = OpInst;
+while (isaPHINode(InsertPt)) ++InsertPt;
+ }
+}
+
+Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt,
L);
// Replace the use of the operand Value with the new Phi we just created.
Inst-replaceUsesOfWith(OperandValToReplace, NewVal);
DOUT CHANGED: IMM = *ImmInst = *Inst;
___
llvm-commits mailing list
[EMAIL PROTECTED]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.127 - 1.128
---
Log message:
switch LSR to use isLegalAddressingMode instead of other simpler hooks
---
Diffs of the changes: (+21 -18)
LoopStrengthReduce.cpp | 39 +--
1 files changed, 21 insertions(+), 18 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.127
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.128
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.127 Sat Apr 7
02:17:27 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Mon Apr 9 17:20:14 2007
@@ -143,8 +143,7 @@
const TargetLowering *TLI;
public:
-LoopStrengthReduce(const TargetLowering *tli = NULL)
- : TLI(tli) {
+LoopStrengthReduce(const TargetLowering *tli = NULL) : TLI(tli) {
}
bool runOnLoop(Loop *L, LPPassManager LPM);
@@ -631,20 +630,25 @@
const TargetLowering *TLI) {
if (SCEVConstant *SC = dyn_castSCEVConstant(V)) {
int64_t VC = SC-getValue()-getSExtValue();
-if (TLI)
- return TLI-isLegalAddressImmediate(VC, UseTy);
-else
+if (TLI) {
+ TargetLowering::AddrMode AM;
+ AM.BaseOffs = VC;
+ return TLI-isLegalAddressingMode(AM, UseTy);
+} else {
// Defaults to PPC. PPC allows a sign-extended 16-bit immediate field.
return (VC -(1 16) VC (1 16)-1);
+}
}
if (SCEVUnknown *SU = dyn_castSCEVUnknown(V))
if (ConstantExpr *CE = dyn_castConstantExpr(SU-getValue()))
- if (CE-getOpcode() == Instruction::PtrToInt) {
+ if (TLI CE-getOpcode() == Instruction::PtrToInt) {
Constant *Op0 = CE-getOperand(0);
-if (isaGlobalValue(Op0) TLI
-TLI-isLegalAddressImmediate(castGlobalValue(Op0)))
- return true;
+if (GlobalValue *GV = dyn_castGlobalValue(Op0)) {
+ TargetLowering::AddrMode AM;
+ AM.BaseGV = GV;
+ return TLI-isLegalAddressingMode(AM, UseTy);
+}
}
return false;
}
@@ -889,18 +893,11 @@
}
/// ValidStride - Check whether the given Scale is valid for all loads and
-/// stores in UsersToProcess. Pulled into a function to avoid disturbing the
-/// sensibilities of those who dislike goto's.
+/// stores in UsersToProcess.
///
bool LoopStrengthReduce::ValidStride(int64_t Scale,
const std::vectorBasedUser UsersToProcess) {
- int64_t Imm;
for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) {
-if (SCEVConstant *SC = dyn_castSCEVConstant(UsersToProcess[i].Imm))
- Imm = SC-getValue()-getSExtValue();
-else
- Imm = 0;
-
// If this is a load or other access, pass the type of the access in.
const Type *AccessTy = Type::VoidTy;
if (StoreInst *SI = dyn_castStoreInst(UsersToProcess[i].Inst))
@@ -908,7 +905,13 @@
else if (LoadInst *LI = dyn_castLoadInst(UsersToProcess[i].Inst))
AccessTy = LI-getType();
-if (!TLI-isLegalAddressScaleAndImm(Scale, Imm, AccessTy))
+TargetLowering::AddrMode AM;
+if (SCEVConstant *SC = dyn_castSCEVConstant(UsersToProcess[i].Imm))
+ AM.BaseOffs = SC-getValue()-getSExtValue();
+AM.Scale = Scale;
+
+// If load[imm+r*scale] is illegal, bail out.
+if (!TLI-isLegalAddressingMode(AM, AccessTy))
return false;
}
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopStrengthReduce.cpp updated: 1.126 - 1.127 --- Log message: Completely purge DomSet. This is the (hopefully) final patch for PR1171: http://llvm.org/PR1171 . --- Diffs of the changes: (+0 -1) LoopStrengthReduce.cpp |1 - 1 files changed, 1 deletion(-) Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.126 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.127 --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.126 Tue Apr 3 00:11:24 2007 +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Sat Apr 7 02:17:27 2007 @@ -154,7 +154,6 @@ // many analyses if they are around. AU.addPreservedID(LoopSimplifyID); AU.addPreservedLoopInfo(); - AU.addPreservedDominatorSet(); AU.addPreservedETForest(); AU.addPreservedImmediateDominators(); AU.addPreservedDominanceFrontier(); ___ 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopStrengthReduce.cpp updated: 1.123 - 1.124 --- Log message: Pass the type of the store access, not the type of the store, into the target hook. This allows us to codegen a loop as: LBB1_1: @cond_next mov r2, #0 str r2, [r0, +r3, lsl #2] add r3, r3, #1 cmn r3, #1 bne LBB1_1 @cond_next instead of: LBB1_1: @cond_next mov r2, #0 str r2, [r0], #+4 add r3, r3, #1 cmn r3, #1 bne LBB1_1 @cond_next This looks the same, but has one fewer induction variable (and therefore, one fewer register) live in the loop. --- Diffs of the changes: (+9 -2) LoopStrengthReduce.cpp | 11 +-- 1 files changed, 9 insertions(+), 2 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.123 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.124 --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.123 Sun Apr 1 17:21:39 2007 +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Mon Apr 2 01:34:44 2007 @@ -899,8 +899,15 @@ Imm = SC-getValue()-getSExtValue(); else Imm = 0; -if (!TLI-isLegalAddressScaleAndImm(Scale, Imm, - UsersToProcess[i].Inst-getType())) + +// If this is a load or other access, pass the type of the access in. +const Type *AccessTy = Type::VoidTy; +if (StoreInst *SI = dyn_castStoreInst(UsersToProcess[i].Inst)) + AccessTy = SI-getOperand(0)-getType(); +else if (LoadInst *LI = dyn_castLoadInst(UsersToProcess[i].Inst)) + AccessTy = LI-getType(); + +if (!TLI-isLegalAddressScaleAndImm(Scale, Imm, AccessTy)) return false; } 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.124 - 1.125
---
Log message:
allow -1 strides to reuse 1 strides.
---
Diffs of the changes: (+2 -1)
LoopStrengthReduce.cpp |3 ++-
1 files changed, 2 insertions(+), 1 deletion(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.124
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.125
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.124 Mon Apr 2
01:34:44 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Mon Apr 2 17:51:58 2007
@@ -929,7 +929,8 @@
for (std::mapSCEVHandle, IVsOfOneStride::iterator SI=
IVsByStride.begin(),
SE = IVsByStride.end(); SI != SE; ++SI) {
int64_t SSInt =
castSCEVConstant(SI-first)-getValue()-getSExtValue();
- if (unsigned(abs(SInt)) SSInt || (SInt % SSInt) != 0)
+ if (SInt != -SSInt
+ (unsigned(abs(SInt)) SSInt || (SInt % SSInt) != 0))
continue;
int64_t Scale = SInt / SSInt;
// Check that this stride is valid for all the types used for loads and
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.125 - 1.126
---
Log message:
split some code out into a helper function
---
Diffs of the changes: (+30 -18)
LoopStrengthReduce.cpp | 48 ++--
1 files changed, 30 insertions(+), 18 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.125
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.126
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.125 Mon Apr 2
17:51:58 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Tue Apr 3 00:11:24 2007
@@ -176,6 +176,8 @@
SCEVHandle GetExpressionSCEV(Instruction *E, Loop *L);
void OptimizeIndvars(Loop *L);
+bool FindIVForUser(ICmpInst *Cond, IVStrideUse *CondUse,
+ const SCEVHandle *CondStride);
unsigned CheckForIVReuse(const SCEVHandle, IVExpr, const Type*,
const std::vectorBasedUser UsersToProcess);
@@ -1222,6 +1224,31 @@
// different starting values, into different PHIs.
}
+/// FindIVForUser - If Cond has an operand that is an expression of an IV,
+/// set the IV user and stride information and return true, otherwise return
+/// false.
+bool LoopStrengthReduce::FindIVForUser(ICmpInst *Cond, IVStrideUse *CondUse,
+ const SCEVHandle *CondStride) {
+ for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e !CondUse;
+ ++Stride) {
+std::mapSCEVHandle, IVUsersOfOneStride::iterator SI =
+IVUsesByStride.find(StrideOrder[Stride]);
+assert(SI != IVUsesByStride.end() Stride doesn't exist!);
+
+for (std::vectorIVStrideUse::iterator UI = SI-second.Users.begin(),
+ E = SI-second.Users.end(); UI != E; ++UI)
+ if (UI-User == Cond) {
+// NOTE: we could handle setcc instructions with multiple uses here,
but
+// InstCombine does it as well for simple uses, it's not clear that it
+// occurs enough in real life to handle.
+CondUse = *UI;
+CondStride = SI-first;
+return true;
+ }
+ }
+ return false;
+}
+
// OptimizeIndvars - Now that IVUsesByStride is set up with all of the indvar
// uses in the loop, look to see if we can eliminate some, in favor of using
// common indvars for the different uses.
@@ -1246,24 +1273,9 @@
IVStrideUse *CondUse = 0;
const SCEVHandle *CondStride = 0;
- for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e !CondUse;
- ++Stride) {
-std::mapSCEVHandle, IVUsersOfOneStride::iterator SI =
- IVUsesByStride.find(StrideOrder[Stride]);
-assert(SI != IVUsesByStride.end() Stride doesn't exist!);
-
-for (std::vectorIVStrideUse::iterator UI = SI-second.Users.begin(),
- E = SI-second.Users.end(); UI != E; ++UI)
- if (UI-User == Cond) {
-CondUse = *UI;
-CondStride = SI-first;
-// NOTE: we could handle setcc instructions with multiple uses here,
but
-// InstCombine does it as well for simple uses, it's not clear that it
-// occurs enough in real life to handle.
-break;
- }
- }
- if (!CondUse) return; // setcc doesn't use the IV.
+ if (!FindIVForUser(Cond, CondUse, CondStride))
+return; // setcc doesn't use the IV.
+
// It's possible for the setcc instruction to be anywhere in the loop, and
// possible for it to have multiple users. If it is not immediately before
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopStrengthReduce.cpp updated: 1.122 - 1.123 --- Log message: print the type of an inserted IV in -debug mode. --- Diffs of the changes: (+4 -3) LoopStrengthReduce.cpp |7 --- 1 files changed, 4 insertions(+), 3 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.122 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.123 --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.122 Sun Mar 25 22:01:27 2007 +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Sun Apr 1 17:21:39 2007 @@ -1029,10 +1029,12 @@ IncV = ReuseIV.IncV; } + const Type *ReplacedTy = CommonExprs-getType(); + // Now that we know what we need to do, insert the PHI node itself. // - DOUT INSERTING IV of STRIDE *Stride and BASE -*CommonExprs :\n; + DOUT INSERTING IV of TYPE *ReplacedTy of STRIDE +*Stride and BASE *CommonExprs :\n; SCEVExpander Rewriter(*SE, *LI); SCEVExpander PreheaderRewriter(*SE, *LI); @@ -1043,7 +1045,6 @@ BasicBlock *LatchBlock = L-getLoopLatch(); - const Type *ReplacedTy = CommonExprs-getType(); // Emit the initial base value into the loop preheader. Value *CommonBaseV ___ 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.121 - 1.122
---
Log message:
Look through bitcast when finding IVs. (Chris' patch really.)
---
Diffs of the changes: (+10 -0)
LoopStrengthReduce.cpp | 10 ++
1 files changed, 10 insertions(+)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.121
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.122
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.121 Tue Mar 20
16:54:54 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Sun Mar 25 22:01:27 2007
@@ -235,6 +235,16 @@
/// GetExpressionSCEV - Compute and return the SCEV for the specified
/// instruction.
SCEVHandle LoopStrengthReduce::GetExpressionSCEV(Instruction *Exp, Loop *L) {
+ // Pointer to pointer bitcast instructions return the same value as their
+ // operand.
+ if (BitCastInst *BCI = dyn_castBitCastInst(Exp)) {
+if (SE-hasSCEV(BCI) || !isaInstruction(BCI-getOperand(0)))
+ return SE-getSCEV(BCI);
+SCEVHandle R = GetExpressionSCEV(castInstruction(BCI-getOperand(0)), L);
+SE-setSCEV(BCI, R);
+return R;
+ }
+
// Scalar Evolutions doesn't know how to compute SCEV's for GEP instructions.
// If this is a GEP that SE doesn't know about, compute it now and insert it.
// If this is not a GEP, or if we have already done this computation, just
let
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.119 - 1.120
---
Log message:
Fix some VC++ warnings.
---
Diffs of the changes: (+1 -1)
LoopStrengthReduce.cpp |2 +-
1 files changed, 1 insertion(+), 1 deletion(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.119
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.120
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.119 Mon Mar 19
19:47:50 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Tue Mar 20 15:43:18 2007
@@ -44,7 +44,7 @@
namespace {
- class BasedUser;
+ struct BasedUser;
/// IVStrideUse - Keep track of one use of a strided induction variable,
where
/// the stride is stored externally. The Offset member keeps track of the
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.120 - 1.121
---
Log message:
do not share old induction variables when this would result in invalid
instructions (that would have to be split later)
---
Diffs of the changes: (+26 -18)
LoopStrengthReduce.cpp | 44 ++--
1 files changed, 26 insertions(+), 18 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.120
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.121
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.120 Tue Mar 20
15:43:18 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Tue Mar 20 16:54:54 2007
@@ -883,9 +883,16 @@
///
bool LoopStrengthReduce::ValidStride(int64_t Scale,
const std::vectorBasedUser UsersToProcess) {
- for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i)
-if (!TLI-isLegalAddressScale(Scale, UsersToProcess[i].Inst-getType()))
+ int64_t Imm;
+ for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) {
+if (SCEVConstant *SC = dyn_castSCEVConstant(UsersToProcess[i].Imm))
+ Imm = SC-getValue()-getSExtValue();
+else
+ Imm = 0;
+if (!TLI-isLegalAddressScaleAndImm(Scale, Imm,
+ UsersToProcess[i].Inst-getType()))
return false;
+ }
return true;
}
@@ -968,22 +975,6 @@
SCEVHandle CommonExprs =
RemoveCommonExpressionsFromUseBases(UsersToProcess);
- // Check if it is possible to reuse a IV with stride that is factor of this
- // stride. And the multiple is a number that can be encoded in the scale
- // field of the target addressing mode.
- PHINode *NewPHI = NULL;
- Value *IncV = NULL;
- IVExpr ReuseIV;
- unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV,
- CommonExprs-getType(),
- UsersToProcess);
- if (RewriteFactor != 0) {
-DOUT BASED ON IV of STRIDE *ReuseIV.Stride
- and BASE *ReuseIV.Base :\n;
-NewPHI = ReuseIV.PHI;
-IncV = ReuseIV.IncV;
- }
-
// Next, figure out what we can represent in the immediate fields of
// instructions. If we can represent anything there, move it to the imm
// fields of the BasedUsers. We do this so that it increases the commonality
@@ -1011,6 +1002,23 @@
}
}
+ // Check if it is possible to reuse a IV with stride that is factor of this
+ // stride. And the multiple is a number that can be encoded in the scale
+ // field of the target addressing mode. And we will have a valid
+ // instruction after this substition, including the immediate field, if any.
+ PHINode *NewPHI = NULL;
+ Value *IncV = NULL;
+ IVExpr ReuseIV;
+ unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV,
+ CommonExprs-getType(),
+ UsersToProcess);
+ if (RewriteFactor != 0) {
+DOUT BASED ON IV of STRIDE *ReuseIV.Stride
+ and BASE *ReuseIV.Base :\n;
+NewPHI = ReuseIV.PHI;
+IncV = ReuseIV.IncV;
+ }
+
// Now that we know what we need to do, insert the PHI node itself.
//
DOUT INSERTING IV of STRIDE *Stride and BASE
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.118 - 1.119
---
Log message:
use types of loads and stores, not address, in CheckForIVReuse
---
Diffs of the changes: (+28 -7)
LoopStrengthReduce.cpp | 35 ---
1 files changed, 28 insertions(+), 7 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.118
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.119
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.118 Tue Mar 13
15:34:37 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Mon Mar 19 19:47:50 2007
@@ -43,6 +43,9 @@
STATISTIC(NumVariable, Number of PHIs with variable strides);
namespace {
+
+ class BasedUser;
+
/// IVStrideUse - Keep track of one use of a strided induction variable,
where
/// the stride is stored externally. The Offset member keeps track of the
/// offset from the IV, User is the actual user of the operand, and 'Operand'
@@ -174,7 +177,10 @@
void OptimizeIndvars(Loop *L);
-unsigned CheckForIVReuse(const SCEVHandle, IVExpr, const Type*);
+unsigned CheckForIVReuse(const SCEVHandle, IVExpr, const Type*,
+ const std::vectorBasedUser UsersToProcess);
+
+bool ValidStride(int64_t, const std::vectorBasedUser UsersToProcess);
void StrengthReduceStridedIVUsers(const SCEVHandle Stride,
IVUsersOfOneStride Uses,
@@ -871,13 +877,25 @@
return false;
}
+/// ValidStride - Check whether the given Scale is valid for all loads and
+/// stores in UsersToProcess. Pulled into a function to avoid disturbing the
+/// sensibilities of those who dislike goto's.
+///
+bool LoopStrengthReduce::ValidStride(int64_t Scale,
+ const std::vectorBasedUser UsersToProcess) {
+ for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i)
+if (!TLI-isLegalAddressScale(Scale, UsersToProcess[i].Inst-getType()))
+ return false;
+ return true;
+}
/// CheckForIVReuse - Returns the multiple if the stride is the multiple
/// of a previous stride and it is a legal value for the target addressing
/// mode scale component. This allows the users of this stride to be rewritten
/// as prev iv * factor. It returns 0 if no reuse is possible.
-unsigned LoopStrengthReduce::CheckForIVReuse(const SCEVHandle Stride,
- IVExpr IV, const Type *Ty) {
+unsigned LoopStrengthReduce::CheckForIVReuse(const SCEVHandle Stride,
+IVExpr IV, const Type *Ty,
+const std::vectorBasedUser UsersToProcess) {
if (!TLI) return 0;
if (SCEVConstant *SC = dyn_castSCEVConstant(Stride)) {
@@ -890,7 +908,11 @@
if (unsigned(abs(SInt)) SSInt || (SInt % SSInt) != 0)
continue;
int64_t Scale = SInt / SSInt;
- if (TLI-isLegalAddressScale(Scale, Ty)) {
+ // Check that this stride is valid for all the types used for loads and
+ // stores; if it can be used for some and not others, we might as well
use
+ // the original stride everywhere, since we have to create the IV for it
+ // anyway.
+ if (ValidStride(Scale, UsersToProcess))
for (std::vectorIVExpr::iterator II = SI-second.IVs.begin(),
IE = SI-second.IVs.end(); II != IE; ++II)
// FIXME: Only handle base == 0 for now.
@@ -899,10 +921,8 @@
IV = *II;
return Scale;
}
- }
}
}
-
return 0;
}
@@ -955,7 +975,8 @@
Value *IncV = NULL;
IVExpr ReuseIV;
unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV,
- CommonExprs-getType());
+ CommonExprs-getType(),
+ UsersToProcess);
if (RewriteFactor != 0) {
DOUT BASED ON IV of STRIDE *ReuseIV.Stride
and BASE *ReuseIV.Base :\n;
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.117 - 1.118
---
Log message:
Correct type info for isLegalAddressImmediate() check.
---
Diffs of the changes: (+18 -12)
LoopStrengthReduce.cpp | 30 ++
1 files changed, 18 insertions(+), 12 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.117
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.118
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.117 Mon Mar 12
18:27:37 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Tue Mar 13 15:34:37 2007
@@ -610,11 +610,12 @@
/// isTargetConstant - Return true if the following can be referenced by the
/// immediate field of a target instruction.
-static bool isTargetConstant(const SCEVHandle V, const TargetLowering *TLI) {
+static bool isTargetConstant(const SCEVHandle V, const Type *UseTy,
+ const TargetLowering *TLI) {
if (SCEVConstant *SC = dyn_castSCEVConstant(V)) {
int64_t VC = SC-getValue()-getSExtValue();
if (TLI)
- return TLI-isLegalAddressImmediate(VC, V-getType());
+ return TLI-isLegalAddressImmediate(VC, UseTy);
else
// Defaults to PPC. PPC allows a sign-extended 16-bit immediate field.
return (VC -(1 16) VC (1 16)-1);
@@ -674,15 +675,20 @@
/// that can fit into the immediate field of instructions in the target.
/// Accumulate these immediate values into the Imm value.
static void MoveImmediateValues(const TargetLowering *TLI,
+Instruction *User,
SCEVHandle Val, SCEVHandle Imm,
bool isAddress, Loop *L) {
+ const Type *UseTy = User-getType();
+ if (StoreInst *SI = dyn_castStoreInst(User))
+UseTy = SI-getOperand(0)-getType();
+
if (SCEVAddExpr *SAE = dyn_castSCEVAddExpr(Val)) {
std::vectorSCEVHandle NewOps;
NewOps.reserve(SAE-getNumOperands());
for (unsigned i = 0; i != SAE-getNumOperands(); ++i) {
SCEVHandle NewOp = SAE-getOperand(i);
- MoveImmediateValues(TLI, NewOp, Imm, isAddress, L);
+ MoveImmediateValues(TLI, User, NewOp, Imm, isAddress, L);
if (!NewOp-isLoopInvariant(L)) {
// If this is a loop-variant expression, it must stay in the immediate
@@ -701,7 +707,7 @@
} else if (SCEVAddRecExpr *SARE = dyn_castSCEVAddRecExpr(Val)) {
// Try to pull immediates out of the start value of nested addrec's.
SCEVHandle Start = SARE-getStart();
-MoveImmediateValues(TLI, Start, Imm, isAddress, L);
+MoveImmediateValues(TLI, User, Start, Imm, isAddress, L);
if (Start != SARE-getStart()) {
std::vectorSCEVHandle Ops(SARE-op_begin(), SARE-op_end());
@@ -711,12 +717,12 @@
return;
} else if (SCEVMulExpr *SME = dyn_castSCEVMulExpr(Val)) {
// Transform 8 * (4 + v) - 32 + 8*V if 32 fits in the immed field.
-if (isAddress isTargetConstant(SME-getOperand(0), TLI)
+if (isAddress isTargetConstant(SME-getOperand(0), UseTy, TLI)
SME-getNumOperands() == 2 SME-isLoopInvariant(L)) {
SCEVHandle SubImm = SCEVUnknown::getIntegerSCEV(0, Val-getType());
SCEVHandle NewOp = SME-getOperand(1);
- MoveImmediateValues(TLI, NewOp, SubImm, isAddress, L);
+ MoveImmediateValues(TLI, User, NewOp, SubImm, isAddress, L);
// If we extracted something out of the subexpressions, see if we can
// simplify this!
@@ -724,7 +730,7 @@
// Scale SubImm up by 8. If the result is a target constant, we are
// good.
SubImm = SCEVMulExpr::get(SubImm, SME-getOperand(0));
-if (isTargetConstant(SubImm, TLI)) {
+if (isTargetConstant(SubImm, UseTy, TLI)) {
// Accumulate the immediate.
Imm = SCEVAddExpr::get(Imm, SubImm);
@@ -738,7 +744,7 @@
// Loop-variant expressions must stay in the immediate field of the
// expression.
- if ((isAddress isTargetConstant(Val, TLI)) ||
+ if ((isAddress isTargetConstant(Val, UseTy, TLI)) ||
!Val-isLoopInvariant(L)) {
Imm = SCEVAddExpr::get(Imm, Val);
Val = SCEVUnknown::getIntegerSCEV(0, Val-getType());
@@ -979,8 +985,8 @@
if (SI-getOperand(1) == UsersToProcess[i].OperandValToReplace)
isAddress = true;
- MoveImmediateValues(TLI, UsersToProcess[i].Base, UsersToProcess[i].Imm,
- isAddress, L);
+ MoveImmediateValues(TLI, UsersToProcess[i].Inst, UsersToProcess[i].Base,
+ UsersToProcess[i].Imm, isAddress, L);
}
}
@@ -1034,7 +1040,7 @@
Constant *C = dyn_castConstant(CommonBaseV);
if (!C ||
(!C-isNullValue()
- !isTargetConstant(SCEVUnknown::get(CommonBaseV), TLI)))
+ !isTargetConstant(SCEVUnknown::get(CommonBaseV), ReplacedTy, TLI)))
// We want the common base
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.116 - 1.117
---
Log message:
Use new TargetLowering addressing modes hooks.
---
Diffs of the changes: (+18 -20)
LoopStrengthReduce.cpp | 38 ++
1 files changed, 18 insertions(+), 20 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.116
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.117
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.116 Fri Mar 9
15:19:53 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Mon Mar 12 18:27:37 2007
@@ -612,12 +612,12 @@
/// immediate field of a target instruction.
static bool isTargetConstant(const SCEVHandle V, const TargetLowering *TLI) {
if (SCEVConstant *SC = dyn_castSCEVConstant(V)) {
-int64_t V = SC-getValue()-getSExtValue();
+int64_t VC = SC-getValue()-getSExtValue();
if (TLI)
- return TLI-isLegalAddressImmediate(V);
+ return TLI-isLegalAddressImmediate(VC, V-getType());
else
// Defaults to PPC. PPC allows a sign-extended 16-bit immediate field.
- return (V -(1 16) V (1 16)-1);
+ return (VC -(1 16) VC (1 16)-1);
}
if (SCEVUnknown *SU = dyn_castSCEVUnknown(V))
@@ -878,24 +878,22 @@
int64_t SInt = SC-getValue()-getSExtValue();
if (SInt == 1) return 0;
-for (TargetLowering::legal_am_scale_iterator
- I = TLI-legal_am_scale_begin(), E = TLI-legal_am_scale_end();
- I != E; ++I) {
- unsigned Scale = *I;
- if (unsigned(abs(SInt)) Scale || (SInt % Scale) != 0)
+for (std::mapSCEVHandle, IVsOfOneStride::iterator SI=
IVsByStride.begin(),
+ SE = IVsByStride.end(); SI != SE; ++SI) {
+ int64_t SSInt =
castSCEVConstant(SI-first)-getValue()-getSExtValue();
+ if (unsigned(abs(SInt)) SSInt || (SInt % SSInt) != 0)
continue;
- std::mapSCEVHandle, IVsOfOneStride::iterator SI =
-IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt/Scale, UIntPtrTy));
- if (SI == IVsByStride.end())
-continue;
- for (std::vectorIVExpr::iterator II = SI-second.IVs.begin(),
- IE = SI-second.IVs.end(); II != IE; ++II)
-// FIXME: Only handle base == 0 for now.
-// Only reuse previous IV if it would not require a type conversion.
-if (isZero(II-Base) II-Base-getType() == Ty) {
- IV = *II;
- return Scale;
-}
+ int64_t Scale = SInt / SSInt;
+ if (TLI-isLegalAddressScale(Scale, Ty)) {
+for (std::vectorIVExpr::iterator II = SI-second.IVs.begin(),
+ IE = SI-second.IVs.end(); II != IE; ++II)
+ // FIXME: Only handle base == 0 for now.
+ // Only reuse previous IV if it would not require a type conversion.
+ if (isZero(II-Base) II-Base-getType() == Ty) {
+IV = *II;
+return Scale;
+ }
+ }
}
}
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.115 - 1.116
---
Log message:
Increment iterator now because IVUseShouldUsePostIncValue may remove
User from the list of I users.
---
Diffs of the changes: (+6 -2)
LoopStrengthReduce.cpp |8 ++--
1 files changed, 6 insertions(+), 2 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.115
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.116
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.115 Tue Mar 6
15:14:09 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri Mar 9 15:19:53 2007
@@ -400,10 +400,14 @@
SCEVHandle Stride = Start;
if (!getSCEVStartAndStride(ISE, L, Start, Stride))
return false; // Non-reducible symbolic expression, bail out.
-
- for (Value::use_iterator UI = I-use_begin(), E = I-use_end(); UI !=
E;++UI){
+
+ for (Value::use_iterator UI = I-use_begin(), E = I-use_end(); UI != E;) {
Instruction *User = castInstruction(*UI);
+// Increment iterator now because IVUseShouldUsePostIncValue may remove
+// User from the list of I users.
+++UI;
+
// Do not infinitely recurse on PHI nodes.
if (isaPHINode(User) Processed.count(User))
continue;
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.114 - 1.115
---
Log message:
Now LoopStrengthReduce is a LoopPass.
---
Diffs of the changes: (+14 -23)
LoopStrengthReduce.cpp | 37 ++---
1 files changed, 14 insertions(+), 23 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.114
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.115
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.114 Fri Mar 2
17:51:25 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Tue Mar 6 15:14:09 2007
@@ -23,6 +23,7 @@
#include llvm/DerivedTypes.h
#include llvm/Analysis/Dominators.h
#include llvm/Analysis/LoopInfo.h
+#include llvm/Analysis/LoopPass.h
#include llvm/Analysis/ScalarEvolutionExpander.h
#include llvm/Support/CFG.h
#include llvm/Support/GetElementPtrTypeIterator.h
@@ -104,7 +105,7 @@
}
};
- class VISIBILITY_HIDDEN LoopStrengthReduce : public FunctionPass {
+ class VISIBILITY_HIDDEN LoopStrengthReduce : public LoopPass {
LoopInfo *LI;
ETForest *EF;
ScalarEvolution *SE;
@@ -143,19 +144,7 @@
: TLI(tli) {
}
-virtual bool runOnFunction(Function ) {
- LI = getAnalysisLoopInfo();
- EF = getAnalysisETForest();
- SE = getAnalysisScalarEvolution();
- TD = getAnalysisTargetData();
- UIntPtrTy = TD-getIntPtrType();
- Changed = false;
-
- for (LoopInfo::iterator I = LI-begin(), E = LI-end(); I != E; ++I)
-runOnLoop(*I);
-
- return Changed;
-}
+bool runOnLoop(Loop *L, LPPassManager LPM);
virtual void getAnalysisUsage(AnalysisUsage AU) const {
// We split critical edges, so we change the CFG. However, we do update
@@ -179,7 +168,6 @@
///
Value *getCastedVersionOf(Instruction::CastOps opcode, Value *V);
private:
-void runOnLoop(Loop *L);
bool AddUsersIfInteresting(Instruction *I, Loop *L,
std::setInstruction* Processed);
SCEVHandle GetExpressionSCEV(Instruction *E, Loop *L);
@@ -196,7 +184,7 @@
RegisterPassLoopStrengthReduce X(loop-reduce, Loop Strength Reduction);
}
-FunctionPass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) {
+LoopPass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) {
return new LoopStrengthReduce(TLI);
}
@@ -1271,12 +1259,15 @@
};
}
-void LoopStrengthReduce::runOnLoop(Loop *L) {
- // First step, transform all loops nesting inside of this loop.
- for (LoopInfo::iterator I = L-begin(), E = L-end(); I != E; ++I)
-runOnLoop(*I);
+bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager LPM) {
- // Next, find all uses of induction variables in this loop, and catagorize
+ LI = getAnalysisLoopInfo();
+ EF = getAnalysisETForest();
+ SE = getAnalysisScalarEvolution();
+ TD = getAnalysisTargetData();
+ UIntPtrTy = TD-getIntPtrType();
+
+ // Find all uses of induction variables in this loop, and catagorize
// them by stride. Start by finding all of the PHI nodes in the header for
// this loop. If they are induction variables, inspect their uses.
std::setInstruction* Processed; // Don't reprocess instructions.
@@ -1284,7 +1275,7 @@
AddUsersIfInteresting(I, L, Processed);
// If we have nothing to do, return.
- if (IVUsesByStride.empty()) return;
+ if (IVUsesByStride.empty()) return false;
// Optimize induction variables. Some indvar uses can be transformed to use
// strides that will be needed for other purposes. A common example of this
@@ -1368,5 +1359,5 @@
CastedPointers.clear();
IVUsesByStride.clear();
StrideOrder.clear();
- return;
+ return false;
}
___
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/LoopStrengthReduce.cpp LoopUnswitch.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.111 - 1.112
LoopUnswitch.cpp updated: 1.63 - 1.64
---
Log message:
Use more efficient test for one value in a ConstantInt.
---
Diffs of the changes: (+14 -13)
LoopStrengthReduce.cpp | 23 ---
LoopUnswitch.cpp |4 ++--
2 files changed, 14 insertions(+), 13 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.111
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.112
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.111 Thu Mar 1
18:31:39 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri Mar 2 17:35:28 2007
@@ -540,7 +540,7 @@
// If there is no immediate value, skip the next part.
if (SCEVConstant *SC = dyn_castSCEVConstant(Imm))
-if (SC-getValue()-isNullValue())
+if (SC-getValue()-isZero())
return Rewriter.expandCodeFor(NewBase, BaseInsertPt,
OperandValToReplace-getType());
@@ -779,7 +779,7 @@
SeparateSubExprs(SubExprs, SARE-getOperand(0));
}
} else if (!isaSCEVConstant(Expr) ||
- !castSCEVConstant(Expr)-getValue()-isNullValue()) {
+ !castSCEVConstant(Expr)-getValue()-isZero()) {
// Do not add zero.
SubExprs.push_back(Expr);
}
@@ -869,7 +869,7 @@
///
static bool isZero(SCEVHandle V) {
if (SCEVConstant *SC = dyn_castSCEVConstant(V))
-return SC-getValue()-getZExtValue() == 0;
+return SC-getValue()-isZero();
return false;
}
@@ -883,17 +883,18 @@
if (!TLI) return 0;
if (SCEVConstant *SC = dyn_castSCEVConstant(Stride)) {
-int64_t SInt = SC-getValue()-getSExtValue();
-if (SInt == 1) return 0;
+APInt SInt(SC-getValue()-getValue());
+if (SInt == 1)
+ return 0;
for (TargetLowering::legal_am_scale_iterator
I = TLI-legal_am_scale_begin(), E = TLI-legal_am_scale_end();
I != E; ++I) {
- unsigned Scale = *I;
- if (unsigned(abs(SInt)) Scale || (SInt % Scale) != 0)
+ APInt Scale(SInt.getBitWidth(), *I);
+ if (SInt.abs().ult(Scale) || SInt.srem(Scale) != 0)
continue;
std::mapSCEVHandle, IVsOfOneStride::iterator SI =
-IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt/Scale, UIntPtrTy));
+IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt.sdiv(Scale)));
if (SI == IVsByStride.end())
continue;
for (std::vectorIVExpr::iterator II = SI-second.IVs.begin(),
@@ -902,7 +903,7 @@
// Only reuse previous IV if it would not require a type conversion.
if (isZero(II-Base) II-Base-getType() == Ty) {
IV = *II;
- return Scale;
+ return Scale.getZExtValue();
}
}
}
@@ -1148,14 +1149,14 @@
// are reusing an IV, it has not been used to initialize the PHI node.
// Add it to the expression used to rewrite the uses.
if (!isaConstantInt(CommonBaseV) ||
-!castConstantInt(CommonBaseV)-isNullValue())
+!castConstantInt(CommonBaseV)-isZero())
RewriteExpr = SCEVAddExpr::get(RewriteExpr,
SCEVUnknown::get(CommonBaseV));
}
// Now that we know what we need to do, insert code before User for the
// immediate and any loop-variant expressions.
- if (!isaConstantInt(BaseV) || !castConstantInt(BaseV)-isNullValue())
+ if (!isaConstantInt(BaseV) || !castConstantInt(BaseV)-isZero())
// Add BaseV to the PHI value if needed.
RewriteExpr = SCEVAddExpr::get(RewriteExpr, SCEVUnknown::get(BaseV));
Index: llvm/lib/Transforms/Scalar/LoopUnswitch.cpp
diff -u llvm/lib/Transforms/Scalar/LoopUnswitch.cpp:1.63
llvm/lib/Transforms/Scalar/LoopUnswitch.cpp:1.64
--- llvm/lib/Transforms/Scalar/LoopUnswitch.cpp:1.63Mon Feb 26 14:22:50 2007
+++ llvm/lib/Transforms/Scalar/LoopUnswitch.cpp Fri Mar 2 17:35:28 2007
@@ -1048,7 +1048,7 @@
castBinaryOperator(I)-swapOperands();
if (ConstantInt *CB = dyn_castConstantInt(I-getOperand(1)))
if (CB-getType() == Type::Int1Ty) {
- if (CB-getZExtValue()) // X 1 - X
+ if (CB-isOne()) // X 1 - X
ReplaceUsesOfWith(I, I-getOperand(0), Worklist);
else // X 0 - 0
ReplaceUsesOfWith(I, I-getOperand(1), Worklist);
@@ -1061,7 +1061,7 @@
castBinaryOperator(I)-swapOperands();
if (ConstantInt *CB = dyn_castConstantInt(I-getOperand(1)))
if (CB-getType() == Type::Int1Ty) {
- if (CB-getZExtValue()) // X | 1 - 1
+ if (CB-isOne()) // X | 1 - 1
ReplaceUsesOfWith(I, I-getOperand(1), Worklist);
else // X | 0 - X
ReplaceUsesOfWith(I, I-getOperand(0), Worklist);
___
llvm-commits mailing list
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.112 - 1.113
---
Log message:
Dang, I've done that twice now! Undo previous commit.
---
Diffs of the changes: (+11 -12)
LoopStrengthReduce.cpp | 23 +++
1 files changed, 11 insertions(+), 12 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.112
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.113
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.112 Fri Mar 2
17:35:28 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri Mar 2 17:37:53 2007
@@ -540,7 +540,7 @@
// If there is no immediate value, skip the next part.
if (SCEVConstant *SC = dyn_castSCEVConstant(Imm))
-if (SC-getValue()-isZero())
+if (SC-getValue()-isNullValue())
return Rewriter.expandCodeFor(NewBase, BaseInsertPt,
OperandValToReplace-getType());
@@ -779,7 +779,7 @@
SeparateSubExprs(SubExprs, SARE-getOperand(0));
}
} else if (!isaSCEVConstant(Expr) ||
- !castSCEVConstant(Expr)-getValue()-isZero()) {
+ !castSCEVConstant(Expr)-getValue()-isNullValue()) {
// Do not add zero.
SubExprs.push_back(Expr);
}
@@ -869,7 +869,7 @@
///
static bool isZero(SCEVHandle V) {
if (SCEVConstant *SC = dyn_castSCEVConstant(V))
-return SC-getValue()-isZero();
+return SC-getValue()-getZExtValue() == 0;
return false;
}
@@ -883,18 +883,17 @@
if (!TLI) return 0;
if (SCEVConstant *SC = dyn_castSCEVConstant(Stride)) {
-APInt SInt(SC-getValue()-getValue());
-if (SInt == 1)
- return 0;
+int64_t SInt = SC-getValue()-getSExtValue();
+if (SInt == 1) return 0;
for (TargetLowering::legal_am_scale_iterator
I = TLI-legal_am_scale_begin(), E = TLI-legal_am_scale_end();
I != E; ++I) {
- APInt Scale(SInt.getBitWidth(), *I);
- if (SInt.abs().ult(Scale) || SInt.srem(Scale) != 0)
+ unsigned Scale = *I;
+ if (unsigned(abs(SInt)) Scale || (SInt % Scale) != 0)
continue;
std::mapSCEVHandle, IVsOfOneStride::iterator SI =
-IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt.sdiv(Scale)));
+IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt/Scale, UIntPtrTy));
if (SI == IVsByStride.end())
continue;
for (std::vectorIVExpr::iterator II = SI-second.IVs.begin(),
@@ -903,7 +902,7 @@
// Only reuse previous IV if it would not require a type conversion.
if (isZero(II-Base) II-Base-getType() == Ty) {
IV = *II;
- return Scale.getZExtValue();
+ return Scale;
}
}
}
@@ -1149,14 +1148,14 @@
// are reusing an IV, it has not been used to initialize the PHI node.
// Add it to the expression used to rewrite the uses.
if (!isaConstantInt(CommonBaseV) ||
-!castConstantInt(CommonBaseV)-isZero())
+!castConstantInt(CommonBaseV)-isNullValue())
RewriteExpr = SCEVAddExpr::get(RewriteExpr,
SCEVUnknown::get(CommonBaseV));
}
// Now that we know what we need to do, insert code before User for the
// immediate and any loop-variant expressions.
- if (!isaConstantInt(BaseV) || !castConstantInt(BaseV)-isZero())
+ if (!isaConstantInt(BaseV) || !castConstantInt(BaseV)-isNullValue())
// Add BaseV to the PHI value if needed.
RewriteExpr = SCEVAddExpr::get(RewriteExpr, SCEVUnknown::get(BaseV));
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.113 - 1.114
---
Log message:
Finally get this patch right :)
Replace expensive getZExtValue() == 0 calls with isZero() calls.
---
Diffs of the changes: (+5 -5)
LoopStrengthReduce.cpp | 10 +-
1 files changed, 5 insertions(+), 5 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.113
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.114
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.113 Fri Mar 2
17:37:53 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri Mar 2 17:51:25 2007
@@ -540,7 +540,7 @@
// If there is no immediate value, skip the next part.
if (SCEVConstant *SC = dyn_castSCEVConstant(Imm))
-if (SC-getValue()-isNullValue())
+if (SC-getValue()-isZero())
return Rewriter.expandCodeFor(NewBase, BaseInsertPt,
OperandValToReplace-getType());
@@ -779,7 +779,7 @@
SeparateSubExprs(SubExprs, SARE-getOperand(0));
}
} else if (!isaSCEVConstant(Expr) ||
- !castSCEVConstant(Expr)-getValue()-isNullValue()) {
+ !castSCEVConstant(Expr)-getValue()-isZero()) {
// Do not add zero.
SubExprs.push_back(Expr);
}
@@ -869,7 +869,7 @@
///
static bool isZero(SCEVHandle V) {
if (SCEVConstant *SC = dyn_castSCEVConstant(V))
-return SC-getValue()-getZExtValue() == 0;
+return SC-getValue()-isZero();
return false;
}
@@ -1148,14 +1148,14 @@
// are reusing an IV, it has not been used to initialize the PHI node.
// Add it to the expression used to rewrite the uses.
if (!isaConstantInt(CommonBaseV) ||
-!castConstantInt(CommonBaseV)-isNullValue())
+!castConstantInt(CommonBaseV)-isZero())
RewriteExpr = SCEVAddExpr::get(RewriteExpr,
SCEVUnknown::get(CommonBaseV));
}
// Now that we know what we need to do, insert code before User for the
// immediate and any loop-variant expressions.
- if (!isaConstantInt(BaseV) || !castConstantInt(BaseV)-isNullValue())
+ if (!isaConstantInt(BaseV) || !castConstantInt(BaseV)-isZero())
// Add BaseV to the PHI value if needed.
RewriteExpr = SCEVAddExpr::get(RewriteExpr, SCEVUnknown::get(BaseV));
___
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/LoopStrengthReduce.cpp ScalarReplAggregates.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.108 - 1.109
ScalarReplAggregates.cpp updated: 1.70 - 1.71
---
Log message:
Privatize StructLayout::MemberOffsets, adding an accessor
---
Diffs of the changes: (+3 -2)
LoopStrengthReduce.cpp |2 +-
ScalarReplAggregates.cpp |3 ++-
2 files changed, 3 insertions(+), 2 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.108
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.109
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.108 Mon Feb 5
17:32:05 2007
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Sat Feb 10 13:55:17 2007
@@ -267,7 +267,7 @@
if (const StructType *STy = dyn_castStructType(*GTI)) {
const StructLayout *SL = TD-getStructLayout(STy);
unsigned Idx = castConstantInt(GEP-getOperand(i))-getZExtValue();
- uint64_t Offset = SL-MemberOffsets[Idx];
+ uint64_t Offset = SL-getElementOffset(Idx);
GEPVal = SCEVAddExpr::get(GEPVal,
SCEVUnknown::getIntegerSCEV(Offset,
UIntPtrTy));
} else {
Index: llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp
diff -u llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp:1.70
llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp:1.71
--- llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp:1.70Fri Feb 2
08:08:20 2007
+++ llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp Sat Feb 10 13:55:17 2007
@@ -801,7 +801,8 @@
else
NewOffset += AggSizeInBits-ElSizeBits*(Idx+1);
} else if (const StructType *STy = dyn_castStructType(AggTy)) {
- unsigned EltBitOffset =
TD.getStructLayout(STy)-MemberOffsets[Idx]*8;
+ unsigned EltBitOffset =
+TD.getStructLayout(STy)-getElementOffset(Idx)*8;
if (TD.isLittleEndian() || isVectorInsert)
NewOffset += EltBitOffset;
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopStrengthReduce.cpp updated: 1.104 - 1.105 --- Log message: For PR1097: http://llvm.org/PR1097 : Enable complex addressing modes on 64-bit platforms involving two induction variables by keeping a size and scale in 64-bits not 32. Patch by Dan Gohman. --- Diffs of the changes: (+1 -1) LoopStrengthReduce.cpp |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.104 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.105 --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.104 Fri Jan 5 19:37:35 2007 +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Mon Jan 8 10:17:51 2007 @@ -893,7 +893,7 @@ if (unsigned(abs(SInt)) Scale || (SInt % Scale) != 0) continue; std::mapSCEVHandle, IVsOfOneStride::iterator SI = -IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt/Scale, Type::Int32Ty)); +IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt/Scale, UIntPtrTy)); if (SI == IVsByStride.end()) continue; for (std::vectorIVExpr::iterator II = SI-second.IVs.begin(), ___ 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.103 - 1.104
---
Log message:
no need to worry about int vs uint any more.
---
Diffs of the changes: (+1 -2)
LoopStrengthReduce.cpp |3 +--
1 files changed, 1 insertion(+), 2 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.103
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.104
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.103 Sat Dec 30
23:48:39 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri Jan 5 19:37:35 2007
@@ -900,8 +900,7 @@
IE = SI-second.IVs.end(); II != IE; ++II)
// FIXME: Only handle base == 0 for now.
// Only reuse previous IV if it would not require a type conversion.
-if (isZero(II-Base)
-II-Base-getType()-canLosslesslyBitCastTo(Ty)) {
+if (isZero(II-Base) II-Base-getType() == Ty) {
IV = *II;
return Scale;
}
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.99 - 1.100
---
Log message:
Change the interface to SCEVExpander::InsertCastOfTo to take a cast opcode
so the decision of which opcode to use is pushed upward to the caller.
Adjust the callers to pass the expected opcode.
---
Diffs of the changes: (+21 -12)
LoopStrengthReduce.cpp | 33 +
1 files changed, 21 insertions(+), 12 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.99
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.100
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.99 Mon Dec 11
23:04:59 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Wed Dec 13 02:06:42 2006
@@ -177,7 +177,7 @@
/// getCastedVersionOf - Return the specified value casted to uintptr_t.
///
-Value *getCastedVersionOf(Value *V);
+Value *getCastedVersionOf(Instruction::CastOps opcode, Value *V);
private:
void runOnLoop(Loop *L);
bool AddUsersIfInteresting(Instruction *I, Loop *L,
@@ -203,19 +203,16 @@
/// getCastedVersionOf - Return the specified value casted to uintptr_t. This
/// assumes that the Value* V is of integer or pointer type only.
///
-Value *LoopStrengthReduce::getCastedVersionOf(Value *V) {
+Value *LoopStrengthReduce::getCastedVersionOf(Instruction::CastOps opcode,
+ Value *V) {
if (V-getType() == UIntPtrTy) return V;
if (Constant *CB = dyn_castConstant(V))
-if (CB-getType()-isInteger())
- return ConstantExpr::getIntegerCast(CB, UIntPtrTy,
- CB-getType()-isSigned());
-else
- return ConstantExpr::getPtrToInt(CB, UIntPtrTy);
+return ConstantExpr::getCast(opcode, CB, UIntPtrTy);
Value *New = CastedPointers[V];
if (New) return New;
- New = SCEVExpander::InsertCastOfTo(V, UIntPtrTy);
+ New = SCEVExpander::InsertCastOfTo(opcode, V, UIntPtrTy);
DeadInsts.insert(castInstruction(New));
return New;
}
@@ -258,7 +255,8 @@
// Build up the base expression. Insert an LLVM cast of the pointer to
// uintptr_t first.
- SCEVHandle GEPVal = SCEVUnknown::get(getCastedVersionOf(GEP-getOperand(0)));
+ SCEVHandle GEPVal = SCEVUnknown::get(
+ getCastedVersionOf(Instruction::PtrToInt, GEP-getOperand(0)));
gep_type_iterator GTI = gep_type_begin(GEP);
@@ -273,7 +271,13 @@
GEPVal = SCEVAddExpr::get(GEPVal,
SCEVUnknown::getIntegerSCEV(Offset,
UIntPtrTy));
} else {
- Value *OpVal = getCastedVersionOf(GEP-getOperand(i));
+ unsigned GEPOpiBits =
+GEP-getOperand(i)-getType()-getPrimitiveSizeInBits();
+ unsigned IntPtrBits = UIntPtrTy-getPrimitiveSizeInBits();
+ Instruction::CastOps opcode = (GEPOpiBits IntPtrBits ?
+ Instruction::SExt : (GEPOpiBits IntPtrBits ? Instruction::Trunc :
+Instruction::BitCast));
+ Value *OpVal = getCastedVersionOf(opcode, GEP-getOperand(i));
SCEVHandle Idx = SE-getSCEV(OpVal);
uint64_t TypeSize = TD-getTypeSize(GTI.getIndexedType());
@@ -1125,8 +1129,13 @@
if (L-contains(User.Inst-getParent()))
User.Inst-moveBefore(LatchBlock-getTerminator());
}
- if (RewriteOp-getType() != ReplacedTy)
-RewriteOp = SCEVExpander::InsertCastOfTo(RewriteOp, ReplacedTy);
+ if (RewriteOp-getType() != ReplacedTy) {
+Instruction::CastOps opcode = Instruction::Trunc;
+if (ReplacedTy-getPrimitiveSizeInBits() ==
+RewriteOp-getType()-getPrimitiveSizeInBits())
+ opcode = Instruction::BitCast;
+RewriteOp = SCEVExpander::InsertCastOfTo(opcode, RewriteOp,
ReplacedTy);
+ }
SCEVHandle RewriteExpr = SCEVUnknown::get(RewriteOp);
___
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/LoopStrengthReduce.cpp SCCP.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.98 - 1.99
SCCP.cpp updated: 1.140 - 1.141
---
Log message:
Change inferred getCast into specific getCast. Passes all tests.
---
Diffs of the changes: (+9 -3)
LoopStrengthReduce.cpp |9 +++--
SCCP.cpp |3 ++-
2 files changed, 9 insertions(+), 3 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.98
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.99
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.98 Wed Dec 6
19:30:31 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Mon Dec 11 23:04:59 2006
@@ -200,12 +200,17 @@
return new LoopStrengthReduce(TLI);
}
-/// getCastedVersionOf - Return the specified value casted to uintptr_t.
+/// getCastedVersionOf - Return the specified value casted to uintptr_t. This
+/// assumes that the Value* V is of integer or pointer type only.
///
Value *LoopStrengthReduce::getCastedVersionOf(Value *V) {
if (V-getType() == UIntPtrTy) return V;
if (Constant *CB = dyn_castConstant(V))
-return ConstantExpr::getCast(CB, UIntPtrTy);
+if (CB-getType()-isInteger())
+ return ConstantExpr::getIntegerCast(CB, UIntPtrTy,
+ CB-getType()-isSigned());
+else
+ return ConstantExpr::getPtrToInt(CB, UIntPtrTy);
Value *New = CastedPointers[V];
if (New) return New;
Index: llvm/lib/Transforms/Scalar/SCCP.cpp
diff -u llvm/lib/Transforms/Scalar/SCCP.cpp:1.140
llvm/lib/Transforms/Scalar/SCCP.cpp:1.141
--- llvm/lib/Transforms/Scalar/SCCP.cpp:1.140 Wed Dec 6 19:30:31 2006
+++ llvm/lib/Transforms/Scalar/SCCP.cpp Mon Dec 11 23:04:59 2006
@@ -589,7 +589,8 @@
if (VState.isOverdefined()) // Inherit overdefinedness of operand
markOverdefined(I);
else if (VState.isConstant())// Propagate constant value
-markConstant(I, ConstantExpr::getCast(VState.getConstant(), I.getType()));
+markConstant(I, ConstantExpr::getCast(I.getOpcode(),
+ VState.getConstant(), I.getType()));
}
void SCCPSolver::visitSelectInst(SelectInst 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.86 - 1.87
---
Log message:
Changes:
1. Update an obsolete comment.
2. Make the sorting by base an explicit (though still N^2) step, so
that the code is more clear on what it is doing.
3. Partition uses so that uses inside the loop are handled before uses
outside the loop.
Note that none of these changes currently changes the code inserted by LSR,
but they are a stepping stone to getting there.
This code is the result of some crazy pair programming with Nate. :)
---
Diffs of the changes: (+46 -17)
LoopStrengthReduce.cpp | 63 +++--
1 files changed, 46 insertions(+), 17 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.86
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.87
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.86 Tue Jul 18
14:07:58 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Thu Aug 3 01:34:50 2006
@@ -750,9 +750,9 @@
}
-/// IncrementAddExprUses - Decompose the specified expression into its added
-/// subexpressions, and increment SubExpressionUseCounts for each of these
-/// decomposed parts.
+/// SeparateSubExprs - Decompose Expr into all of the subexpressions that are
+/// added together. This is used to reassociate common addition subexprs
+/// together for maximal sharing when rewriting bases.
static void SeparateSubExprs(std::vectorSCEVHandle SubExprs,
SCEVHandle Expr) {
if (SCEVAddExpr *AE = dyn_castSCEVAddExpr(Expr)) {
@@ -904,6 +904,11 @@
return 0;
}
+/// PartitionByIsUseOfPostIncrementedValue - Simple boolean predicate that
+/// returns true if Val's isUseOfPostIncrementedValue is true.
+static bool PartitionByIsUseOfPostIncrementedValue(const BasedUser Val) {
+ return Val.isUseOfPostIncrementedValue;
+}
/// StrengthReduceStridedIVUsers - Strength reduce all of the users of a single
/// stride of IV. All of the users may have different starting values, and
this
@@ -1039,8 +1044,38 @@
commonbase, PreInsertPt);
}
- // Sort by the base value, so that all IVs with identical bases are next to
- // each other.
+ // We want to emit code for users inside the loop first. To do this, we
+ // rearrange BasedUser so that the entries at the end have
+ // isUseOfPostIncrementedValue = false, because we pop off the end of the
+ // vector (so we handle them first).
+ std::partition(UsersToProcess.begin(), UsersToProcess.end(),
+ PartitionByIsUseOfPostIncrementedValue);
+
+ // Sort this by base, so that things with the same base are handled
+ // together. By partitioning first and stable-sorting later, we are
+ // guaranteed that within each base we will pop off users from within the
+ // loop before users outside of the loop with a particular base.
+ //
+ // We would like to use stable_sort here, but we can't. The problem is that
+ // SCEVHandle's don't have a deterministic ordering w.r.t to each other, so
+ // we don't have anything to do a '' comparison on. Because we think the
+ // number of uses is small, do a horrible bubble sort which just relies on
+ // ==.
+ for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) {
+// Get a base value.
+SCEVHandle Base = UsersToProcess[i].Base;
+
+// Compact everything with this base to be consequetive with this one.
+for (unsigned j = i+1; j != e; ++j) {
+ if (UsersToProcess[j].Base == Base) {
+std::swap(UsersToProcess[i+1], UsersToProcess[j]);
+++i;
+ }
+}
+ }
+
+ // Process all the users now. This outer loop handles all bases, the inner
+ // loop handles all users of a particular base.
while (!UsersToProcess.empty()) {
SCEVHandle Base = UsersToProcess.back().Base;
@@ -1054,17 +1089,18 @@
// the preheader, instead of being forward substituted into the uses. We
do
// this by forcing a noop cast to be inserted into the preheader in this
// case.
-if (Constant *C = dyn_castConstant(BaseV))
+if (Constant *C = dyn_castConstant(BaseV)) {
if (!C-isNullValue() !isTargetConstant(Base, TLI)) {
// We want this constant emitted into the preheader!
BaseV = new CastInst(BaseV, BaseV-getType(), preheaderinsert,
PreInsertPt);
}
-
+}
+
// Emit the code to add the immediate offset to the Phi value, just before
// the instructions that we identified as using this stride and base.
-unsigned ScanPos = 0;
do {
+ // FIXME: Use emitted users to emit other users.
BasedUser User = UsersToProcess.back();
// If this instruction wants to use the post-incremented value, move it
@@ -1119,15 +1155,8 @@
UsersToProcess.pop_back();
++NumReduced;
- // If there are
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp LowerAllocations.cpp ScalarReplAggregates.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.84 - 1.85
LowerAllocations.cpp updated: 1.58 - 1.59
ScalarReplAggregates.cpp updated: 1.39 - 1.40
---
Log message:
Use hidden visibility to make symbols in an anonymous namespace get
dropped. This shrinks libllvmgcc.dylib another 67K
---
Diffs of the changes: (+7 -4)
LoopStrengthReduce.cpp |3 ++-
LowerAllocations.cpp |3 ++-
ScalarReplAggregates.cpp |5 +++--
3 files changed, 7 insertions(+), 4 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.84
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.85
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.84 Thu Jun 8
19:12:42 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Wed Jun 28 18:17:24 2006
@@ -31,6 +31,7 @@
#include llvm/Target/TargetData.h
#include llvm/ADT/Statistic.h
#include llvm/Support/Debug.h
+#include llvm/Support/Visibility.h
#include llvm/Target/TargetLowering.h
#include algorithm
#include iostream
@@ -104,7 +105,7 @@
}
};
- class LoopStrengthReduce : public FunctionPass {
+ class VISIBILITY_HIDDEN LoopStrengthReduce : public FunctionPass {
LoopInfo *LI;
ETForest *EF;
ScalarEvolution *SE;
Index: llvm/lib/Transforms/Scalar/LowerAllocations.cpp
diff -u llvm/lib/Transforms/Scalar/LowerAllocations.cpp:1.58
llvm/lib/Transforms/Scalar/LowerAllocations.cpp:1.59
--- llvm/lib/Transforms/Scalar/LowerAllocations.cpp:1.58Wed May 17
16:05:27 2006
+++ llvm/lib/Transforms/Scalar/LowerAllocations.cpp Wed Jun 28 18:17:24 2006
@@ -21,6 +21,7 @@
#include llvm/Pass.h
#include llvm/ADT/Statistic.h
#include llvm/Target/TargetData.h
+#include llvm/Support/Visibility.h
using namespace llvm;
namespace {
@@ -29,7 +30,7 @@
/// LowerAllocations - Turn malloc and free instructions into %malloc and
/// %free calls.
///
- class LowerAllocations : public BasicBlockPass {
+ class VISIBILITY_HIDDEN LowerAllocations : public BasicBlockPass {
Function *MallocFunc; // Functions in the module we are processing
Function *FreeFunc; // Initialized by doInitialization
bool LowerMallocArgToInteger;
Index: llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp
diff -u llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp:1.39
llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp:1.40
--- llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp:1.39Thu Apr 20
15:48:50 2006
+++ llvm/lib/Transforms/Scalar/ScalarReplAggregates.cpp Wed Jun 28 18:17:24 2006
@@ -28,9 +28,10 @@
#include llvm/Analysis/Dominators.h
#include llvm/Target/TargetData.h
#include llvm/Transforms/Utils/PromoteMemToReg.h
+#include llvm/Support/Debug.h
#include llvm/Support/GetElementPtrTypeIterator.h
#include llvm/Support/MathExtras.h
-#include llvm/Support/Debug.h
+#include llvm/Support/Visibility.h
#include llvm/ADT/Statistic.h
#include llvm/ADT/StringExtras.h
#include iostream
@@ -42,7 +43,7 @@
Statistic NumConverted(scalarrepl,
Number of aggregates converted to scalar);
- struct SROA : public FunctionPass {
+ struct VISIBILITY_HIDDEN SROA : public FunctionPass {
bool runOnFunction(Function F);
bool performScalarRepl(Function F);
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopStrengthReduce.cpp updated: 1.83 - 1.84 --- Log message: RewriteExpr, either the new PHI node of induction variable or the post-increment value, should be first cast to the appropriated type (to the type of the common expr). Otherwise, the rewrite of a use based on (common + iv) may end up with an incorrect type. --- Diffs of the changes: (+3 -0) LoopStrengthReduce.cpp |3 +++ 1 files changed, 3 insertions(+) Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.83 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.84 --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.83 Wed Apr 12 14:28:15 2006 +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Thu Jun 8 19:12:42 2006 @@ -1074,6 +1074,9 @@ if (L-contains(User.Inst-getParent())) User.Inst-moveBefore(LatchBlock-getTerminator()); } + if (RewriteOp-getType() != ReplacedTy) +RewriteOp = SCEVExpander::InsertCastOfTo(RewriteOp, ReplacedTy); + SCEVHandle RewriteExpr = SCEVUnknown::get(RewriteOp); // Clear the SCEVExpander's expression map so that we are guaranteed ___ 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopStrengthReduce.cpp updated: 1.81 - 1.82 --- Log message: Fix spello --- Diffs of the changes: (+2 -2) LoopStrengthReduce.cpp |4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.81 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.82 --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.81 Wed Mar 22 11:27:24 2006 +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri Mar 24 01:14:34 2006 @@ -1140,7 +1140,7 @@ // Finally, get the terminating condition for the loop if possible. If we // can, we want to change it to use a post-incremented version of its - // induction variable, to allow coallescing the live ranges for the IV into + // induction variable, to allow coalescing the live ranges for the IV into // one register value. PHINode *SomePHI = castPHINode(L-getHeader()-begin()); BasicBlock *Preheader = L-getLoopPreheader(); @@ -1199,7 +1199,7 @@ } // If we get to here, we know that we can transform the setcc instruction to - // use the post-incremented version of the IV, allowing us to coallesce the + // use the post-incremented version of the IV, allowing us to coalesce the // live ranges for the IV correctly. CondUse-Offset = SCEV::getMinusSCEV(CondUse-Offset, *CondStride); CondUse-isUseOfPostIncrementedValue = 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar: LoopStrengthReduce.cpp updated: 1.80 - 1.81 --- Log message: silence a bogus gcc warning --- Diffs of the changes: (+2 -2) LoopStrengthReduce.cpp |4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.80 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.81 --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.80 Sat Mar 18 02:03:12 2006 +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Wed Mar 22 11:27:24 2006 @@ -1223,8 +1223,8 @@ return LV RV; else return ALV ARV; - } else -return (LHSC !RHSC); + } + return (LHSC !RHSC); } }; } ___ 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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.79 - 1.80
---
Log message:
- Fixed a bogus if condition.
- Added more debugging info.
- Allow reuse of IV of negative stride. e.g. -4 stride == 2 * iv of -2 stride.
---
Diffs of the changes: (+25 -19)
LoopStrengthReduce.cpp | 44 +---
1 files changed, 25 insertions(+), 19 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.79
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.80
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.79 Fri Mar 17
18:44:49 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Sat Mar 18 02:03:12 2006
@@ -77,15 +77,20 @@
};
/// IVInfo - This structure keeps track of one IV expression inserted during
- /// StrengthReduceStridedIVUsers. It contains the base value, as well as the
- /// PHI node and increment value created for rewrite.
+ /// StrengthReduceStridedIVUsers. It contains the stride, the common base, as
+ /// well as the PHI node and increment value created for rewrite.
struct IVExpr {
+SCEVHandle Stride;
SCEVHandle Base;
PHINode*PHI;
Value *IncV;
-IVExpr(const SCEVHandle base, PHINode *phi, Value *incv)
- : Base(base), PHI(phi), IncV(incv) {}
+IVExpr()
+ : Stride(SCEVUnknown::getIntegerSCEV(0, Type::UIntTy)),
+Base (SCEVUnknown::getIntegerSCEV(0, Type::UIntTy)) {}
+IVExpr(const SCEVHandle stride, const SCEVHandle base, PHINode *phi,
+ Value *incv)
+ : Stride(stride), Base(base), PHI(phi), IncV(incv) {}
};
/// IVsOfOneStride - This structure keeps track of all IV expression inserted
@@ -93,8 +98,9 @@
struct IVsOfOneStride {
std::vectorIVExpr IVs;
-void addIV(const SCEVHandle Base, PHINode *PHI, Value *IncV) {
- IVs.push_back(IVExpr(Base, PHI, IncV));
+void addIV(const SCEVHandle Stride, const SCEVHandle Base, PHINode *PHI,
+ Value *IncV) {
+ IVs.push_back(IVExpr(Stride, Base, PHI, IncV));
}
};
@@ -863,22 +869,20 @@
/// CheckForIVReuse - Returns the multiple if the stride is the multiple
/// of a previous stride and it is a legal value for the target addressing
/// mode scale component. This allows the users of this stride to be rewritten
-/// as prev iv * factor. It returns 1 if no reuse is possible.
+/// as prev iv * factor. It returns 0 if no reuse is possible.
unsigned LoopStrengthReduce::CheckForIVReuse(const SCEVHandle Stride,
IVExpr IV) {
- if (!TLI)
-return 1;
+ if (!TLI) return 0;
if (SCEVConstant *SC = dyn_castSCEVConstant(Stride)) {
-unsigned SInt = SC-getValue()-getRawValue();
-if (SInt == 1)
- return 1;
+int64_t SInt = SC-getValue()-getSExtValue();
+if (SInt == 1) return 0;
for (TargetLowering::legal_am_scale_iterator
I = TLI-legal_am_scale_begin(), E = TLI-legal_am_scale_end();
I != E; ++I) {
unsigned Scale = *I;
- if (SInt = Scale (SInt % Scale) != 0)
+ if (abs(SInt) Scale || (SInt % Scale) != 0)
continue;
std::mapSCEVHandle, IVsOfOneStride::iterator SI =
IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt/Scale,
Type::UIntTy));
@@ -894,7 +898,7 @@
}
}
- return 1;
+ return 0;
}
@@ -929,9 +933,11 @@
// field of the target addressing mode.
PHINode *NewPHI = NULL;
Value *IncV = NULL;
- IVExpr ReuseIV(Stride, NULL, NULL);
+ IVExpr ReuseIV;
unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV);
- if (RewriteFactor 1) {
+ if (RewriteFactor != 0) {
+DEBUG(std::cerr BASED ON IV of STRIDE *ReuseIV.Stride
+and BASE *ReuseIV.Base :\n);
NewPHI = ReuseIV.PHI;
IncV = ReuseIV.IncV;
}
@@ -994,7 +1000,7 @@
= PreheaderRewriter.expandCodeFor(CommonExprs, PreInsertPt,
ReplacedTy);
- if (RewriteFactor == 1) {
+ if (RewriteFactor == 0) {
// Create a new Phi for this base, and stick it in the loop header.
NewPHI = new PHINode(ReplacedTy, iv., PhiInsertBefore);
++NumInserted;
@@ -1018,7 +1024,7 @@
NewPHI-addIncoming(IncV, LatchBlock);
// Remember this in case a later stride is multiple of this.
-IVsByStride[Stride].addIV(CommonExprs, NewPHI, IncV);
+IVsByStride[Stride].addIV(Stride, CommonExprs, NewPHI, IncV);
} else {
Constant *C = dyn_castConstant(CommonBaseV);
if (!C ||
@@ -1076,7 +1082,7 @@
// If we are reusing the iv, then it must be multiplied by a constant
// factor take advantage of addressing mode scale component.
- if (RewriteFactor != 1) {
+ if (RewriteFactor != 0) {
RewriteExpr =
SCEVMulExpr::get(SCEVUnknown::getIntegerSCEV(RewriteFactor,
RewriteExpr-getType()),
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.77 - 1.78
---
Log message:
Allow users of iv / stride to be rewritten with expression that is a multiply
of a smaller stride even if they have a common loop invariant expression part.
---
Diffs of the changes: (+83 -41)
LoopStrengthReduce.cpp | 124 -
1 files changed, 83 insertions(+), 41 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.77
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.78
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.77 Thu Mar 16
15:53:05 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri Mar 17 13:52:23 2006
@@ -180,6 +180,8 @@
void OptimizeIndvars(Loop *L);
+unsigned CheckForIVReuse(const SCEVHandle Stride, IVExpr IV);
+
void StrengthReduceStridedIVUsers(const SCEVHandle Stride,
IVUsersOfOneStride Uses,
Loop *L, bool isOnlyStride);
@@ -858,6 +860,44 @@
}
+/// CheckForIVReuse - Returns the multiple if the stride is the multiple
+/// of a previous stride and it is a legal value for the target addressing
+/// mode scale component. This allows the users of this stride to be rewritten
+/// as prev iv * factor. It returns 1 if no reuse is possible.
+unsigned LoopStrengthReduce::CheckForIVReuse(const SCEVHandle Stride,
+ IVExpr IV) {
+ if (!TLI)
+return 1;
+
+ if (SCEVConstant *SC = dyn_castSCEVConstant(Stride)) {
+unsigned SInt = SC-getValue()-getRawValue();
+if (SInt == 1)
+ return 1;
+
+for (TargetLowering::legal_am_scale_iterator
+ I = TLI-legal_am_scale_begin(), E = TLI-legal_am_scale_end();
+ I != E; ++I) {
+ unsigned Scale = *I;
+ if (SInt = Scale (SInt % Scale) != 0)
+continue;
+ std::mapSCEVHandle, IVsOfOneStride::iterator SI =
+IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt/Scale,
Type::UIntTy));
+ if (SI == IVsByStride.end())
+continue;
+ for (std::vectorIVExpr::iterator II = SI-second.IVs.begin(),
+ IE = SI-second.IVs.end(); II != IE; ++II)
+// FIXME: Only handle base == 0 for now.
+if (isZero(II-Base)) {
+ IV = *II;
+ return Scale;
+}
+}
+ }
+
+ return 1;
+}
+
+
/// StrengthReduceStridedIVUsers - Strength reduce all of the users of a single
/// stride of IV. All of the users may have different starting values, and
this
/// may not be the only stride (we know it is if isOnlyStride is true).
@@ -883,7 +923,19 @@
assert(UsersToProcess.back().Base-isLoopInvariant(L)
Base value is not loop invariant!);
}
-
+
+ // Check if it is possible to reuse a IV with stride that is factor of this
+ // stride. And the multiple is a number that can be encoded in the scale
+ // field of the target addressing mode.
+ PHINode *NewPHI = NULL;
+ Value *IncV = NULL;
+ IVExpr ReuseIV(Stride, NULL, NULL);
+ unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV);
+ if (RewriteFactor 1) {
+NewPHI = ReuseIV.PHI;
+IncV = ReuseIV.IncV;
+ }
+
// We now have a whole bunch of uses of like-strided induction variables, but
// they might all have different bases. We want to emit one PHI node for
this
// stride which we fold as many common expressions (between the IVs) into as
@@ -935,55 +987,26 @@
BasicBlock *LatchBlock = L-getLoopLatch();
- unsigned RewriteFactor = 1;
- PHINode *NewPHI = NULL;
- Value *IncV = NULL;
- // FIXME: Only handle base == 0 for now.
- if (TLI isZero(CommonExprs)) {
-if (SCEVConstant *SC = dyn_castSCEVConstant(Stride)) {
- unsigned SInt = SC-getValue()-getRawValue();
- for (TargetLowering::legal_am_scale_iterator
- I = TLI-legal_am_scale_begin(), E = TLI-legal_am_scale_end();
- I != E; ++I) {
-unsigned Scale = *I;
-if ((SInt % Scale) != 0)
- continue;
-std::mapSCEVHandle, IVsOfOneStride::iterator SI =
-IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt/Scale,
Type::UIntTy));
-if (SI == IVsByStride.end())
- continue;
-for (std::vectorIVExpr::iterator II = SI-second.IVs.begin(),
- IE = SI-second.IVs.end(); II != IE; ++II)
- if (isZero(II-Base)) {
-RewriteFactor = Scale;
-NewPHI = II-PHI;
-IncV = II-IncV;
-break;
- }
-if (RewriteFactor != 1)
- break;
- }
-}
- }
-
const Type *ReplacedTy = CommonExprs-getType();
+
+ // Emit the initial base value into the loop preheader.
+ Value *CommonBaseV
+= PreheaderRewriter.expandCodeFor(CommonExprs, PreInsertPt,
+ ReplacedTy);
+
if (RewriteFactor == 1) {
// Create
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.78 - 1.79
---
Log message:
Sort StrideOrder so we can process the smallest strides first. This allows
for more IV reuses.
---
Diffs of the changes: (+27 -0)
LoopStrengthReduce.cpp | 27 +++
1 files changed, 27 insertions(+)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.78
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.79
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.78 Fri Mar 17
13:52:23 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Fri Mar 17 18:44:49 2006
@@ -1199,6 +1199,30 @@
CondUse-isUseOfPostIncrementedValue = true;
}
+namespace {
+ // Constant strides come first which in turns are sorted by their absolute
+ // values. If absolute values are the same, then positive strides comes
first.
+ // e.g.
+ // 4, -1, X, 1, 2 == 1, -1, 2, 4, X
+ struct StrideCompare {
+bool operator()(const SCEVHandle LHS, const SCEVHandle RHS) {
+ SCEVConstant *LHSC = dyn_castSCEVConstant(LHS);
+ SCEVConstant *RHSC = dyn_castSCEVConstant(RHS);
+ if (LHSC RHSC) {
+int64_t LV = LHSC-getValue()-getSExtValue();
+int64_t RV = RHSC-getValue()-getSExtValue();
+uint64_t ALV = (LV 0) ? -LV : LV;
+uint64_t ARV = (RV 0) ? -RV : RV;
+if (ALV == ARV)
+ return LV RV;
+else
+ return ALV ARV;
+ } else
+return (LHSC !RHSC);
+}
+ };
+}
+
void LoopStrengthReduce::runOnLoop(Loop *L) {
// First step, transform all loops nesting inside of this loop.
for (LoopInfo::iterator I = L-begin(), E = L-end(); I != E; ++I)
@@ -1241,6 +1265,9 @@
// IVsByStride keeps IVs for one particular loop.
IVsByStride.clear();
+ // Sort the StrideOrder so we process larger strides first.
+ std::stable_sort(StrideOrder.begin(), StrideOrder.end(), StrideCompare());
+
// Note: this processes each stride/type pair individually. All users passed
// into StrengthReduceStridedIVUsers have the same type AND stride. Also,
// node that we iterate over IVUsesByStride indirectly by using StrideOrder.
___
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/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.76 - 1.77
---
Log message:
For each loop, keep track of all the IV expressions inserted indexed by
stride. For a set of uses of the IV of a stride which is a multiple
of another stride, do not insert a new IV expression. Rather, reuse the
previous IV and rewrite the uses as uses of IV expression multiplied by
the factor.
e.g.
x = 0 ...; x ++
y = 0 ...; y += 4
then use of y can be rewritten as use of 4*x for x86.
---
Diffs of the changes: (+119 -40)
LoopStrengthReduce.cpp | 159 -
1 files changed, 119 insertions(+), 40 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.76
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.77
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.76 Mon Mar 13
17:14:23 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Thu Mar 16 15:53:05 2006
@@ -76,6 +76,27 @@
}
};
+ /// IVInfo - This structure keeps track of one IV expression inserted during
+ /// StrengthReduceStridedIVUsers. It contains the base value, as well as the
+ /// PHI node and increment value created for rewrite.
+ struct IVExpr {
+SCEVHandle Base;
+PHINode*PHI;
+Value *IncV;
+
+IVExpr(const SCEVHandle base, PHINode *phi, Value *incv)
+ : Base(base), PHI(phi), IncV(incv) {}
+ };
+
+ /// IVsOfOneStride - This structure keeps track of all IV expression inserted
+ /// during StrengthReduceStridedIVUsers for a particular stride of the IV.
+ struct IVsOfOneStride {
+std::vectorIVExpr IVs;
+
+void addIV(const SCEVHandle Base, PHINode *PHI, Value *IncV) {
+ IVs.push_back(IVExpr(Base, PHI, IncV));
+}
+ };
class LoopStrengthReduce : public FunctionPass {
LoopInfo *LI;
@@ -85,14 +106,14 @@
const Type *UIntPtrTy;
bool Changed;
-/// MaxTargetAMSize - This is the maximum power-of-two scale value that the
-/// target can handle for free with its addressing modes.
-unsigned MaxTargetAMSize;
-
/// IVUsesByStride - Keep track of all uses of induction variables that we
/// are interested in. The key of the map is the stride of the access.
std::mapSCEVHandle, IVUsersOfOneStride IVUsesByStride;
+/// IVsByStride - Keep track of all IVs that have been inserted for a
+/// particular stride.
+std::mapSCEVHandle, IVsOfOneStride IVsByStride;
+
/// StrideOrder - An ordering of the keys in IVUsesByStride that is stable:
/// We use this to iterate over the IVUsesByStride collection without being
/// dependent on random ordering of pointers in the process.
@@ -112,8 +133,8 @@
const TargetLowering *TLI;
public:
-LoopStrengthReduce(unsigned MTAMS = 1, const TargetLowering *tli = NULL)
- : MaxTargetAMSize(MTAMS), TLI(tli) {
+LoopStrengthReduce(const TargetLowering *tli = NULL)
+ : TLI(tli) {
}
virtual bool runOnFunction(Function ) {
@@ -168,9 +189,8 @@
Loop Strength Reduction);
}
-FunctionPass *llvm::createLoopStrengthReducePass(unsigned MaxTargetAMSize,
- const TargetLowering *TLI) {
- return new LoopStrengthReduce(MaxTargetAMSize, TLI);
+FunctionPass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) {
+ return new LoopStrengthReduce(TLI);
}
/// getCastedVersionOf - Return the specified value casted to uintptr_t.
@@ -829,6 +849,14 @@
return Result;
}
+/// isZero - returns true if the scalar evolution expression is zero.
+///
+static bool isZero(SCEVHandle V) {
+ if (SCEVConstant *SC = dyn_castSCEVConstant(V))
+return SC-getValue()-getRawValue() == 0;
+ return false;
+}
+
/// StrengthReduceStridedIVUsers - Strength reduce all of the users of a single
/// stride of IV. All of the users may have different starting values, and
this
@@ -863,7 +891,8 @@
// for the strides (e.g. if we have A+C+B and A+B+D as our bases, find
// A+B), emit it to the preheader, then remove the expression from the
// UsersToProcess base values.
- SCEVHandle CommonExprs = RemoveCommonExpressionsFromUseBases(UsersToProcess);
+ SCEVHandle CommonExprs =
+RemoveCommonExpressionsFromUseBases(UsersToProcess);
// Next, figure out what we can represent in the immediate fields of
// instructions. If we can represent anything there, move it to the imm
@@ -891,12 +920,12 @@
isAddress, L);
}
}
-
+
// Now that we know what we need to do, insert the PHI node itself.
//
DEBUG(std::cerr INSERTING IV of STRIDE *Stride and BASE
*CommonExprs :\n);
-
+
SCEVExpander Rewriter(*SE, *LI);
SCEVExpander PreheaderRewriter(*SE, *LI);
@@ -905,33 +934,68 @@
Instruction *PhiInsertBefore = L-getHeader()-begin();
BasicBlock *LatchBlock =
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.73 - 1.74
---
Log message:
Fix two significant bugs in LSR:
1. When rewriting code in outer loops, sometimes we would insert code into
inner loops that is invariant in that loop.
2. Notice that 4*(2+x) is 8+4*x and use that to simplify expressions.
This is a performance neutral change.
---
Diffs of the changes: (+75 -14)
LoopStrengthReduce.cpp | 89 +
1 files changed, 75 insertions(+), 14 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.73
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.74
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.73 Sun Jan 22
17:32:06 2006
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Sat Feb 4 01:36:50 2006
@@ -477,6 +477,10 @@
void RewriteInstructionToUseNewBase(const SCEVHandle NewBase,
SCEVExpander Rewriter, Loop *L,
Pass *P);
+
+Value *InsertCodeForBaseAtPosition(const SCEVHandle NewBase,
+ SCEVExpander Rewriter,
+ Instruction *IP, Loop *L);
void dump() const;
};
}
@@ -490,6 +494,41 @@
std::cerr Inst: *Inst;
}
+Value *BasedUser::InsertCodeForBaseAtPosition(const SCEVHandle NewBase,
+ SCEVExpander Rewriter,
+ Instruction *IP, Loop *L) {
+ // Figure out where we *really* want to insert this code. In particular, if
+ // the user is inside of a loop that is nested inside of L, we really don't
+ // want to insert this expression before the user, we'd rather pull it out as
+ // many loops as possible.
+ LoopInfo LI = Rewriter.getLoopInfo();
+ Instruction *BaseInsertPt = IP;
+
+ // Figure out the most-nested loop that IP is in.
+ Loop *InsertLoop = LI.getLoopFor(IP-getParent());
+
+ // If InsertLoop is not L, and InsertLoop is nested inside of L, figure out
+ // the preheader of the outer-most loop where NewBase is not loop invariant.
+ while (InsertLoop NewBase-isLoopInvariant(InsertLoop)) {
+BaseInsertPt = InsertLoop-getLoopPreheader()-getTerminator();
+InsertLoop = InsertLoop-getParentLoop();
+ }
+
+ // If there is no immediate value, skip the next part.
+ if (SCEVConstant *SC = dyn_castSCEVConstant(Imm))
+if (SC-getValue()-isNullValue())
+ return Rewriter.expandCodeFor(NewBase, BaseInsertPt,
+OperandValToReplace-getType());
+
+ Value *Base = Rewriter.expandCodeFor(NewBase, BaseInsertPt);
+
+ // Always emit the immediate (if non-zero) into the same block as the user.
+ SCEVHandle NewValSCEV = SCEVAddExpr::get(SCEVUnknown::get(Base), Imm);
+ return Rewriter.expandCodeFor(NewValSCEV, IP,
+OperandValToReplace-getType());
+}
+
+
// Once we rewrite the code to insert the new IVs we want, update the
// operands of Inst to use the new expression 'NewBase', with 'Imm' added
// to it.
@@ -497,9 +536,7 @@
SCEVExpander Rewriter,
Loop *L, Pass *P) {
if (!isaPHINode(Inst)) {
-SCEVHandle NewValSCEV = SCEVAddExpr::get(NewBase, Imm);
-Value *NewVal = Rewriter.expandCodeFor(NewValSCEV, Inst,
- OperandValToReplace-getType());
+Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, Inst, L);
// Replace the use of the operand Value with the new Phi we just created.
Inst-replaceUsesOfWith(OperandValToReplace, NewVal);
DEBUG(std::cerr CHANGED: IMM = *ImmInst = *Inst);
@@ -539,11 +576,8 @@
Value *Code = InsertedCode[PN-getIncomingBlock(i)];
if (!Code) {
// Insert the code into the end of the predecessor block.
-BasicBlock::iterator InsertPt
=PN-getIncomingBlock(i)-getTerminator();
-
-SCEVHandle NewValSCEV = SCEVAddExpr::get(NewBase, Imm);
-Code = Rewriter.expandCodeFor(NewValSCEV, InsertPt,
- OperandValToReplace-getType());
+Instruction *InsertPt = PN-getIncomingBlock(i)-getTerminator();
+Code = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
}
// Replace the use of the operand Value with the new Phi we just created.
@@ -627,16 +661,18 @@
std::vectorSCEVHandle NewOps;
NewOps.reserve(SAE-getNumOperands());
-for (unsigned i = 0; i != SAE-getNumOperands(); ++i)
- if (isAddress isTargetConstant(SAE-getOperand(i))) {
-Imm = SCEVAddExpr::get(Imm, SAE-getOperand(i));
- } else if (!SAE-getOperand(i)-isLoopInvariant(L)) {
+for (unsigned i = 0; i != SAE-getNumOperands(); ++i) {
+ SCEVHandle
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LoopStrengthReduce.cpp updated: 1.70 - 1.71
---
Log message:
getRawValue zero extens for unsigned values, use getsextvalue so that we
know that small negative values fit into the immediate field of addressing
modes.
---
Diffs of the changes: (+3 -3)
LoopStrengthReduce.cpp |6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
diff -u llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.70
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.71
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:1.70 Fri Oct 21
00:45:41 2005
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp Mon Dec 5 12:23:57 2005
@@ -560,9 +560,9 @@
// FIXME: Look at the target to decide if GV is a legal constant immediate.
if (SCEVConstant *SC = dyn_castSCEVConstant(V)) {
// PPC allows a sign-extended 16-bit immediate field.
-if ((int64_t)SC-getValue()-getRawValue() -(1 16)
-(int64_t)SC-getValue()-getRawValue() (1 16)-1)
- return true;
+int64_t V = SC-getValue()-getSExtValue();
+if (V -(1 16) V (1 16)-1)
+return true;
return false;
}
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
