Extended Description

The strength reduction pass is causing the code generator to miss opportunities
for using complex addressing modes.

For this test case:

define void %foo(double* %y) {
entry:
br label %bb

bb:
%i = phi i64 [ 0, %entry ], [ %k, %bb ]
%j = getelementptr double* %y, i64 %i
store double 0.000000e+00, double* %j
%k = add i64 %i, 1
%n = icmp eq i64 %k, 0
br bool %n, label %return, label %bb

return:
ret void
}

The strength reduction pass changes the output on x86-64 to have two induction
variables:

    %iv..inc = add i64 %iv., 1
    ...
    %iv.1.inc = add i64 %iv.1, 8

which causes the codegen to produce this:

.LBB1_1: #bb
movq $0, (%rdi)
addq $8, %rdi
incq %rax
cmpq $0, %rax
jne .LBB1_1 #bb

instead of this:

.LBB1_1: #bb
movq $0, (%rdi,%rax,8)
incq %rax
cmpq $0, %rax
jne .LBB1_1 #bb

Here's a patch that fixes this.

Index: LoopStrengthReduce.cpp

RCS file: /var/cvs/llvm/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp,v
retrieving revision 1.104
diff -u -r1.104 LoopStrengthReduce.cpp
--- LoopStrengthReduce.cpp
+++ LoopStrengthReduce.cpp
@@ -893,7 +893,7 @@
if (unsigned(abs(SInt)) < Scale || (SInt % Scale) != 0)
continue;
std::map<SCEVHandle, 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::vector<IVExpr>::iterator II = SI->second.IVs.begin(),