Page MenuHomePhabricator

[DivRemPairs] Avoid RAUW pitfalls (PR42823)
ClosedPublic

Authored by lebedev.ri on Jul 30 2019, 7:43 AM.

Details

Summary

DivRemPairs internally creates two maps:

  • {sign, divident, divisor} -> div instruction
  • {sign, divident, divisor} -> rem instruction

Then it iterates over rem map, and looks if there is an entry
in div map with the same key. Then depending on some internal logic
it may RAUW rem instruction with something else.

But if that rem instruction is an input to other div/rem,
then it was used as a key in these maps, so the old value (used in key)
is now dandling, because RAUW didn't update those maps.
And we can't even RAUW map keys in general, there's ValueMap,
but we don't have a single Value as key...

The bug was discovered via D65298, and the test there exists.
Now, i'm not sure how to expose this issue in trunk.
The bug is clearly there if i change the map keys to be AssertingVH/PoisoningVH,
but i guess this didn't miscompiled anything thus far?
I really don't think this is benin without that patch.

The fix is actually rather straight-forward - instead of trying to somehow
shoe-horn ValueMap here (doesn't fit, key isn't just Value), or writing a new
ValueMap with key being a struct of Values, we can just have an intermediate
data structure - a vector, each entry containing matching Div, Rem pair,
and pre-filling it before doing any modifications.
This way we won't need to query map after doing RAUW, so no bug is possible.

Diff Detail

Repository
rL LLVM

Event Timeline

lebedev.ri created this revision.Jul 30 2019, 7:43 AM

Sorry about the bug - this is why I suggested in the previous review that someone with a better grasp of C++ / data structures have a look. :)
In the original code, if we delay the RAUW by inserting instructions in a ToBeKilled worklist in the loop (and only doing the erasing as a post-processing step) is there still a bug?

llvm/lib/Transforms/Scalar/DivRemPairs.cpp
62 ↗(On Diff #212337)

spelling: getDivident --> getDividend

lebedev.ri marked an inline comment as done.
lebedev.ri edited the summary of this revision. (Show Details)

Updated - fix typo, no need for TrackingVH, simply using worklist was sufficient to fix it.

spatel accepted this revision.Jul 31 2019, 3:09 AM

LGTM - should the test from https://bugs.llvm.org/show_bug.cgi?id=42823 be included with this patch even if does not fail yet without D65298?

llvm/lib/Transforms/Scalar/DivRemPairs.cpp
210–214 ↗(On Diff #212386)

Add to this code comment to explain why we need to preserve the Sub in RemInst?

This revision is now accepted and ready to land.Jul 31 2019, 3:09 AM

LGTM

Thank you for the review.

should the test from https://bugs.llvm.org/show_bug.cgi?id=42823 be included with this patch even if does not fail yet without D65298?

I precommitted them already.

Closed by commit rL367417: [DivRemPairs] Avoid RAUW pitfalls (PR42823) (authored by lebedevri, committed by ). · Explain WhyJul 31 2019, 5:08 AM
This revision was automatically updated to reflect the committed changes.