Merge pull request #4513 from rust-lang/rustup-2025-08-04

Automatic Rustup

16 files changed, 391 insertions, 92 deletions

diff --git a/src/bootstrap/src/bin/main.rs b/src/bootstrap/src/bin/main.rs
index 181d71f63c2..cf24fedaebb 100644
--- a/src/bootstrap/src/bin/main.rs
+++ b/src/bootstrap/src/bin/main.rs
@@ -159,6 +159,9 @@ fn main() {
     if is_bootstrap_profiling_enabled() {
         build.report_summary(start_time);
     }
+
+    #[cfg(feature = "tracing")]
+    build.report_step_graph();
 }
 
 fn check_version(config: &Config) -> Option<String> {
diff --git a/src/bootstrap/src/core/build_steps/check.rs b/src/bootstrap/src/core/build_steps/check.rs
index b4232409ba8..f6653ed899b 100644
--- a/src/bootstrap/src/core/build_steps/check.rs
+++ b/src/bootstrap/src/core/build_steps/check.rs
@@ -13,7 +13,7 @@ use crate::core::builder::{
 };
 use crate::core::config::TargetSelection;
 use crate::utils::build_stamp::{self, BuildStamp};
-use crate::{Compiler, Mode, Subcommand};
+use crate::{CodegenBackendKind, Compiler, Mode, Subcommand};
 
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct Std {
@@ -312,7 +312,7 @@ fn prepare_compiler_for_check(
 pub struct CodegenBackend {
     pub build_compiler: Compiler,
     pub target: TargetSelection,
-    pub backend: &'static str,
+    pub backend: CodegenBackendKind,
 }
 
 impl Step for CodegenBackend {
@@ -327,14 +327,14 @@ impl Step for CodegenBackend {
     fn make_run(run: RunConfig<'_>) {
         // FIXME: only check the backend(s) that were actually selected in run.paths
         let build_compiler = prepare_compiler_for_check(run.builder, run.target, Mode::Codegen);
-        for &backend in &["cranelift", "gcc"] {
+        for backend in [CodegenBackendKind::Cranelift, CodegenBackendKind::Gcc] {
             run.builder.ensure(CodegenBackend { build_compiler, target: run.target, backend });
         }
     }
 
     fn run(self, builder: &Builder<'_>) {
         // FIXME: remove once https://github.com/rust-lang/rust/issues/112393 is resolved
-        if builder.build.config.vendor && self.backend == "gcc" {
+        if builder.build.config.vendor && self.backend.is_gcc() {
             println!("Skipping checking of `rustc_codegen_gcc` with vendoring enabled.");
             return;
         }
@@ -354,19 +354,22 @@ impl Step for CodegenBackend {
 
         cargo
             .arg("--manifest-path")
-            .arg(builder.src.join(format!("compiler/rustc_codegen_{backend}/Cargo.toml")));
+            .arg(builder.src.join(format!("compiler/{}/Cargo.toml", backend.crate_name())));
         rustc_cargo_env(builder, &mut cargo, target);
 
-        let _guard = builder.msg_check(format!("rustc_codegen_{backend}"), target, None);
+        let _guard = builder.msg_check(backend.crate_name(), target, None);
 
-        let stamp = build_stamp::codegen_backend_stamp(builder, build_compiler, target, backend)
+        let stamp = build_stamp::codegen_backend_stamp(builder, build_compiler, target, &backend)
             .with_prefix("check");
 
         run_cargo(builder, cargo, builder.config.free_args.clone(), &stamp, vec![], true, false);
     }
 
     fn metadata(&self) -> Option<StepMetadata> {
-        Some(StepMetadata::check(self.backend, self.target).built_by(self.build_compiler))
+        Some(
+            StepMetadata::check(&self.backend.crate_name(), self.target)
+                .built_by(self.build_compiler),
+        )
     }
 }
 
diff --git a/src/bootstrap/src/core/build_steps/compile.rs b/src/bootstrap/src/core/build_steps/compile.rs
index 4abfe1843eb..59541bf12de 100644
--- a/src/bootstrap/src/core/build_steps/compile.rs
+++ b/src/bootstrap/src/core/build_steps/compile.rs
@@ -33,7 +33,10 @@ use crate::utils::exec::command;
 use crate::utils::helpers::{
     exe, get_clang_cl_resource_dir, is_debug_info, is_dylib, symlink_dir, t, up_to_date,
 };
-use crate::{CLang, Compiler, DependencyType, FileType, GitRepo, LLVM_TOOLS, Mode, debug, trace};
+use crate::{
+    CLang, CodegenBackendKind, Compiler, DependencyType, FileType, GitRepo, LLVM_TOOLS, Mode,
+    debug, trace,
+};
 
 /// Build a standard library for the given `target` using the given `compiler`.
 #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
@@ -1330,7 +1333,7 @@ pub fn rustc_cargo_env(builder: &Builder<'_>, cargo: &mut Cargo, target: TargetS
     }
 
     if let Some(backend) = builder.config.default_codegen_backend(target) {
-        cargo.env("CFG_DEFAULT_CODEGEN_BACKEND", backend);
+        cargo.env("CFG_DEFAULT_CODEGEN_BACKEND", backend.name());
     }
 
     let libdir_relative = builder.config.libdir_relative().unwrap_or_else(|| Path::new("lib"));
@@ -1543,7 +1546,7 @@ impl Step for RustcLink {
 pub struct CodegenBackend {
     pub target: TargetSelection,
     pub compiler: Compiler,
-    pub backend: String,
+    pub backend: CodegenBackendKind,
 }
 
 fn needs_codegen_config(run: &RunConfig<'_>) -> bool {
@@ -1568,7 +1571,7 @@ fn is_codegen_cfg_needed(path: &TaskPath, run: &RunConfig<'_>) -> bool {
     if path.contains(CODEGEN_BACKEND_PREFIX) {
         let mut needs_codegen_backend_config = true;
         for backend in run.builder.config.codegen_backends(run.target) {
-            if path.ends_with(&(CODEGEN_BACKEND_PREFIX.to_owned() + backend)) {
+            if path.ends_with(&(CODEGEN_BACKEND_PREFIX.to_owned() + backend.name())) {
                 needs_codegen_backend_config = false;
             }
         }
@@ -1602,7 +1605,7 @@ impl Step for CodegenBackend {
         }
 
         for backend in run.builder.config.codegen_backends(run.target) {
-            if backend == "llvm" {
+            if backend.is_llvm() {
                 continue; // Already built as part of rustc
             }
 
@@ -1663,20 +1666,21 @@ impl Step for CodegenBackend {
         );
         cargo
             .arg("--manifest-path")
-            .arg(builder.src.join(format!("compiler/rustc_codegen_{backend}/Cargo.toml")));
+            .arg(builder.src.join(format!("compiler/{}/Cargo.toml", backend.crate_name())));
         rustc_cargo_env(builder, &mut cargo, target);
 
         // Ideally, we'd have a separate step for the individual codegen backends,
         // like we have in tests (test::CodegenGCC) but that would require a lot of restructuring.
         // If the logic gets more complicated, it should probably be done.
-        if backend == "gcc" {
+        if backend.is_gcc() {
             let gcc = builder.ensure(Gcc { target });
             add_cg_gcc_cargo_flags(&mut cargo, &gcc);
         }
 
         let tmp_stamp = BuildStamp::new(&out_dir).with_prefix("tmp");
 
-        let _guard = builder.msg_build(compiler, format_args!("codegen backend {backend}"), target);
+        let _guard =
+            builder.msg_build(compiler, format_args!("codegen backend {}", backend.name()), target);
         let files = run_cargo(builder, cargo, vec![], &tmp_stamp, vec![], false, false);
         if builder.config.dry_run() {
             return;
@@ -1731,7 +1735,7 @@ fn copy_codegen_backends_to_sysroot(
     }
 
     for backend in builder.config.codegen_backends(target) {
-        if backend == "llvm" {
+        if backend.is_llvm() {
             continue; // Already built as part of rustc
         }
 
@@ -2161,7 +2165,7 @@ impl Step for Assemble {
         let _codegen_backend_span =
             span!(tracing::Level::DEBUG, "building requested codegen backends").entered();
         for backend in builder.config.codegen_backends(target_compiler.host) {
-            if backend == "llvm" {
+            if backend.is_llvm() {
                 debug!("llvm codegen backend is already built as part of rustc");
                 continue; // Already built as part of rustc
             }
diff --git a/src/bootstrap/src/core/build_steps/dist.rs b/src/bootstrap/src/core/build_steps/dist.rs
index c8a54ad250c..4699813abf4 100644
--- a/src/bootstrap/src/core/build_steps/dist.rs
+++ b/src/bootstrap/src/core/build_steps/dist.rs
@@ -32,7 +32,7 @@ use crate::utils::helpers::{
     exe, is_dylib, move_file, t, target_supports_cranelift_backend, timeit,
 };
 use crate::utils::tarball::{GeneratedTarball, OverlayKind, Tarball};
-use crate::{Compiler, DependencyType, FileType, LLVM_TOOLS, Mode, trace};
+use crate::{CodegenBackendKind, Compiler, DependencyType, FileType, LLVM_TOOLS, Mode, trace};
 
 pub fn pkgname(builder: &Builder<'_>, component: &str) -> String {
     format!("{}-{}", component, builder.rust_package_vers())
@@ -1372,10 +1372,10 @@ impl Step for Miri {
     }
 }
 
-#[derive(Debug, PartialOrd, Ord, Clone, Hash, PartialEq, Eq)]
+#[derive(Debug, Clone, Hash, PartialEq, Eq)]
 pub struct CodegenBackend {
     pub compiler: Compiler,
-    pub backend: String,
+    pub backend: CodegenBackendKind,
 }
 
 impl Step for CodegenBackend {
@@ -1389,7 +1389,7 @@ impl Step for CodegenBackend {
 
     fn make_run(run: RunConfig<'_>) {
         for backend in run.builder.config.codegen_backends(run.target) {
-            if backend == "llvm" {
+            if backend.is_llvm() {
                 continue; // Already built as part of rustc
             }
 
@@ -1412,12 +1412,11 @@ impl Step for CodegenBackend {
             return None;
         }
 
-        if !builder.config.codegen_backends(self.compiler.host).contains(&self.backend.to_string())
-        {
+        if !builder.config.codegen_backends(self.compiler.host).contains(&self.backend) {
             return None;
         }
 
-        if self.backend == "cranelift" && !target_supports_cranelift_backend(self.compiler.host) {
+        if self.backend.is_cranelift() && !target_supports_cranelift_backend(self.compiler.host) {
             builder.info("target not supported by rustc_codegen_cranelift. skipping");
             return None;
         }
@@ -1425,15 +1424,18 @@ impl Step for CodegenBackend {
         let compiler = self.compiler;
         let backend = self.backend;
 
-        let mut tarball =
-            Tarball::new(builder, &format!("rustc-codegen-{backend}"), &compiler.host.triple);
-        if backend == "cranelift" {
+        let mut tarball = Tarball::new(
+            builder,
+            &format!("rustc-codegen-{}", backend.name()),
+            &compiler.host.triple,
+        );
+        if backend.is_cranelift() {
             tarball.set_overlay(OverlayKind::RustcCodegenCranelift);
         } else {
-            panic!("Unknown backend rustc_codegen_{backend}");
+            panic!("Unknown codegen backend {}", backend.name());
         }
         tarball.is_preview(true);
-        tarball.add_legal_and_readme_to(format!("share/doc/rustc_codegen_{backend}"));
+        tarball.add_legal_and_readme_to(format!("share/doc/{}", backend.crate_name()));
 
         let src = builder.sysroot(compiler);
         let backends_src = builder.sysroot_codegen_backends(compiler);
@@ -1445,7 +1447,7 @@ impl Step for CodegenBackend {
         // Don't use custom libdir here because ^lib/ will be resolved again with installer
         let backends_dst = PathBuf::from("lib").join(backends_rel);
 
-        let backend_name = format!("rustc_codegen_{backend}");
+        let backend_name = backend.crate_name();
         let mut found_backend = false;
         for backend in fs::read_dir(&backends_src).unwrap() {
             let file_name = backend.unwrap().file_name();
@@ -1575,7 +1577,7 @@ impl Step for Extended {
         add_component!("analysis" => Analysis { compiler, target });
         add_component!("rustc-codegen-cranelift" => CodegenBackend {
             compiler: builder.compiler(stage, target),
-            backend: "cranelift".to_string(),
+            backend: CodegenBackendKind::Cranelift,
         });
         add_component!("llvm-bitcode-linker" => LlvmBitcodeLinker {
             build_compiler: compiler,
diff --git a/src/bootstrap/src/core/build_steps/install.rs b/src/bootstrap/src/core/build_steps/install.rs
index 4156b49a8b3..4513a138e19 100644
--- a/src/bootstrap/src/core/build_steps/install.rs
+++ b/src/bootstrap/src/core/build_steps/install.rs
@@ -12,7 +12,7 @@ use crate::core::config::{Config, TargetSelection};
 use crate::utils::exec::command;
 use crate::utils::helpers::t;
 use crate::utils::tarball::GeneratedTarball;
-use crate::{Compiler, Kind};
+use crate::{CodegenBackendKind, Compiler, Kind};
 
 #[cfg(target_os = "illumos")]
 const SHELL: &str = "bash";
@@ -276,7 +276,7 @@ install!((self, builder, _config),
     RustcCodegenCranelift, alias = "rustc-codegen-cranelift", Self::should_build(_config), only_hosts: true, {
         if let Some(tarball) = builder.ensure(dist::CodegenBackend {
             compiler: self.compiler,
-            backend: "cranelift".to_string(),
+            backend: CodegenBackendKind::Cranelift,
         }) {
             install_sh(builder, "rustc-codegen-cranelift", self.compiler.stage, Some(self.target), &tarball);
         } else {
diff --git a/src/bootstrap/src/core/build_steps/test.rs b/src/bootstrap/src/core/build_steps/test.rs
index 951ca73fcc4..8bee00a9c13 100644
--- a/src/bootstrap/src/core/build_steps/test.rs
+++ b/src/bootstrap/src/core/build_steps/test.rs
@@ -33,7 +33,7 @@ use crate::utils::helpers::{
     linker_flags, t, target_supports_cranelift_backend, up_to_date,
 };
 use crate::utils::render_tests::{add_flags_and_try_run_tests, try_run_tests};
-use crate::{CLang, DocTests, GitRepo, Mode, PathSet, debug, envify};
+use crate::{CLang, CodegenBackendKind, DocTests, GitRepo, Mode, PathSet, debug, envify};
 
 const ADB_TEST_DIR: &str = "/data/local/tmp/work";
 
@@ -749,6 +749,12 @@ NOTE: if you're sure you want to do this, please open an issue as to why. In the
             SourceType::InTree,
             &[],
         );
+
+        // Used for `compiletest` self-tests to have the path to the *staged* compiler. Getting this
+        // right is important, as `compiletest` is intended to only support one target spec JSON
+        // format, namely that of the staged compiler.
+        cargo.env("TEST_RUSTC", builder.rustc(compiler));
+
         cargo.allow_features(COMPILETEST_ALLOW_FEATURES);
         run_cargo_test(cargo, &[], &[], "compiletest self test", host, builder);
     }
@@ -1657,7 +1663,11 @@ NOTE: if you're sure you want to do this, please open an issue as to why. In the
         // bootstrap compiler.
         // NOTE: Only stage 1 is special cased because we need the rustc_private artifacts to match the
         // running compiler in stage 2 when plugins run.
+        let query_compiler;
         let (stage, stage_id) = if suite == "ui-fulldeps" && compiler.stage == 1 {
+            // Even when using the stage 0 compiler, we also need to provide the stage 1 compiler
+            // so that compiletest can query it for target information.
+            query_compiler = Some(compiler);
             // At stage 0 (stage - 1) we are using the stage0 compiler. Using `self.target` can lead
             // finding an incorrect compiler path on cross-targets, as the stage 0 is always equal to
             // `build.build` in the configuration.
@@ -1666,6 +1676,7 @@ NOTE: if you're sure you want to do this, please open an issue as to why. In the
             let test_stage = compiler.stage + 1;
             (test_stage, format!("stage{test_stage}-{build}"))
         } else {
+            query_compiler = None;
             let stage = compiler.stage;
             (stage, format!("stage{stage}-{target}"))
         };
@@ -1710,6 +1721,9 @@ NOTE: if you're sure you want to do this, please open an issue as to why. In the
         cmd.arg("--compile-lib-path").arg(builder.rustc_libdir(compiler));
         cmd.arg("--run-lib-path").arg(builder.sysroot_target_libdir(compiler, target));
         cmd.arg("--rustc-path").arg(builder.rustc(compiler));
+        if let Some(query_compiler) = query_compiler {
+            cmd.arg("--query-rustc-path").arg(builder.rustc(query_compiler));
+        }
 
         // Minicore auxiliary lib for `no_core` tests that need `core` stubs in cross-compilation
         // scenarios.
@@ -1786,7 +1800,9 @@ NOTE: if you're sure you want to do this, please open an issue as to why. In the
         cmd.arg("--llvm-filecheck").arg(builder.llvm_filecheck(builder.config.host_target));
 
         if let Some(codegen_backend) = builder.config.default_codegen_backend(compiler.host) {
-            cmd.arg("--codegen-backend").arg(&codegen_backend);
+            // Tells compiletest which codegen backend is used by default by the compiler.
+            // It is used to e.g. ignore tests that don't support that codegen backend.
+            cmd.arg("--codegen-backend").arg(codegen_backend.name());
         }
 
         if builder.build.config.llvm_enzyme {
@@ -3406,7 +3422,7 @@ impl Step for CodegenCranelift {
             return;
         }
 
-        if !builder.config.codegen_backends(run.target).contains(&"cranelift".to_owned()) {
+        if !builder.config.codegen_backends(run.target).contains(&CodegenBackendKind::Cranelift) {
             builder.info("cranelift not in rust.codegen-backends. skipping");
             return;
         }
@@ -3533,7 +3549,7 @@ impl Step for CodegenGCC {
             return;
         }
 
-        if !builder.config.codegen_backends(run.target).contains(&"gcc".to_owned()) {
+        if !builder.config.codegen_backends(run.target).contains(&CodegenBackendKind::Gcc) {
             builder.info("gcc not in rust.codegen-backends. skipping");
             return;
         }
diff --git a/src/bootstrap/src/core/builder/cargo.rs b/src/bootstrap/src/core/builder/cargo.rs
index badd5f24dba..6b3236ef47e 100644
--- a/src/bootstrap/src/core/builder/cargo.rs
+++ b/src/bootstrap/src/core/builder/cargo.rs
@@ -1286,7 +1286,7 @@ impl Builder<'_> {
 
             if let Some(limit) = limit
                 && (build_compiler_stage == 0
-                    || self.config.default_codegen_backend(target).unwrap_or_default() == "llvm")
+                    || self.config.default_codegen_backend(target).unwrap_or_default().is_llvm())
             {
                 rustflags.arg(&format!("-Cllvm-args=-import-instr-limit={limit}"));
             }
diff --git a/src/bootstrap/src/core/builder/mod.rs b/src/bootstrap/src/core/builder/mod.rs
index 020622d1c12..20f3fee1c6c 100644
--- a/src/bootstrap/src/core/builder/mod.rs
+++ b/src/bootstrap/src/core/builder/mod.rs
@@ -77,7 +77,7 @@ impl Deref for Builder<'_> {
 /// type's [`Debug`] implementation.
 ///
 /// (Trying to debug-print `dyn Any` results in the unhelpful `"Any { .. }"`.)
-trait AnyDebug: Any + Debug {}
+pub trait AnyDebug: Any + Debug {}
 impl<T: Any + Debug> AnyDebug for T {}
 impl dyn AnyDebug {
     /// Equivalent to `<dyn Any>::downcast_ref`.
@@ -141,7 +141,7 @@ pub trait Step: 'static + Clone + Debug + PartialEq + Eq + Hash {
 #[allow(unused)]
 #[derive(Debug, PartialEq, Eq)]
 pub struct StepMetadata {
-    name: &'static str,
+    name: String,
     kind: Kind,
     target: TargetSelection,
     built_by: Option<Compiler>,
@@ -151,28 +151,28 @@ pub struct StepMetadata {
 }
 
 impl StepMetadata {
-    pub fn build(name: &'static str, target: TargetSelection) -> Self {
+    pub fn build(name: &str, target: TargetSelection) -> Self {
         Self::new(name, target, Kind::Build)
     }
 
-    pub fn check(name: &'static str, target: TargetSelection) -> Self {
+    pub fn check(name: &str, target: TargetSelection) -> Self {
         Self::new(name, target, Kind::Check)
     }
 
-    pub fn doc(name: &'static str, target: TargetSelection) -> Self {
+    pub fn doc(name: &str, target: TargetSelection) -> Self {
         Self::new(name, target, Kind::Doc)
     }
 
-    pub fn dist(name: &'static str, target: TargetSelection) -> Self {
+    pub fn dist(name: &str, target: TargetSelection) -> Self {
         Self::new(name, target, Kind::Dist)
     }
 
-    pub fn test(name: &'static str, target: TargetSelection) -> Self {
+    pub fn test(name: &str, target: TargetSelection) -> Self {
         Self::new(name, target, Kind::Test)
     }
 
-    fn new(name: &'static str, target: TargetSelection, kind: Kind) -> Self {
-        Self { name, kind, target, built_by: None, stage: None, metadata: None }
+    fn new(name: &str, target: TargetSelection, kind: Kind) -> Self {
+        Self { name: name.to_string(), kind, target, built_by: None, stage: None, metadata: None }
     }
 
     pub fn built_by(mut self, compiler: Compiler) -> Self {
@@ -197,6 +197,14 @@ impl StepMetadata {
             // For everything else, a stage N things gets built by a stage N-1 compiler.
             .map(|compiler| if self.name == "std" { compiler.stage } else { compiler.stage + 1 }))
     }
+
+    pub fn get_name(&self) -> &str {
+        &self.name
+    }
+
+    pub fn get_target(&self) -> TargetSelection {
+        self.target
+    }
 }
 
 pub struct RunConfig<'a> {
@@ -1657,9 +1665,24 @@ You have to build a stage1 compiler for `{}` first, and then use it to build a s
             if let Some(out) = self.cache.get(&step) {
                 self.verbose_than(1, || println!("{}c {:?}", "  ".repeat(stack.len()), step));
 
+                #[cfg(feature = "tracing")]
+                {
+                    if let Some(parent) = stack.last() {
+                        let mut graph = self.build.step_graph.borrow_mut();
+                        graph.register_cached_step(&step, parent, self.config.dry_run());
+                    }
+                }
                 return out;
             }
             self.verbose_than(1, || println!("{}> {:?}", "  ".repeat(stack.len()), step));
+
+            #[cfg(feature = "tracing")]
+            {
+                let parent = stack.last();
+                let mut graph = self.build.step_graph.borrow_mut();
+                graph.register_step_execution(&step, parent, self.config.dry_run());
+            }
+
             stack.push(Box::new(step.clone()));
         }
 
diff --git a/src/bootstrap/src/core/builder/tests.rs b/src/bootstrap/src/core/builder/tests.rs
index 6ea5d4e6553..f012645b7ef 100644
--- a/src/bootstrap/src/core/builder/tests.rs
+++ b/src/bootstrap/src/core/builder/tests.rs
@@ -999,7 +999,7 @@ mod snapshot {
         [build] llvm <host>
         [build] rustc 0 <host> -> rustc 1 <host>
         [build] rustdoc 0 <host>
-        [doc] std 1 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
+        [doc] std 1 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
         ");
     }
 
@@ -1048,7 +1048,7 @@ mod snapshot {
         [build] rustc 1 <host> -> std 1 <host>
         [build] rustc 1 <host> -> rustc 2 <host>
         [build] rustdoc 1 <host>
-        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
+        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
         [build] rustc 2 <host> -> std 2 <host>
         [build] rustc 0 <host> -> LintDocs 1 <host>
         [build] rustc 0 <host> -> RustInstaller 1 <host>
@@ -1090,7 +1090,7 @@ mod snapshot {
         [build] rustc 1 <host> -> WasmComponentLd 2 <host>
         [build] rustc 1 <host> -> LlvmBitcodeLinker 2 <host>
         [build] rustdoc 1 <host>
-        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
+        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
         [build] rustc 2 <host> -> std 2 <host>
         [build] rustc 0 <host> -> LintDocs 1 <host>
         [build] rustc 0 <host> -> RustInstaller 1 <host>
@@ -1126,8 +1126,8 @@ mod snapshot {
         [build] rustc 1 <host> -> std 1 <host>
         [build] rustc 1 <host> -> rustc 2 <host>
         [build] rustdoc 1 <host>
-        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
-        [doc] std 2 <target1> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
+        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
+        [doc] std 2 <target1> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
         [build] rustc 2 <host> -> std 2 <host>
         [build] rustc 0 <host> -> LintDocs 1 <host>
         [build] rustc 0 <host> -> RustInstaller 1 <host>
@@ -1163,7 +1163,7 @@ mod snapshot {
         [build] rustc 1 <host> -> std 1 <host>
         [build] rustc 1 <host> -> rustc 2 <host>
         [build] rustdoc 1 <host>
-        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
+        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
         [build] rustc 2 <host> -> std 2 <host>
         [build] rustc 0 <host> -> LintDocs 1 <host>
         [build] rustc 1 <host> -> std 1 <target1>
@@ -1200,8 +1200,8 @@ mod snapshot {
         [build] rustc 1 <host> -> std 1 <host>
         [build] rustc 1 <host> -> rustc 2 <host>
         [build] rustdoc 1 <host>
-        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
-        [doc] std 2 <target1> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
+        [doc] std 2 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
+        [doc] std 2 <target1> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
         [build] rustc 2 <host> -> std 2 <host>
         [build] rustc 0 <host> -> LintDocs 1 <host>
         [build] rustc 1 <host> -> std 1 <target1>
@@ -1242,7 +1242,7 @@ mod snapshot {
         [build] rustc 1 <host> -> std 1 <host>
         [build] rustc 1 <host> -> rustc 2 <host>
         [build] rustdoc 1 <host>
-        [doc] std 2 <target1> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
+        [doc] std 2 <target1> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
         [build] rustc 2 <host> -> std 2 <host>
         [build] rustc 0 <host> -> RustInstaller 1 <host>
         [dist] docs <target1>
@@ -1274,7 +1274,7 @@ mod snapshot {
         [build] rustc 1 <host> -> rustc 2 <host>
         [build] rustc 1 <host> -> WasmComponentLd 2 <host>
         [build] rustdoc 1 <host>
-        [doc] std 2 <target1> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
+        [doc] std 2 <target1> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
         [build] rustc 2 <host> -> std 2 <host>
         [build] rustc 1 <host> -> std 1 <target1>
         [build] rustc 2 <host> -> std 2 <target1>
@@ -1309,8 +1309,8 @@ mod snapshot {
                 .path("compiler")
                 .render_steps(), @r"
         [check] rustc 0 <host> -> rustc 1 <host>
-        [check] rustc 0 <host> -> cranelift 1 <host>
-        [check] rustc 0 <host> -> gcc 1 <host>
+        [check] rustc 0 <host> -> rustc_codegen_cranelift 1 <host>
+        [check] rustc 0 <host> -> rustc_codegen_gcc 1 <host>
         ");
     }
 
@@ -1341,8 +1341,8 @@ mod snapshot {
                 .stage(1)
                 .render_steps(), @r"
         [check] rustc 0 <host> -> rustc 1 <host>
-        [check] rustc 0 <host> -> cranelift 1 <host>
-        [check] rustc 0 <host> -> gcc 1 <host>
+        [check] rustc 0 <host> -> rustc_codegen_cranelift 1 <host>
+        [check] rustc 0 <host> -> rustc_codegen_gcc 1 <host>
         ");
     }
 
@@ -1358,8 +1358,8 @@ mod snapshot {
         [build] rustc 0 <host> -> rustc 1 <host>
         [build] rustc 1 <host> -> std 1 <host>
         [check] rustc 1 <host> -> rustc 2 <host>
-        [check] rustc 1 <host> -> cranelift 2 <host>
-        [check] rustc 1 <host> -> gcc 2 <host>
+        [check] rustc 1 <host> -> rustc_codegen_cranelift 2 <host>
+        [check] rustc 1 <host> -> rustc_codegen_gcc 2 <host>
         ");
     }
 
@@ -1377,8 +1377,8 @@ mod snapshot {
         [build] rustc 1 <host> -> std 1 <target1>
         [check] rustc 1 <host> -> rustc 2 <target1>
         [check] rustc 1 <host> -> Rustdoc 2 <target1>
-        [check] rustc 1 <host> -> cranelift 2 <target1>
-        [check] rustc 1 <host> -> gcc 2 <target1>
+        [check] rustc 1 <host> -> rustc_codegen_cranelift 2 <target1>
+        [check] rustc 1 <host> -> rustc_codegen_gcc 2 <target1>
         [check] rustc 1 <host> -> Clippy 2 <target1>
         [check] rustc 1 <host> -> Miri 2 <target1>
         [check] rustc 1 <host> -> CargoMiri 2 <target1>
@@ -1472,8 +1472,8 @@ mod snapshot {
                 .args(&args)
                 .render_steps(), @r"
         [check] rustc 0 <host> -> rustc 1 <host>
-        [check] rustc 0 <host> -> cranelift 1 <host>
-        [check] rustc 0 <host> -> gcc 1 <host>
+        [check] rustc 0 <host> -> rustc_codegen_cranelift 1 <host>
+        [check] rustc 0 <host> -> rustc_codegen_gcc 1 <host>
         ");
     }
 
@@ -1557,8 +1557,8 @@ mod snapshot {
                 .path("rustc_codegen_cranelift")
                 .render_steps(), @r"
         [check] rustc 0 <host> -> rustc 1 <host>
-        [check] rustc 0 <host> -> cranelift 1 <host>
-        [check] rustc 0 <host> -> gcc 1 <host>
+        [check] rustc 0 <host> -> rustc_codegen_cranelift 1 <host>
+        [check] rustc 0 <host> -> rustc_codegen_gcc 1 <host>
         ");
     }
 
@@ -1620,7 +1620,7 @@ mod snapshot {
         [build] llvm <host>
         [build] rustc 0 <host> -> rustc 1 <host>
         [build] rustdoc 0 <host>
-        [doc] std 1 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,std,std_detect,sysroot,test,unwind]
+        [doc] std 1 <host> crates=[alloc,compiler_builtins,core,panic_abort,panic_unwind,proc_macro,rustc-std-workspace-core,std,std_detect,sysroot,test,unwind]
         ");
     }
 
diff --git a/src/bootstrap/src/core/config/config.rs b/src/bootstrap/src/core/config/config.rs
index 78abdd7f9b8..6055876c475 100644
--- a/src/bootstrap/src/core/config/config.rs
+++ b/src/bootstrap/src/core/config/config.rs
@@ -51,7 +51,7 @@ use crate::core::download::{
 use crate::utils::channel;
 use crate::utils::exec::{ExecutionContext, command};
 use crate::utils::helpers::{exe, get_host_target};
-use crate::{GitInfo, OnceLock, TargetSelection, check_ci_llvm, helpers, t};
+use crate::{CodegenBackendKind, GitInfo, OnceLock, TargetSelection, check_ci_llvm, helpers, t};
 
 /// Each path in this list is considered "allowed" in the `download-rustc="if-unchanged"` logic.
 /// This means they can be modified and changes to these paths should never trigger a compiler build
@@ -208,7 +208,7 @@ pub struct Config {
     pub rustc_default_linker: Option<String>,
     pub rust_optimize_tests: bool,
     pub rust_dist_src: bool,
-    pub rust_codegen_backends: Vec<String>,
+    pub rust_codegen_backends: Vec<CodegenBackendKind>,
     pub rust_verify_llvm_ir: bool,
     pub rust_thin_lto_import_instr_limit: Option<u32>,
     pub rust_randomize_layout: bool,
@@ -350,7 +350,7 @@ impl Config {
             channel: "dev".to_string(),
             codegen_tests: true,
             rust_dist_src: true,
-            rust_codegen_backends: vec!["llvm".to_owned()],
+            rust_codegen_backends: vec![CodegenBackendKind::Llvm],
             deny_warnings: true,
             bindir: "bin".into(),
             dist_include_mingw_linker: true,
@@ -1747,7 +1747,7 @@ impl Config {
             .unwrap_or(self.profiler)
     }
 
-    pub fn codegen_backends(&self, target: TargetSelection) -> &[String] {
+    pub fn codegen_backends(&self, target: TargetSelection) -> &[CodegenBackendKind] {
         self.target_config
             .get(&target)
             .and_then(|cfg| cfg.codegen_backends.as_deref())
@@ -1758,7 +1758,7 @@ impl Config {
         self.target_config.get(&target).and_then(|cfg| cfg.jemalloc).unwrap_or(self.jemalloc)
     }
 
-    pub fn default_codegen_backend(&self, target: TargetSelection) -> Option<String> {
+    pub fn default_codegen_backend(&self, target: TargetSelection) -> Option<CodegenBackendKind> {
         self.codegen_backends(target).first().cloned()
     }
 
@@ -1774,7 +1774,7 @@ impl Config {
     }
 
     pub fn llvm_enabled(&self, target: TargetSelection) -> bool {
-        self.codegen_backends(target).contains(&"llvm".to_owned())
+        self.codegen_backends(target).contains(&CodegenBackendKind::Llvm)
     }
 
     pub fn llvm_libunwind(&self, target: TargetSelection) -> LlvmLibunwind {
diff --git a/src/bootstrap/src/core/config/toml/rust.rs b/src/bootstrap/src/core/config/toml/rust.rs
index c136bd4a6f9..03da993a17d 100644
--- a/src/bootstrap/src/core/config/toml/rust.rs
+++ b/src/bootstrap/src/core/config/toml/rust.rs
@@ -11,7 +11,9 @@ use crate::core::config::{
     DebuginfoLevel, Merge, ReplaceOpt, RustcLto, StringOrBool, set, threads_from_config,
 };
 use crate::flags::Warnings;
-use crate::{BTreeSet, Config, HashSet, PathBuf, TargetSelection, define_config, exit};
+use crate::{
+    BTreeSet, CodegenBackendKind, Config, HashSet, PathBuf, TargetSelection, define_config, exit,
+};
 
 define_config! {
     /// TOML representation of how the Rust build is configured.
@@ -389,9 +391,13 @@ pub fn check_incompatible_options_for_ci_rustc(
     Ok(())
 }
 
-pub(crate) const VALID_CODEGEN_BACKENDS: &[&str] = &["llvm", "cranelift", "gcc"];
+pub(crate) const BUILTIN_CODEGEN_BACKENDS: &[&str] = &["llvm", "cranelift", "gcc"];
 
-pub(crate) fn validate_codegen_backends(backends: Vec<String>, section: &str) -> Vec<String> {
+pub(crate) fn parse_codegen_backends(
+    backends: Vec<String>,
+    section: &str,
+) -> Vec<CodegenBackendKind> {
+    let mut found_backends = vec![];
     for backend in &backends {
         if let Some(stripped) = backend.strip_prefix(CODEGEN_BACKEND_PREFIX) {
             panic!(
@@ -400,14 +406,21 @@ pub(crate) fn validate_codegen_backends(backends: Vec<String>, section: &str) ->
                 Please, use '{stripped}' instead."
             )
         }
-        if !VALID_CODEGEN_BACKENDS.contains(&backend.as_str()) {
+        if !BUILTIN_CODEGEN_BACKENDS.contains(&backend.as_str()) {
             println!(
                 "HELP: '{backend}' for '{section}.codegen-backends' might fail. \
-                List of known good values: {VALID_CODEGEN_BACKENDS:?}"
+                List of known codegen backends: {BUILTIN_CODEGEN_BACKENDS:?}"
             );
         }
+        let backend = match backend.as_str() {
+            "llvm" => CodegenBackendKind::Llvm,
+            "cranelift" => CodegenBackendKind::Cranelift,
+            "gcc" => CodegenBackendKind::Gcc,
+            backend => CodegenBackendKind::Custom(backend.to_string()),
+        };
+        found_backends.push(backend);
     }
-    backends
+    found_backends
 }
 
 #[cfg(not(test))]
@@ -609,7 +622,7 @@ impl Config {
                 llvm_libunwind.map(|v| v.parse().expect("failed to parse rust.llvm-libunwind"));
             set(
                 &mut self.rust_codegen_backends,
-                codegen_backends.map(|backends| validate_codegen_backends(backends, "rust")),
+                codegen_backends.map(|backends| parse_codegen_backends(backends, "rust")),
             );
 
             self.rust_codegen_units = codegen_units.map(threads_from_config);
diff --git a/src/bootstrap/src/core/config/toml/target.rs b/src/bootstrap/src/core/config/toml/target.rs
index 337276948b3..9dedadff3a1 100644
--- a/src/bootstrap/src/core/config/toml/target.rs
+++ b/src/bootstrap/src/core/config/toml/target.rs
@@ -16,9 +16,9 @@ use std::collections::HashMap;
 
 use serde::{Deserialize, Deserializer};
 
-use crate::core::config::toml::rust::validate_codegen_backends;
+use crate::core::config::toml::rust::parse_codegen_backends;
 use crate::core::config::{LlvmLibunwind, Merge, ReplaceOpt, SplitDebuginfo, StringOrBool};
-use crate::{Config, HashSet, PathBuf, TargetSelection, define_config, exit};
+use crate::{CodegenBackendKind, Config, HashSet, PathBuf, TargetSelection, define_config, exit};
 
 define_config! {
     /// TOML representation of how each build target is configured.
@@ -76,7 +76,7 @@ pub struct Target {
     pub qemu_rootfs: Option<PathBuf>,
     pub runner: Option<String>,
     pub no_std: bool,
-    pub codegen_backends: Option<Vec<String>>,
+    pub codegen_backends: Option<Vec<CodegenBackendKind>>,
     pub optimized_compiler_builtins: Option<bool>,
     pub jemalloc: Option<bool>,
 }
@@ -144,7 +144,7 @@ impl Config {
                 target.jemalloc = cfg.jemalloc;
                 if let Some(backends) = cfg.codegen_backends {
                     target.codegen_backends =
-                        Some(validate_codegen_backends(backends, &format!("target.{triple}")))
+                        Some(parse_codegen_backends(backends, &format!("target.{triple}")))
                 }
 
                 target.split_debuginfo = cfg.split_debuginfo.as_ref().map(|v| {
diff --git a/src/bootstrap/src/lib.rs b/src/bootstrap/src/lib.rs
index 51a84ad5272..e49513a2116 100644
--- a/src/bootstrap/src/lib.rs
+++ b/src/bootstrap/src/lib.rs
@@ -123,6 +123,46 @@ impl PartialEq for Compiler {
     }
 }
 
+/// Represents a codegen backend.
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
+pub enum CodegenBackendKind {
+    #[default]
+    Llvm,
+    Cranelift,
+    Gcc,
+    Custom(String),
+}
+
+impl CodegenBackendKind {
+    /// Name of the codegen backend, as identified in the `compiler` directory
+    /// (`rustc_codegen_<name>`).
+    pub fn name(&self) -> &str {
+        match self {
+            CodegenBackendKind::Llvm => "llvm",
+            CodegenBackendKind::Cranelift => "cranelift",
+            CodegenBackendKind::Gcc => "gcc",
+            CodegenBackendKind::Custom(name) => name,
+        }
+    }
+
+    /// Name of the codegen backend's crate, e.g. `rustc_codegen_cranelift`.
+    pub fn crate_name(&self) -> String {
+        format!("rustc_codegen_{}", self.name())
+    }
+
+    pub fn is_llvm(&self) -> bool {
+        matches!(self, Self::Llvm)
+    }
+
+    pub fn is_cranelift(&self) -> bool {
+        matches!(self, Self::Cranelift)
+    }
+
+    pub fn is_gcc(&self) -> bool {
+        matches!(self, Self::Gcc)
+    }
+}
+
 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
 pub enum DocTests {
     /// Run normal tests and doc tests (default).
@@ -148,7 +188,6 @@ pub enum GitRepo {
 /// although most functions are implemented as free functions rather than
 /// methods specifically on this structure itself (to make it easier to
 /// organize).
-#[derive(Clone)]
 pub struct Build {
     /// User-specified configuration from `bootstrap.toml`.
     config: Config,
@@ -204,6 +243,9 @@ pub struct Build {
 
     #[cfg(feature = "build-metrics")]
     metrics: crate::utils::metrics::BuildMetrics,
+
+    #[cfg(feature = "tracing")]
+    step_graph: std::cell::RefCell<crate::utils::step_graph::StepGraph>,
 }
 
 #[derive(Debug, Clone)]
@@ -507,6 +549,9 @@ impl Build {
 
             #[cfg(feature = "build-metrics")]
             metrics: crate::utils::metrics::BuildMetrics::init(),
+
+            #[cfg(feature = "tracing")]
+            step_graph: std::cell::RefCell::new(crate::utils::step_graph::StepGraph::default()),
         };
 
         // If local-rust is the same major.minor as the current version, then force a
@@ -1984,6 +2029,11 @@ to download LLVM rather than building it.
     pub fn report_summary(&self, start_time: Instant) {
         self.config.exec_ctx.profiler().report_summary(start_time);
     }
+
+    #[cfg(feature = "tracing")]
+    pub fn report_step_graph(self) {
+        self.step_graph.into_inner().store_to_dot_files();
+    }
 }
 
 impl AsRef<ExecutionContext> for Build {
diff --git a/src/bootstrap/src/utils/build_stamp.rs b/src/bootstrap/src/utils/build_stamp.rs
index f43d860893f..bd4eb790ae5 100644
--- a/src/bootstrap/src/utils/build_stamp.rs
+++ b/src/bootstrap/src/utils/build_stamp.rs
@@ -10,7 +10,7 @@ use sha2::digest::Digest;
 use crate::core::builder::Builder;
 use crate::core::config::TargetSelection;
 use crate::utils::helpers::{hex_encode, mtime};
-use crate::{Compiler, Mode, helpers, t};
+use crate::{CodegenBackendKind, Compiler, Mode, helpers, t};
 
 #[cfg(test)]
 mod tests;
@@ -129,10 +129,10 @@ pub fn codegen_backend_stamp(
     builder: &Builder<'_>,
     compiler: Compiler,
     target: TargetSelection,
-    backend: &str,
+    backend: &CodegenBackendKind,
 ) -> BuildStamp {
     BuildStamp::new(&builder.cargo_out(compiler, Mode::Codegen, target))
-        .with_prefix(&format!("librustc_codegen_{backend}"))
+        .with_prefix(&format!("lib{}", backend.crate_name()))
 }
 
 /// Cargo's output path for the standard library in a given stage, compiled
diff --git a/src/bootstrap/src/utils/mod.rs b/src/bootstrap/src/utils/mod.rs
index 169fcec303e..97d8d274e8f 100644
--- a/src/bootstrap/src/utils/mod.rs
+++ b/src/bootstrap/src/utils/mod.rs
@@ -19,5 +19,8 @@ pub(crate) mod tracing;
 #[cfg(feature = "build-metrics")]
 pub(crate) mod metrics;
 
+#[cfg(feature = "tracing")]
+pub(crate) mod step_graph;
+
 #[cfg(test)]
 pub(crate) mod tests;
diff --git a/src/bootstrap/src/utils/step_graph.rs b/src/bootstrap/src/utils/step_graph.rs
new file mode 100644
index 00000000000..c45825a4222
--- /dev/null
+++ b/src/bootstrap/src/utils/step_graph.rs
@@ -0,0 +1,182 @@
+use std::collections::{HashMap, HashSet};
+use std::fmt::Debug;
+use std::io::BufWriter;
+
+use crate::core::builder::{AnyDebug, Step};
+
+/// Records the executed steps and their dependencies in a directed graph,
+/// which can then be rendered into a DOT file for visualization.
+///
+/// The graph visualizes the first execution of a step with a solid edge,
+/// and cached executions of steps with a dashed edge.
+/// If you only want to see first executions, you can modify the code in `DotGraph` to
+/// always set `cached: false`.
+#[derive(Default)]
+pub struct StepGraph {
+    /// We essentially store one graph per dry run mode.
+    graphs: HashMap<String, DotGraph>,
+}
+
+impl StepGraph {
+    pub fn register_step_execution<S: Step>(
+        &mut self,
+        step: &S,
+        parent: Option<&Box<dyn AnyDebug>>,
+        dry_run: bool,
+    ) {
+        let key = get_graph_key(dry_run);
+        let graph = self.graphs.entry(key.to_string()).or_insert_with(|| DotGraph::default());
+
+        // The debug output of the step sort of serves as the unique identifier of it.
+        // We use it to access the node ID of parents to generate edges.
+        // We could probably also use addresses on the heap from the `Box`, but this seems less
+        // magical.
+        let node_key = render_step(step);
+
+        let label = if let Some(metadata) = step.metadata() {
+            format!(
+                "{}{} [{}]",
+                metadata.get_name(),
+                metadata.get_stage().map(|s| format!(" stage {s}")).unwrap_or_default(),
+                metadata.get_target()
+            )
+        } else {
+            let type_name = std::any::type_name::<S>();
+            type_name
+                .strip_prefix("bootstrap::core::")
+                .unwrap_or(type_name)
+                .strip_prefix("build_steps::")
+                .unwrap_or(type_name)
+                .to_string()
+        };
+
+        let node = Node { label, tooltip: node_key.clone() };
+        let node_handle = graph.add_node(node_key, node);
+
+        if let Some(parent) = parent {
+            let parent_key = render_step(parent);
+            if let Some(src_node_handle) = graph.get_handle_by_key(&parent_key) {
+                graph.add_edge(src_node_handle, node_handle);
+            }
+        }
+    }
+
+    pub fn register_cached_step<S: Step>(
+        &mut self,
+        step: &S,
+        parent: &Box<dyn AnyDebug>,
+        dry_run: bool,
+    ) {
+        let key = get_graph_key(dry_run);
+        let graph = self.graphs.get_mut(key).unwrap();
+
+        let node_key = render_step(step);
+        let parent_key = render_step(parent);
+
+        if let Some(src_node_handle) = graph.get_handle_by_key(&parent_key) {
+            if let Some(dst_node_handle) = graph.get_handle_by_key(&node_key) {
+                graph.add_cached_edge(src_node_handle, dst_node_handle);
+            }
+        }
+    }
+
+    pub fn store_to_dot_files(self) {
+        for (key, graph) in self.graphs.into_iter() {
+            let filename = format!("bootstrap-steps{key}.dot");
+            graph.render(&filename).unwrap();
+        }
+    }
+}
+
+fn get_graph_key(dry_run: bool) -> &'static str {
+    if dry_run { ".dryrun" } else { "" }
+}
+
+struct Node {
+    label: String,
+    tooltip: String,
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
+struct NodeHandle(usize);
+
+/// Represents a dependency between two bootstrap steps.
+#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
+struct Edge {
+    src: NodeHandle,
+    dst: NodeHandle,
+    // Was the corresponding execution of a step cached, or was the step actually executed?
+    cached: bool,
+}
+
+// We could use a library for this, but they either:
+// - require lifetimes, which gets annoying (dot_writer)
+// - don't support tooltips (dot_graph)
+// - have a lot of dependencies (graphviz_rust)
+// - only have SVG export (layout-rs)
+// - use a builder pattern that is very annoying to use here (tabbycat)
+#[derive(Default)]
+struct DotGraph {
+    nodes: Vec<Node>,
+    /// The `NodeHandle` represents an index within `self.nodes`
+    edges: HashSet<Edge>,
+    key_to_index: HashMap<String, NodeHandle>,
+}
+
+impl DotGraph {
+    fn add_node(&mut self, key: String, node: Node) -> NodeHandle {
+        let handle = NodeHandle(self.nodes.len());
+        self.nodes.push(node);
+        self.key_to_index.insert(key, handle);
+        handle
+    }
+
+    fn add_edge(&mut self, src: NodeHandle, dst: NodeHandle) {
+        self.edges.insert(Edge { src, dst, cached: false });
+    }
+
+    fn add_cached_edge(&mut self, src: NodeHandle, dst: NodeHandle) {
+        // There's no point in rendering both cached and uncached edge
+        let uncached = Edge { src, dst, cached: false };
+        if !self.edges.contains(&uncached) {
+            self.edges.insert(Edge { src, dst, cached: true });
+        }
+    }
+
+    fn get_handle_by_key(&self, key: &str) -> Option<NodeHandle> {
+        self.key_to_index.get(key).copied()
+    }
+
+    fn render(&self, path: &str) -> std::io::Result<()> {
+        use std::io::Write;
+
+        let mut file = BufWriter::new(std::fs::File::create(path)?);
+        writeln!(file, "digraph bootstrap_steps {{")?;
+        for (index, node) in self.nodes.iter().enumerate() {
+            writeln!(
+                file,
+                r#"{index} [label="{}", tooltip="{}"]"#,
+                escape(&node.label),
+                escape(&node.tooltip)
+            )?;
+        }
+
+        let mut edges: Vec<&Edge> = self.edges.iter().collect();
+        edges.sort();
+        for edge in edges {
+            let style = if edge.cached { "dashed" } else { "solid" };
+            writeln!(file, r#"{} -> {} [style="{style}"]"#, edge.src.0, edge.dst.0)?;
+        }
+
+        writeln!(file, "}}")
+    }
+}
+
+fn render_step(step: &dyn Debug) -> String {
+    format!("{step:?}")
+}
+
+/// Normalizes the string so that it can be rendered into a DOT file.
+fn escape(input: &str) -> String {
+    input.replace("\"", "\\\"")
+}