[LLVM] Missed tail call due to extractvalue/insertvalue
- 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
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