[llvm-bugs] [Bug 50485] New: Exponential code explosion during inlining

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=50485

            Bug ID: 50485
           Summary: Exponential code explosion during inlining
           Product: new-bugs
           Version: trunk
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: JCTremoulet at gmail.com
                CC: htmldeveloper at gmail.com, llvm-bugs at lists.llvm.org

Created attachment 24893
  --> https://bugs.llvm.org/attachment.cgi?id=24893&action=edit
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 https://godbolt.org/z/3vccKbxb5).

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

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20210526/71d3bef9/attachment.html>