[SCEVExpander] Avoid re-using existing casts if it means updating users.

[fhahn]

Summary

Currently the SCEVExpander tries to re-use existing casts, even if they
are not exactly at the insertion point it was asked to create the cast.
To do so in some case, it creates a new cast at the insertion point and
updates all users to use the new cast.

This behavior is problematic, because it changes the IR outside of the
instructions created during the expansion. Therefore we cannot
completely undo all changes made during expansion.

This re-use should be only an extra optimization, so only using the new
cast in the expanded instructions should not be a correctness issue.
There are many cases equivalent instructions are created during
expansion.

This has minor impact on the tests, but there is one LoopDistribute test
that checks explicitly that only the new value is used. For now I just
XFAIL'd the test.

Once SCEVExpanderCleaner is added, we could keep a mapping of
values to replace and apply them once the result is used.

[efriedma]

llvm/test/Transforms/LoopDistribute/bounds-expansion-bug.ll

8

Does the pass semantically depend on reusing casts, or does failing to reuse casts just make the generated code uglier?

[mkazantsev]

llvm/test/Transforms/LoopDistribute/bounds-expansion-bug.ll

3

Is it XFAIL with a crash? If it's not, I'd like to see checks update and FIXME comment instead.

[lebedev.ri]

I think this makes sense overall.

llvm/test/Transforms/LoopDistribute/bounds-expansion-bug.ll

8

If this is a single test that actually ensures that casts are reused,
i'm not sure it's a very cornerstone feature of the pass.

[lebedev.ri]

As per comments.

[fhahn]

Adjust code to allow for better re-use inserted values with the following changes:

1. Update findInsertPointAfter to skip inserted instructions. This ensures we can straight-forwardly re-use inserted instructions for expanding the same value multiple times. There's no documentation of the intended behavior of the function, but from the name and uses, we are looking for an insertion pointer after the given instruction, which new code does.

2. Adjust ReuseOrCreateCast to re-use the first suitable cast that locally comes before the requested IP. This should return a suitable cast, while allowing re-using already inserted instructions. It also simplifies the logic. Now it is clear that we either re-use an existing cast or create a new one outside the loop.

With those changes, the regression in the LoopDistribute test is gone.

Note that both changes mentioned above depend on each other to work together, so it is not possible to split them off.

[fhahn]

llvm/test/Transforms/LoopDistribute/bounds-expansion-bug.ll

3

The FIXME is not longer needed :)

8

I updated the code to allow for better re-using existing casts even in the updated version. There is no regression in this test any longer, other than the fact that we do not generate the 'invalidate' bit casts any longer.

[fhahn]

Add missing findInsertPointAfter changes to review.

[lebedev.ri]

This seems good to me, but please wait for one more reviewer.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

60–61

a cast *in the basic block specified by insertion point*

llvm/test/Transforms/LoopStrengthReduce/pr27056.ll

39

Why were we emitting an unused instruction in the first place?

[fhahn]

llvm/test/Transforms/LoopStrengthReduce/pr27056.ll

39

That's probably due to the cast re-using logic, which in some cases makes certain values dead by replacing all uses with an equivalent cast.

[efriedma]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

113

I'm not sure I understand what's happening here. "I" dominates "MustDominate" because the we're inserting an instruction that uses I. And we're assuming MustDominate itself must be a legal insertion point. So the only way we could skip past MustDominate is if IsInsertedInstruction() is true for MustDominate.

Is it actually possible for isInsertedInstruction(MustDominate) to be true? If it is, could we check it directly?

[fhahn]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

113

Is it actually possible for isInsertedInstruction(MustDominate) to be true? If it is, could we check it directly?

