Page MenuHomePhabricator

[LV] Fix crash when target instruction for sinking is dead.
ClosedPublic

Authored by fhahn on Jun 20 2021, 3:17 AM.

Details

Summary

This patch fixes a crash when the target instruction for sinking is
dead. In that case, no recipe is created and trying to get the recipe
for it results in a crash. To ensure all sink targets are alive, find &
use the first previous alive instruction.

Note that the case where the sink source is dead is already handled.

Found by
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=35320

Diff Detail

Event Timeline

fhahn created this revision.Jun 20 2021, 3:17 AM
fhahn requested review of this revision.Jun 20 2021, 3:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 20 2021, 3:17 AM
Ayal added a comment.Jun 21 2021, 7:15 AM

Ahh, the culprit here is a chain of FOR phi-users all sinking after a Previous - the latter should never be dead, but any member of the chain may by dead.
In the test case: %rec.2 is the FOR phi, %rec.2.prev is Previous, and {%cmp, %C, %B2} is the chain of users, where %B2 is dead as it feeds the loop's conditional branch only.

An alternative fix is to have RecurrenceDescriptor::isFirstOrderRecurrence() sink the chain in reverse, always after the non-dead Previous; as you originally suggested in D84951?

fhahn updated this revision to Diff 353445.Jun 21 2021, 11:55 AM

Ahh, the culprit here is a chain of FOR phi-users all sinking after a Previous - the latter should never be dead, but any member of the chain may by dead.
In the test case: %rec.2 is the FOR phi, %rec.2.prev is Previous, and {%cmp, %C, %B2} is the chain of users, where %B2 is dead as it feeds the loop's conditional branch only.

Yes exactly! Let me improve the naming of the variables a bit.

An alternative fix is to have RecurrenceDescriptor::isFirstOrderRecurrence() sink the chain in reverse, always after the non-dead Previous; as you originally suggested in D84951?

I think another alternative would be to handle the check for dead instructions directly at the place where we do sinking. I updated the code to do that. Please let me know if you prefer the alternative.

I think chaining the instructions in the map makes sense and the handling of dead instructions before VPlan creation may go away in the medium term anyways?

fhahn updated this revision to Diff 353446.Jun 21 2021, 11:56 AM

Adjust FOR phi variable name in test.

Ayal added a comment.Jun 27 2021, 2:47 AM

Ahh, the culprit here is a chain of FOR phi-users all sinking after a Previous - the latter should never be dead, but any member of the chain may by dead.
In the test case: %rec.2 is the FOR phi, %rec.2.prev is Previous, and {%cmp, %C, %B2} is the chain of users, where %B2 is dead as it feeds the loop's conditional branch only.

Yes exactly! Let me improve the naming of the variables a bit.

Good! Can also call out explicitly the %dead value.

An alternative fix is to have RecurrenceDescriptor::isFirstOrderRecurrence() sink the chain in reverse, always after the non-dead Previous; as you originally suggested in D84951?

I think another alternative would be to handle the check for dead instructions directly at the place where we do sinking. I updated the code to do that. Please let me know if you prefer the alternative.

I think chaining the instructions in the map makes sense and the handling of dead instructions before VPlan creation may go away in the medium term anyways?

Agreed that in the medium term, dead instructions may be handled differently in/before VPlan/Legal, so would be good to have a simple fix for now.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
9041

It may be better to handle all updates of SinkAfter due to DeadInstructions in one place, i.e., erasing dead sinks and bumping dead targets, either both here or both below inside buildVPlanWithVPRecipes(Range).

9224

Traversing the dead backwards here should also be ok, but raises additional thoughts.
If we reach FirstInst == SinkTarget then no sinking is required, which should not happen, so best have an assert instead? May want to also assert against falling off the first recipe of the block.

Additional alternatives, on top of reversing SinkAfter chains, include (mainly for completion):

  1. Letting Legal handle DeadInstructions, so that SinkTarget will include only live sinks to be moved after live targets. But there's a dependence on FoldTail wanting to "reuse" Primary Induction.
  2. Having the first VPlan wrap Dead Instructions with a (recorded) Dead Recipe, to be eliminated by a VPlan-to-VPlan DCE.
  3. Set LastLiveSecond = (Entry.second is live ? Entry.second : LastLiveSecond), and always sink SinkTarget after LastLiveSecond. This relies on iteration order over SinkAfter being {U_1,Previous},{U_2,U_1},...,{U_k,U_{k-1}} whenever some target U_i is dead, where Previous must be live.

Can also handle dead sinks here, as mentioned above, e.g., by continue. Less efficient, but sizes of SinkAfter and DeadInstructions should be very small if positive.

Can also update the sinkAfter pair whose target was revived, caching the result for next Range.

fhahn updated this revision to Diff 354840.Jun 28 2021, 4:25 AM

Moved back to location next to deleting dead sink sources. Also added assertions as suggested.

Ahh, the culprit here is a chain of FOR phi-users all sinking after a Previous - the latter should never be dead, but any member of the chain may by dead.
In the test case: %rec.2 is the FOR phi, %rec.2.prev is Previous, and {%cmp, %C, %B2} is the chain of users, where %B2 is dead as it feeds the loop's conditional branch only.

Yes exactly! Let me improve the naming of the variables a bit.

Good! Can also call out explicitly the %dead value.

Done, also added a comment to the test.

fhahn updated this revision to Diff 354842.Jun 28 2021, 4:28 AM
fhahn marked an inline comment as done.

Rename *Cur* to *SinkTarget*.

fhahn added inline comments.Jun 28 2021, 4:29 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
9224

Traversing the dead backwards here should also be ok, but raises additional thoughts.
If we reach FirstInst == SinkTarget then no sinking is required, which should not happen, so best have an assert instead? May want to also assert against falling off the first recipe of the block.

I added 2 assertions above:

  • SinkTarget != FirstInst, should guard against failing of the first recipe in the block
  • SinkTarget != SinkSource, should guard against cases not requiring any sinking?

WDYT?

Ayal accepted this revision.Jun 28 2021, 2:32 PM

Thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
9052

a alive >> a live

9054

This second assert(SinkTarget != P.first) should be placed right after bumping SinkTarget to its prev node.
(We know P.first ain't dead - these were taken care of above; so if SinkTarget get set to P.first, we will immediately exit the loop, before reaching this assert here. So can also place the assert right after the loop.)
(The first assert is placed well, guarding against taking FirstInst->getPrevNode().)

9224

+1, just a remark above about where to place the second assert.

This revision is now accepted and ready to land.Jun 28 2021, 2:32 PM
This revision was landed with ongoing or failed builds.Jun 29 2021, 5:35 AM
This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.
fhahn added a comment.Jun 29 2021, 5:35 AM

Thanks Ayal!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
9054

Thanks, I moved the second assert in the committed version.