Teach IVUsers to stop at non-affine expressions unless they are both

outside the loop and reducible.

This more completely hides them from LSR, which isn't usually able to
do anything meaningful with non-affine expressions anyway, and this
consequently hides them from SCEVExpander, which is acutely unprepared
for non-affine expressions.

Replace test/CodeGen/X86/lsr-nonaffine.ll with a new test that tests
the new behavior.

This works around the bug in PR10117 / rdar://problem/9633149, and is
generally an improvement besides.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134268 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 35 insertions, 25 deletions

diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp
index 7a9dc0f14c..e5f0a77ab6 100644
--- a/lib/Analysis/IVUsers.cpp
+++ b/lib/Analysis/IVUsers.cpp
@@ -46,17 +46,20 @@ Pass *llvm::createIVUsersPass() {
 /// used by the given expression, within the context of analyzing the
 /// given loop.
 static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
-                          ScalarEvolution *SE) {
+                          ScalarEvolution *SE, LoopInfo *LI) {
   // An addrec is interesting if it's affine or if it has an interesting start.
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
-    // Keep things simple. Don't touch loop-variant strides.
+    // Keep things simple. Don't touch loop-variant strides unless they're
+    // only used outside the loop and we can simplify them.
     if (AR->getLoop() == L)
-      return AR->isAffine() || !L->contains(I);
+      return AR->isAffine() ||
+             (!L->contains(I) &&
+              SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR);
     // Otherwise recurse to see if the start value is interesting, and that
     // the step value is not interesting, since we don't yet know how to
     // do effective SCEV expansions for addrecs with interesting steps.
-    return isInteresting(AR->getStart(), I, L, SE) &&
-          !isInteresting(AR->getStepRecurrence(*SE), I, L, SE);
+    return isInteresting(AR->getStart(), I, L, SE, LI) &&
+          !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI);
   }
 
   // An add is interesting if exactly one of its operands is interesting.
@@ -64,7 +67,7 @@ static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
     bool AnyInterestingYet = false;
     for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end();
          OI != OE; ++OI)
-      if (isInteresting(*OI, I, L, SE)) {
+      if (isInteresting(*OI, I, L, SE, LI)) {
         if (AnyInterestingYet)
           return false;
         AnyInterestingYet = true;
@@ -98,7 +101,7 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
 
   // If we've come to an uninteresting expression, stop the traversal and
   // call this a user.
-  if (!isInteresting(ISE, I, L, SE))
+  if (!isInteresting(ISE, I, L, SE, LI))
     return false;
 
   SmallPtrSet<Instruction *, 4> UniqueUsers;
diff --git a/test/CodeGen/X86/lsr-nonaffine.ll b/test/CodeGen/X86/lsr-nonaffine.ll
index b0d30641dd..4771646f41 100644
--- a/test/CodeGen/X86/lsr-nonaffine.ll
+++ b/test/CodeGen/X86/lsr-nonaffine.ll
@@ -1,23 +1,30 @@
-; RUN: llc -march=x86-64 < %s | FileCheck %s
+; RUN: llc -asm-verbose=false -march=x86-64 -o - < %s | FileCheck %s
 
-; LSR should compute the correct starting values for this loop. Note that
-; it's not necessarily LSR's job to compute loop exit expressions; that's
-; indvars' job.
-; CHECK: movl  $12
-; CHECK: movl  $42
+; LSR should leave non-affine expressions alone because it currently
+; doesn't know how to do anything with them, and when it tries, it
+; gets SCEVExpander's current expansion for them, which is suboptimal.
 
-define i32 @real_symmetric_eigen(i32 %n) nounwind {
-while.body127:                                    ; preds = %while.cond122
-  br label %while.cond141
+; CHECK:        xorl %eax, %eax
+; CHECK-NEXT:   align
+; CHECK-NEXT: BB0_1:
+; CHECK-NEXT:   movq  %rax, (%rdx)
+; CHECK-NEXT:   addq  %rsi, %rax
+; CHECK-NEXT:   cmpq  %rdi, %rax
+; CHECK-NEXT:   jl
+; CHECK-NEXT:   imulq %rax, %rax
+; CHECK-NEXT:   ret
+define i64 @foo(i64 %n, i64 %s, i64* %p) nounwind {
+entry:
+  br label %loop
 
-while.cond141:                                    ; preds = %while.cond141, %while.body127
-  %0 = phi i32 [ 7, %while.body127 ], [ %indvar.next67, %while.cond141 ] ; <i32> [#uses=3]
-  %indvar.next67 = add i32 %0, 1                  ; <i32> [#uses=1]
-  %t = icmp slt i32 %indvar.next67, %n
-  br i1 %t, label %if.then171, label %while.cond141
+loop:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
+  volatile store i64 %i, i64* %p
+  %i.next = add i64 %i, %s
+  %c = icmp slt i64 %i.next, %n
+  br i1 %c, label %loop, label %exit
 
-if.then171:                                       ; preds = %while.cond141
-  %mul150 = mul i32 %0, %0                 ; <i32> [#uses=1]
-  %add174 = add i32 %mul150, %0                 ; <i32> [#uses=1]
-  ret i32 %add174
+exit:
+  %mul = mul i64 %i.next, %i.next
+  ret i64 %mul
 }