[IndVars] Turn isValidRewrite into an assertion

[mkazantsev]

Summary

Function rewriteLoopExitValues contains a check on isValidRewrite which
is needed to make sure that SCEV does not convert the pattern
gep Base, (&p[n] - &p[0]) into gep &p[n], Base - &p[0]. This problem
has been fixed in SCEV long ago, so this check is just obsolete.

This patch converts it into an assertion to make sure that the SCEV will
not mess up this case in the future.

[atrick]

isValidRewrite is a hack that wasn't supposed to live this long.

At the IR level, the problem is simply that we don't want to rewrite

gep Base, (&p[n] - &p[0])

as

gep &p[n], Base - &p[0]

SCEV no longer does the kind of reassociation. I'm not sure when it was fixed, but the original test case definitely no longer requires the isValidRewrite check.

[atrick]

@sanjoy may have some insight as to why SCEV is now safe. If we know this why can't happen, you can completely remove isValidRewrite and don't need to assert.

If you want to keep the logic under an assert, then you could add a more understandable comment:

"Avoid converting gep Base, (&p[n] - &p[0]) into gep &p[n], Base - &p[0]"

[llvm-commits]

I think this particular problem was fixed a long time ago, likely
before I started working on SCEV. I think the relevant bit is here:
https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L6451

It's tempting to handle inttoptr and ptrtoint as no-ops, however this can
lead to pointer expressions which cannot safely be expanded to GEPs,
because ScalarEvolution doesn't respect the GEP aliasing rules when
simplifying integer expressions.

because we don't handle ptrtoint (&p[n] - &p[0]) will be a SCEVUnknown
and SCEV should not reassociate through this expression.

• Sanjoy

[atrick]

The bitcast bailout (implemented in 2009) (https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L6451)

wasn't catching this case (fixed in 2011). The problem had to do with LCSSA preventing normal SCEV simplification...

Before:

define i8* @stdimpl_itoa(i32 %v, i8* %string, i32 %r) nounwind {
entry:
  %buf.i = alloca [34 x i8], align 4
...
bb4.i12.preheader:                                ; preds = %bb.i4                                                                                                                                      
  %.lcssa20 = phi i8* [ %21, %bb.i4 ]
  br label %bb4.i12

bb4.i12:                                          ; preds = %bb4.i12, %bb4.i12.preheader                                                                                                                
  %start.0.i10 = phi i8* [ %26, %bb4.i12 ], [ %string, %bb4.i12.preheader ]
  %p.1.i11 = phi i8* [ %24, %bb4.i12 ], [ %.lcssa20, %bb4.i12.preheader ]
...
  store i8 %25, i8* %start.0.i10, align 1
  %26 = getelementptr inbounds i8* %start.0.i10, i32 1
  %27 = icmp eq i8* %16, %24
  br i1 %27, label %_ZL5_xtoamPcii.exit14, label %bb4.i12

_ZL5_xtoamPcii.exit14:                            ; preds = %bb4.i12                                                                                                                                    
  %.lcssa19 = phi i8* [ %26, %bb4.i12 ]
  store i8 0, i8* %.lcssa19, align 1
  ret i8* %string

Notice the definition of %26, the phi in the exit block and the store address.

After:

bb4.i12.preheader:                                ; preds = %bb.i4                                                                                                                                      
  %.lcssa20 = phi i8* [ %scevgep31, %bb.i4 ]
...
_ZL5_xtoamPcii.exit14:                            ; preds = %bb4.i12                                                                                                                                    
  %scevgep18 = getelementptr i8* %.lcssa20, i32 %scevgep1617
  store i8 0, i8* %scevgep18, align 1
  ret i8* %string

The address is effectively %scevgep31 which is defined in bb.i4:
%scevgep31 = getelementptr [34 x i8]* %buf.i, i32 0, i32 %tmp30

%buf.i is an alloca so DSE will end up deleting the store.

---

So, maybe it's best to leave the assertion.

[mkazantsev]

Added clarification comment, updated commit message to describe what is going on.

In D51582#1223389, @atrick wrote:

isValidRewrite is a hack that wasn't supposed to live this long.

At the IR level, the problem is simply that we don't want to rewrite

gep Base, (&p[n] - &p[0])

as

gep &p[n], Base - &p[0]

SCEV no longer does the kind of reassociation. I'm not sure when it was fixed, but the original test case definitely no longer requires the isValidRewrite check.

Thanks for explanation! Is the "original test case" you are mentioning present somewhere in the unit tests? If no, I'd appreciate if you could check it in.

Do you guys feel OK if we check in this patch (leaving this as assertion) with the comment update I've just made?

[atrick]

Is the "original test case" you are mentioning present somewhere in the unit tests? If no, I'd appreciate if you could check it in.

It looks like there was some proprietary C code that exposed this but never a reduced .ll test sadly. I'm positive that the original .c test no longer hits this assert, and think it's very unlikely that the current LLVM pipeline could still expose the issue. I'm just not sure exactly how SCEV itself guards against it.

I think it's fine for you to checkin this PR as-is, with the assert as a measure of safety.

[mkazantsev]

It seems we were wrong: http://lab.llvm.org:8011/builders/clang-ppc64be-linux-multistage/builds/11583/steps/build%20stage%202/logs/stdio

Patch reverted as rL341517. It seems that this situation is still possible. I'll try to make a reduced test example on that and commit it separately.

[mkazantsev]

This patch has been reverted, the situation it protects against seems still possible. It means that the initial theory was true and we need a unit test on that.

[atrick]

It's great that you have a reproducer. Sad that SCEV still hasn't been fixed. As I mentioned, I wasn't able to easily reproduce the problem from source. I know that, back in 2011, the issue was only exposed because LCSSA form was blocking some obvious SCEV optimization.

[mkazantsev]

I don't think I'll ever have time for this.

llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp

class IndVarSimplify {
   DominatorTree *DT;
   const DataLayout &DL;
   TargetLibraryInfo *TLI;
   const TargetTransformInfo *TTI;
 
   SmallVector<WeakTrackingVH, 16> DeadInsts;
   bool Changed = false;
 
+#ifndef NDEBUG
   bool isValidRewrite(Value *FromVal, Value *ToVal);
+#endif
 
   void handleFloatingPointIV(Loop *L, PHINode *PH);
   void rewriteNonIntegerIVs(Loop *L);
 
   void simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
 
   bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
   void rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
IndVarSimplify(LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
                  TargetTransformInfo *TTI)
       : LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI) {}
 
   bool run(Loop *L);
 };
 
 } // end anonymous namespace
 
+#ifndef NDEBUG
 /// 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.
+/// it is produced may be illegal IR.
 bool IndVarSimplify::isValidRewrite(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.
+  // could fail in a dangerous way. Specifically, we want to make sure that SCEV
+  // does not convert gep Base, (&p[n] - &p[0]) into gep &p[n], Base - &p[0].
   //
   // 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 (FromPtr != FromVal || ToPtr != ToVal) {
 
     LLVM_DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " << *FromBase
                       << " != " << *ToBase << "\n");
 
     return false;
   }
   return true;
 }
+#endif
 
 /// Determine the insertion point for this user. By default, insert immediately
 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
 /// common dominator for the incoming blocks.
 static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
                                           DominatorTree *DT, LoopInfo *LI) {
   PHINode *PHI = dyn_cast<PHINode>(User);
while ((PN = dyn_cast<PHINode>(BBI++))) {
 
         bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, Inst);
         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;
-        }
+        assert(isValidRewrite(Inst, ExitVal) && "Must be!");
 
 #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>(ExitVal))
           if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
             if (EVL != L)