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