[IndVars] Fix usage of SCEVExpander to not mess with SCEVConstant. PR38674

[mkazantsev]

Summary

This patch removes the function expandSCEVIfNeeded which behaves not as
it was intended. This function tries to make a lookup for exact existing expansion
and only goes to normal expansion via expandCodeFor if this lookup hasn't found
anything. As a result of this, if some instruction above the loop has a SCEVConstant
SCEV, this logic will return this instruction when asked for this SCEVConstant rather
than return a constant value. This is both non-profitable and in some cases leads to
breach of LCSSA form (as in PR38674).

Whether or not it is possible to break LCSSA with this algorithm and with some
non-constant SCEVs is still in question, this is still being investigated. I wasn't
able to construct such a test so far, so maybe this situation is impossible. If it is,
it will go as a separate fix.

Rather than do it, it is always correct to just invoke expandCodeFor unconditionally:
it behaves smarter about insertion points, and as side effect of this it will choose a
constant value for SCEVConstants. For other SCEVs it may end up finding a better insertion
point. So it should not be worse in any case.

NOTE: So far the only known case for which this transform may break LCSSA is mapping of SCEVConstant to an instruction. However there is a suspicion that the entire algorithm can compromise LCSSA form for other cases as well (yet not proved).

[uabelho]

This indeed solves the problem I reported in PR38674 but I don't know IndVarSimplify enough to say if this is the right solution or not.

Thanks!

[greened]

test/Transforms/IndVarSimplify/pr38674.ll

103

Is it really necessary to check all of the generated IR like this? Could the test be written to only check the instructions participating in the LCSSA value flow? If so, it would make the test more robust.

[etherzhhb]

LGTM in general.

So by removing expandSCEVIfNeeded, we now rely on gvn to eliminate the redundant code.

Maybe we could explain in the commit message:
Is mapping SCEVConstant to Instruction the only problem of expandSCEVIfNeeded?
Is it possible to fix the problem by directly codegening the constant from SCEVConstant in expandSCEVIfNeeded?

[mkazantsev]

In D51286#1222271, @etherzhhb wrote:

So by removing expandSCEVIfNeeded, we now rely on gvn to eliminate the redundant code.

I don't think that anything will change in this perspective. expandCodeFor also makes this lookup, so if the map contains an existing value it will reuse it. It just behaves smarter about expansion points, constants etc.

Is mapping SCEVConstant to Instruction the only problem of expandSCEVIfNeeded?

It's the only case for which I have prove. The correctness of entire algorithm is under suspicion, I am currently investigating it.

Is it possible to fix the problem by directly codegening the constant from SCEVConstant in expandSCEVIfNeeded?

What's the point of that? I generally don't see any profit in going manually into rewriting internals and trying to find something in its map. Expand methods are designed to handle such cases.

[mkazantsev]

test/Transforms/IndVarSimplify/pr38674.ll

103

I'm having a crawling suspicion that this algorithm is generally wrong in terms of preserving SSA form. I would rather keep the tests verbose as possible just to make sure that we don't break it anyhow else.

lib/Transforms/Scalar/IndVarSimplify.cpp

class IndVarSimplify {
   void rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
   void rewriteFirstIterationLoopExitValues(Loop *L);
 
   Value *linearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
                                    PHINode *IndVar, SCEVExpander &Rewriter);
 
   void sinkUnusedInvariants(Loop *L);
 
-  Value *expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S, Loop *L,
-                            Instruction *InsertPt, Type *Ty);
-
 public:
   IndVarSimplify(LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
                  const DataLayout &DL, TargetLibraryInfo *TLI,
                  TargetTransformInfo *TTI)
       : LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI) {}
 
   bool run(Loop *L);
 };
struct RewritePhi {
   bool HighCost;
 
   RewritePhi(PHINode *P, unsigned I, Value *V, bool H)
       : PN(P), Ith(I), Val(V), HighCost(H) {}
 };
 
 } // end anonymous namespace
 
