Skip to content

Commit 8628b78

Browse files
ZalatharZalathar
authored
Rollup merge of #144232 - xacrimon:explicit-tail-call, r=WaffleLapkin
Implement support for `become` and explicit tail call codegen for the LLVM backend This PR implements codegen of explicit tail calls via `become` in `rustc_codegen_ssa` and support within the LLVM backend. Completes a task on (#112788). This PR implements all the necessary bits to make explicit tail calls usable, other backends have received stubs for now and will ICE if you use `become` on them. I suspect there is some bikeshedding to be done on how we should go about implementing this for other backends, but it should be relatively straightforward for GCC after this is merged. During development I also put together a POC bytecode VM based on tail call dispatch to test these changes out and analyze the codegen to make sure it generates expected assembly. That is available [here](https://github.com/xacrimon/tcvm).
2 parents f478bec + a448837 commit 8628b78

File tree

10 files changed

+191
-12
lines changed

10 files changed

+191
-12
lines changed

‎compiler/rustc_codegen_gcc/messages.ftl‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,3 +4,5 @@ codegen_gcc_unwinding_inline_asm =
44
codegen_gcc_copy_bitcode = failed to copy bitcode to object file: {$err}
55
66
codegen_gcc_lto_bitcode_from_rlib = failed to get bitcode from object file for LTO ({$gcc_err})
7+
8+
codegen_gcc_explicit_tail_calls_unsupported = explicit tail calls with the 'become' keyword are not implemented in the GCC backend

‎compiler/rustc_codegen_gcc/src/builder.rs‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ use rustc_target::spec::{HasTargetSpec, HasX86AbiOpt, Target, X86Abi};
3434

3535
use crate::common::{SignType, TypeReflection, type_is_pointer};
3636
use crate::context::CodegenCx;
37+
use crate::errors;
3738
use crate::intrinsic::llvm;
3839
use crate::type_of::LayoutGccExt;
3940

@@ -1742,6 +1743,20 @@ impl<'a, 'gcc, 'tcx> BuilderMethods<'a, 'tcx> for Builder<'a, 'gcc, 'tcx> {
17421743
call
17431744
}
17441745

1746+
fn tail_call(
1747+
&mut self,
1748+
_llty: Self::Type,
1749+
_fn_attrs: Option<&CodegenFnAttrs>,
1750+
_fn_abi: &FnAbi<'tcx, Ty<'tcx>>,
1751+
_llfn: Self::Value,
1752+
_args: &[Self::Value],
1753+
_funclet: Option<&Self::Funclet>,
1754+
_instance: Option<Instance<'tcx>>,
1755+
) {
1756+
// FIXME: implement support for explicit tail calls like rustc_codegen_llvm.
1757+
self.tcx.dcx().emit_fatal(errors::ExplicitTailCallsUnsupported);
1758+
}
1759+
17451760
fn zext(&mut self, value: RValue<'gcc>, dest_typ: Type<'gcc>) -> RValue<'gcc> {
17461761
// FIXME(antoyo): this does not zero-extend.
17471762
self.gcc_int_cast(value, dest_typ)

‎compiler/rustc_codegen_gcc/src/errors.rs‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,3 +19,7 @@ pub(crate) struct CopyBitcode {
1919
pub(crate) struct LtoBitcodeFromRlib {
2020
pub gcc_err: String,
2121
}
22+
23+
#[derive(Diagnostic)]
24+
#[diag(codegen_gcc_explicit_tail_calls_unsupported)]
25+
pub(crate) struct ExplicitTailCallsUnsupported;

‎compiler/rustc_codegen_llvm/src/builder.rs‎

Lines changed: 24 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@ use rustc_codegen_ssa::mir::place::PlaceRef;
1515
use rustc_codegen_ssa::traits::*;
1616
use rustc_data_structures::small_c_str::SmallCStr;
1717
use rustc_hir::def_id::DefId;
18+
use rustc_middle::bug;
1819
use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrs;
1920
use rustc_middle::ty::layout::{
2021
FnAbiError, FnAbiOfHelpers, FnAbiRequest, HasTypingEnv, LayoutError, LayoutOfHelpers,
@@ -24,7 +25,7 @@ use rustc_middle::ty::{self, Instance, Ty, TyCtxt};
2425
use rustc_sanitizers::{cfi, kcfi};
2526
use rustc_session::config::OptLevel;
2627
use rustc_span::Span;
27-
use rustc_target::callconv::FnAbi;
28+
use rustc_target::callconv::{FnAbi, PassMode};
2829
use rustc_target::spec::{HasTargetSpec, SanitizerSet, Target};
2930
use smallvec::SmallVec;
3031
use tracing::{debug, instrument};
@@ -1431,6 +1432,28 @@ impl<'a, 'll, 'tcx> BuilderMethods<'a, 'tcx> for Builder<'a, 'll, 'tcx> {
14311432
call
14321433
}
14331434

1435+
fn tail_call(
1436+
&mut self,
1437+
llty: Self::Type,
1438+
fn_attrs: Option<&CodegenFnAttrs>,
1439+
fn_abi: &FnAbi<'tcx, Ty<'tcx>>,
1440+
llfn: Self::Value,
1441+
args: &[Self::Value],
1442+
funclet: Option<&Self::Funclet>,
1443+
instance: Option<Instance<'tcx>>,
1444+
) {
1445+
let call = self.call(llty, fn_attrs, Some(fn_abi), llfn, args, funclet, instance);
1446+
llvm::LLVMRustSetTailCallKind(call, llvm::TailCallKind::MustTail);
1447+
1448+
match &fn_abi.ret.mode {
1449+
PassMode::Ignore | PassMode::Indirect { .. } => self.ret_void(),
1450+
PassMode::Direct(_) | PassMode::Pair { .. } => self.ret(call),
1451+
mode @ PassMode::Cast { .. } => {
1452+
bug!("Encountered `PassMode::{mode:?}` during codegen")
1453+
}
1454+
}
1455+
}
1456+
14341457
fn zext(&mut self, val: &'ll Value, dest_ty: &'ll Type) -> &'ll Value {
14351458
unsafe { llvm::LLVMBuildZExt(self.llbuilder, val, dest_ty, UNNAMED) }
14361459
}

‎compiler/rustc_codegen_llvm/src/llvm/ffi.rs‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,16 @@ pub(crate) enum ModuleFlagMergeBehavior {
9797

9898
// Consts for the LLVM CallConv type, pre-cast to usize.
9999

100+
#[derive(Copy, Clone, PartialEq, Debug)]
101+
#[repr(C)]
102+
#[allow(dead_code)]
103+
pub(crate) enum TailCallKind {
104+
None = 0,
105+
Tail = 1,
106+
MustTail = 2,
107+
NoTail = 3,
108+
}
109+
100110
/// LLVM CallingConv::ID. Should we wrap this?
101111
///
102112
/// See <https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/IR/CallingConv.h>
@@ -1186,6 +1196,7 @@ unsafe extern "C" {
11861196
pub(crate) safe fn LLVMIsGlobalConstant(GlobalVar: &Value) -> Bool;
11871197
pub(crate) safe fn LLVMSetGlobalConstant(GlobalVar: &Value, IsConstant: Bool);
11881198
pub(crate) safe fn LLVMSetTailCall(CallInst: &Value, IsTailCall: Bool);
1199+
pub(crate) safe fn LLVMRustSetTailCallKind(CallInst: &Value, Kind: TailCallKind);
11891200

11901201
// Operations on attributes
11911202
pub(crate) fn LLVMCreateStringAttribute(

‎compiler/rustc_codegen_ssa/src/mir/block.rs‎

Lines changed: 62 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,14 @@ enum MergingSucc {
3535
True,
3636
}
3737

38+
/// Indicates to the call terminator codegen whether a cal
39+
/// is a normal call or an explicit tail call.
40+
#[derive(Debug, PartialEq)]
41+
enum CallKind {
42+
Normal,
43+
Tail,
44+
}
45+
3846
/// Used by `FunctionCx::codegen_terminator` for emitting common patterns
3947
/// e.g., creating a basic block, calling a function, etc.
4048
struct TerminatorCodegenHelper<'tcx> {
@@ -160,6 +168,7 @@ impl<'a, 'tcx> TerminatorCodegenHelper<'tcx> {
160168
mut unwind: mir::UnwindAction,
161169
lifetime_ends_after_call: &[(Bx::Value, Size)],
162170
instance: Option<Instance<'tcx>>,
171+
kind: CallKind,
163172
mergeable_succ: bool,
164173
) -> MergingSucc {
165174
let tcx = bx.tcx();
@@ -221,6 +230,11 @@ impl<'a, 'tcx> TerminatorCodegenHelper<'tcx> {
221230
}
222231
};
223232

233+
if kind == CallKind::Tail {
234+
bx.tail_call(fn_ty, fn_attrs, fn_abi, fn_ptr, llargs, self.funclet(fx), instance);
235+
return MergingSucc::False;
236+
}
237+
224238
if let Some(unwind_block) = unwind_block {
225239
let ret_llbb = if let Some((_, target)) = destination {
226240
fx.llbb(target)
@@ -659,6 +673,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
659673
unwind,
660674
&[],
661675
Some(drop_instance),
676+
CallKind::Normal,
662677
!maybe_null && mergeable_succ,
663678
)
664679
}
@@ -747,8 +762,19 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
747762
let (fn_abi, llfn, instance) = common::build_langcall(bx, span, lang_item);
748763

749764
// Codegen the actual panic invoke/call.
750-
let merging_succ =
751-
helper.do_call(self, bx, fn_abi, llfn, &args, None, unwind, &[], Some(instance), false);
765+
let merging_succ = helper.do_call(
766+
self,
767+
bx,
768+
fn_abi,
769+
llfn,
770+
&args,
771+
None,
772+
unwind,
773+
&[],
774+
Some(instance),
775+
CallKind::Normal,
776+
false,
777+
);
752778
assert_eq!(merging_succ, MergingSucc::False);
753779
MergingSucc::False
754780
}
@@ -777,6 +803,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
777803
mir::UnwindAction::Unreachable,
778804
&[],
779805
Some(instance),
806+
CallKind::Normal,
780807
false,
781808
);
782809
assert_eq!(merging_succ, MergingSucc::False);
@@ -845,6 +872,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
845872
unwind,
846873
&[],
847874
Some(instance),
875+
CallKind::Normal,
848876
mergeable_succ,
849877
))
850878
}
@@ -860,6 +888,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
860888
target: Option<mir::BasicBlock>,
861889
unwind: mir::UnwindAction,
862890
fn_span: Span,
891+
kind: CallKind,
863892
mergeable_succ: bool,
864893
) -> MergingSucc {
865894
let source_info = mir::SourceInfo { span: fn_span, ..terminator.source_info };
@@ -1003,8 +1032,13 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
10031032
// We still need to call `make_return_dest` even if there's no `target`, since
10041033
// `fn_abi.ret` could be `PassMode::Indirect`, even if it is uninhabited,
10051034
// and `make_return_dest` adds the return-place indirect pointer to `llargs`.
1006-
let return_dest = self.make_return_dest(bx, destination, &fn_abi.ret, &mut llargs);
1007-
let destination = target.map(|target| (return_dest, target));
1035+
let destination = match kind {
1036+
CallKind::Normal => {
1037+
let return_dest = self.make_return_dest(bx, destination, &fn_abi.ret, &mut llargs);
1038+
target.map(|target| (return_dest, target))
1039+
}
1040+
CallKind::Tail => None,
1041+
};
10081042

10091043
// Split the rust-call tupled arguments off.
10101044
let (first_args, untuple) = if sig.abi() == ExternAbi::RustCall
@@ -1020,6 +1054,14 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
10201054
// to generate `lifetime_end` when the call returns.
10211055
let mut lifetime_ends_after_call: Vec<(Bx::Value, Size)> = Vec::new();
10221056
'make_args: for (i, arg) in first_args.iter().enumerate() {
1057+
if kind == CallKind::Tail && matches!(fn_abi.args[i].mode, PassMode::Indirect { .. }) {
1058+
// FIXME: https://github.com/rust-lang/rust/pull/144232#discussion_r2218543841
1059+
span_bug!(
1060+
fn_span,
1061+
"arguments using PassMode::Indirect are currently not supported for tail calls"
1062+
);
1063+
}
1064+
10231065
let mut op = self.codegen_operand(bx, &arg.node);
10241066

10251067
if let (0, Some(ty::InstanceKind::Virtual(_, idx))) = (i, instance.map(|i| i.def)) {
@@ -1147,6 +1189,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
11471189
unwind,
11481190
&lifetime_ends_after_call,
11491191
instance,
1192+
kind,
11501193
mergeable_succ,
11511194
)
11521195
}
@@ -1388,15 +1431,23 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
13881431
target,
13891432
unwind,
13901433
fn_span,
1434+
CallKind::Normal,
13911435
mergeable_succ(),
13921436
),
1393-
mir::TerminatorKind::TailCall { .. } => {
1394-
// FIXME(explicit_tail_calls): implement tail calls in ssa backend
1395-
span_bug!(
1396-
terminator.source_info.span,
1397-
"`TailCall` terminator is not yet supported by `rustc_codegen_ssa`"
1398-
)
1399-
}
1437+
mir::TerminatorKind::TailCall { ref func, ref args, fn_span } => self
1438+
.codegen_call_terminator(
1439+
helper,
1440+
bx,
1441+
terminator,
1442+
func,
1443+
args,
1444+
mir::Place::from(mir::RETURN_PLACE),
1445+
None,
1446+
mir::UnwindAction::Unreachable,
1447+
fn_span,
1448+
CallKind::Tail,
1449+
mergeable_succ(),
1450+
),
14001451
mir::TerminatorKind::CoroutineDrop | mir::TerminatorKind::Yield { .. } => {
14011452
bug!("coroutine ops in codegen")
14021453
}

