[LLVMdev] induction variable computation not preserving scev

[Nick Lewycky]

On 20 January 2011 11:23, Dan Gohman <gohman at apple.com> wrote:

>
> On Jan 19, 2011, at 2:03 PM, Nick Lewycky wrote:
>
> > On 19 January 2011 13:01, Dan Gohman <gohman at apple.com> wrote:
> >
> > On Jan 18, 2011, at 12:32 AM, Nick Lewycky wrote:
> >
> > > Hi,
> > >
> > > I tracked down a bug in indvars where we weren't updating SCEV
> properly. The attached patch shows the fix to this bug with a testcase, but
> it also causes five new test failures.
> >
> > Indvars isn't restructuring the loop there, so it ideally shouldn't
> > need to call forgetLoop().
> >
> > Hmm? It certainly is, it's changing the condition on the branch
> instruction that makes up the loop latch!
> >
> > Offhand, is it possible that the problem
> > here is the same as the one in PR8037?
> >
> > No, that only shows up when you try to run "opt -analyze -indvars
> -scalar-evolution" by causing a crash. With that patch in place, you can see
> that "opt -analyze -indvars -scalar-evolution" produces different values for
> the SCEVs than you get with "opt -indvars | opt -analyze -scalar-evolution"
> which led me to add the forgetLoop here.
>
> Ah, I tried the testcase, saw the crash, and assumed that was the bug
> you were aiming to fix. The forgetLoop() call shouldn't be necessary
> for correctness.


Why not though? Is there some guarantee that the values of the variables
within the loop can't have been changed by this? I expected to find such a
property based on my understanding of indvars, but when I looked through the
code I couldn't convince myself of it. Can you make such an argument?

But I do see how ScalarEvolution's cached tripcounts
> are sub-optimal in this case, because they retain the type of the loop's
> original induction variable, rather than the type that indvars has
> chosen for the new induction variable. So forgetLoop() makes sense
> there.
>

That's what I expected, and what I see in the testcase attached. However, a
bunch of tests fail with this patch in:

Failing Tests (5):
>     LLVM :: Transforms/IndVarSimplify/ashr-tripcount.ll
>     LLVM :: Transforms/IndVarSimplify/iv-sext.ll
>     LLVM :: Transforms/IndVarSimplify/preserve-signed-wrap.ll
>     LLVM :: Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll
>     LLVM :: Transforms/IndVarSimplify/signed-trip-count.ll


and as far as I can see, they're not just silly errors because we changed
the SCEVs slightly; we're actually generating worse code when with
forgetLoop() in indvars. That's what I don't understand.

I debugged one example and that led to the simplification I added to SCEV in
r123838, but we're still not eliminating the sext instructions that the
testcases expect.

Nick
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110120/ddb95b83/attachment.html>