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

[Oleg Ranevskyy via llvm-dev]

Hi Sanjoy,

Thank you for looking into this!
Yes, your patch does fix my larger test case too. My algorithm gets double
performance improvement with the patch, as the loop now has a smaller
instruction set and succeeds to unroll w/o any extra #pragma's.

I also ran the LLVM tests against the patch. There are 6 new failures:
    Analysis/LoopAccessAnalysis/number-of-memchecks.ll
    Analysis/LoopAccessAnalysis/reverse-memcheck-bounds.ll
    Analysis/ScalarEvolution/flags-from-poison.ll
    Analysis/ScalarEvolution/nsw-offset-assume.ll
    Analysis/ScalarEvolution/nsw-offset.ll
    Analysis/ScalarEvolution/nsw.ll

I haven't inspected these failures in detail yet, but it's likely the tests
merely need to be adjusted to handle the new no-wrap flags the patch
introduced. I will double-check this soon.

Kind regards,
Oleg

On Fri, Apr 22, 2016 at 11:02 AM, Sanjoy Das <sanjoy at playingwithpointers.com
> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160423/178fcd8d/attachment.html>