<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/60773>60773</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [Inliner] Exponential inlining through devirtualised call
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          jmorse
      </td>
    </tr>
</table>

<pre>
    Hi,

We're observing exponential inlining in scenarios where a function call can be devirtualised when being inlined into an outer reference-cycle. See the reproducer below, and hopefully my terminology is correct: I believe `rec_call_to_longname` and `longname` form one RefSCC, while the chain of calls from `e` form an outer RefSCC. Whenever we inline the inner cycle into the outer RefSCC, it devirtualises the indirect function call and generates a new inlining site to be expanded -- as there are two calls to %0 in `longname`, this becomes exponential. 

I think this is similar to #44598 and https://reviews.llvm.org/D121084 , where the same thing happens within an SCC. In this example that recursion is hidden behind the devirtualised call. The fix in D121084 was to annotate recursively inlined functions with an attribute increasing their inline-cost -- the diff below extends that behaviour to identifying function calls that have definitely been devirtualised during inlining, and thus risk cycling around a RefSCC(?) (my terminology here is shaky). The compile-time cost is a linear examination of edges in the newly inlined function, and whether the callee has an edge to the new-call-site function -- if it doesn't, the new-call-site must have been devirtutalised.

Reproducer with the 8-day-old 2399497c9d68, 

    target triple = "x86_64-unknown-unknown"

    @extern = external global ptr

 declare void @extern1()
    declare void @extern2()
    declare i32 @extern3()

    define internal void @rec_call_to_longname() {
 store ptr @extern, ptr @e
      br i1 undef, label %1, label %2, !prof !0

    1:
      call void @longname(ptr @rec_call_to_longname, ptr undef, ptr undef)
      br label %2

    2:
      ret void
 }

    define internal void @longname(ptr %0, ptr %1, ptr %2) {
 call void @extern1()
      call void @extern2()
      %4 = call i32 @extern3()
      br label %5

    5:          
      call void %0()  ; jmorse: with one call, linear grown
      call void %0()  ; jmorse: with two, exponential
      ret void
    }

    define void @e() {
      call void @c()
      ret void
    }

 define internal void @c() {
      call void @a()
      ret void
 }

    define internal void @a() {
      call void @rec_call_to_longname()
      ret void
    }

    !0 = !{!"branch_weights", i32 8, i32 592480}

`opt --passes=cgscc(inline) -o - -S` causes the definition of `e` to contain 7 different instances of `longname`. Adding another call into the chain from `e` to `rec_call_to_longname` causes another round of inlining and more function size.

