[llvm-dev] Glued nodes from legalization lead to cycle after combine2 (original) (raw)

Tim Neumann via llvm-dev llvm-dev at lists.llvm.org
Wed Oct 10 08:43:42 PDT 2018

Hi all,

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.

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 at 341010 [1] with some Rust specific [2] and an unrelated local patch [3]. The reduced test case reproduces the problem on LLVM HEAD.

To reproduce: Run llc -O1 reduced.ll [0].

What happens: The assertion (Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] && "Wrong topological sorting" triggers in ScheduleDAG.cpp:506.

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.

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).

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.

Even though I only found this bug on an experimental target, I feel like the core issue is target independent.

I would appreciate your thoughts on the matter, especially regarding a potential solution.

I can see three places where to attempt a solution:

(1) Change the TypeLegalizer to no longer generate the glue. (2) Change the Combiner to better handle glue links. (3) Change the scheduler to not merge the glued nodes if doing so would create a cycle.

(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).

[0] https://gist.github.com/TimNN/149b9e5b1967eb0a4d004c34ff73f728 [1] https://github.com/llvm-mirror/llvm/commit/bdeb8b88b91 [2] https://github.com/rust-lang/llvm/compare/bdeb8b88b91...caddcd9b9dc [3] https://github.com/avr-rust/rust/issues/92#issuecomment-428407427 [4] https://user-images.githubusercontent.com/1178249/46693484-31ad9980-cc0a-11e8-9943-f2c01c8eae6c.png [5] https://user-images.githubusercontent.com/1178249/46693487-35412080-cc0a-11e8-8808-5c40edabb48d.png [6] https://user-images.githubusercontent.com/1178249/46692253-168d5a80-cc07-11e8-9333-4c1082fc3470.png

Best Regards Tim -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181010/d1b1cc7a/attachment-0001.html>

More information about the llvm-dev mailing list