‎compiler/rustc_codegen_ssa/src/traits/builder.rs‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -595,6 +595,18 @@ pub trait BuilderMethods<'a, 'tcx>:
595595
funclet: Option<&Self::Funclet>,
596596
instance: Option<Instance<'tcx>>,
597597
) -> Self::Value;
598+
599+
fn tail_call(
600+
&mut self,
601+
llty: Self::Type,
602+
fn_attrs: Option<&CodegenFnAttrs>,
603+
fn_abi: &FnAbi<'tcx, Ty<'tcx>>,
604+
llfn: Self::Value,
605+
args: &[Self::Value],
606+
funclet: Option<&Self::Funclet>,
607+
instance: Option<Instance<'tcx>>,
608+
);
609+
598610
fn zext(&mut self, val: Self::Value, dest_ty: Self::Type) -> Self::Value;
599611

600612
fn apply_attrs_to_cleanup_callsite(&mut self, llret: Self::Value);

‎compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1986,3 +1986,29 @@ extern "C" void LLVMRustSetNoSanitizeHWAddress(LLVMValueRef Global) {
19861986
MD.NoHWAddress = true;
19871987
GV.setSanitizerMetadata(MD);
19881988
}
1989+
1990+
enum class LLVMRustTailCallKind {
1991+
None = 0,
1992+
Tail = 1,
1993+
MustTail = 2,
1994+
NoTail = 3
1995+
};
1996+
1997+
extern "C" void LLVMRustSetTailCallKind(LLVMValueRef Call,
1998+
LLVMRustTailCallKind Kind) {
1999+
CallInst *CI = unwrap<CallInst>(Call);
2000+
switch (Kind) {
2001+
case LLVMRustTailCallKind::None:
2002+
CI->setTailCallKind(CallInst::TCK_None);
2003+
break;
2004+
case LLVMRustTailCallKind::Tail:
2005+
CI->setTailCallKind(CallInst::TCK_Tail);
2006+
break;
2007+
case LLVMRustTailCallKind::MustTail:
2008+
CI->setTailCallKind(CallInst::TCK_MustTail);
2009+
break;
2010+
case LLVMRustTailCallKind::NoTail:
2011+
CI->setTailCallKind(CallInst::TCK_NoTail);
2012+
break;
2013+
}
2014+
}

