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`

4 files changed, 62 insertions, 51 deletions

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);
 }