[llvm-dev] DominatorTree, JumpThreading and EarlyCSE non-determinism

Tue Sep 21 07:27:02 PDT 2021

Hi Björn,

>From the perspective of DomTree, node children are generally unordered. I
think a pass can be sensitive to DT order by either directly relying on
tree children order or on DFS numbers.
If that's the case, one workaround would be to re-order children based on
the block order in the parent. If that's a common enough requirement, we
could add it to DT.

Would that solve the problem?
-Jakub

On Tue, Sep 21, 2021 at 9:33 AM Björn Pettersson A via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Yes, the IR looks the same out from jump-threading for this specific input
> (at least when comparing output from -print-after-all).
>
> It is the order of the DominatorTree updates that I suspect differ a bit
> (at least according to the -debug printouts), giving slightly different
> node orders in the DominatorTree. And I have no idea if JumpThreading can
> be blamed for that or if it is the Lazy strategy in the DomTreeUpdater.
>
> I guess I'll file a PR for this. But I'm still not quite sure what the
> rules are here (if both passes are wrong, or which one to blame), and what
> to expect more generally in situation like this one.
>
> /Björn
>
> > -----Original Message-----
> > From: Roman Lebedev <lebedev.ri at gmail.com>
> > Sent: den 21 september 2021 15:15
> > To: Björn Pettersson A <bjorn.a.pettersson at ericsson.com>
> > Cc: llvm-dev <llvm-dev at lists.llvm.org>; Johan Ringström
> > <johan.ringstrom at ericsson.com>
> > Subject: Re: [llvm-dev] DominatorTree, JumpThreading and EarlyCSE non-
> > determinism
> >
> > Does JumpThreading produce exactly the same IR in all of the situations?
> > But even if it does, this does seem like a bug.
> >
> > Roman
> >
> > On Tue, Sep 21, 2021 at 4:10 PM Björn Pettersson A via llvm-dev
> > <llvm-dev at lists.llvm.org> wrote:
> > >
> > > Hello llvm-dev,
> > >
> > > Recently I've been debugging a non-determinism problem.
> > >
> > > I've managed to narrow it down to running:
> > >
> > >  opt -passes='function(jump-threading,print<domtree>,early-cse)'
> > >
> > >
> > > From debug printouts (also adding -debug to the cmd line) it looks like
> > jump-threading is doing doing dominator tree updates in a
> non-deterministic
> > order (when comparing different runs).
> > >
> > > I randomly get either of these two DominatorTrees in the print<domtree>
> > printouts:
> > >
> > > DominatorTree for function: g
> > > =============================--------------------------------
> > > Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries.
> > >   [1] %entry {4294967295,4294967295} [0]
> > >     [2] %for.cond1 {4294967295,4294967295} [1]
> > >       [3] %if.then {4294967295,4294967295} [2]
> > >         [4] %for.cond5.preheader {4294967295,4294967295} [3]
> > >           [5] %cleanup {4294967295,4294967295} [4]
> > >             [6] %cleanup16 {4294967295,4294967295} [5]
> > >               [7] %unreachable {4294967295,4294967295} [6]
> > >               [7] %for.end21 {4294967295,4294967295} [6]
> > >           [5] %for.body7 {4294967295,4294967295} [4]
> > >             [6] %for.inc {4294967295,4294967295} [5]
> > >           [5] %return {4294967295,4294967295} [4]
> > >       [3] %cleanup16.thread {4294967295,4294967295} [2]
> > >       [3] %for.inc19 {4294967295,4294967295} [2]
> > >     [2] %for.cond {4294967295,4294967295} [1]
> > > Roots: %entry
> > >
> > > DominatorTree for function: g
> > > =============================--------------------------------
> > > Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries.
> > >   [1] %entry {4294967295,4294967295} [0]
> > >     [2] %for.cond1 {4294967295,4294967295} [1]
> > >       [3] %for.inc19 {4294967295,4294967295} [2]
> > >       [3] %if.then {4294967295,4294967295} [2]
> > >         [4] %for.cond5.preheader {4294967295,4294967295} [3]
> > >           [5] %cleanup {4294967295,4294967295} [4]
> > >             [6] %cleanup16 {4294967295,4294967295} [5]
> > >               [7] %unreachable {4294967295,4294967295} [6]
> > >               [7] %for.end21 {4294967295,4294967295} [6]
> > >           [5] %for.body7 {4294967295,4294967295} [4]
> > >             [6] %for.inc {4294967295,4294967295} [5]
> > >           [5] %return {4294967295,4294967295} [4]
> > >       [3] %cleanup16.thread {4294967295,4294967295} [2]
> > >     [2] %for.cond {4294967295,4294967295} [1]
> > > Roots: %entry
> > >
> > >
> > > I think both trees are correct, the nodes are just in a different
> order.
> > This can also be seen if I add invalidate<domtree> before print<domtree>
> to
> > force a recalculation. Then it will look like this instead (same content,
> > but the level 3 nodes printed in yet another order):
> > >
> > > DominatorTree for function: g
> > > =============================--------------------------------
> > > Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries.
> > >   [1] %entry {4294967295,4294967295} [0]
> > >     [2] %for.cond1 {4294967295,4294967295} [1]
> > >       [3] %cleanup16.thread {4294967295,4294967295} [2]
> > >       [3] %for.inc19 {4294967295,4294967295} [2]
> > >       [3] %if.then {4294967295,4294967295} [2]
> > >         [4] %for.cond5.preheader {4294967295,4294967295} [3]
> > >           [5] %cleanup {4294967295,4294967295} [4]
> > >             [6] %cleanup16 {4294967295,4294967295} [5]
> > >               [7] %unreachable {4294967295,4294967295} [6]
> > >               [7] %for.end21 {4294967295,4294967295} [6]
> > >           [5] %return {4294967295,4294967295} [4]
> > >           [5] %for.body7 {4294967295,4294967295} [4]
> > >             [6] %for.inc {4294967295,4294967295} [5]
> > >     [2] %for.cond {4294967295,4294967295} [1]
> > > Roots: %entry
> > >
> > >
> > > *** Question one ***
> > > Maybe it is OK from a correctness point-of-view that JumpThreading
> isn't
> > producing the same node order every time (given same input), even though
> it
> > might be a bit confusing when debugging. Or should this be seen as a bug?
> > >
> > >
> > > Next problem/question is related to EarlyCSE. It looks like the output
> > from EarlyCSE depends on the node order in the dominator tree. So
> depending
> > on if JumpThreading has produced the first or second of the DominatorTree
> > structures above we might end up eliminating one more/less PHI node
> during
> > EarlyCSE.
> > >
> > > *** Question two ***
> > > Should be seen as a bug? Or are passes in general sensitive to how
> > analysis information is produced (such as the node order in a dominator
> > tree) and thus being allowed to produce better/worse code depending on
> such
> > things?
> > >
> > >
> > > To summarize:
> > > JumpThreading is non-deterministic but produces semantically
> "equivalent"
> > results.
> > > EarlyCSE is deterministic, but the result depends on order of nodes in
> > the DominatorTree.
> > > Those two things together gives a non-deterministic IR result. And I
> > figure that should be seen as a bug. Just not sure if the fault is in
> > DominatorTreeUpdater, JumpThreading or EarlyCSE (or if it should be seen
> as
> > multiple faults).
> > >
> > > Regards,
> > > Björn
> > > _______________________________________________
> > > LLVM Developers mailing list
> > > llvm-dev at lists.llvm.org
> > > https://protect2.fireeye.com/v1/url?k=dfb69fe9-802da6ec-dfb6df72-
> > 86959e472243-b94d5bb9ef523712&q=1&e=3ff5c3d9-dda7-472c-aef6-
> > a705903687cb&u=https%3A%2F%2Flists.llvm.org%2Fcgi-
> > bin%2Fmailman%2Flistinfo%2Fllvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

-- 
Jakub Kuderski
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210921/c8dcffe6/attachment.html>