‎tests/codegen-llvm/become-musttail.rs‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
//@ compile-flags: -C opt-level=0 -Cpanic=abort -C no-prepopulate-passes
2+
//@ needs-unwind
3+
4+
#![crate_type = "lib"]
5+
#![feature(explicit_tail_calls)]
6+
7+
// CHECK-LABEL: define {{.*}}@fibonacci(
8+
#[no_mangle]
9+
#[inline(never)]
10+
pub fn fibonacci(n: u64, a: u64, b: u64) -> u64 {
11+
// CHECK: musttail call {{.*}}@fibonacci(
12+
// CHECK-NEXT: ret i64
13+
match n {
14+
0 => a,
15+
1 => b,
16+
_ => become fibonacci(n - 1, b, a + b),
17+
}
18+
}

‎tests/ui/explicit-tail-calls/recursion-etc.rs‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
//@ run-pass
2+
#![expect(incomplete_features)]
3+
#![feature(explicit_tail_calls)]
4+
5+
use std::hint::black_box;
6+
7+
pub fn count(curr: u64, top: u64) -> u64 {
8+
if black_box(curr) >= top {
9+
curr
10+
} else {
11+
become count(curr + 1, top)
12+
}
13+
}
14+
15+
fn main() {
16+
println!("{}", count(0, black_box(1000000)));
17+
}

0 commit comments

Comments
 (0)