[SimplifyIndVar] Replace IVUsers with loop invariant if possible

[efriedma]

lib/Transforms/Utils/SimplifyIndVar.cpp

551

Could you use SCEVExpander rather than writing out the cast logic here? I'm not sure this covers all the relevant cases.

557

Does it actually matter whether the value here is a Constant?

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

551

Ok, will do

557

You means we gain something if we can "simplify" the IV user from a SCEVAddRec to a SCEVUnknown?*

SE->getSCEV(I); may directly return an SCEUnknown, so we need to compare the new LLVM Value and the original one.
We are not going to do the replace if they are the same

[efriedma]

lib/Transforms/Utils/SimplifyIndVar.cpp

557

Rather than try to check for equality, you can just check whether the SCEVUnknown is loop-invariant.

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

557

This sounds great

[etherzhhb]

Address reviewer's comments

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

553–554

Should we only expand SCEVConstant and SCEVUnknown?

If we should expand all SCEV that is Loop Invariant, should we make the SCEVExpander global, such that we have a global "InsertedExpressions" map (in the SCEVExpander) to remember the SCEV expression that we expanded?

[etherzhhb]

Looks like I need to pass the SCEVExpander from the IndVarSimpilfy pass to coordinate SCEV rewrite, otherwise we will fail test/Transforms/IndVarSimplify/pr20680.ll

[etherzhhb]

Update format

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

550

We may only want to do the replace if S is invariant of the IV's Loop, which may be different from "L" which is the innermost loop that contains the IV user

[efriedma]

lib/Transforms/Utils/SimplifyIndVar.cpp

550

Yes; otherwise, the transform isn't doing anything useful.

We might need to call isHighCostExpansion here, so we don't generate something ridiculous?

553–554

"I" is probably not the right place the put any expansion code, given it's inside the loop.

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

553–554

SCEVExpander figure out the correct place by itself (at least in test4 of test/Transforms/IndVarSimplify/replace-iv-with-loop-invariant.ll), otherwise we need to find the preheader (and fallback to I if there is no preheader)

test/Transforms/IndVarSimplify/replace-iv-with-loop-invariant.ll

85

Here the SCEVExpander expand the expression before the loop (before the phi)

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

550

Yes, this make sense.

I did some experiments and we may want to actually write:

if (!SE->isLoopInvariant(S, IV's Loop) || !SE->isLoopInvariant(S, IV User's Loop))

If IV's Loop do not contains IV User's Loop

[efriedma]

lib/Transforms/Utils/SimplifyIndVar.cpp

550

Given a function in LCSSA form, I don't think this relevant? But feel free to prove me wrong. :)

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

550

Not sure if we assume LCSSA (or SCEV could see through it), I hit some crash when I just test 'if (!SE->isLoopInvariant(S, IV's Loop))' and it turned out that IV's Loop do not contain IV's user. I will find those cases

[etherzhhb]

Partially address reviewer's comment. This is a WIP patch

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

552

Maybe we should not push IV users in pushIVUsers at all if IV users do not in the IV loop (e.g. LCSSA phi)

[efriedma]

lib/Transforms/Utils/SimplifyIndVar.cpp

552

Yeah, that makes sense; we have special handling for exit values in IndVarSimplify::rewriteLoopExitValues.

[etherzhhb]

Address reviewer comments

[etherzhhb]

Ping?

[hfinkel]

lib/Transforms/Utils/SimplifyIndVar.cpp

552–553

End comments with a period (here and also below).

[etherzhhb]

Update comments

[efriedma]

lib/Transforms/Utils/SimplifyIndVar.cpp

549

SE->getSCEVAtScope(SE->getSCEV(I), LI->getLoopFor(I->getParent())) should be equivalent to SE->getSCEV(I). The point of getSCEVAtScope is to compute the value of a SCEV outside of its associated loop (the exit value).

Sorry, I should have spotted this earlier.

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

549

Thanks for pointing this out, I will update the patch

[etherzhhb]

Delete the redundant getSCEVAtScope

[efriedma]

LGTM.

lib/Transforms/Utils/SimplifyIndVar.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
-#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
public:
     /// Iteratively perform simplification on a worklist of users of the
     /// specified induction variable. This is the top-level driver that applies
     /// all simplifications to users of an IV.
     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
 
     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
 
     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
-    bool foldConstantSCEV(Instruction *UseInst);
+    bool replaceIVUserWithLoopInvariant(Instruction *UseInst);
 
     bool eliminateOverflowIntrinsic(CallInst *CI);
     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
     void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
                              bool IsSigned);
     void replaceRemWithNumerator(BinaryOperator *Rem);
     void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
 
   if (eliminateIdentitySCEV(UseInst, IVOperand))
     return true;
 
   return false;
 }
 
 /// Replace the UseInst with a constant if possible