Unfortunately, at the moment there is a case where we might mark existing instructions as 'inserted' (
https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp#L1247)

This check is indeed a workaround, in case such an instruction is an insert point, so checking directly for it would be more straight forward. I'll update the code, thanks!

llvm/test/Transforms/LoopStrengthReduce/pr27056.ll

39

(which this patch removes)

[fhahn]

Handle the case where MustDominate is in InsertedInstructions more obviously, by including the check in the loop condition.

This also requires us to track the inserted LCSSA phis, so I put up D85037

[lebedev.ri]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

70

Note that comesBefore() only handles same-BB cases.
Should this be something like this instead?

[fhahn]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

70

Note that comesBefore() only handles same-BB cases.

Yep, that's why it checks for being in the same BB. I guess we could, but I'd like to keep the change the least disruptive as possible, to also keep the potential fallout small. IMO changing the BB only reuse would best be done as follow up.

[lebedev.ri]

In D84399#2178306, @lebedev.ri wrote:

This seems good to me, but please wait for one more reviewer.

[fhahn]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

113

@efriedma, does the update make sense to you?

[fhahn]

rebase

[lebedev.ri]

@efriedma sudo-reverse-ping, thanks.

[efriedma]

LGTM

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

#endif
   /// At. Return nullptr if value was not found.
   ///
   /// Note that this function does not perform an exhaustive search. I.e if it
   /// didn't find any value it does not mean that there is no such value.
   ///
   Optional<ScalarEvolution::ValueOffsetPair>
   getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
 
+  /// Returns a suitable insert point after \p I, that dominates \p
+  /// MustDominate. Skips instructions inserted by the expander.
+  BasicBlock::iterator findInsertPointAfter(Instruction *I,
+                                            Instruction *MustDominate);
+
 private:
   LLVMContext &getContext() const { return SE.getContext(); }
 
   /// Insert code to directly compute the specified SCEV expression into the
   /// program. The code is inserted into the SCEVExpander's current
   /// insertion point. If a type is specified, the result will be expanded to
   /// have that type, with a cast if necessary. If \p Root is true, this
   /// indicates that \p SH is the top-level expression to expand passed from

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

 cl::opt<unsigned> llvm::SCEVCheapExpansionBudget(
     "scev-cheap-expansion-budget", cl::Hidden, cl::init(4),
     cl::desc("When performing SCEV expansion only if it is cheap to do, this "
              "controls the budget that is considered cheap (default = 4)"));
 
 using namespace PatternMatch;
 
 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
-/// reusing an existing cast if a suitable one exists, moving an existing
-/// cast if a suitable one exists but isn't in the right place, or
+/// reusing an existing cast if a suitable one (= dominating IP) exists, or
 /// creating a new one.
 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
                                        Instruction::CastOps Op,
                                        BasicBlock::iterator IP) {
   // This function must be called with the builder having a valid insertion
   // point. It doesn't need to be the actual IP where the uses of the returned
   // cast will be added, but it must dominate such IP.
   // We use this precondition to produce a cast that will dominate all its
   // uses. In particular, this is crucial for the case where the builder's
   // insertion point *is* the point where we were asked to put the cast.
   // Since we don't know the builder's insertion point is actually
   // where the uses will be added (only that it dominates it), we are
   // not allowed to move it.
   BasicBlock::iterator BIP = Builder.GetInsertPoint();
 
   Instruction *Ret = nullptr;
 
   // Check to see if there is already a cast!
-  for (User *U : V->users())
-    if (U->getType() == Ty)
-      if (CastInst *CI = dyn_cast<CastInst>(U))
-        if (CI->getOpcode() == Op) {
-          // If the cast isn't where we want it, create a new cast at IP.
-          // Likewise, do not reuse a cast at BIP because it must dominate
-          // instructions that might be inserted before BIP.
-          if (BasicBlock::iterator(CI) != IP || BIP == IP) {
-            // Create a new cast, and leave the old cast in place in case
-            // it is being used as an insert point.
-            Ret = CastInst::Create(Op, V, Ty, "", &*IP);
-            Ret->takeName(CI);
-            CI->replaceAllUsesWith(Ret);
-            break;
-          }
-          Ret = CI;
-          break;
-        }
+  for (User *U : V->users()) {
+    if (U->getType() != Ty)
+      continue;
+    CastInst *CI = dyn_cast<CastInst>(U);
+    if (!CI || CI->getOpcode() != Op)
+      continue;
+
+    // Found a suitable cast that is at IP or comes before IP. Use it.
+    if (IP->getParent() == CI->getParent() &&
+        (&*IP == CI || CI->comesBefore(&*IP))) {
+  }
 
   // Create a new cast.
-  if (!Ret)
+  if (!Ret) {
     Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP);
+    rememberInstruction(Ret);
+  }
 
   // We assert at the end of the function since IP might point to an
   // instruction with different dominance properties than a cast
   // (an invoke for example) and not dominate BIP (but the cast does).
   assert(SE.DT.dominates(Ret, &*BIP));
 
-  rememberInstruction(Ret);
   return Ret;
 }
 