Here's a patch that fixes it for me. I've never touched the inliner before, so this might not be a suitable approach; I also don't have a good way of getting a representative benchmark of the runtime performance implications.

    diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp
    index 5bcfc38c585b..58683e913c2c 100644
    --- a/llvm/lib/Transforms/IPO/Inliner.cpp
    +++ b/llvm/lib/Transforms/IPO/Inliner.cpp
    @@ -959,7 +959,33 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
 // inline through the SCC the function will end up being
 // self-recursive which the inliner bails out on, and inlining
 // within an SCC is necessary for performance.
    - if (CalleeSCC != C &&
    +
    +              // Was there an edge from the callee to the new callee? if there
    +              // wasn't, this call was devirtualised.
    +              bool WasEdge = false;
    +              auto &Node = CG.get(Callee);
    + for (llvm::LazyCallGraph::Edge &E : *Node)
    +                if (&E.getNode() == &CG.get(*NewCallee))
    +                  WasEdge = true;
    +
    +              if (!WasEdge && CalleeSCC != C &&
 +                  CalleeSCC != CG.lookupSCC(CG.get(*NewCallee)))  {
    + // Take cost multiplier from the new call-site function: we do
    +                // not get the SCC-post-order traversal guarantee, the new
    +                // call could be to somewhere before or after our current
    +                // position in the RefSCC, and might be "reset" to a lower
    +                // value by another call.
 +                auto OptCost =
    + getStringFnAttrAsInt(
    +                        *ICB, InlineConstants::
    + FunctionInlineCostMultiplierAttributeName);
    + CBCostMult = (OptCost) ? *OptCost : 1;
    +                Attribute NewCBCostMult = Attribute::get(
    + M.getContext(),
    + InlineConstants::FunctionInlineCostMultiplierAttributeName,
    + itostr(std::min(CBCostMult * IntraSCCCostMultiplier, 10000)));
 +                NewCallee->addFnAttr(NewCBCostMult);
    + } else if (CalleeSCC != C &&
                       CalleeSCC == CG.lookupSCC(CG.get(*NewCallee))) {
                     Attribute NewCBCostMult = Attribute::get(
 M.getContext(),


</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJysWVtv4zjP_jXqDZHAkXO86EUmne4W-PaA7QJ7OZBtOtZWlgxJTpr99R8oOY6dpp3O4C2KHGyRIh-S4kNHOCf3GvGeLb6wxcOdaH1l7P2_tbEO7zJTnO5_lYzvWPLAkm18_QcZX1kEkzm0B6n3gK-N0ai9FAqkVlLTRanB5aiFlcbBsUKLIKBsde6l0ZALpSAXGjKEAg_S-lYo6bCgpXQ1qlBSYwFSewNCg2k9WrBYokWd4yQ_5Qqn8IwIvkKw2FhTtDlayFCZI-M7ELqAyjRYtkqdoD6BR1tLbZTZn0A6yI21mHuWbuGJpCQeENgysZh_Ixu_efNNGb3Xoka2TII-tkyGl0pjazAa4S8sn3c72vVYSRVtyishNZgyOOygtKYm-Ytg71aUnsI_FWo8oIUjdgAERVJrtBA8jnjQxaEk7Sv9CEzXSRaSfLwCnzzZo0YrPDoQoPF4CZ6THsEbig6-NkIXWMBkAiJopEhaBH80nVfeAOOLhEI-xoZs8pV0kGFuanTDTJnCMKmeaJ1-iaulAydrqYSNqtP5fLFZx1h63ziWbhl_ZPzR4kHi0U2VOtRTY_eMPz7M-CxZzyGGgWwlDJyoMeywh0o0DWoHR0nfCf8A-5OOe-OrqJsQPOHBYt5aR5BJB5UsipCaldRF0DpOXMJiCn9XCKV8JSzOphxFgEhobbzweNZ6QHXqU_wcm2gXWSW8tzJrPQUwtygcGe8rlLYTmuTGeYpKMEWWZcx6wFePunDRgwwrcZCmDUjKgqAvT6RplAzd4kocyKlSaunJuAxRXzlZtLavTKn35xLzVevASvcSMpRWCGtaXYDos3PN0kfGN8D4-qoMQ5Qo5pV4OTG-iSDmpm6kwomXNX1xnpYIIM-FDWGSWgQPTAlY7NER5oSFxuMNZM-mHiukHI7VKZRChEo4QpyUQFdZGo8TujsJldCDNZmALEOZGXSa8ZWPKX4tULeug3OIoY8gToeJ_9fl0AqRJ13rSSFOE6MK4OlmM9-s8k2xXNNOQ0kAAC_sHj14KylnWfoAjPPX9fLbcj5p9Ys2R31-Z5xfS7N5QslidZCMH4WCvTKZUNB4OxIoMFdU9wcji4vojCLLNxelt5fx95bJlF9WpcNVw7UlHYNSdwaeVd88pIMGYKsvnbzzxiI5c9mGkDxfuOwCkFmQM2h1gSUtUSJDRSfbbPSNh0DwWWNNSe_JtbkzOp8GasNxe7Z5YGdnwm0vooW9LYMvmyuTB4ZdGcKvDLHogx3dNbZ6-CzS11bzRdKD2OHTfeZj9Ee-v5MxcGvVm4QB0j4PmRqWv584b5FZXPu5oIbf_71jSnAyZBOw9AtEUkSCoVCp49PikBvxUNpbqrOfUeaPhvQM2uMHcSOL3w1dj-KbQniLdP4Wte9v9V6K5J_YUHx3wx_ISfGJDd8_IX4YX6r07oSd0ZZ8xjjPrNB59e2Icl95R0cssbCUw_r8YbHh83VypY8tE9NQ726Ec-hY-pDvXU4Ixq5Fbk0MTGDyTEQxF-2ZzHXduWt7ZybpDeRGe6Kaq0AFiCB7kNp5oXN03doBM5vCtihCn9YmtMNYU2diGWnriK0SE3ufF3cmnrXF5m_KC6Ok1lvTSdz3Uif_w1Er_BUtjRbU5Rvh8yqSklK-Umv3RJehxik8Mb46UMMlkuxNm1dYdESXsCPyXxobjlBnIqmrKTygDfEhEOBa6UWmEETTWCPyiiryCYRyBgoT2nps3gL2xhRwFCfyZY_eB1fCpIEOtRdehh6v86oW9oVWhUmk1YG2NGiJ5FMMQNaNknlgLG76JseJvk0me-lBMP5IfJbeZMb4499WaEdqHOOPT3_-Qa_R02neNJD92PrLnlIX-AqLLC_zdJ0v1otsOl2sl-sUN7M05znMkmQ5n18EJjQB_OxujH-J_z9vMJsnbJ7AZLPYML5bkcr4MU3P9_6ksNgDFlst1IkystP0p3BhbEi3ttWMr_9P_HfaCaV-saKp4o3nHbX15ROVl1C7fuqFOGtchjFr2n0kaiRC731OH6VSgLqAtokz7FiFQ1VOevpPY2JejVNXSOVorIMLYe259kjVaHwhaqwxR-eEPYVCGWTedBBBYq-Mr3eB90aHZ3SmBc_pfxSv4RcY_XVG_HMZCDv6HI6MAbW-0OnuCksfyYgg9f0NjmLIsmlep2OKBqrRWDL9QFNmjCJDv5J55GspFHXej9wTbZg7l7-bIsrsfpnu0ffIUf-4VkCoM74OmR3y6UaKRRv48itQ52d8SxuMmtEbU6ALGUmRDVEiNr70IfajZW8eqcTjxcjvqIYRMN62b3D5QPxs16zXEVIIvpdcN-14K_TLVBnz0jZxePzIw8CpVlemdgn0t3jppse6VV42SqK9JOk5LcdTXmBlCIX5ELtuA2oqYQSLx8GkMc5PjC2oN1lxQOtoomqFFdojDqbFzyiPT8lMqwpqXN6AMzXGpxqxyYGxIEqPFmjEz1tLff8zmhvjIovoZubLM6TQqEO_zCiknE5UzzgPjzBAmSPaz2xwEKpFyE4jgjF9PwVCyf3R-B3FijJ7tMce_bO3Uu8f9dZ7u3VPOiTDx8l9Nmj7tPtCrsVesDOBFvmuH4x1PHY5cF7q_G993mzPT2R-Dyzy7RGw-3IW6IjiunMoVusjmXJxcUuD4kcFBtDvCJTzY-39vehGVx0jbb9RzeyM9vjqO9bbN7VuyU1IfgCEK3XSG-ct42vni6irltRuh7bzLTxpb8XzbjdWTSGaJUmS9HV9wecGOP0xMGHpV1EUMTUYX4-wuhUntnoAVA4_3w1v_A2k4jn8YyfW1dTyPwr8BxGPr3fFfVps0o24w_vZcrWcr1bJbHNX3Rd8juvVqihTPlsvE464WSQJrtZzjrjI-J285wlPEz5bzJZJmm6mi02R5ckaswSTcr3MaOishVT909g76VyL98tktUrvwizuwu8MnIdnzXSTJqbFw529J5lJ1u4dmydKOn95pnvnpVfhB4qOyrHFA3y99YvDmZm9fSx711p1P350vJe-arNpbuoBHSUjGmv-xdwz_hgsJE4aPPj_AAAA__8Mx4z4">