This is an archive of the discontinued LLVM Phabricator instance.

Handle some cases of mismatched types in IRCE
ClosedPublic

Authored by sanjoy on Jan 21 2015, 12:48 AM.

Details

Summary

There are places where the inductive range check elimination pass depends on two llvm::Values or llvm::SCEVs to be of the same llvm::Type when they do not need to be. This patch relaxes those restrictions, and adds test cases to trigger those paths.

Three things to note:

  • These issues were found by bootstrapping clang with IRCE running in the -O3 pass ordering.
  • I will follow up with a change that factors out an independent Range construct -- things like Range.first->getType() are ugly.
  • I have not added a test case that exercises the CIVComparedToSCEV->getType() != LatchCount->getType()) part of the change. That part of the change is needed when -indvars widens the induction variable, but leaves behind the old cached value for a loop's backedge taken count in scalar evolution (so the types mismatch but the actual value of the backedge-taken-count is still accurate). So far I have not managed to reproduce this problem outside of clang.

Diff Detail

Event Timeline

sanjoy updated this revision to Diff 18486.Jan 21 2015, 12:48 AM
sanjoy retitled this revision from to Handle some cases of mismatched types in IRCE.
sanjoy updated this object.
sanjoy edited the test plan for this revision. (Show Details)
sanjoy added reviewers: reames, hfinkel.
sanjoy added a subscriber: Unknown Object (MLST).
reames edited edge metadata.Jan 21 2015, 4:01 PM

LGTM once comments are addressed.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
666

Given these are non obvious, can you comment how such a scenario arises? Doesn't have to be repeated at each place, but some hint somewhere?

1136

Maybe add a TODO:?

test/Transforms/IRCE/bug-mismatched-types.ll
5

Add check lines and/or comments.

This revision was automatically updated to reflect the committed changes.
hfinkel edited edge metadata.Jan 22 2015, 9:44 PM

I have not added a test case that exercises the CIVComparedToSCEV->getType() != LatchCount->getType()) part of the change. That part of the change is needed when -indvars widens the induction variable, but leaves behind the old cached value for a loop's backedge taken count in scalar evolution (so the types mismatch but the actual value of the backedge-taken-count is still accurate). So far I have not managed to reproduce this problem outside of clang.

This sounds like a bug in indvars. Is it obvious how to fix it there?

This sounds like a bug in indvars. Is it obvious how to fix it there?

I think this is intentional -- IndVarSimplify has code to deal with this when verifying that the loop-backedge counts have not changed:

https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/IndVarSimplify.cpp#L2026

This sounds like a bug in indvars. Is it obvious how to fix it there?

I think this is intentional -- IndVarSimplify has code to deal with this when verifying that the loop-backedge counts have not changed:

https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/IndVarSimplify.cpp#L2026

Intentional or not, I think this is a bad idea. The results of an analysis should not depend on what transformations were run previously, but only on the current state of the IR. Do you agree?

If nothing else, there should at least be a loud warning about it on the interface to getBackedgeTakenCount in ScalarEvolution.h. I'd rather fix this so that we can get the backedge count of the proper size (maybe we need a better updating interface in SE? -- IndVars seems to *have* the correct updated BETC).

Intentional or not, I think this is a bad idea. The results of an analysis should not depend on what transformations were run previously, but only on the current state of the IR. Do you agree?

Agreed. It was mildly confusing when I could not reproduce the issue
with an IR dump taken before the pass was run in clang.

If nothing else, there should at least be a loud warning about it on the interface to getBackedgeTakenCount in ScalarEvolution.h. I'd rather fix this so that we can get the backedge count of the proper size (maybe we need a better updating interface in SE? -- IndVars seems to *have* the correct updated BETC).

Currently the only precedent for updating cached information in a
ScalarEvolution object are the forget.* family of functions. Will
adding anything more fine grained than these
("widenLoopBackedgeTakenCount") be a layering violation?

  • Sanjoy

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7082

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

Intentional or not, I think this is a bad idea. The results of an analysis should not depend on what transformations were run previously, but only on the current state of the IR. Do you agree?

Agreed. It was mildly confusing when I could not reproduce the issue
with an IR dump taken before the pass was run in clang.

Alright, let's fix this then ;)

If nothing else, there should at least be a loud warning about it on the interface to getBackedgeTakenCount in ScalarEvolution.h. I'd rather fix this so that we can get the backedge count of the proper size (maybe we need a better updating interface in SE? -- IndVars seems to *have* the correct updated BETC).

Currently the only precedent for updating cached information in a
ScalarEvolution object are the forget.* family of functions. Will
adding anything more fine grained than these
("widenLoopBackedgeTakenCount") be a layering violation?

Why does calling SE->forgetLoop(L) (as is done on line 2024), not clear the cache used to answer the SE->getBackedgeTakenCount(L) query (on line 2025)? Or am I misunderstanding something?

  • Sanjoy

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7082

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

Alright, let's fix this then ;)

Sure, I'll try to send in a fix soon.

Why does calling SE->forgetLoop(L) (as is done on line 2024), not clear the cache used to answer the SE->getBackedgeTakenCount(L) query (on line 2025)? Or am I misunderstanding something?

That bit of code runs under NDEBUG and VerifyIndVars to check that
widening the induction variable does not change the backedge taken
counts computed by scalar evolution. The reason I brought it up is
that it too has to compensate for the fact that the backedge taken
count computed by SCEV before and after running indvars have different
types (so what I faced is not an unknown issue).

  • Sanjoy
  • Sanjoy

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7082

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7082

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/