-bool SimplifyIndvar::foldConstantSCEV(Instruction *I) {
+bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
   if (!SE->isSCEVable(I->getType()))
     return false;
 
   // Get the symbolic expression for this instruction.
   const SCEV *S = SE->getSCEV(I);
 
   const Loop *L = LI->getLoopFor(I->getParent());
   S = SE->getSCEVAtScope(S, L);
-  auto *C = dyn_cast<SCEVConstant>(S);
 
-  if (!C)
+  if (!SE->isLoopInvariant(S, L))
     return false;
 
-  Constant *V = C->getValue();
-  // The SCEV will have a different type than the instruction if the instruction
-  // has a pointer type. Skip the replacement
-  // TODO: Replace ConstantInt Zero by ConstantPointerNull
-  if (V->getType() != I->getType())
-    return false;
+  SCEVExpander Expander(*SE, SE->getDataLayout(), "loop.invarant");
+  auto *Invariant = Expander.expandCodeFor(S, I->getType(), I);
 
-  I->replaceAllUsesWith(V);
-  DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I << " with constant: " << *C
-               << '\n');
+  I->replaceAllUsesWith(Invariant);
+  DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
+               << " with loop invariant: " << *S << '\n');
   ++NumFoldedUser;
   Changed = true;
   DeadInsts.emplace_back(I);
   return true;
 }
 
 /// Eliminate any operation that SCEV can prove is an identity function.
 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
   while (!SimpleIVUsers.empty()) {
     std::pair<Instruction*, Instruction*> UseOper =
       SimpleIVUsers.pop_back_val();
     Instruction *UseInst = UseOper.first;
 
     // Bypass back edges to avoid extra work.
     if (UseInst == CurrIV) continue;
 
-    // Try to replace UseInst with a constant before any other simplifications
-    if (foldConstantSCEV(UseInst))
+    // Try to replace UseInst with a loop invariant before any other
+    // simplifications
+    if (replaceIVUserWithLoopInvariant(UseInst))
       continue;
 
     Instruction *IVOperand = UseOper.second;
     for (unsigned N = 0; IVOperand; ++N) {
       assert(N <= Simplified.size() && "runaway iteration");
 
       Value *NewOper = foldIVUser(UseOper.first, IVOperand);
       if (!NewOper)

test/Transforms/IndVarSimplify/constant-fold-1.ll

-; RUN: opt < %s -indvars -S | FileCheck %s
-
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @test(i64* %arg) unnamed_addr align 2 {
-bb:
-  switch i64 undef, label %bb1 [
-  ]
-
-bb1:                                              ; preds = %bb
-  br label %bb2
-
-bb2:                                              ; preds = %bb6, %bb1
-  %tmp = phi i64* [%arg, %bb1 ], [ %tmp7, %bb6 ]
-  switch i2 undef, label %bb6 [
-    i2 1, label %bb5
-    i2 -2, label %bb3
-    i2 -1, label %bb3
-  ]
-
-bb3:                                              ; preds = %bb2, %bb2
-  %tmp4 = call fastcc i32* @wobble(i64* nonnull %tmp, i32* null)
-  %tmp5 = load i32, i32* %tmp4 , align 8
-  br label %bb6
-
-bb5:                                              ; preds = %bb2
-  unreachable
-
-bb6:                                              ; preds = %bb3, %bb2
-  %tmp7 = load i64*, i64** undef, align 8
-  br label %bb2
-}
-
-declare i32* @wobble(i64*, i32* returned)
-
-; Should not fail when SCEV is fold to ConstantPointerNull
-; CHECK-LABEL: void @test
-; CHECK:         load i32, i32* %{{[a-zA-Z$._0-9]+}}

test/Transforms/IndVarSimplify/replace-iv-with-loop-invariant.ll

+; RUN: opt < %s -indvars -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@G = external global i32
+
+define void @test0(i64* %arg) {
+bb:
+  br label %bb2
+
+bb2:
+  %tmp = phi i64* [%arg, %bb ], [ %tmp7, %bb2 ]
+  %tmp4 = call i32* @wobble(i64* nonnull %tmp, i32* null)
+  %tmp5 = load i32, i32* %tmp4, align 8
+  %tmp7 = load i64*, i64** undef, align 8
+  br label %bb2
+}
+
+; CHECK-LABEL: void @test0
+; CHECK:         load i32, i32* null
+
+define void @test1(i64* %arg) {
+bb:
+  br label %bb2
+
+bb2:
+  %tmp = phi i64* [%arg, %bb ], [ %tmp7, %bb2 ]
+  %tmp4 = call i32* @wobble(i64* nonnull %tmp, i32* inttoptr (i64 4 to i32*))
+  %tmp5 = load i32, i32* %tmp4
+  %tmp7 = load i64*, i64** undef, align 8
+  br label %bb2
+}
+
+; CHECK-LABEL: void @test1
+; CHECK:         load i32, i32* inttoptr (i64 4 to i32*)
+
+define void @test2(i64* %arg) {
+bb:
+  br label %bb2
+
+bb2:
+  %tmp = phi i64* [%arg, %bb ], [ %tmp7, %bb2 ]
+  %tmp4 = call i32* @wobble(i64* nonnull %tmp, i32* @G)
+  %tmp5 = load i32, i32* %tmp4
+  %tmp7 = load i64*, i64** undef, align 8
+  br label %bb2
+}
+
+; CHECK-LABEL: void @test2
+; CHECK:         load i32, i32* @G
+
+
+define void @test3(i64* %arg, i32* %loop.invariant) {
+bb:
+  br label %bb2
+
+bb2:
+  %tmp = phi i64* [%arg, %bb ], [ %tmp7, %bb2 ]
+  %tmp4 = call i32* @wobble(i64* nonnull %tmp, i32* %loop.invariant)
+  %tmp5 = load i32, i32* %tmp4
+  %tmp7 = load i64*, i64** undef, align 8
+  br label %bb2
+}
+
+; CHECK-LABEL: void @test3
+; CHECK:         load i32, i32* %loop.invariant
+
+declare i32* @wobble(i64*, i32* returned)