Page MenuHomePhabricator

[Dominators] Use Instruction::comesBefore for block-local queries, NFC
ClosedPublic

Authored by vsk on Feb 20 2020, 2:21 PM.

Details

Summary

Use the lazy instruction ordering facility for block-local dominance
queries. IIUC this was just left out of https://reviews.llvm.org/D51664
as it was rebased.

Diff Detail

Event Timeline

vsk created this revision.Feb 20 2020, 2:21 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 20 2020, 2:21 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
kuhar accepted this revision.Feb 20 2020, 2:24 PM

LGTM

This revision is now accepted and ready to land.Feb 20 2020, 2:24 PM
rnk accepted this revision.Feb 20 2020, 2:26 PM

lgtm

I don't think it got lost in the rebase, I just never actually did this, the obvious thing. The next cleanup is to get rid of OrderedInstructions which is now a glorified wrapper of DominatorTree.

kuhar added inline comments.Feb 20 2020, 2:34 PM
llvm/lib/IR/Dominators.cpp
284

This code makes every user that is a phi be dominated by the def?
So if we have two phis, the one that comes later may be said to dominate its predecessor?

Not sure if I got confused here, but this looks fishy to me. Do we need this if at all?

vsk marked an inline comment as done.Feb 20 2020, 3:12 PM
vsk added inline comments.
llvm/lib/IR/Dominators.cpp
284

Yes, that's what this is doing, and no, I'm not sure this is /really/ needed.

IIUC all phis in a block are thought to execute "instantly, together". The verifier tries to make this clear by enforcing grouping of phis at the start of a block. Perhaps this is part of the enforcement mechanism, by making phi1 dom phi2 = phi2 dom phi1?

I find this inherently confusing, fwiw it's mentioned as a motivation for basic block arguments in the SIL/MLIR docs.

kuhar added inline comments.Feb 20 2020, 3:22 PM
llvm/lib/IR/Dominators.cpp
284

Ugh. But what happens when a phi has an incoming value that is another phi? Consider this pseudocode:

llvm
; predecessors %A, %B
%a = phi i32, [0, %A], [%b, %B]
%b = phi i32  [1, %A], [%2, %B]

The use of b in a's definition is considered valid from the perspective of dominance according to this code. Quickly glancing the llvm language reference I don't see anything saying you cannot use a phi value from the same basic block as an incoming value in another phi.

vsk updated this revision to Diff 245762.Feb 20 2020, 4:15 PM
vsk marked an inline comment as done.
vsk added inline comments.
llvm/lib/IR/Dominators.cpp
284

Thanks for the example. That's.. weird. But, yes, I think that is allowed under the "phis execute instantly, together" interpretation. I've added a unit test that shows this.

This revision was automatically updated to reflect the committed changes.
kuhar added inline comments.Feb 20 2020, 7:41 PM
llvm/lib/IR/Dominators.cpp
284

Great, thanks for including this, especially since this isn't a part of your change.

Note that the unit test is not exectly what I described, though: in my example, the first phi was forward-referencing the second phi. I'll try to follow up on this in a separe revision this weekend of the next week.

kuhar marked an inline comment as done.Feb 29 2020, 2:38 PM
kuhar added inline comments.
llvm/lib/IR/Dominators.cpp
284

Hi @vsk,

I've just checked this and both the pattern I described and the one that you added in the test are invalid; there's verification rules and LIT tests that make sure phi nodes in the same block don't cross-reference each other. Empirically, removing this special case for phi nodes breaks lots of existing tests.