[llvm-dev] [IndVarSimplify] Narrow IV's are not eliminated resulting in inefficient code

[Sanjoy Das via llvm-dev]

Hi Oleg,

I think the problem here is that SCEV forgets to propagate no-wrap
flags when folding "{S,+,X}+T ==> {S+T,+,X}".

I haven't carefully thought about the implications and whether the
change is even correct, but the appended patch fixes the test case
you've attached.  I'll give it some more thought and if it holds up
I'll check it in in the next few days.  Meanwhile if you have a larger
test case that you extracted indvar_test.cpp from, I'd be interested
in hearing if this change works there as well.

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 39ced1e..2e87902 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -2274,19 +2274,19 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
        }

      // If we found some loop invariants, fold them into the recurrence.
      if (!LIOps.empty()) {
        //  NLI + LI + {Start,+,Step}  -->  NLI + {LI+Start,+,Step}
        LIOps.push_back(AddRec->getStart());

        SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
                                               AddRec->op_end());
-      AddRecOps[0] = getAddExpr(LIOps);
+      AddRecOps[0] = getAddExpr(LIOps, Flags);

        // Build the new addrec. Propagate the NUW and NSW flags if both the
        // outer add and the inner addrec are guaranteed to have no overflow.
        // Always propagate NW.
        Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
        const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags);

        // If all of the other operands were loop invariant, we are done.
        if (Ops.size() == 1) return NewRec;

Thanks!
-- Sanjoy