-static BasicBlock::iterator findInsertPointAfter(Instruction *I,
-                                                 BasicBlock *MustDominate) {
+BasicBlock::iterator
+SCEVExpander::findInsertPointAfter(Instruction *I, Instruction *MustDominate) {
   BasicBlock::iterator IP = ++I->getIterator();
   if (auto *II = dyn_cast<InvokeInst>(I))
     IP = II->getNormalDest()->begin();
 
   while (isa<PHINode>(IP))
     ++IP;
 
   if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
     ++IP;
   } else if (isa<CatchSwitchInst>(IP)) {
-    IP = MustDominate->getFirstInsertionPt();
+    IP = MustDominate->getParent()->getFirstInsertionPt();
   } else {
     assert(!IP->isEHPad() && "unexpected eh pad!");
   }
 
+  // Adjust insert point to be after instructions inserted by the expander, so
+  // we can re-use already inserted instructions. Avoid skipping past the
+  // original \p MustDominate, in case it is an inserted instruction.
+  while (isInsertedInstruction(&*IP) && &*IP != MustDominate)
+    ++IP;
+
   return IP;
 }
 
 /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
 /// which must be possible with a noop cast, doing what we can to share
 /// the casts.
 Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
   Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
   assert((Op == Instruction::BitCast ||
while ((isa<BitCastInst>(IP) &&
             cast<BitCastInst>(IP)->getOperand(0) != A) ||
            isa<DbgInfoIntrinsic>(IP))
       ++IP;
     return ReuseOrCreateCast(A, Ty, Op, IP);
   }
 
   // Cast the instruction immediately after the instruction.
   Instruction *I = cast<Instruction>(V);
-  BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
+  BasicBlock::iterator IP = findInsertPointAfter(I, &*Builder.GetInsertPoint());
   return ReuseOrCreateCast(I, Ty, Op, IP);
 }
 
 /// InsertBinop - Insert the specified binary operator, doing a small amount
 /// of work to avoid inserting an obviously redundant operation, and hoisting
 /// to an outer loop when the opportunity is there and it is safe.
 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
                                  Value *LHS, Value *RHS,
if (CanonicalIV &&
       SE.getTypeSizeInBits(CanonicalIV->getType()) >
       SE.getTypeSizeInBits(Ty)) {
     SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
     for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
       NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
     Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
                                        S->getNoWrapFlags(SCEV::FlagNW)));
     BasicBlock::iterator NewInsertPt =
-        findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock());
+        findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint());
     V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
                           &*NewInsertPt, false);
     return V;
   }
 
   // {X,+,F} --> X + {0,+,F}
   if (!S->getStart()->isZero()) {
     SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end());

llvm/test/Transforms/LoopDistribute/bounds-expansion-bug.ll

 ; RUN: opt -basic-aa -loop-distribute -enable-loop-distribute -S < %s | FileCheck %s
 
 ; When emitting the memchecks for:
 ;
 ;   for (i = 0; i < n; i++) {
 ;     A[i + 1] = A[i] * B[i];
 ;     =======================
 ;     C[i] = D[i] * E[i];
 ;   }
 ;
 ; we had a bug when expanding the bounds for A and C.  These are expanded
 ; multiple times and rely on the caching in SCEV expansion to avoid any
 ; redundancy.  However, due to logic in SCEVExpander::ReuseOrCreateCast, we
 ; can get earlier expanded values invalidated when casts are used.  This test
 ; ensure that we are not using the invalidated values.
 

 ;     %0 = bitcast i32* %c to i8*                 <--- old, invalidated
 ;     %1 = bitcast i32* %a to i8*
 
   %a = phi i32* [%a1, %one], [%a2, %two]
   %c = phi i32* [%c1, %one], [%c2, %two]
   br label %for.body
 
 ; CHECK: join
-; CHECK: {{%[0-9a-z]+}} = bitcast i32* %c to i8*
 ; CHECK: {{%[0-9a-z]+}} = bitcast i32* %a to i8*
