Auto merge of #106364 - JakobDegen:top-down-inlining, r=cjgillot

Reenable limited top-down MIR inlining

Reverts most of #105119 and uses an alternative strategy to prevent exponential blowup. Specifically, we allow doing top-down inlining up to depth at most five, and for at most one call site per nested body.

r? `@cjgillot`

1 files changed, 36 insertions, 6 deletions

diff --git a/compiler/rustc_mir_transform/src/inline.rs b/compiler/rustc_mir_transform/src/inline.rs
index 8bdd965deb2..4219e6280eb 100644
--- a/compiler/rustc_mir_transform/src/inline.rs
+++ b/compiler/rustc_mir_transform/src/inline.rs
@@ -1,6 +1,7 @@
 //! Inlining pass for MIR functions
 use crate::deref_separator::deref_finder;
 use rustc_attr::InlineAttr;
+use rustc_hir::def_id::DefId;
 use rustc_index::bit_set::BitSet;
 use rustc_index::vec::Idx;
 use rustc_middle::middle::codegen_fn_attrs::{CodegenFnAttrFlags, CodegenFnAttrs};
@@ -27,6 +28,8 @@ const RESUME_PENALTY: usize = 45;
 
 const UNKNOWN_SIZE_COST: usize = 10;
 
+const TOP_DOWN_DEPTH_LIMIT: usize = 5;
+
 pub struct Inline;
 
 #[derive(Copy, Clone, Debug)]
@@ -86,8 +89,13 @@ fn inline<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) -> bool {
 
     let param_env = tcx.param_env_reveal_all_normalized(def_id);
 
-    let mut this =
-        Inliner { tcx, param_env, codegen_fn_attrs: tcx.codegen_fn_attrs(def_id), changed: false };
+    let mut this = Inliner {
+        tcx,
+        param_env,
+        codegen_fn_attrs: tcx.codegen_fn_attrs(def_id),
+        history: Vec::new(),
+        changed: false,
+    };
     let blocks = BasicBlock::new(0)..body.basic_blocks.next_index();
     this.process_blocks(body, blocks);
     this.changed
@@ -98,12 +106,26 @@ struct Inliner<'tcx> {
     param_env: ParamEnv<'tcx>,
     /// Caller codegen attributes.
     codegen_fn_attrs: &'tcx CodegenFnAttrs,
+    /// Stack of inlined instances.
+    /// We only check the `DefId` and not the substs because we want to
+    /// avoid inlining cases of polymorphic recursion.
+    /// The number of `DefId`s is finite, so checking history is enough
+    /// to ensure that we do not loop endlessly while inlining.
+    history: Vec<DefId>,
     /// Indicates that the caller body has been modified.
     changed: bool,
 }
 
 impl<'tcx> Inliner<'tcx> {
     fn process_blocks(&mut self, caller_body: &mut Body<'tcx>, blocks: Range<BasicBlock>) {
+        // How many callsites in this body are we allowed to inline? We need to limit this in order
+        // to prevent super-linear growth in MIR size
+        let inline_limit = match self.history.len() {
+            0 => usize::MAX,
+            1..=TOP_DOWN_DEPTH_LIMIT => 1,
+            _ => return,
+        };
+        let mut inlined_count = 0;
         for bb in blocks {
             let bb_data = &caller_body[bb];
             if bb_data.is_cleanup {
@@ -122,12 +144,16 @@ impl<'tcx> Inliner<'tcx> {
                     debug!("not-inlined {} [{}]", callsite.callee, reason);
                     continue;
                 }
-                Ok(_) => {
+                Ok(new_blocks) => {
                     debug!("inlined {}", callsite.callee);
                     self.changed = true;
-                    // We could process the blocks returned by `try_inlining` here. However, that
-                    // leads to exponential compile times due to the top-down nature of this kind
-                    // of inlining.
+                    inlined_count += 1;
+                    if inlined_count == inline_limit {
+                        return;
+                    }
+                    self.history.push(callsite.callee.def_id());
+                    self.process_blocks(caller_body, new_blocks);
+                    self.history.pop();
                 }
             }
         }
@@ -301,6 +327,10 @@ impl<'tcx> Inliner<'tcx> {
                     return None;
                 }
 
+                if self.history.contains(&callee.def_id()) {
+                    return None;
+                }
+
                 let fn_sig = self.tcx.bound_fn_sig(def_id).subst(self.tcx, substs);
                 let source_info = SourceInfo { span: fn_span, ..terminator.source_info };