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

[Friedman, Eli via llvm-dev]

On 10/10/2018 8:43 AM, Tim Neumann via llvm-dev wrote:
> 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.

This is probably viable; the legalizer only generates 
ISD::ADDC/ISD::ADDE if your target marks them "Legal".  We've been 
gradually switching other targets to use ISD::UADDO/ISD::ADDCARRY 
instead, which don't use glue.

> (2) Change the Combiner to better handle glue links.

This is probably a good idea in any case.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181010/151aec26/attachment.html>