Page MenuHomePhabricator

[VPlan] Keep induction recipes in header.
ClosedPublic

Authored by fhahn on Oct 7 2021, 4:24 AM.

Details

Summary

This patch updates recipe creation to ensure all
VPWidenIntOrFpInductionRecipes are in the header block. At the moment,
new induction recipes can be created in different blocks when trying to
optimize casts and induction variables.

Having all induction recipes in the header makes it easier to
analyze/transform them in VPlan.

Diff Detail

Event Timeline

fhahn created this revision.Oct 7 2021, 4:24 AM
fhahn requested review of this revision.Oct 7 2021, 4:24 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 7 2021, 4:24 AM
Herald added a subscriber: vkmr. · View Herald Transcript
Ayal added inline comments.Oct 25 2021, 1:19 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
9371

Worth a comment why VPWidenIntOrFpInductionRecipe deserves special displacement.

(Easiest to handle here; just raising some related thoughts:
This is somewhat reminiscent of SinkAfter, in that recipes created next to their triggering ingredient need to be placed elsewhere; but SinkAfter is quite cumbersome. Other conceptual approaches may be to search for Trunc's when processing an IV Phi and produce a recipe for each (but current scheme produces a single recipe per triggering ingredient), and first hoisting the Trunc to appear in the header (i.e., cleaning up SinkAfter - perhaps once VPlan starts by representing the original scalar loop).)

9377

Suffice to have Header->insert(Recipe, Header->getFirstNonPhi()) for both cases?

May be worth wrapping within an insertPhi() method.

fhahn updated this revision to Diff 382356.Oct 26 2021, 9:06 AM

Added a comment as suggested and updated to use Header->insert() to avoid checking whether to append or not.

fhahn marked 2 inline comments as done.Oct 26 2021, 9:07 AM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
9371

Thanks, added a comment.

9377

Updated to use Header->insert(), thanks!

May be worth wrapping within an insertPhi() method.

Not sure if it's worth adding that helper just now. I think it would be good to add once we have multiple users.

Ayal accepted this revision.Oct 26 2021, 10:56 AM

Minor last comment nit.

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

That's clear, but suggest to explain what's unique about VPWidenIntOrFpInductionRecipe. E.g., something like:

// Make sure induction recipes are all kept in the header block.
// VPWidenIntOrFpInductionRecipe may be generated when reaching a
// Trunc of an induction Phi, where Trunc may not be in the header.
This revision is now accepted and ready to land.Oct 26 2021, 10:56 AM
fhahn updated this revision to Diff 383073.Oct 28 2021, 10:00 AM
fhahn marked 2 inline comments as done.

rebase

This revision was landed with ongoing or failed builds.Oct 28 2021, 10:22 AM
This revision was automatically updated to reflect the committed changes.
dyung added a subscriber: dyung.Tue, Nov 9, 7:24 PM

Hi, this change is hitting an assertion failure when run on one of our internal tests. I have put the details in PR52460, can you take a look?

fhahn added a comment.Wed, Nov 10, 3:44 AM

Hi, this change is hitting an assertion failure when run on one of our internal tests. I have put the details in PR52460, can you take a look?

Thanks for the report!

The issue is that sink-after for first-order recurrences might need to sink after the original truncate instruction of an optimized IV recipe, so we need to keep them in the original position until *after* sink-after. I pushed e7f1232cb777 to fix the crash. @Ayal it would be great if you could take a post-commit look, in case you have any ideas/thoughts how to resolve this differently.

Ayal added a comment.Wed, Nov 10, 2:08 PM

Hi, this change is hitting an assertion failure when run on one of our internal tests. I have put the details in PR52460, can you take a look?

Thanks for the report!

The issue is that sink-after for first-order recurrences might need to sink after the original truncate instruction of an optimized IV recipe, so we need to keep them in the original position until *after* sink-after. I pushed e7f1232cb777 to fix the crash. @Ayal it would be great if you could take a post-commit look, in case you have any ideas/thoughts how to resolve this differently.

An alternative fix: hoist trunc's into header phi recipes when created, as this patch originally did, and ignore/silence any sink-after targeting such truncs. Sink-afters ensure that uses of a FOR phi which originally appear before the Previous feeding the FOR phi, will appear after it; if Previous is hoisted to become a header phi, any such use is sure to appear after it, w/o needing to sink. I.e., the hoisting cancels the sinking. Sinking a user after a hoisted Previous may actually hoist the user, thereby potentially breaking dependences, as demonstrated by the PR/testcase.