-Value *IndVarSimplify::expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S,
-                                          Loop *L, Instruction *InsertPt,
-                                          Type *ResultTy) {
-  // 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.getExactExistingExpansion(S, InsertPt, L))
-    if (ExistingValue->getType() == ResultTy)
-      return ExistingValue;
-
-  // We didn't find anything, fall back to using SCEVExpander.
-  return Rewriter.expandCodeFor(S, ResultTy, InsertPt);
-}
-
 //===----------------------------------------------------------------------===//
 // rewriteLoopExitValues - Optimize IV users outside the loop.
 // As a side effect, reduces the amount of IV processing within the loop.
 //===----------------------------------------------------------------------===//
 
 /// Check to see if this loop has a computable loop-invariant execution count.
 /// If so, this means that we can compute the final value of any expressions
 /// that are recurrent in the loop, and substitute the exit values from the loop
while ((PN = dyn_cast<PHINode>(BBI++))) {
                 NumSoftExternalUses++;
             }
           }
           if (NumUses <= 6 && NumHardInternalUses && !NumSoftExternalUses)
             continue;
         }
 
         bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, Inst);
-        Value *ExitVal =
-            expandSCEVIfNeeded(Rewriter, ExitValue, L, Inst, PN->getType());
+        Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
 
         LLVM_DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
                           << '\n'
                           << "  LoopVal = " << *Inst << "\n");
 
         if (!isValidRewrite(Inst, ExitVal)) {
           DeadInsts.push_back(ExitVal);
           continue;

test/Transforms/IndVarSimplify/pr38674.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -indvars < %s | FileCheck %s
+
+; Check that we don't reuse %zext instead of %inc11 for LCSSA Phi node. Case
+; with constants SCEV.
+
+define i32 @test_01() {
+; CHECK-LABEL: @test_01(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND1_PREHEADER:%.*]]
+; CHECK:       for.cond1.preheader:
+; CHECK-NEXT:    br label [[FOR_COND4_PREHEADER:%.*]]
+; CHECK:       for.cond4.preheader:
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i16 1 to i32
+; CHECK-NEXT:    br label [[FOR_BODY6:%.*]]
+; CHECK:       for.cond4:
+; CHECK-NEXT:    [[CMP5:%.*]] = icmp ult i32 [[INC:%.*]], 2
+; CHECK-NEXT:    br i1 [[CMP5]], label [[FOR_BODY6]], label [[FOR_END:%.*]]
+; CHECK:       for.body6:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[FOR_COND4_PREHEADER]] ], [ [[INC]], [[FOR_COND4:%.*]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[IV]], [[ZEXT]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
+; CHECK-NEXT:    br i1 [[TMP0]], label [[RETURN_LOOPEXIT:%.*]], label [[FOR_COND4]]
+; CHECK:       for.end:
+; CHECK-NEXT:    br i1 false, label [[FOR_COND4_PREHEADER]], label [[FOR_END9:%.*]]
+; CHECK:       for.end9:
+; CHECK-NEXT:    br i1 false, label [[FOR_COND1_PREHEADER]], label [[RETURN_LOOPEXIT3:%.*]]
+; CHECK:       return.loopexit:
+; CHECK-NEXT:    unreachable
+; CHECK:       return.loopexit3:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 1
+;
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.end9, %entry
+  br label %for.cond4.preheader
+
+for.cond4.preheader:                              ; preds = %for.end, %for.cond1.preheader
+  %zext = zext i16 1 to i32
+  br label %for.body6
+
+for.cond4:                                        ; preds = %for.body6
+  %cmp5 = icmp ult i32 %inc, 2
+  br i1 %cmp5, label %for.body6, label %for.end
+
+for.body6:                                        ; preds = %for.cond4, %for.cond4.preheader
+  %iv = phi i32 [ 0, %for.cond4.preheader ], [ %inc, %for.cond4 ]
+  %0 = icmp eq i32 %iv, %zext
+  %inc = add nuw nsw i32 %iv, 1
+  br i1 %0, label %return.loopexit, label %for.cond4
+
+for.end:                                          ; preds = %for.cond4
+  br i1 false, label %for.cond4.preheader, label %for.end9
+
+for.end9:                                         ; preds = %for.end
+  %inc11 = add nuw nsw i32 0, 1
+  br i1 false, label %for.cond1.preheader, label %return.loopexit3
+
+return.loopexit:                                  ; preds = %for.body6
+  unreachable
+
+return.loopexit3:                                 ; preds = %for.end9
+  %inc11.lcssa = phi i32 [ %inc11, %for.end9 ]
+  br label %return
+
+return:                                           ; preds = %return.loopexit3
+  ret i32 %inc11.lcssa
+}
+
+; Same as test_01, but the instructions with the same SCEV have a non-constant
+; SCEV.
+define i32 @test_02(i32 %x) {
+; CHECK-LABEL: @test_02(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND1_PREHEADER:%.*]]
+; CHECK:       for.cond1.preheader:
+; CHECK-NEXT:    br label [[FOR_COND4_PREHEADER:%.*]]
+; CHECK:       for.cond4.preheader:
+; CHECK-NEXT:    [[ZEXT:%.*]] = mul i32 [[X:%.*]], 1
+; CHECK-NEXT:    br label [[FOR_BODY6:%.*]]
+; CHECK:       for.cond4:
+; CHECK-NEXT:    [[CMP5:%.*]] = icmp ult i32 [[INC:%.*]], 2
+; CHECK-NEXT:    br i1 [[CMP5]], label [[FOR_BODY6]], label [[FOR_END:%.*]]
+; CHECK:       for.body6:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[FOR_COND4_PREHEADER]] ], [ [[INC]], [[FOR_COND4:%.*]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[IV]], [[ZEXT]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
+; CHECK-NEXT:    br i1 [[TMP0]], label [[RETURN_LOOPEXIT:%.*]], label [[FOR_COND4]]
+; CHECK:       for.end:
+; CHECK-NEXT:    br i1 false, label [[FOR_COND4_PREHEADER]], label [[FOR_END9:%.*]]
+; CHECK:       for.end9:
+; CHECK-NEXT:    [[INC11:%.*]] = add nuw nsw i32 0, [[X]]
+; CHECK-NEXT:    br i1 false, label [[FOR_COND1_PREHEADER]], label [[RETURN_LOOPEXIT3:%.*]]
+; CHECK:       return.loopexit:
+; CHECK-NEXT:    unreachable
+; CHECK:       return.loopexit3:
+; CHECK-NEXT:    [[INC11_LCSSA:%.*]] = phi i32 [ [[INC11]], [[FOR_END9]] ]
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 [[INC11_LCSSA]]
+;
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.end9, %entry
+  br label %for.cond4.preheader
+
+for.cond4.preheader:                              ; preds = %for.end, %for.cond1.preheader
+  %zext = mul i32 %x, 1
+  br label %for.body6
+
+for.cond4:                                        ; preds = %for.body6
+  %cmp5 = icmp ult i32 %inc, 2
+  br i1 %cmp5, label %for.body6, label %for.end
+
+for.body6:                                        ; preds = %for.cond4, %for.cond4.preheader
+  %iv = phi i32 [ 0, %for.cond4.preheader ], [ %inc, %for.cond4 ]
+  %0 = icmp eq i32 %iv, %zext
+  %inc = add nuw nsw i32 %iv, 1
+  br i1 %0, label %return.loopexit, label %for.cond4
+
+for.end:                                          ; preds = %for.cond4
+  br i1 false, label %for.cond4.preheader, label %for.end9
+
+for.end9:                                         ; preds = %for.end
+  %inc11 = add nuw nsw i32 0, %x
+  br i1 false, label %for.cond1.preheader, label %return.loopexit3
+
+return.loopexit:                                  ; preds = %for.body6
+  unreachable
+
+return.loopexit3:                                 ; preds = %for.end9
+  %inc11.lcssa = phi i32 [ %inc11, %for.end9 ]
+  br label %return
+
+return:                                           ; preds = %return.loopexit3
+  ret i32 %inc11.lcssa
+}