[IndVars] Drop check for the validity of rewrite

[lebedev.ri]

Summary

isValidRewrite() checks that the both the original SCEV,
and the rewrite SCEV have the same base pointer.
I believe, after all the recent SCEV improvements,
this invariant is already enforced by SCEV itself.

I originally tried changing it into an assert in D108043,
but that showed that it triggers on e.g. https://reviews.llvm.org/D108043#2946621,
where SCEV manages to forward the store to load.

@efriedma @mkazantsev @reames does my understanding i outlied above match the current state of reality?

[nikic]

LGTM, I believe your reasoning is correct.

Might make sense to add the test case from D108043 to show that this is an increase in power (because isValidRewrite was a conservative check)? I believe the only relevant part of that test case is that the phi has a loop-invariant input on the backedge and the exit is known to not be taken on the first iteration (thus the value coming from the backedge must be used) -- I don't think load/store forwarding is relevant there.

llvm/lib/Transforms/Utils/LoopUtils.cpp

return SE.isAvailableAtLoopEntry(S, L) &&
                                      SE.getConstant(Max));
 }
 
 //===----------------------------------------------------------------------===//
 // rewriteLoopExitValues - Optimize IV users outside the loop.
 // As a side effect, reduces the amount of IV processing within the loop.
 //===----------------------------------------------------------------------===//
 
