[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

576–577

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

574

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

574

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

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

576–577

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

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

576–577

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

84 ↗

(On Diff #117271)

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

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

574

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

574

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

574

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

575

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

575

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

576–577

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

[etherzhhb]

Update comments

[efriedma]

lib/Transforms/Utils/SimplifyIndVar.cpp

572

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

572

Thanks for pointing this out, I will update the patch

[etherzhhb]

Delete the redundant getSCEVAtScope

[efriedma]

LGTM.

lib/Transforms/Utils/SimplifyIndVar.cpp

if (eliminateOverflowIntrinsic(CI))
       return true;
 
   if (eliminateIdentitySCEV(UseInst, IVOperand))
     return true;
 
   return false;
 }
 
+static Constant *ExtractConstant(const SCEV *S, Type *T) {
+  if (auto *C = dyn_cast<SCEVConstant>(S)) {
+    Constant *V = C->getValue();
+
+    if (V->getType() != T) {
+      // Since only integers and pointers are SCEVable and SCEVConstant are
+      // integers, the instruction can only have pointer type it does not have
+      // the same time with the SCEVConstant.
+      auto *PT = cast<PointerType>(T);
+      assert(V->isNullValue() &&
+             "SCEV only folds ConstantPointerNull to constant!");
+      V = ConstantPointerNull::get(PT);
+    }
+
+    return V;
+  }
+
+  if (auto *U = dyn_cast<SCEVUnknown>(S))
+    return dyn_cast<Constant>(U->getValue());
+
+  return nullptr;
+}
+
 /// Replace the UseInst with a constant if possible
 bool SimplifyIndvar::foldConstantSCEV(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);
 
+  auto *C = ExtractConstant(S, I->getType());
   if (!C)
     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;
-
-  I->replaceAllUsesWith(V);
+  I->replaceAllUsesWith(C);
   DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I << " with constant: " << *C
                << '\n');
   ++NumFoldedUser;
   Changed = true;
   DeadInsts.emplace_back(I);
   return true;
 }
 

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 {
+@G = external global i32
+
+define void @test0(i64* %arg) {
 bb:
-  switch i64 undef, label %bb1 [
-  ]
+  br label %bb2
 
-bb1:                                              ; preds = %bb
+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
+}
 
-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
-  ]
+; Should not fail when SCEV is fold to ConstantPointerNull
+; CHECK-LABEL: void @test0
+; CHECK:         load i32, i32* null
 
-bb3:                                              ; preds = %bb2, %bb2
-  %tmp4 = call fastcc i32* @wobble(i64* nonnull %tmp, i32* null)
-  %tmp5 = load i32, i32* %tmp4 , align 8
-  br label %bb6
+define void @test1(i64* %arg) {
+bb:
+  br label %bb2
 
-bb5:                                              ; preds = %bb2
-  unreachable
+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
+}
+
+; Should not fail on strange constant
+; CHECK-LABEL: void @test1
+; CHECK:         load i32, i32* inttoptr (i64 4 to i32*)
 
-bb6:                                              ; preds = %bb3, %bb2
+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
 }
 
-declare i32* @wobble(i64*, i32* returned)
+; Should not fail on strange constant
+; CHECK-LABEL: void @test2
+; CHECK:         load i32, i32* @G
 
-; Should not fail when SCEV is fold to ConstantPointerNull
-; CHECK-LABEL: void @test
-; CHECK:         load i32, i32* %{{[a-zA-Z$._0-9]+}}
+declare i32* @wobble(i64*, i32* returned)