<div dir="ltr"><div dir="auto">Hi all,</div><div dir="auto"><br></div><div dir="auto">TL;DR: Legalization introduces 2 glued nodes, combine2 creates a pseudo-cycle because the glue edge is only unidirectional, the scheduler merges the glued nodes ==> cycle between SUnits ==> Assertion triggers.</div><div dir="auto"><br></div><div dir="auto">Background: I've been experiment with Rust & AVR and ran into the following issue. The original source was Rust, the IR of the reduced test [0] case was generated by LLVM@341010 [1] with some Rust specific [2] and an unrelated local patch [3]. The reduced test case reproduces the problem on LLVM HEAD.</div><div dir="auto"><br></div><div dir="auto">To reproduce: Run `llc -O1 reduced.ll [0]`.</div><div dir="auto"><br></div><div dir="auto">What happens: The assertion `(Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] && "Wrong topological sorting"` triggers in `ScheduleDAG.cpp:506`. </div><div dir="auto"><br></div><div>Consider the graphs before [4] and after [5] combine2: `t28` and `t29` are glued together and have been created by `DAGTypeLegalizer::ExpandIntRes_ADDSUB`. In `DAGCombiner::CombineToPostIndexedLoadStore`, LLVM considers `t21` and `t35` and decides that they can be combined to `t40`. This creates a "pseudo-cycle": If the glued nodes `t28` and `t29` were combined (or the glue edge reversed) there would be an actual cycle.</div><div><br></div><div>A comment in `CombineToPostIndexedLoadStore` states that "Op must be independent of N, i.e. Op is neither a predecessor nor a successor of N. Otherwise, if Op is folded that would create a cycle", which is, of course, correct. To verify the two nodes' (Op and N) independence, LLVM checks if they are predecessors of each other. This check returns `false` in the case at hand, which is correct if one only follows the edges actually present in the graph. However, the way the two glue nodes are handled later by the scheduler means that the edge between them would need to be treated as bidirectional to get the desired result. (Note that if you flip the glue edge, you have the dependency `t35` -> `t28` -> `t29` -> `t22` -> `t21`).</div><div><br></div><div>The schedule later combines the two nodes (graph at [6]), leading to a cycle. That cycle then causes the assertion error when verifying the topological ordering.</div><div><br></div><div>Even though I only found this bug on an experimental target, I feel like the core issue is target independent. </div><div><br></div><div><b>I would appreciate your thoughts on the matter, especially regarding a potential solution.</b></div><div><b><br></b></div><div>I can see three places where to attempt a solution:</div><div><br></div><div>(1) Change the TypeLegalizer to no longer generate the glue.</div><div>(2) Change the Combiner to better handle glue links.</div><div>(3) Change the scheduler to not merge the glued nodes if doing so would create a cycle.</div><div><br></div><div>(2) looks most promising to me, so I will experiment with that solution for now, by treating glue links as bidirectional (whether to do this for all predecessor checks or only some, how to implement that most efficiently, and how to handle the existing topological ordering optimization are questions for another time).</div><div><br></div><div>[0] <a href="https://gist.github.com/TimNN/149b9e5b1967eb0a4d004c34ff73f728">https://gist.github.com/TimNN/149b9e5b1967eb0a4d004c34ff73f728</a></div><div>[1] <a href="https://github.com/llvm-mirror/llvm/commit/bdeb8b88b91">https://github.com/llvm-mirror/llvm/commit/bdeb8b88b91</a></div><div>[2] <a href="https://github.com/rust-lang/llvm/compare/bdeb8b88b91...caddcd9b9dc">https://github.com/rust-lang/llvm/compare/bdeb8b88b91...caddcd9b9dc</a></div><div>[3] <a href="https://github.com/avr-rust/rust/issues/92#issuecomment-428407427">https://github.com/avr-rust/rust/issues/92#issuecomment-428407427</a></div><div>[4] <a href="https://user-images.githubusercontent.com/1178249/46693484-31ad9980-cc0a-11e8-9943-f2c01c8eae6c.png">https://user-images.githubusercontent.com/1178249/46693484-31ad9980-cc0a-11e8-9943-f2c01c8eae6c.png</a></div><div>[5] <a href="https://user-images.githubusercontent.com/1178249/46693487-35412080-cc0a-11e8-8808-5c40edabb48d.png">https://user-images.githubusercontent.com/1178249/46693487-35412080-cc0a-11e8-8808-5c40edabb48d.png</a></div><div>[6] <a href="https://user-images.githubusercontent.com/1178249/46692253-168d5a80-cc07-11e8-9333-4c1082fc3470.png">https://user-images.githubusercontent.com/1178249/46692253-168d5a80-cc07-11e8-9333-4c1082fc3470.png</a></div><div><br></div><div>Best Regards</div><div>Tim </div><div><br></div>
</div>