-// Return true if the SCEV expansion generated by the rewriter can replace the
-// original value. SCEV guarantees that it produces the same value, but the way
-// it is produced may be illegal IR.  Ideally, this function will only be
-// called for verification.
-static bool isValidRewrite(ScalarEvolution *SE, Value *FromVal, Value *ToVal) {
-  // If an SCEV expression subsumed multiple pointers, its expansion could
-  // reassociate the GEP changing the base pointer. This is illegal because the
-  // final address produced by a GEP chain must be inbounds relative to its
-  // underlying object. Otherwise basic alias analysis, among other things,
-  // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
-  // producing an expression involving multiple pointers. Until then, we must
-  // bail out here.
-  //
-  // Retrieve the pointer operand of the GEP. Don't use getUnderlyingObject
-  // because it understands lcssa phis while SCEV does not.
-  Value *FromPtr = FromVal;
-  Value *ToPtr = ToVal;
-  if (auto *GEP = dyn_cast<GEPOperator>(FromVal))
-    FromPtr = GEP->getPointerOperand();
-
-  if (auto *GEP = dyn_cast<GEPOperator>(ToVal))
-    ToPtr = GEP->getPointerOperand();
-
-  if (FromPtr != FromVal || ToPtr != ToVal) {
-    // Quickly check the common case
-    if (FromPtr == ToPtr)
-      return true;
-
-    // SCEV may have rewritten an expression that produces the GEP's pointer
-    // operand. That's ok as long as the pointer operand has the same base
-    // pointer. Unlike getUnderlyingObject(), getPointerBase() will find the
-    // base of a recurrence. This handles the case in which SCEV expansion
-    // converts a pointer type recurrence into a nonrecurrent pointer base
-    // indexed by an integer recurrence.
-
-    // If the GEP base pointer is a vector of pointers, abort.
-    if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy())
-      return false;
-
-    const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
-    const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
-    if (FromBase == ToBase)
-      return true;
-
-    LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: GEP rewrite bail out "
-                      << *FromBase << " != " << *ToBase << "\n");
-
-    return false;
-  }
-  return true;
-}
-
 static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) {
   SmallPtrSet<const Instruction *, 8> Visited;
   SmallVector<const Instruction *, 8> WorkList;
   Visited.insert(I);
   WorkList.push_back(I);
   while (!WorkList.empty()) {
     const Instruction *Curr = WorkList.pop_back_val();
     // This use is outside the loop, nothing to do.

 struct RewritePhi {
   PHINode *PN;               // For which PHI node is this replacement?
   unsigned Ith;              // For which incoming value?
   const SCEV *ExpansionSCEV; // The SCEV of the incoming value we are rewriting.
   Instruction *ExpansionPoint; // Where we'd like to expand that SCEV?
   bool HighCost;               // Is this expansion a high-cost?
 
   Value *Expansion = nullptr;
-  bool ValidRewrite = false;
 
   RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt,
              bool H)
       : PN(P), Ith(I), ExpansionSCEV(Val), ExpansionPoint(ExpansionPt),
         HighCost(H) {}
 };
 
 // Check whether it is possible to delete the loop after rewriting exit
static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
   while (PHINode *P = dyn_cast<PHINode>(BI)) {
     Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
 
     // If the Incoming value of P is found in RewritePhiSet, we know it
     // could be rewritten to use a loop invariant value in transformation
     // phase later. Skip it in the loop invariant check below.
     bool found = false;
     for (const RewritePhi &Phi : RewritePhiSet) {
-      if (!Phi.ValidRewrite)
-        continue;
       unsigned i = Phi.Ith;
       if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
         found = true;
         break;
       }
     }
 
     Instruction *I;
int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
   for (RewritePhi &Phi : RewritePhiSet) {
     Phi.Expansion = Rewriter.expandCodeFor(Phi.ExpansionSCEV, Phi.PN->getType(),
                                            Phi.ExpansionPoint);
 
     LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = "
                       << *(Phi.Expansion) << '\n'
                       << "  LoopVal = " << *(Phi.ExpansionPoint) << "\n");
 
-    // FIXME: isValidRewrite() is a hack. it should be an assert, eventually.
-    Phi.ValidRewrite = isValidRewrite(SE, Phi.ExpansionPoint, Phi.Expansion);
-    if (!Phi.ValidRewrite) {
-      DeadInsts.push_back(Phi.Expansion);
-      continue;
-    }
-
 #ifndef NDEBUG
     // If we reuse an instruction from a loop which is neither L nor one of
     // its containing loops, we end up breaking LCSSA form for this loop by
     // creating a new use of its instruction.
     if (auto *ExitInsn = dyn_cast<Instruction>(Phi.Expansion))
       if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
         if (EVL != L)
           assert(EVL->contains(L) && "LCSSA breach detected!");
 #endif
   }
 
   // TODO: after isValidRewrite() is an assertion, evaluate whether
   // it is beneficial to change how we calculate high-cost:
   // if we have SCEV 'A' which we know we will expand, should we calculate
   // the cost of other SCEV's after expanding SCEV 'A',
   // thus potentially giving cost bonus to those other SCEV's?
 
   bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
   int NumReplaced = 0;
 
   // Transformation.
   for (const RewritePhi &Phi : RewritePhiSet) {
-    if (!Phi.ValidRewrite)
-      continue;
-
     PHINode *PN = Phi.PN;
     Value *ExitVal = Phi.Expansion;
 
     // Only do the rewrite when the ExitValue can be expanded cheaply.
     // If LoopCanBeDel is true, rewrite exit value aggressively.
     if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
       DeadInsts.push_back(ExitVal);
       continue;

llvm/test/Transforms/IndVarSimplify/D108043.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -indvars -S %s | FileCheck %s
 
 @g_2168 = external global [4 x [6 x i32]], align 16
 @g_1150 = external global i32*, align 8
 
 define internal fastcc void @func_2() unnamed_addr {
 ; CHECK-LABEL: @func_2(
 ; CHECK-NEXT:  lbl_2898.preheader:
 ; CHECK-NEXT:    br label [[LBL_2898:%.*]]
 ; CHECK:       lbl_2898.loopexit:
-; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32* [ [[TMP0:%.*]], [[FOR_COND884:%.*]] ]
-; CHECK-NEXT:    store i32* [[DOTLCSSA]], i32** @g_1150, align 8
+; CHECK-NEXT:    store i32* getelementptr inbounds ([4 x [6 x i32]], [4 x [6 x i32]]* @g_2168, i64 0, i64 3, i64 1), i32** @g_1150, align 8
 ; CHECK-NEXT:    br label [[LBL_2898]]
 ; CHECK:       lbl_2898:
-; CHECK-NEXT:    [[G_1150_PROMOTED:%.*]] = load i32*, i32** @g_1150, align 8
-; CHECK-NEXT:    br label [[FOR_COND884]]
+; CHECK-NEXT:    br label [[FOR_COND884:%.*]]
 ; CHECK:       for.cond884:
-; CHECK-NEXT:    [[TMP0]] = phi i32* [ getelementptr inbounds ([4 x [6 x i32]], [4 x [6 x i32]]* @g_2168, i64 0, i64 3, i64 1), [[FOR_END987:%.*]] ], [ [[G_1150_PROMOTED]], [[LBL_2898]] ]
-; CHECK-NEXT:    [[STOREMERGE9:%.*]] = phi i16 [ [[ADD990:%.*]], [[FOR_END987]] ], [ 0, [[LBL_2898]] ]
-; CHECK-NEXT:    [[CMP886:%.*]] = icmp ult i16 [[STOREMERGE9]], 3
-; CHECK-NEXT:    br i1 [[CMP886]], label [[FOR_BODY888:%.*]], label [[LBL_2898_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br i1 false, label [[FOR_BODY888:%.*]], label [[LBL_2898_LOOPEXIT:%.*]]
 ; CHECK:       for.body888:
 ; CHECK-NEXT:    br label [[FOR_COND918:%.*]]
 ; CHECK:       for.cond918:
 ; CHECK-NEXT:    br label [[FOR_END926:%.*]]
 ; CHECK:       for.end926:
 ; CHECK-NEXT:    br label [[FOR_COND936:%.*]]
 ; CHECK:       for.cond936:
-; CHECK-NEXT:    br label [[FOR_END987]]
+; CHECK-NEXT:    br label [[FOR_END987:%.*]]
 ; CHECK:       for.end987:
-; CHECK-NEXT:    [[ADD990]] = add nuw nsw i16 [[STOREMERGE9]], 1
 ; CHECK-NEXT:    br label [[FOR_COND884]]
 ;
 lbl_2898.preheader:
   br label %lbl_2898
 
 lbl_2898.loopexit:
   %.lcssa = phi i32* [ %0, %for.cond884 ]
   store i32* %.lcssa, i32** @g_1150, align 8