Page MenuHomePhabricator

[NaryReassociate] Detect deleted instr with WeakTrackingVH
ClosedPublic

Authored by Ka-Ka on May 21 2018, 7:18 AM.

Details

Summary

If NaryReassociate succeed it will, when replacing the old instruction
with the new instruction, also recursively delete trivially
dead instructions from the old instruction. However, if the input to the
NaryReassociate pass contain dead code it is not save to recursively
delete trivially deadinstructions as it might lead to deleting the newly
created instruction.

This patch will fix the problem by using WeakTrackingVH to detect this
rare case, when the newly created instruction is dead, and it will then
restart the basic block iteration from the beginning.

This fixes pr37539

Diff Detail

Repository
rL LLVM

Event Timeline

Ka-Ka created this revision.May 21 2018, 7:18 AM
tra edited reviewers, added: sanjoy; removed: jingyue.May 22 2018, 11:37 AM

@sanjoy is more familiar with this, so I've asked him to take a look.

test/Transforms/NaryReassociate/pr37539.ll
9 ↗(On Diff #147779)

You may want to replace it with CHECK: [[BB1]]
Same for BB7 below.

sanjoy requested changes to this revision.May 22 2018, 2:10 PM
sanjoy added inline comments.
lib/Transforms/Scalar/NaryReassociate.cpp
243 ↗(On Diff #147779)

You probably want WeakVH instead of WeakTrackingVH here. However, did you consider lazily deleting &*I instead of doing them in this loop? You could keep an std::vector of WeakVHs that are pending delete and delete them after leaving this loop.

This revision now requires changes to proceed.May 22 2018, 2:10 PM
Ka-Ka updated this revision to Diff 148166.May 23 2018, 12:23 AM
Ka-Ka marked 2 inline comments as done.

The reason for me to use WeakTrackingVH instead of WeakVH from the beginning was only that it was used elsewhere in the file. However as you point out WeakVH should be fine as RAUW is not used in RecursivelyDeleteTriviallyDeadInstructions(). I adjust the code to use WeakVH.

I did considered using the lazy approach. I actually tried it out, but it seems like the algorithm used here actually require RecursivelyDeleteTriviallyDeadInstructions to be used in the loop. I end up with infinite loops when trying the lazy approach. As I'm not really familiar with the the algorithm used, I instead made this minimal change to fix the problem I saw in pr37539.

I updated the testcase according to what was suggested in the review.

I end up with infinite loops when trying the lazy approach. As I'm not really familiar with the the algorithm used, I instead made this minimal change to fix the problem I saw in pr37539.

I see. However, the current patch is also risky in the same way (in that it looks like it may lead to infinite loops), but I don't know the algorithm here either. Unless the current patch is clearly not going to introduce infinite loops in your understanding, I'd suggest taking a closer look at making the lazy deletion work, or have some other scheme of avoiding the reset-to-beginning behavior.

lib/Transforms/Scalar/NaryReassociate.cpp
251 ↗(On Diff #148166)

This bit me is worrying me somewhat -- can this lead to an infinite loop (where we reassociate from A to B then back)?

Ka-Ka added inline comments.May 23 2018, 12:29 PM
lib/Transforms/Scalar/NaryReassociate.cpp
251 ↗(On Diff #148166)

I agree that restarting the iteration from BB->begin() is kind of ugly, but it will not lead to a infinite loop. The reason why is that RecursivelyDeleteTriviallyDeadInstructions() is starting deleting from 'I' that is a part of BB (as it looked from the beginning). We end up in this if clause if we, when recursively deleting, end up deleting 'NewI' (the instruction that should replace 'I'). However, as at least 'I' and 'NewI' was deleted, the basic block BB have always shrunk when restarting the iteration from BB-begin().

sanjoy accepted this revision.May 23 2018, 1:13 PM

lgtm

lib/Transforms/Scalar/NaryReassociate.cpp
251 ↗(On Diff #148166)

SGTM.

This revision is now accepted and ready to land.May 23 2018, 1:13 PM
This revision was automatically updated to reflect the committed changes.