<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">On 10/10/2018 8:43 AM, Tim Neumann via
llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAJpFH-wFzxY=074=YNnajGDfTf1qHfbE_Uka=-waafvAXT3qRw@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<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>
</blockquote>
<br>
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.<br>
<br>
<blockquote type="cite"
cite="mid:CAJpFH-wFzxY=074=YNnajGDfTf1qHfbE_Uka=-waafvAXT3qRw@mail.gmail.com">
<div dir="ltr">
<div>(2) Change the Combiner to better handle glue links.</div>
</div>
</blockquote>
<br>
This is probably a good idea in any case.<br>
<br>
-Eli<br>
<br>
<pre class="moz-signature" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</body>
</html>