[llvm-dev] Glued nodes from legalization lead to cycle after combine2

[Tim Neumann via llvm-dev]

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>