This is an archive of the discontinued LLVM Phabricator instance.

[IndVarSimplify][LoopUtils] Avoid TOCTOU/ordering issues (PR45835)
ClosedPublic

Authored by lebedev.ri on May 12 2020, 7:23 AM.

Details

Summary

Currently, rewriteLoopExitValues()'s logic is roughly as following:

Loop over each incoming value in each PHI node.
Query whether the SCEV for that incoming value is high-cost.
Expand the SCEV.
Perform sanity check (isValidRewrite(), D51582)
Record the info
Afterwards, see if we can drop the loop given replacements.
Maybe perform replacements.

The problem is that we interleave SCEV cost checking and expansion.
This is A Problem, because isHighCostExpansion() takes special care
to not bill for the expansions that were already expanded, and we can reuse.

While it makes sense in general - if we know that we will expand some SCEV,
all the other SCEV's costs should account for that, which might cause
some of them to become non-high-cost too, and cause chain reaction.

But that isn't what we are doing here. We expand *all* SCEV's, unconditionally.
So every next SCEV's cost will be affected by the already-performed expansions
for previous SCEV's. Even if we are not planning on keeping
some of the expansions we performed.

Worse yet, this current "bonus" depends on the exact PHI node
incoming value processing order. This is completely wrong.

As an example of an issue, see @dmajor's pr45835.ll - if we happen to have
a PHI node with two(!) identical high-cost incoming values for the same basic blocks,
we would decide first time around that it is high-cost, expand it,
and immediately decide that it is not high-cost because we have an expansion
that we could reuse (because we expanded it right before, temporarily),
and replace the second incoming value but not the first one;
thus resulting in a broken PHI.

What we instead should do for now, is not perform any expansions
until after we've queried all the costs.

Later, in particular after isValidRewrite() is an assertion (D51582)
we could improve upon that, but in a more coherent fashion.

See PR45835

Diff Detail

Event Timeline

lebedev.ri created this revision.May 12 2020, 7:23 AM
nikic added a subscriber: nikic.May 12 2020, 7:53 AM

Is it a problem that the test case doesn't fail on trunk before the patch, since SCEVMinMaxExpr is no longer automatically high cost? I noted this in D79720 but wasn't sure how to nudge the code around it.

Is it a problem that the test case doesn't fail on trunk before the patch, since SCEVMinMaxExpr is no longer automatically high cost? I noted this in D79720 but wasn't sure how to nudge the code around it.

Oh right, fixed.

dmajor accepted this revision.May 12 2020, 9:32 AM

Thanks a lot for taking this over! Looks good from my side but you may wish to wait for a more expert review.

I also confirmed that this still fixes our issue on the 10.0 branch. I had to remove -scev-cheap-expansion-budget=1 since that didn't exist in 10, but fortunately it's not needed there. Since it wasn't a clean merge, I put the diff in P8220 if it makes your/Tom's life easier.

This revision is now accepted and ready to land.May 12 2020, 9:32 AM

Thanks a lot for taking this over! Looks good from my side but you may wish to wait for a more expert review.

I also confirmed that this still fixes our issue on the 10.0 branch. I had to remove -scev-cheap-expansion-budget=1 since that didn't exist in 10, but fortunately it's not needed there. Since it wasn't a clean merge, I put the diff in P8220 if it makes your/Tom's life easier.

Thank you for the review!
Waiting on @reames / @mkazantsev / ...

lebedev.ri requested review of this revision.May 19 2020, 5:33 AM
mkazantsev added a comment.EditedMay 19 2020, 9:33 PM

In general, I'm ok with nits regarding naming. However this FIXME is concerning. Could you please add a XFAIL test that shows the difference between current state and when this check is turned into assert?

llvm/lib/Transforms/Utils/LoopUtils.cpp
1219

Please give it either more clear name or more clear comment. The actual SCEV of what? Besides, please avoid including word Value into the name of SCEVs in a code that has both, it creates confusion. :)

1220

Nit: maybe call it insertion/expansion point?

1220

Initialization?

Thank you for taking a look!

In general, I'm ok with nits regarding naming.

However this FIXME is concerning. Could you please add a XFAIL test that shows the difference between current state and when this check is turned into assert?

I don't have an actionable example at hand. I could just drop FIXME if it's too weird.

The thought is:
since the current as we have just seen in the new testcase the order of expansion affects the cost calculation,
then

  1. may it be the case that we might have two exit values (A and B) that we can rewrite
  2. one is high-cost (A) while other one is not high-cost (B)
  3. the high-cost A is based on low-cost B (something like A = B + 42)

Therefore, if we'd expand low-cost B first, then the cost of high-cost A would be lower,
potentially becoming low-cost, and we could be okay expanding it too.
Let me know if that does/doesn't make sense.

lebedev.ri marked 3 inline comments as done.

Attempted to address naming nits. Is this any better?

mkazantsev accepted this revision.May 21 2020, 1:16 AM

I don't have an actionable example at hand. I could just drop FIXME if it's too weird.

Then please add a debug printout that it happened.

Otherwise I don't have much objections. LGTM.

llvm/lib/Transforms/Utils/LoopUtils.cpp
1220

Better call it ValidRewrite because of HighCost without Is above.

This revision is now accepted and ready to land.May 21 2020, 1:16 AM

I don't have an actionable example at hand. I could just drop FIXME if it's too weird.

Then please add a debug printout that it happened.

I'm sorry, i'm not sure i follow. It's not a bug, it's a potential improvement.
There is no point in trying to detect such a situation right now
because it will bring no benefit but will cost us compile time.

Otherwise I don't have much objections. LGTM.

Thank you for the review!

This revision was automatically updated to reflect the committed changes.