Exponential inlining when inlining through mutually recursive functions in the presence of devirtualization

[aeubanks]

$ cat /tmp/a.ll

declare void @asdf()

@a = constant [2 x ptr] [ptr @g, ptr @h]

define void @f() {
        %a = alloca [2 x ptr]
        store [2 x ptr] [ptr @g, ptr @h], ptr %a
        call void @g(ptr %a, i64 0)
        ret void
}

define void @g(ptr %p, i64 %a) minsize {
        %b = add i64 %a, 1
        %c = getelementptr ptr, ptr %p, i64 %b
        %f = load ptr, ptr %c
        call void %f(ptr %p, i64 %b)
        call void @asdf()
        ret void
}

define void @h(ptr %p, i64 %a) minsize {
        %b = add i64 %a, -1
        %c = getelementptr ptr, ptr %p, i64 %b
        %f = load ptr, ptr %c
        call void %f(ptr %p, i64 %b)
        call void @asdf()
        ret void
}

$ opt -O3 -S /tmp/a.ll -max-devirt-iterations=20

...
define void @f() local_unnamed_addr {        
  %a = alloca [2 x ptr], align 8
  store ptr @g, ptr %a, align 8    
  %.fca.1.gep = getelementptr inbounds nuw i8, ptr %a, i64 8
  store ptr @h, ptr %.fca.1.gep, align 8
  call void @h(ptr nonnull %a, i64 1)
  call void @asdf()
  call void @asdf()      
  call void @asdf()                                     
  call void @asdf()  
  call void @asdf()                                     
  call void @asdf()                                     
  call void @asdf()                                     
  call void @asdf()     
  call void @asdf()
  call void @asdf()
  call void @asdf()
  call void @asdf()        
  call void @asdf()                                     
  call void @asdf()
  call void @asdf()
  call void @asdf()
  call void @asdf()
  call void @asdf()
  call void @asdf()
  call void @asdf()
  call void @asdf()
  ret void
}
...

the example here doesn't blow up exponentially but with more layers it can, as we've seen internally

g and h are mutually recursive given the arguments passed from f. normally the inline history would detect this, but the history is only kept within a run of the inliner pass. after inlining once, the indirect call can't be inlined, and we move on in the pipeline. another pass devirtualizes the call, and the devirtualization wrapper reruns the inliner + simplification pipeline. there's no inline history and we keep repeating the devirtualization + inlining until we hit -max-devirt-iterations.

we have things we keep track of within the context of an entire run of CGSCCPassManager, e.g.

llvm-project/llvm/include/llvm/Analysis/CGSCCPassManager.h

Line 289 in 6527a3a

&InlinedInternalEdges;

. we could keep track of inline history there, although I'm unsure of the proper way to do so, given that the inline history needs to be per-CallBase, and those CallBases can be modified/removed/cloned in the simplification pipeline. perhaps the most principled way is to mark the inline history in the IR itself, as we already do in the presence of debug information. for this bug we probably only need to do this for inlined indirect calls, but there may be some edge case with direct calls that would also benefit from this. I'm unsure of the overhead of doing so, and the type of debug info we'd want to emit in the case of no debug info

[tmimmanuel]

Hi, @aeubanks @EugeneZelenko I looked into the issue and traced the root cause.

InlineHistory in Inliner.cpp (line 291) is a local SmallVector that gets recreated fresh on each inliner invocation. When the devirt wrapper in CGSCCPassManager.cpp re-runs the inliner after detecting devirtualization, the new invocation has no memory of what was already inlined in previous iterations. This allows mutual recursion (like g↔h) to be inlined repeatedly, once per devirt iteration.

There are existing cross-iteration mechanisms (UR.InlinedInternalEdges, setIsNoInline() on recursive calls), but they don't cover the case where a newly devirtualized call reintroduces a previously-inlined function.

I think the cleanest fix is attaching !inline_history metadata to call sites produced by inlining, recording the chain of inlined functions. On subsequent devirt iterations, the inliner would read this metadata to reconstruct the history and skip calls that would re-inline an already-inlined function. This approach:

• Survives IR transformations (unlike pointer-based tracking across pass boundaries)
• Doesn't require new fields in CGSCCUpdateResult
• Follows the same pattern as DILocation/inlinedAt for debug info
• Handles call site cloning/SCC restructuring naturally

Can I try this way and raise a PR?

[EugeneZelenko]

@tmimmanuel, Sure, you could create pull request.