From e1269fa6d77239b191f2bc1ad79bf9002e7f4367 Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Tue, 15 Sep 2015 23:45:39 +0000
Subject: [PATCH] [IndVars] Fix PR24783.

In `IndVarSimplify::ExpandSCEVIfNeeded`,
`SCEVExpander::findExistingExpansion` may return an `llvm::Value` that
differs in type from the SCEV it was asked to find an expansion for (but
computes the same value).  In such cases, we fall back on
`expandCodeFor`; and rely on LLVM to CSE the two equivalent
expressions (different only by a no-op cast) into a single computation.

I tried a few other approaches to fixing PR24783, all of which turned
out to be more complex than this current version:

 1. Move the `ExpandSCEVIfNeeded` logic into `expandCodeFor`.  This got
    problematic because currently we do not pass in the `Loop *` into
    `expandCodeFor`.  Changing the interface to do this is a more
    invasive change, and really does not make much semantic sense unless
    the SCEV being passed in is an add recurrence.

    There is also the problem of `expandCodeFor` being used in places
    other than `indvars` -- there may be performance / correctness
    issues elsewhere if `expandCodeFor` is moved from always generating
    IR from scratch to cache-like model.

 2. Have `findExistingExpansion` only return expression with the correct
    type.  This would make `isHighCostExpansionHelper` and thus
    `isHighCostExpansion` more conservative than necessary.

 3. Insert casts on the value returned by `findExistingExpansion` if
    needed using `InsertNoopCastOfTo`.  This is complicated because
    `InsertNoopCastOfTo` depends on internal state of its
    `SCEVExpander` (specifically `Builder.GetInserPoint()`), and this
    may not be set up when `ExpandSCEVIfNeeded` is called.

 4. Manually insert casts on the value returned by
    `findExistingExpansion` if needed using `InsertNoopCastOfTo` via
    `CastInst::Create`.  This is probably workable, but figuring out the
    location where the cast instruction needs to be inserted has enough
    edge cases (arguments, constants, invokes, LCSSA must be preserved)
    makes me feel what I have right now is simplest solution.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@247749 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/IndVarSimplify.cpp  |  3 ++-
 test/Transforms/IndVarSimplify/pr24783.ll | 30 +++++++++++++++++++++++
 2 files changed, 32 insertions(+), 1 deletion(-)
 create mode 100644 test/Transforms/IndVarSimplify/pr24783.ll

diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index c9fcf8ddf56..73b8052961c 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -509,7 +509,8 @@ Value *IndVarSimplify::ExpandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S,
   // Before expanding S into an expensive LLVM expression, see if we can use an
   // already existing value as the expansion for S.
   if (Value *ExistingValue = Rewriter.findExistingExpansion(S, InsertPt, L))
-    return ExistingValue;
+    if (ExistingValue->getType() == ResultTy)
+      return ExistingValue;
 
   // We didn't find anything, fall back to using SCEVExpander.
   return Rewriter.expandCodeFor(S, ResultTy, InsertPt);
diff --git a/test/Transforms/IndVarSimplify/pr24783.ll b/test/Transforms/IndVarSimplify/pr24783.ll
new file mode 100644
index 00000000000..637cb1e196c
--- /dev/null
+++ b/test/Transforms/IndVarSimplify/pr24783.ll
@@ -0,0 +1,30 @@
+; RUN: opt -S -indvars < %s | FileCheck %s
+
+target datalayout = "E-m:e-i64:64-n32:64"
+target triple = "powerpc64-unknown-linux-gnu"
+
+define void @f(i32* %end.s, i8** %loc, i32 %p) {
+; CHECK-LABEL: @f(
+entry:
+; CHECK:  [[P_SEXT:%[0-9a-z]+]] = sext i32 %p to i64
+; CHECK:  [[END:%[0-9a-z]+]] = getelementptr i32, i32* %end.s, i64 [[P_SEXT]]
+
+  %end = getelementptr inbounds i32, i32* %end.s, i32 %p
+  %init = bitcast i32* %end.s to i8*
+  br label %while.body.i
+
+while.body.i:
+  %ptr = phi i8* [ %ptr.inc, %while.body.i ], [ %init, %entry ]
+  %ptr.inc = getelementptr inbounds i8, i8* %ptr, i8 1
+  %ptr.inc.cast = bitcast i8* %ptr.inc to i32*
+  %cmp.i = icmp eq i32* %ptr.inc.cast, %end
+  br i1 %cmp.i, label %loop.exit, label %while.body.i
+
+loop.exit:
+; CHECK: loop.exit:
+; CHECK: [[END_BCASTED:%[a-z0-9]+]] = bitcast i32* %scevgep to i8*
+; CHECK: store i8* [[END_BCASTED]], i8** %loc
+  %ptr.inc.lcssa = phi i8* [ %ptr.inc, %while.body.i ]
+  store i8* %ptr.inc.lcssa, i8** %loc
+  ret void
+}
-- 
2.34.1