-; CHECK: [[OLD_C:%[0-9a-z]+]] = bitcast i32* %c to i8*
-; CHECK: [[OLD_A:%[0-9a-z]+]] = bitcast i32* %a to i8*
-; CHECK-NOT: [[OLD_C]]
-; CHECK-NOT: [[OLD_A]]
+; CHECK: {{%[0-9a-z]+}} = bitcast i32* %c to i8*
+; CHECK-NOT: bitcast i32* %c to i8*
+; CHECK-NOT: bitcast i32* %a to i8*
 
 for.body:                                         ; preds = %for.body, %entry
   %ind = phi i64 [ 0, %join ], [ %add, %for.body ]
 
   %arrayidxA = getelementptr inbounds i32, i32* %a, i64 %ind
   %loadA = load i32, i32* %arrayidxA, align 4
 
   %arrayidxB = getelementptr inbounds i32, i32* %b, i64 %ind

llvm/test/Transforms/LoopIdiom/reuse-cast.ll

 
 declare void @use.i8(i8*)
 
 declare void @use.i1(i1)
 
 define void @reuse_cast_2(i32 %x, i32* %ptr.1.start) {
 ; CHECK-LABEL: @reuse_cast_2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[PTR_1_START1:%.*]] = bitcast i32* [[PTR_1_START:%.*]] to i8*
+; CHECK-NEXT:    [[PTR_1_START2:%.*]] = bitcast i32* [[PTR_1_START:%.*]] to i8*
 ; CHECK-NEXT:    [[STACK:%.*]] = alloca [2 x i32], align 4
-; CHECK-NEXT:    [[CAST_TO_REUSE:%.*]] = bitcast [2 x i32]* [[STACK]] to i8*
+; CHECK-NEXT:    [[STACK1:%.*]] = bitcast [2 x i32]* [[STACK]] to i8*
 ; CHECK-NEXT:    [[C_0:%.*]] = icmp sgt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[TMP0:%.*]] = bitcast [2 x i32]* [[STACK]] to i8*
+; CHECK-NEXT:    [[CAST_TO_REUSE:%.*]] = bitcast [2 x i32]* [[STACK]] to i8*
 ; CHECK-NEXT:    [[PTR_2_START:%.*]] = getelementptr inbounds [2 x i32], [2 x i32]* [[STACK]], i64 0, i64 0
 ; CHECK-NEXT:    call void @use.i8(i8* [[CAST_TO_REUSE]])
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 [[CAST_TO_REUSE]], i8* align 4 [[PTR_1_START1]], i64 8, i1 false)
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 [[STACK1]], i8* align 4 [[PTR_1_START2]], i64 8, i1 false)
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[PTR_1:%.*]] = phi i32* [ [[PTR_1_START]], [[ENTRY]] ], [ [[PTR_1_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[PTR_2:%.*]] = phi i32* [ [[PTR_2_START]], [[ENTRY]] ], [ [[PTR_2_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[PTR_1_NEXT]] = getelementptr inbounds i32, i32* [[PTR_1]], i64 1
 ; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[PTR_1]], align 4
 ; CHECK-NEXT:    [[PTR_2_NEXT]] = getelementptr inbounds i32, i32* [[PTR_2]], i64 1

llvm/test/Transforms/LoopStrengthReduce/pr27056.ll

 ; CHECK-NEXT:    [[CMP16:%.*]] = icmp eq %struct.L* [[TMP]], null
 ; CHECK-NEXT:    [[TMP4:%.*]] = sub i64 0, [[TMP1]]
 ; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, i8* getelementptr inbounds (%struct.L, %struct.L* @GV2, i32 0, i32 0), i64 [[TMP4]]
 ; CHECK-NEXT:    [[UGLYGEP1:%.*]] = bitcast i8* [[UGLYGEP]] to %struct.L*
 ; CHECK-NEXT:    br i1 [[CMP16]], label [[FOR_END:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
 ; CHECK:       for.body.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[TMP5:%.*]] = inttoptr i64 [[LSR_IV]] to %struct.L*
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq %struct.L* [[UGLYGEP1]], [[TMP]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq %struct.L* [[UGLYGEP1]], [[TMP5]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    catchret from [[TMP3]] to label [[TRY_CONT:%.*]]
 ; CHECK:       try.cont:
 ; CHECK-NEXT:    ret void
 ;