llvm / llvm/llvm-project

[LLVM] Missed tail call due to extractvalue/insertvalue

Open
#219,486 0 comments 0 reactions 0 assignees View on GitHub
llvm:codegen missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

I'm currently working on iteration of `std::set` and have the following function to count the number of nodes:
```llvm
define { i64, i32 } @recurse(ptr %__break.coerce, ptr nofree noundef readonly captures(address) %__root, i32 %__func.coerce) {
entry:
%0 = load ptr, ptr %__root, align 8
%tobool.not = icmp eq ptr %0, null
br i1 %tobool.not, label %if.end14, label %if.then

if.then:
%call = tail call { i64, i32 } @recurse(ptr %__break.coerce, ptr noundef nonnull %0, i32 %__func.coerce)
%call.fca.0.extract = extractvalue { i64, i32 } %call, 0
%call.fca.1.extract = extractvalue { i64, i32 } %call, 1
%tobool10.not.not = icmp eq i64 %call.fca.0.extract, 0
br i1 %tobool10.not.not, label %if.end14, label %return

if.end14:
%__func.sroa.0.0 = phi i32 [ %__func.coerce, %entry ], [ %call.fca.1.extract, %if.then ]
%cmp.i = icmp eq ptr %__root, %__break.coerce
br i1 %cmp.i, label %return, label %if.end18

if.end18:
%inc.i.i = add nsw i32 %__func.sroa.0.0, 1
%__right_ = getelementptr inbounds nuw i8, ptr %__root, i64 8
%1 = load ptr, ptr %__right_, align 8
%tobool21.not = icmp eq ptr %1, null
br i1 %tobool21.not, label %return, label %if.then22

if.then22:
; here
%call29 = tail call { i64, i32 } @recurse(ptr %__break.coerce, ptr noundef nonnull %1, i32 %inc.i.i)
%call29.fca.0.extract = extractvalue { i64, i32 } %call29, 0
%call29.fca.1.extract = extractvalue { i64, i32 } %call29, 1
br label %return

return:
%retval.sroa.0.1 = phi i64 [ 1, %if.then ], [ 1, %if.end14 ], [ %call29.fca.0.extract, %if.then22 ], [ 0, %if.end18 ]
%retval.sroa.5.1 = phi i32 [ %call.fca.1.extract, %if.then ], [ %__func.sroa.0.0, %if.end14 ], [ %call29.fca.1.extract, %if.then22 ], [ %inc.i.i, %if.end18 ]
%.fca.0.insert = insertvalue { i64, i32 } poison, i64 %retval.sroa.0.1, 0
%.fca.1.insert = insertvalue { i64, i32 } %.fca.0.insert, i32 %retval.sroa.5.1, 1
ret { i64, i32 } %.fca.1.insert
}
```

This currently doesn't produce a tail call at `; here`. Replacing that basic block with
```llvm
%call29 = tail call { i64, i32 } @recurse(ptr %__break.coerce, ptr noundef nonnull %1, i32 %inc.i.i)
ret {i64, i32} %call29
```
does result in a tail call, producing significantly better code, since the tail call can be turned into a jump. This can be forced to be generated by clang via a `[[clang::musttail]]`, but that's too temperamental to be usable in generic code. It would be great if LLVM was able to fold this scenario on its own instead.

Contributor guide

Open the contributing guide

Research direction

Start with the supplied LLVM IR reproducer, especially the recursive @recurse function and the block marked ; here. Compare its extractvalue/insertvalue return path with the shown direct ret {i64, i32} %call29 form. Done means the original form is recognized as a tail call and produces the improved jump-based code generation without requiring [[clang::musttail]].

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.