<html>
<head>
<base href="https://bugs.llvm.org/">
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - Exponential code explosion during inlining"
href="https://bugs.llvm.org/show_bug.cgi?id=50485">50485</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Exponential code explosion during inlining
</td>
</tr>
<tr>
<th>Product</th>
<td>new-bugs
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>All
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>new bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>JCTremoulet@gmail.com
</td>
</tr>
<tr>
<th>CC</th>
<td>htmldeveloper@gmail.com, llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=24893" name="attach_24893" title="Repro showing pattern for exponential explosion, grows 1000x at this size.">attachment 24893</a> <a href="attachment.cgi?id=24893&action=edit" title="Repro showing pattern for exponential explosion, grows 1000x at this size.">[details]</a></span>
Repro showing pattern for exponential explosion, grows 1000x at this size.
Some of our code started failing to compile when change ed9df5bd2f50b changed
the optimization pipeline. The attached repro case demonstrates the issue
(seen via `opt -passes 'default<O3>'` or at <a href="https://godbolt.org/z/3vccKbxb5">https://godbolt.org/z/3vccKbxb5</a>).
The optimizations done to clean up inlined code can result in code being
smaller when considered as a transitive inline from a subsequent SCC than it
was when considered from its own SCC. This makes the inlines look more
favorable after their SCC has already converged, defeating the intent that the
bottom-up ordering will ensure that prior SCCs are already flattened out to the
point that inlining deeply through them will be undesirable.
Why commit ed9df5bd2f50b triggered this in our code is that the function sizes
before and after inlining cleanup now happen to yield inline costs that
straddle the threshold.
The attached repro case is structured as follows:
- It contains an SCC comprising a series of tiers. Each tier is densely
connected (one edge short of a clique), and has one edge to the next tier, with
the last having an edge back to the first, completing the cycle.
- Each individual function in each tier has just the right size and redundant
code (a handful of noop stores) so that calls to it are not inlined when the
large SCC is visited, but are inlined when it is revisited by transitive
inlining of the next SCC.
- The only other code is a singleton SCC (function @outside_scc) that calls
into the large SCC.
Inlining in @outside_scc proceeds until the InlineHistory kicks in and cuts it
off, which permits one inline of each acyclic path through the SCC, and the
number of such paths is exponential in the number of tiers, hence the code
explosion.
The original repro cases we've seen this in are actually two of the specint2k
benchmarks, though of course this is using our custom toolchain, so I'd say it
occurs in code that's real to us (we'll need a fix downstream regardless of
what happens upstream).</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>