Page MenuHomePhabricator

[DA] propagate loop live-out values that get used in a branch
ClosedPublic

Authored by sameerds on Jun 14 2020, 10:10 PM.

Details

Summary

Values that are uniform within a loop but appear divergent to uses
outside the loop are "tainted" so that such uses are marked
divergent. But if such a use is a branch, then it's divergence needs
to be propagated. The simplest way to do that is to put the branch
back in the main worklist so that it is processed appropriately.

Diff Detail

Event Timeline

sameerds created this revision.Jun 14 2020, 10:10 PM
foad added inline comments.Jun 15 2020, 2:27 AM
llvm/lib/Analysis/DivergenceAnalysis.cpp
111–114

I think it might be cleaner to put this in compute just before the call to updateTerminator. It feels wrong to make updateTerminator non-const, and the relationship between Worklist and DeferredTerminators seems clearer if instructions are removed from them in the same place, in compute. But I'll happily defer to others who are more familiar with this code.

sameerds added inline comments.Jun 15 2020, 5:52 AM
llvm/lib/Analysis/DivergenceAnalysis.cpp
111–114

Yeah, I was torn between what you describe and what is seen here in the patch. I don't have a strong opinion either way, so I just picked one. In its defense, the current version keeps the "detail" out of compute ... membership in the deferred set is just one of the criteria to decide whether to update the terminator. But I can see why removing the const is not palatable.

One way to balance both sides is to move the erase operation to propagateBranchDivergence, which is where the terminator is marked divergent anyway. This nicely separates the readonly part from the modify part.

simoll added a comment.EditedJun 15 2020, 8:06 AM

You could short cut this by calling propagateBranchDivergence right away instead of using DeferredTerminators (and mark the terminator as divergent). That's in the same spirit as calling pushUsers on a regular instruction since sync dependence is just a different kind of dependence.

sameerds updated this revision to Diff 271049.Jun 16 2020, 4:55 AM

eliminate DeferredTerminators; also a small refactor for readability

simoll accepted this revision.Jun 16 2020, 7:04 AM

LGTM. Thanks!

This revision is now accepted and ready to land.Jun 16 2020, 7:04 AM
This revision was automatically updated to reflect the committed changes.