llvm dev - Jan 2011 - [LLVMdev] induction variable computation not preserving scev

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.

> > Would someone be willing to take a look at the failures and figure out
> why we're getting worse output once this patch is applied? If I had to
> hazard a guess, I'd say that indvars is probably emitting code that
can't be
> analyzed by SCEV as easily as the original.
>
> It's certainly plausible. It's easy to loose track of things like
> overflow behavior when folding casts into arithmetic, for example.
>
> Dan
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110119/32cd4172/attachment.html>

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. 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.

Dan

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>