Auto merge of #84993 - eddyb:cg-ssa-on-demand-blocks, r=nagisa

rustc_codegen_ssa: only create backend `BasicBlock`s as-needed.

Instead of creating one backend (e.g. LLVM) block per MIR block ahead of time, and then deleting the ones that weren't visited, this PR moves to creating the blocks as they're needed (either reached via the RPO visit, or used as the target of a branch from a different block).

As deleting a block was the only `unsafe` builder method (generally we only *create* backend objects, not *remove* them), that's gone now and codegen is overall a bit safer.

The only change in output is the order of LLVM blocks (which AFAIK has no semantic meaning, other than the first block being the entry block). This happens because the blocks are now created due to control-flow edges, rather than MIR block order.

I'm making this a standalone PR because I keep getting wild perf results when I change *anything* in codegen, but if you want to read more about my plans in this area, see https://github.com/rust-lang/rust/pull/84771#issuecomment-830636256 (and https://github.com/rust-lang/rust/pull/84771#issue-628295651 - but that may be a bit outdated).

(You may notice some of the APIs in this PR, like `append_block`, don't help with the future plans - but I didn't want to include the necessary refactors that pass a build around everywhere, in this PR, so it's a small compromise)

r? `@nagisa` `@bjorn3`

10 files changed, 100 insertions, 85 deletions

diff --git a/compiler/rustc_codegen_llvm/src/builder.rs b/compiler/rustc_codegen_llvm/src/builder.rs
index 053cda1e7cc..bc9d99ed4a1 100644
--- a/compiler/rustc_codegen_llvm/src/builder.rs
+++ b/compiler/rustc_codegen_llvm/src/builder.rs
@@ -118,24 +118,16 @@ macro_rules! builder_methods_for_value_instructions {
 }
 
 impl BuilderMethods<'a, 'tcx> for Builder<'a, 'll, 'tcx> {
-    fn new_block<'b>(cx: &'a CodegenCx<'ll, 'tcx>, llfn: &'ll Value, name: &'b str) -> Self {
-        let mut bx = Builder::with_cx(cx);
-        let llbb = unsafe {
-            let name = SmallCStr::new(name);
-            llvm::LLVMAppendBasicBlockInContext(cx.llcx, llfn, name.as_ptr())
-        };
-        bx.position_at_end(llbb);
+    fn build(cx: &'a CodegenCx<'ll, 'tcx>, llbb: &'ll BasicBlock) -> Self {
+        let bx = Builder::with_cx(cx);
+        unsafe {
+            llvm::LLVMPositionBuilderAtEnd(bx.llbuilder, llbb);
+        }
         bx
     }
 
-    fn with_cx(cx: &'a CodegenCx<'ll, 'tcx>) -> Self {
-        // Create a fresh builder from the crate context.
-        let llbuilder = unsafe { llvm::LLVMCreateBuilderInContext(cx.llcx) };
-        Builder { llbuilder, cx }
-    }
-
-    fn build_sibling_block(&self, name: &str) -> Self {
-        Builder::new_block(self.cx, self.llfn(), name)
+    fn cx(&self) -> &CodegenCx<'ll, 'tcx> {
+        self.cx
     }
 
     fn llbb(&self) -> &'ll BasicBlock {
@@ -144,12 +136,22 @@ impl BuilderMethods<'a, 'tcx> for Builder<'a, 'll, 'tcx> {
 
     fn set_span(&mut self, _span: Span) {}
 
-    fn position_at_end(&mut self, llbb: &'ll BasicBlock) {
+    fn append_block(cx: &'a CodegenCx<'ll, 'tcx>, llfn: &'ll Value, name: &str) -> &'ll BasicBlock {
         unsafe {
-            llvm::LLVMPositionBuilderAtEnd(self.llbuilder, llbb);
+            let name = SmallCStr::new(name);
+            llvm::LLVMAppendBasicBlockInContext(cx.llcx, llfn, name.as_ptr())
         }
     }
 
+    fn append_sibling_block(&mut self, name: &str) -> &'ll BasicBlock {
+        Self::append_block(self.cx, self.llfn(), name)
+    }
+
+    fn build_sibling_block(&mut self, name: &str) -> Self {
+        let llbb = self.append_sibling_block(name);
+        Self::build(self.cx, llbb)
+    }
+
     fn ret_void(&mut self) {
         unsafe {
             llvm::LLVMBuildRetVoid(self.llbuilder);
@@ -1144,14 +1146,6 @@ impl BuilderMethods<'a, 'tcx> for Builder<'a, 'll, 'tcx> {
         unsafe { llvm::LLVMBuildZExt(self.llbuilder, val, dest_ty, UNNAMED) }
     }
 
-    fn cx(&self) -> &CodegenCx<'ll, 'tcx> {
-        self.cx
-    }
-
-    unsafe fn delete_basic_block(&mut self, bb: &'ll BasicBlock) {
-        llvm::LLVMDeleteBasicBlock(bb);
-    }
-
     fn do_not_inline(&mut self, llret: &'ll Value) {
         llvm::Attribute::NoInline.apply_callsite(llvm::AttributePlace::Function, llret);
     }
@@ -1165,6 +1159,12 @@ impl StaticBuilderMethods for Builder<'a, 'll, 'tcx> {
 }
 
 impl Builder<'a, 'll, 'tcx> {
+    fn with_cx(cx: &'a CodegenCx<'ll, 'tcx>) -> Self {
+        // Create a fresh builder from the crate context.
+        let llbuilder = unsafe { llvm::LLVMCreateBuilderInContext(cx.llcx) };
+        Builder { llbuilder, cx }
+    }
+
     pub fn llfn(&self) -> &'ll Value {
         unsafe { llvm::LLVMGetBasicBlockParent(self.llbb()) }
     }
diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
index afc2bdbfd52..019bf4a09a7 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
@@ -223,7 +223,8 @@ fn declare_unused_fn(cx: &CodegenCx<'ll, 'tcx>, def_id: &DefId) -> Instance<'tcx
 
 fn codegen_unused_fn_and_counter(cx: &CodegenCx<'ll, 'tcx>, instance: Instance<'tcx>) {
     let llfn = cx.get_fn(instance);
-    let mut bx = Builder::new_block(cx, llfn, "unused_function");
+    let llbb = Builder::append_block(cx, llfn, "unused_function");
+    let mut bx = Builder::build(cx, llbb);
     let fn_name = bx.get_pgo_func_name_var(instance);
     let hash = bx.const_u64(0);
     let num_counters = bx.const_u32(1);
diff --git a/compiler/rustc_codegen_llvm/src/intrinsic.rs b/compiler/rustc_codegen_llvm/src/intrinsic.rs
index fc6c1abf4af..22d513d66d1 100644
--- a/compiler/rustc_codegen_llvm/src/intrinsic.rs
+++ b/compiler/rustc_codegen_llvm/src/intrinsic.rs
@@ -678,7 +678,8 @@ fn gen_fn<'ll, 'tcx>(
     cx.apply_target_cpu_attr(llfn);
     // FIXME(eddyb) find a nicer way to do this.
     unsafe { llvm::LLVMRustSetLinkage(llfn, llvm::Linkage::InternalLinkage) };
-    let bx = Builder::new_block(cx, llfn, "entry-block");
+    let llbb = Builder::append_block(cx, llfn, "entry-block");
+    let bx = Builder::build(cx, llbb);
     codegen(bx);
     llfn
 }
diff --git a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
index 32fdde9b42e..bf66040a7eb 100644
--- a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
+++ b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
@@ -1079,7 +1079,6 @@ extern "C" {
         Fn: &'a Value,
         Name: *const c_char,
     ) -> &'a BasicBlock;
-    pub fn LLVMDeleteBasicBlock(BB: &BasicBlock);
 
     // Operations on instructions
     pub fn LLVMIsAInstruction(Val: &Value) -> Option<&Value>;
diff --git a/compiler/rustc_codegen_ssa/src/base.rs b/compiler/rustc_codegen_ssa/src/base.rs
index a9ab075d3db..ac6a1a90bfd 100644
--- a/compiler/rustc_codegen_ssa/src/base.rs
+++ b/compiler/rustc_codegen_ssa/src/base.rs
@@ -409,7 +409,8 @@ pub fn maybe_create_entry_wrapper<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
         cx.set_frame_pointer_elimination(llfn);
         cx.apply_target_cpu_attr(llfn);
 
-        let mut bx = Bx::new_block(&cx, llfn, "top");
+        let llbb = Bx::append_block(&cx, llfn, "top");
+        let mut bx = Bx::build(&cx, llbb);
 
         bx.insert_reference_to_gdb_debug_scripts_section_global();
 
diff --git a/compiler/rustc_codegen_ssa/src/mir/block.rs b/compiler/rustc_codegen_ssa/src/mir/block.rs
index 8f92d3e6b80..93200bd1f26 100644
--- a/compiler/rustc_codegen_ssa/src/mir/block.rs
+++ b/compiler/rustc_codegen_ssa/src/mir/block.rs
@@ -68,7 +68,7 @@ impl<'a, 'tcx> TerminatorCodegenHelper<'tcx> {
         target: mir::BasicBlock,
     ) -> (Bx::BasicBlock, bool) {
         let span = self.terminator.source_info.span;
-        let lltarget = fx.blocks[target];
+        let lltarget = fx.llbb(target);
         let target_funclet = fx.cleanup_kinds[target].funclet_bb(target);
         match (self.funclet_bb, target_funclet) {
             (None, None) => (lltarget, false),
@@ -133,13 +133,13 @@ impl<'a, 'tcx> TerminatorCodegenHelper<'tcx> {
         // If there is a cleanup block and the function we're calling can unwind, then
         // do an invoke, otherwise do a call.
         if let Some(cleanup) = cleanup.filter(|_| fn_abi.can_unwind) {
-            let ret_bx = if let Some((_, target)) = destination {
-                fx.blocks[target]
+            let ret_llbb = if let Some((_, target)) = destination {
+                fx.llbb(target)
             } else {
                 fx.unreachable_block()
             };
             let invokeret =
-                bx.invoke(fn_ptr, &llargs, ret_bx, self.llblock(fx, cleanup), self.funclet(fx));
+                bx.invoke(fn_ptr, &llargs, ret_llbb, self.llblock(fx, cleanup), self.funclet(fx));
             bx.apply_attrs_callsite(&fn_abi, invokeret);
 
             if let Some((ret_dest, target)) = destination {
@@ -386,7 +386,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
 
         // Create the failure block and the conditional branch to it.
         let lltarget = helper.llblock(self, target);
-        let panic_block = self.new_block("panic");
+        let panic_block = bx.build_sibling_block("panic");
         if expected {
             bx.cond_br(cond, lltarget, panic_block.llbb());
         } else {
@@ -1205,7 +1205,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
 
     // FIXME(eddyb) rename this to `eh_pad_for_uncached`.
     fn landing_pad_for_uncached(&mut self, bb: mir::BasicBlock) -> Bx::BasicBlock {
-        let llbb = self.blocks[bb];
+        let llbb = self.llbb(bb);
         if base::wants_msvc_seh(self.cx.sess()) {
             let funclet;
             let ret_llbb;
@@ -1289,14 +1289,29 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
         })
     }
 
-    pub fn new_block(&self, name: &str) -> Bx {
-        Bx::new_block(self.cx, self.llfn, name)
+    // FIXME(eddyb) replace with `build_sibling_block`/`append_sibling_block`
+    // (which requires having a `Bx` already, and not all callers do).
+    fn new_block(&self, name: &str) -> Bx {
+        let llbb = Bx::append_block(self.cx, self.llfn, name);
+        Bx::build(self.cx, llbb)
     }
 
-    pub fn build_block(&self, bb: mir::BasicBlock) -> Bx {
-        let mut bx = Bx::with_cx(self.cx);
-        bx.position_at_end(self.blocks[bb]);
-        bx
+    /// Get the backend `BasicBlock` for a MIR `BasicBlock`, either already
+    /// cached in `self.cached_llbbs`, or created on demand (and cached).
+    // FIXME(eddyb) rename `llbb` and other `ll`-prefixed things to use a
+    // more backend-agnostic prefix such as `cg` (i.e. this would be `cgbb`).
+    pub fn llbb(&mut self, bb: mir::BasicBlock) -> Bx::BasicBlock {
+        self.cached_llbbs[bb].unwrap_or_else(|| {
+            // FIXME(eddyb) only name the block if `fewer_names` is `false`.
+            let llbb = Bx::append_block(self.cx, self.llfn, &format!("{:?}", bb));
+            self.cached_llbbs[bb] = Some(llbb);
+            llbb
+        })
+    }
+
+    pub fn build_block(&mut self, bb: mir::BasicBlock) -> Bx {
+        let llbb = self.llbb(bb);
+        Bx::build(self.cx, llbb)
     }
 
     fn make_return_dest(
diff --git a/compiler/rustc_codegen_ssa/src/mir/mod.rs b/compiler/rustc_codegen_ssa/src/mir/mod.rs
index a14ae16517d..3bbc481b610 100644
--- a/compiler/rustc_codegen_ssa/src/mir/mod.rs
+++ b/compiler/rustc_codegen_ssa/src/mir/mod.rs
@@ -40,8 +40,11 @@ pub struct FunctionCx<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> {
     /// then later loaded when generating the DIVERGE_BLOCK.
     personality_slot: Option<PlaceRef<'tcx, Bx::Value>>,
 
-    /// A `Block` for each MIR `BasicBlock`
-    blocks: IndexVec<mir::BasicBlock, Bx::BasicBlock>,
+    /// A backend `BasicBlock` for each MIR `BasicBlock`, created lazily
+    /// as-needed (e.g. RPO reaching it or another block branching to it).
+    // FIXME(eddyb) rename `llbbs` and other `ll`-prefixed things to use a
+    // more backend-agnostic prefix such as `cg` (i.e. this would be `cgbbs`).
+    cached_llbbs: IndexVec<mir::BasicBlock, Option<Bx::BasicBlock>>,
 
     /// The funclet status of each basic block
     cleanup_kinds: IndexVec<mir::BasicBlock, analyze::CleanupKind>,
@@ -141,7 +144,8 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
 
     let debug_context = cx.create_function_debug_context(instance, &fn_abi, llfn, &mir);
 
-    let mut bx = Bx::new_block(cx, llfn, "start");
+    let start_llbb = Bx::append_block(cx, llfn, "start");
+    let mut bx = Bx::build(cx, start_llbb);
 
     if mir.basic_blocks().iter().any(|bb| bb.is_cleanup) {
         bx.set_personality_fn(cx.eh_personality());
@@ -151,17 +155,17 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
     // Allocate a `Block` for every basic block, except
     // the start block, if nothing loops back to it.
     let reentrant_start_block = !mir.predecessors()[mir::START_BLOCK].is_empty();
-    let block_bxs: IndexVec<mir::BasicBlock, Bx::BasicBlock> = mir
-        .basic_blocks()
-        .indices()
-        .map(|bb| {
-            if bb == mir::START_BLOCK && !reentrant_start_block {
-                bx.llbb()
-            } else {
-                bx.build_sibling_block(&format!("{:?}", bb)).llbb()
-            }
-        })
-        .collect();
+    let cached_llbbs: IndexVec<mir::BasicBlock, Option<Bx::BasicBlock>> =
+        mir.basic_blocks()
+            .indices()
+            .map(|bb| {
+                if bb == mir::START_BLOCK && !reentrant_start_block {
+                    Some(start_llbb)
+                } else {
+                    None
+                }
+            })
+            .collect();
 
     let mut fx = FunctionCx {
         instance,
@@ -170,7 +174,7 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
         fn_abi,
         cx,
         personality_slot: None,
-        blocks: block_bxs,
+        cached_llbbs,
         unreachable_block: None,
         cleanup_kinds,
         landing_pads: IndexVec::from_elem(None, mir.basic_blocks()),
@@ -245,29 +249,14 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
 
     // Branch to the START block, if it's not the entry block.
     if reentrant_start_block {
-        bx.br(fx.blocks[mir::START_BLOCK]);
+        bx.br(fx.llbb(mir::START_BLOCK));
     }
 
-    let rpo = traversal::reverse_postorder(&mir);
-    let mut visited = BitSet::new_empty(mir.basic_blocks().len());
-
     // Codegen the body of each block using reverse postorder
-    for (bb, _) in rpo {
-        visited.insert(bb.index());
+    // FIXME(eddyb) reuse RPO iterator between `analysis` and this.
+    for (bb, _) in traversal::reverse_postorder(&mir) {
         fx.codegen_block(bb);
     }
-
-    // Remove blocks that haven't been visited, or have no
-    // predecessors.
-    for bb in mir.basic_blocks().indices() {
-        // Unreachable block
-        if !visited.contains(bb.index()) {
-            debug!("codegen_mir: block {:?} was not visited", bb);
-            unsafe {
-                bx.delete_basic_block(fx.blocks[bb]);
-            }
-        }
-    }
 }
 
 /// Produces, for each argument, a `Value` pointing at the
diff --git a/compiler/rustc_codegen_ssa/src/traits/builder.rs b/compiler/rustc_codegen_ssa/src/traits/builder.rs
index 1bc05f30e5c..29b2db5d4d7 100644
--- a/compiler/rustc_codegen_ssa/src/traits/builder.rs
+++ b/compiler/rustc_codegen_ssa/src/traits/builder.rs
@@ -40,14 +40,21 @@ pub trait BuilderMethods<'a, 'tcx>:
     + HasParamEnv<'tcx>
     + HasTargetSpec
 {
-    fn new_block<'b>(cx: &'a Self::CodegenCx, llfn: Self::Function, name: &'b str) -> Self;
-    fn with_cx(cx: &'a Self::CodegenCx) -> Self;
-    fn build_sibling_block(&self, name: &str) -> Self;
+    fn build(cx: &'a Self::CodegenCx, llbb: Self::BasicBlock) -> Self;
+
     fn cx(&self) -> &Self::CodegenCx;
     fn llbb(&self) -> Self::BasicBlock;
+
     fn set_span(&mut self, span: Span);
 
-    fn position_at_end(&mut self, llbb: Self::BasicBlock);
+    // FIXME(eddyb) replace uses of this with `append_sibling_block`.
+    fn append_block(cx: &'a Self::CodegenCx, llfn: Self::Function, name: &str) -> Self::BasicBlock;
+
+    fn append_sibling_block(&mut self, name: &str) -> Self::BasicBlock;
+
+    // FIXME(eddyb) replace with callers using `append_sibling_block`.
+    fn build_sibling_block(&mut self, name: &str) -> Self;
+
     fn ret_void(&mut self);
     fn ret(&mut self, v: Self::Value);
     fn br(&mut self, dest: Self::BasicBlock);
@@ -291,6 +298,5 @@ pub trait BuilderMethods<'a, 'tcx>:
     ) -> Self::Value;
     fn zext(&mut self, val: Self::Value, dest_ty: Self::Type) -> Self::Value;
 
-    unsafe fn delete_basic_block(&mut self, bb: Self::BasicBlock);
     fn do_not_inline(&mut self, llret: Self::Value);
 }
diff --git a/src/test/codegen/drop.rs b/src/test/codegen/drop.rs
index b35d5c83552..543b81b0b62 100644
--- a/src/test/codegen/drop.rs
+++ b/src/test/codegen/drop.rs
@@ -23,13 +23,16 @@ pub fn droppy() {
 // FIXME(eddyb) the `void @` forces a match on the instruction, instead of the
 // comment, that's `; call core::ptr::drop_in_place::<drop::SomeUniqueName>`
 // for the `v0` mangling, should switch to matching on that once `legacy` is gone.
-// CHECK-NOT: call void @{{.*}}drop_in_place{{.*}}SomeUniqueName
-// CHECK: invoke void @{{.*}}drop_in_place{{.*}}SomeUniqueName
-// CHECK: invoke void @{{.*}}drop_in_place{{.*}}SomeUniqueName
 // CHECK-NOT: invoke void @{{.*}}drop_in_place{{.*}}SomeUniqueName
 // CHECK: call void @{{.*}}drop_in_place{{.*}}SomeUniqueName
 // CHECK: call void @{{.*}}drop_in_place{{.*}}SomeUniqueName
+// CHECK-NOT: call void @{{.*}}drop_in_place{{.*}}SomeUniqueName
+// CHECK: invoke void @{{.*}}drop_in_place{{.*}}SomeUniqueName
+// CHECK-NOT: invoke void @{{.*}}drop_in_place{{.*}}SomeUniqueName
 // CHECK: call void @{{.*}}drop_in_place{{.*}}SomeUniqueName
+// CHECK-NOT: call void @{{.*}}drop_in_place{{.*}}SomeUniqueName
+// CHECK: invoke void @{{.*}}drop_in_place{{.*}}SomeUniqueName
+// CHECK-NOT: invoke void @{{.*}}drop_in_place{{.*}}SomeUniqueName
 // CHECK: call void @{{.*}}drop_in_place{{.*}}SomeUniqueName
 // CHECK-NOT: {{(call|invoke) void @.*}}drop_in_place{{.*}}SomeUniqueName
 // The next line checks for the } that ends the function definition
diff --git a/src/test/codegen/match.rs b/src/test/codegen/match.rs
index b5ee5ba2394..d0c0202052e 100644
--- a/src/test/codegen/match.rs
+++ b/src/test/codegen/match.rs
@@ -14,14 +14,14 @@ pub fn exhaustive_match(e: E) -> u8 {
 // CHECK-NEXT: i[[TY:[0-9]+]] [[DISCR:[0-9]+]], label %[[A:[a-zA-Z0-9_]+]]
 // CHECK-NEXT: i[[TY:[0-9]+]] [[DISCR:[0-9]+]], label %[[B:[a-zA-Z0-9_]+]]
 // CHECK-NEXT: ]
-// CHECK: [[B]]:
-// CHECK-NEXT: store i8 1, i8* %1, align 1
-// CHECK-NEXT: br label %[[EXIT:[a-zA-Z0-9_]+]]
 // CHECK: [[OTHERWISE]]:
 // CHECK-NEXT: unreachable
 // CHECK: [[A]]:
 // CHECK-NEXT: store i8 0, i8* %1, align 1
 // CHECK-NEXT: br label %[[EXIT:[a-zA-Z0-9_]+]]
+// CHECK: [[B]]:
+// CHECK-NEXT: store i8 1, i8* %1, align 1
+// CHECK-NEXT: br label %[[EXIT:[a-zA-Z0-9_]+]]
     match e {
         E::A => 0,
         E::B => 1,