This is an archive of the discontinued LLVM Phabricator instance.

Use a deterministic order when updating the DominatorTree
ClosedPublic

Authored by bjope on Sep 22 2021, 2:51 PM.

Details

Summary

This solved a problem with non-deterministic output from opt due
to not performing dominator tree updates in a deterministic order.
The problem found was the JumpThreading used the DomTreeUpdater via
llvm::MergeBasicBlockIntoOnlyPred. And when preparing the list of
updates to send to DomTreeUpdater::applyUpdates we iterated over
a SmallPtrSet, which does not give a well-defined order.

The added domtree-updates.ll test case is an example that would
result in non-deterministic printouts of the domtree. Semantically
those domtree:s where equivalent, but since passes (at least EarlyCSE)
are iterating over nodes in the dominator tree the order in which
transforms are applied transitively also depend on the order in which
dominator tree updates are performed.

Diff Detail

Event Timeline

bjope created this revision.Sep 22 2021, 2:51 PM
bjope requested review of this revision.Sep 22 2021, 2:51 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 22 2021, 2:51 PM

I think we need to first establish whether this is a bug in DomTree/DomTreeUpdater or the passes that depend on the dom tree node order or here.

bjope added a comment.Sep 23 2021, 4:36 AM

I think we need to first establish whether this is a bug in DomTree/DomTreeUpdater or the passes that depend on the dom tree node order or here.

Sure! Agreed!
When I started off with this patch I thought it was a single place to update (i.e. that it really was a one-location bug). But now it seems like this was more of a design choice since the patch grew so large.

Here are some of my ideas about it (and my motivations for/against are probably pretty vague):

One assumed upside with this patch is that if passes like EarlyCSE need to make an ordering for the nodes to be iterated themselves, then that would be an extra cost (at least potentially) compared to just doing things in a deterministic order from the start.
With that being said, the accumulative cost of doing things like in this patch up-front might end up being higher than doing a single sorting later. And it will also just add a cost even if there are no passes later in the pipeline that depends on the node order. So lots of uncertainty when considering which is best for compile-time.

One downside with this is that if the analysis is invalidated (and recalculated from scratch) then we probably get a different order of the nodes. Still making things a bit shaky when debugging/bisecting/reducing test cases.
With that being said, when debugging and printing the DomTree between passes etc it could be nice if the printout is deterministic. This could of course be solved by doing some kind of sorting before printing, just like we would have to do in EarlyCSE. And the performance of the print-function should not be that important.

(maybe this discussion should move back to the llvm-dev mailthread...)

foad added a subscriber: foad.Sep 27 2021, 8:38 AM
foad added inline comments.
llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
242

This line looks like a bug fix -- or does it just avoid doing some unnecesssary updates?

bjope added inline comments.Sep 27 2021, 8:51 AM
llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
242

This will go away when rebasing. It was pre committed as: https://reviews.llvm.org/rG85a586501bcc5b556d34a566b9d256d56d6fc5ba

bjope updated this revision to Diff 389960.Nov 26 2021, 2:22 AM

Updated code comments.

bjope added a comment.Nov 26 2021, 2:24 AM

I'm also showing the alternative approach, making EarlyCSE less depending on what other passes is doing when updating the DomTree, here: https://reviews.llvm.org/D114620

kuhar added inline comments.Nov 26 2021, 7:00 AM
llvm/include/llvm/Support/GenericDomTree.h
550–552

unordered -> ordered also here?

llvm/lib/CodeGen/IndirectBrExpandPass.cpp
265–267

This pattern appears many time in the patch. I wonder if we could have a helper function that helps with that. Perhaps something like insert_range(InsertTo, NewElements) -> RangeOfInserted:

for (BasicBlock* Inserted : insert_range(UniqueSuccessors, BBs))
  Updates.push_back(...);
llvm/test/Transforms/JumpThreading/domtree-updates.ll
12

nit: I -> We or `it was possible to see varrying'

lebedev.ri added inline comments.Nov 26 2021, 7:16 AM
llvm/lib/CodeGen/IndirectBrExpandPass.cpp
265–267

I tried doing that in D99444, but reviewers weren't convinced and i lacked motivation to follow-up.

kuhar added a comment.Nov 26 2021, 8:10 AM

I think it would be good to send the DomTree documentation changes separately as they are a clear improvement regardless of whether this patch goes in or not.

llvm/lib/CodeGen/IndirectBrExpandPass.cpp
265–267

Then I think it's fine as is, and we could clean it up separately.

nikic accepted this revision.Nov 28 2021, 12:51 PM
nikic added a subscriber: nikic.

LGTM

This revision is now accepted and ready to land.Nov 28 2021, 12:51 PM
This revision was landed with ongoing or failed builds.Nov 29 2021, 4:22 AM
This revision was automatically updated to reflect the committed changes.
bjope marked 2 inline comments as done.Nov 29 2021, 4:25 AM
bjope added inline comments.
llvm/lib/CodeGen/IndirectBrExpandPass.cpp
265–267

Ok, great. Thanks for all the feedback.