This is an archive of the discontinued LLVM Phabricator instance.

[IVDescriptor] Find original 'Previous' for first-order recurrences.
ClosedPublic

Authored by fhahn on Jan 31 2022, 12:07 PM.

Details

Summary

This patch extends first-order recurrence handling to support cases
where we already sunk an instruction for a different recurrence, but
LastPrev comes before Previous.

To handle those cases correctly, we need to find the earliest entry for
the sink-after chain, because this is references the Previous from the
original recurrence. This is needed to ensure we use the correct
instruction as sink point.

Depends on D118558.

Diff Detail

Event Timeline

fhahn created this revision.Jan 31 2022, 12:07 PM
fhahn requested review of this revision.Jan 31 2022, 12:07 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 31 2022, 12:07 PM

I am not familiar with this code, so adding some likely better reviewers.

The description suggests that we have a potential to miscompile. Is that shown in the test diffs?

fhahn added a comment.Feb 27 2022, 4:57 AM

I am not familiar with this code, so adding some likely better reviewers.

The description suggests that we have a potential to miscompile. Is that shown in the test diffs?

Thanks. This shouldn't fix a mis-compile, it just handles more cases by replacing the exit return Previous->comesBefore(LastPrev); to handle additional cases.

fhahn updated this revision to Diff 411668.Feb 27 2022, 5:02 AM

Undo stale comment change.

Ayal added inline comments.Feb 28 2022, 8:14 AM
llvm/lib/Analysis/IVDescriptors.cpp
921

In addition to "Do not", explain what we "Do", e.g.:
// Avoid sinking an instruction multiple times (if multiple operands are first order recurrences) by sinking once - after the latest 'previous' instruction.

942

This traversal is going upwards, from use to def, maintaining original dependences in order, right? Worth asserting that each SinkAfter[OtherPrev] comes before OtherPrev, and that the initial OtherPrev comes before the last OtherPrev?

945

a[n] instruction

950

instead of sinking to OtherPrev.

fhahn updated this revision to Diff 412077.Mar 1 2022, 6:21 AM

Address latest comments, thanks!

fhahn marked 4 inline comments as done.Mar 1 2022, 6:23 AM
fhahn added inline comments.
llvm/lib/Analysis/IVDescriptors.cpp
921

Thanks, extended the comment!

942

Good point, I added the assertion in the loop. Note that for the last entry the comes-before relation won't hold. I also changed to loop to avoid using SinkAfter[].

945

Fixed, thanks!

950

Added above, thanks!

Allen added a subscriber: Allen.Mar 1 2022, 7:27 AM
Ayal accepted this revision.Mar 1 2022, 8:46 AM

Looks good to me, with a last nit.

llvm/lib/Analysis/IVDescriptors.cpp
937

Assert here that the last 'OtherPrev' is eventually a "Later Inst", i.e., that the original It->second comesBefore the final OtherPrev, or equal to it?

This revision is now accepted and ready to land.Mar 1 2022, 8:46 AM
This revision was automatically updated to reflect the committed changes.
fhahn marked 4 inline comments as done.
Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2022, 8:41 AM
fhahn marked an inline comment as done.Mar 3 2022, 8:52 AM
fhahn added inline comments.
llvm/lib/Analysis/IVDescriptors.cpp
937

Thanks, added in the committed version!

dyung added a subscriber: dyung.Mar 4 2022, 11:34 PM

@fhahn This change seems to be hitting an assertion failure in one of our internal tests. I have filed GHI#54223 with a repro. Can you take a look?

fhahn marked an inline comment as done.Mar 5 2022, 11:50 AM

@fhahn This change seems to be hitting an assertion failure in one of our internal tests. I have filed GHI#54223 with a repro. Can you take a look?

Thanks, that should be fixed by de8ac485e5b7

The issue was that the order in the map vector wasn't correct. That has been fixed by remove the entry before re-sinking. This ensures it will be sunk after all earlier instructions have been sunk.

Ayal added a comment.Mar 6 2022, 12:21 AM

@fhahn This change seems to be hitting an assertion failure in one of our internal tests. I have filed GHI#54223 with a repro. Can you take a look?

Thanks, that should be fixed by de8ac485e5b7

The issue was that the order in the map vector wasn't correct. That has been fixed by remove the entry before re-sinking. This ensures it will be sunk after all earlier instructions have been sunk.

Good catch!
Would be good to document the order: "if x and y both belong to SinkAfter and SinkAfter[x]==y, then y must appear before x"
This is enforced by always inserting at the end, and making sure to insert sinking chains in this order.
Would be good to assert that this order is maintained, either at each insertion, or prior to execution?
Wonder if alternatively SinkAfter could be an std::map with an explicit key comparison function, similar to InstrsToSink(?)