Page MenuHomePhabricator

Use a deterministic order when updating the DominatorTree
Needs ReviewPublic

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

Details

Reviewers
lebedev.ri
kuhar
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

Unit TestsFailed

TimeTest
90 msx64 debian > ORC-x86_64-linux.TestCases/Linux/x86-64::trivial-cxa-atexit.S
Script: -- : 'RUN: at line 3'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -m64 -c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/orc/X86_64LinuxConfig/TestCases/Linux/x86-64/Output/trivial-cxa-atexit.S.tmp /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/orc/TestCases/Linux/x86-64/trivial-cxa-atexit.S
90 msx64 debian > ORC-x86_64-linux.TestCases/Linux/x86-64::trivial-static-initializer.S
Script: -- : 'RUN: at line 7'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -m64 -c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/orc/X86_64LinuxConfig/TestCases/Linux/x86-64/Output/trivial-static-initializer.S.tmp /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/orc/TestCases/Linux/x86-64/trivial-static-initializer.S
80 msx64 debian > ORC-x86_64-linux.TestCases/Linux/x86-64::trivial-tls.S
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -m64 -c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/orc/X86_64LinuxConfig/TestCases/Linux/x86-64/Output/trivial-tls.S.tmp /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/orc/TestCases/Linux/x86-64/trivial-tls.S

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.Thu, Sep 23, 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.Mon, Sep 27, 8:38 AM
foad added inline comments.
llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
234

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

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

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