induction variable computation not preserving scev

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.

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.

Nick

indvars.patch (2.3 KB)

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(). Offhand, is it possible that the problem
here is the same as the one in PR8037?

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

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

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

Indvars doesn't change the values of any existing instructions,
and it doesn't change the actual trip count of the loop. It just
adds new instructions which compute the same values as old
instructions, and deletes the old instructions. ScalarEvolution
uses ValueHandles to be notified of the deletions, and it doesn't
immediately care about new instructions.

Dan