Page MenuHomePhabricator

[SCEV] Handle case where MaxBECount is less precise than ExactBECount for OR.
ClosedPublic

Authored by fhahn on Mar 1 2019, 4:07 PM.

Details

Summary

In some cases, MaxBECount can be less precise than ExactBECount for AND
and OR (the AND case was PR26207). In the OR test case, both ExactBECounts are
undef, but MaxBECount are different, so we hit the assertion below. This
patch uses the same solution the AND case already uses.

Assertion failed:

((isa<SCEVCouldNotCompute>(ExactNotTaken) || !isa<SCEVCouldNotCompute>(MaxNotTaken))
  && "Exact is not allowed to be less precise than Max"), function ExitLimit

This patch also consolidates test cases for both AND and OR in a single
test case.

Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=13245

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.Mar 1 2019, 4:07 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 1 2019, 4:07 PM
sanjoy accepted this revision.Mar 1 2019, 4:43 PM

lgtm!

This revision is now accepted and ready to land.Mar 1 2019, 4:43 PM
fhahn added a comment.Mar 1 2019, 5:29 PM

Thanks! While looking at the assertion failure, I also had a look around to see if callers of getBackedgeTakenCount & co check if the returned SCEVExpr is undef, but it seems most users do not do that. I do not have a good concrete example, where using an undef exit count is problematic, but I was wondering if it is safe in general? To me it seems problematic, e.g. if a pass expands an undef SCEVExpr.

One fishy example I could come up with are alias checks in loop-vectorize. If the trip count is undef, we will generate alias checks using undef as upper bound. Those checks could pass (-> say noalias), even though the pointers actually alias in the vector loop ( because we pick a different value for the undef trip count and now the actual trip count is different than the one used for alias checks)

This revision was automatically updated to reflect the committed changes.

Thanks! While looking at the assertion failure, I also had a look around to see if callers of getBackedgeTakenCount & co check if the returned SCEVExpr is undef, but it seems most users do not do that. I do not have a good concrete example, where using an undef exit count is problematic, but I was wondering if it is safe in general? To me it seems problematic, e.g. if a pass expands an undef SCEVExpr.

One fishy example I could come up with are alias checks in loop-vectorize. If the trip count is undef, we will generate alias checks using undef as upper bound. Those checks could pass (-> say noalias), even though the pointers actually alias in the vector loop ( because we pick a different value for the undef trip count and now the actual trip count is different than the one used for alias checks)

I think you're right -- generating safety checks is unsound if there is an undef in the trip count expression. This will be solved once we use poison as the standard "deferred UB" construct. The software engineering problem here has been that it is very difficult to trigger this sort of corner cases using undef via well defined C/C++ programs, so we as a community haven't had an urgent incentive to fix these corner cases.

For now I think a good workaround would be to:

  • Not simplify undef in SCEV expressions
  • Avoid doing things that would require us to expand SCEV expressions with undef in them