Repository: microsoft/qsharp
Pull request #1498 (2024-05-09 00:43:55)

Support closures in RCA
This change adds full support for analysis of closures for runtime capabilities and calls when the callee expression is known to resolve to a bound closure. This allows analysis to include captured variables as well.

github-actions[bot]: ## Benchmark for 6906242
  <details>
    <summary>Click to view benchmark</summary>

| Test | Base         | PR               | % |
|------|--------------|------------------|---|
| Array append evaluation | 345.0±5.22µs | **341.2±2.14µs** | **-1.10%** |
| Array literal evaluation | 195.1±9.10µs | **170.8±2.32µs** | **-12.46%** |
| Array update evaluation | 429.3±2.94µs | 427.1±2.60µs | -0.51% |
| Core + Standard library compilation | 17.6±0.59ms | 17.4±0.50ms | -1.14% |
| Deutsch-Jozsa evaluation | 5.2±0.05ms | **5.0±0.04ms** | **-3.85%** |
| Large file parity evaluation | 33.8±0.62ms | 33.8±0.62ms | 0.00% |
| Large input file compilation | 12.4±0.45ms | **11.7±0.21ms** | **-5.65%** |
| Large input file compilation (interpreter) | 47.8±1.33ms | 47.1±1.22ms | -1.46% |
| Large nested iteration | 33.9±0.54ms | **33.3±0.25ms** | **-1.77%** |
| Perform Runtime Capabilities Analysis (RCA) on Deutsch-Jozsa sample | 1556.6±78.49µs | 1553.0±51.68µs | -0.23% |
| Perform Runtime Capabilities Analysis (RCA) on large file sample | 7.8±0.13ms | 7.8±0.13ms | 0.00% |
| Perform Runtime Capabilities Analysis (RCA) on teleport sample | 1419.0±60.79µs | 1433.2±86.96µs | +1.00% |
| Perform Runtime Capabilities Analysis (RCA) on the core and std libraries | 27.9±0.27ms | 27.7±0.27ms | -0.72% |
| Teleport evaluation | 89.9±4.03µs | 87.6±3.60µs | -2.56% |

  </details>
  

Patch:
diff --git a/cgmanifest.json b/cgmanifest.json
new file mode 100644
index 00000000..b5503b6b
--- /dev/null
+++ b/cgmanifest.json
@@ -0,0 +1,17 @@
+{
+  "$schema": "https://json.schemastore.org/component-detection-manifest.json",
+  "version": 1,
+  "registrations": [
+    {
+      "component": {
+        "type": "git",
+        "git": {
+          "repositoryUrl": "https://github.com/microsoft/mimalloc",
+          "commitHash": "43ce4bd7fd34bcc730c1c7471c99995597415488",
+          "tag": "v2.1.2"
+        }
+      },
+      "developmentDependency": false
+    }
+  ]
+}
diff --git a/compiler/qsc_partial_eval/src/lib.rs b/compiler/qsc_partial_eval/src/lib.rs
index b9e39cf2..686dde7f 100644
--- a/compiler/qsc_partial_eval/src/lib.rs
+++ b/compiler/qsc_partial_eval/src/lib.rs
@@ -76,7 +76,7 @@ pub enum Error {
     ))]
     UnexpectedDynamicValue(#[label] Span),
 
-    #[error("partial evaluation failed with error {0}")]
+    #[error("partial evaluation failed with error: {0}")]
     #[diagnostic(code("Qsc.PartialEval.EvaluationFailed"))]
     EvaluationFailed(String, #[label] Span),
 
@@ -90,7 +90,7 @@ pub enum Error {
     #[error("an unexpected error occurred related to: {0}")]
     #[diagnostic(code("Qsc.PartialEval.Unexpected"))]
     #[diagnostic(help(
-        "this is probably a bug. please consider reporting this as an issue to the development team"
+        "this is probably a bug, please consider reporting this as an issue to the development team"
     ))]
     Unexpected(String, #[label] Span),
 
@@ -1099,7 +1099,12 @@ impl<'a> PartialEvaluator<'a> {
                     callee_expr_span,
                 ))
             }
-            _ => Ok(self.eval_expr_call_to_intrinsic_qis(store_item_id, callable_decl, args_value)),
+            _ => self.eval_expr_call_to_intrinsic_qis(
+                store_item_id,
+                callable_decl,
+                args_value,
+                callee_expr_span,
+            ),
         }
     }
 
@@ -1108,9 +1113,18 @@ impl<'a> PartialEvaluator<'a> {
         store_item_id: StoreItemId,
         callable_decl: &CallableDecl,
         args_value: Value,
-    ) -> Value {
+        callee_expr_span: Span,
+    ) -> Result<Value, Error> {
         // Intrinsic callables that make it to this point are expected to be unitary.
-        assert_eq!(callable_decl.output, Ty::UNIT);
+        if callable_decl.output != Ty::UNIT {
+            return Err(Error::Unexpected(
+                format!(
+                    "non-classical call to non-Unit intrinsic `{}`",
+                    callable_decl.name.name
+                ),
+                callee_expr_span,
+            ));
+        }
 
         // Check if the callable is already in the program, and if not add it.
         let callable = self.create_intrinsic_callable(store_item_id, callable_decl);
@@ -1135,7 +1149,7 @@ impl<'a> PartialEvaluator<'a> {
         let instruction = Instruction::Call(callable_id, args_operands, None);
         let current_block = self.get_current_rir_block_mut();
         current_block.0.push(instruction);
-        Value::unit()
+        Ok(Value::unit())
     }
 
     fn eval_expr_call_to_spec(
diff --git a/compiler/qsc_rca/src/common.rs b/compiler/qsc_rca/src/common.rs
index 47187128..e4cc6b9e 100644
--- a/compiler/qsc_rca/src/common.rs
+++ b/compiler/qsc_rca/src/common.rs
@@ -155,7 +155,7 @@ pub fn try_resolve_callee(
     package_id: PackageId,
     package: &impl PackageLookup,
     locals_map: &impl LocalsLookup,
-) -> Option<Callee> {
+) -> (Option<Callee>, Option<Vec<LocalVarId>>) {
     // This is a best effort attempt to resolve a callee that currently only supports resolving
     // global callables or locals that eventually resolve to global callables.
     let expr = package.get_expr(expr_id);
@@ -164,14 +164,21 @@ pub fn try_resolve_callee(
             try_resolve_un_op_callee(*operator, *operand_expr_id, package_id, package, locals_map)
         }
         ExprKind::Var(res, _) => match res {
-            Res::Item(item_id) => Some(resolve_item_callee(package_id, *item_id)),
+            Res::Item(item_id) => (Some(resolve_item_callee(package_id, *item_id)), None),
             Res::Local(local_var_id) => {
                 try_resolve_local_callee(*local_var_id, package_id, package, locals_map)
             }
             Res::Err => panic!("callee resolution should not be an error"),
         },
+        ExprKind::Closure(fixed_args, local_item_id) => (
+            Some(Callee {
+                item: (package_id, *local_item_id).into(),
+                functor_app: FunctorApp::default(),
+            }),
+            Some(fixed_args.clone()),
+        ),
         // More complex callee expressions might require evaluation so we don't try to resolve them at compile time.
-        _ => None,
+        _ => (None, None),
     }
 }
 
@@ -188,16 +195,17 @@ fn try_resolve_local_callee(
     package_id: PackageId,
     package: &impl PackageLookup,
     locals_map: &impl LocalsLookup,
-) -> Option<Callee> {
+) -> (Option<Callee>, Option<Vec<LocalVarId>>) {
     // This is a best effort attempt to resolve a callee.
-    locals_map
-        .find(local_var_id)
-        .and_then(|local| match local.kind {
+    match locals_map.find(local_var_id) {
+        Some(local) => match local.kind {
             LocalKind::Immutable(expr_id) => {
                 try_resolve_callee(expr_id, package_id, package, locals_map)
             }
-            _ => None,
-        })
+            _ => (None, None),
+        },
+        None => (None, None),
+    }
 }
 
 fn try_resolve_un_op_callee(
@@ -206,28 +214,32 @@ fn try_resolve_un_op_callee(
     package_id: PackageId,
     package: &impl PackageLookup,
     locals_map: &impl LocalsLookup,
-) -> Option<Callee> {
+) -> (Option<Callee>, Option<Vec<LocalVarId>>) {
     // This is a best effort attempt to resolve a callee.
     let UnOp::Functor(functor_operator) = operator else {
         panic!("unary operator is expected to be a functor for a callee expression")
     };
 
-    try_resolve_callee(expr_id, package_id, package, locals_map).map(|callee| {
-        let spec_functor = match functor_operator {
-            Functor::Adj => FunctorApp {
-                adjoint: !callee.functor_app.adjoint,
-                controlled: callee.functor_app.controlled,
-            },
-            Functor::Ctl => FunctorApp {
-                adjoint: callee.functor_app.adjoint,
-                controlled: callee.functor_app.controlled + 1,
-            },
-        };
-        Callee {
-            item: callee.item,
-            functor_app: spec_functor,
-        }
-    })
+    let (callee, fixed_args) = try_resolve_callee(expr_id, package_id, package, locals_map);
+    (
+        callee.map(|callee| {
+            let spec_functor = match functor_operator {
+                Functor::Adj => FunctorApp {
+                    adjoint: !callee.functor_app.adjoint,
+                    controlled: callee.functor_app.controlled,
+                },
+                Functor::Ctl => FunctorApp {
+                    adjoint: callee.functor_app.adjoint,
+                    controlled: callee.functor_app.controlled + 1,
+                },
+            };
+            Callee {
+                item: callee.item,
+                functor_app: spec_functor,
+            }
+        }),
+        fixed_args,
+    )
 }
 
 pub struct AssignmentStmtCounter<'a> {
diff --git a/compiler/qsc_rca/src/core.rs b/compiler/qsc_rca/src/core.rs
index 0b6c43f2..ad68ad18 100644
--- a/compiler/qsc_rca/src/core.rs
+++ b/compiler/qsc_rca/src/core.rs
@@ -16,9 +16,9 @@ use qsc_fir::{
     extensions::InputParam,
     fir::{
         Block, BlockId, CallableDecl, CallableImpl, CallableKind, Expr, ExprId, ExprKind, Global,
-        Ident, Item, ItemKind, Mutability, Package, PackageId, PackageLookup, PackageStore,
-        PackageStoreLookup, Pat, PatId, PatKind, Res, SpecDecl, SpecImpl, Stmt, StmtId, StmtKind,
-        StoreExprId, StoreItemId, StorePatId, StringComponent,
+        Ident, Item, ItemKind, LocalVarId, Mutability, Package, PackageId, PackageLookup,
+        PackageStore, PackageStoreLookup, Pat, PatId, PatKind, Res, SpecDecl, SpecImpl, Stmt,
+        StmtId, StmtKind, StoreExprId, StoreItemId, StorePatId, StringComponent,
     },
     ty::{Arrow, FunctorSetValue, Prim, Ty},
     visit::Visitor,
@@ -376,6 +376,7 @@ impl<'a> Analyzer<'a> {
         callable_decl: &'a CallableDecl,
         args_expr_id: ExprId,
         expr_type: &Ty,
+        fixed_args: Option<Vec<LocalVarId>>,
     ) -> CallComputeKind {
         // The `Length` intrinsic function has a specialized override.
         if is_length_intrinsic(callable_decl) {
@@ -405,11 +406,30 @@ impl<'a> Analyzer<'a> {
             callee_input_pattern_id,
             args_input_id,
             self.package_store,
+            fixed_args.as_ref().map_or(0, Vec::len),
         );
         let application_instance = self.get_current_application_instance();
 
         // Derive the compute kind based on the value kind of the arguments.
-        let arg_value_kinds = self.derive_arg_value_kinds(&arg_exprs);
+        let arg_value_kinds = if let Some(fixed_args) = fixed_args {
+            // In items that come from lifted lambdas, fixed arguments that capture local variables, if any, come before
+            // other arguments, so we use the `fixed_args` as the base of the chain of values and concatenate the rest of
+            // the arguments when building the full list of arguments for a callable application.
+            fixed_args
+                .into_iter()
+                .map(|local_var_id| {
+                    self.get_current_application_instance()
+                        .locals_map
+                        .find_local_compute_kind(local_var_id)
+                        .expect("local should have been processed before this")
+                        .compute_kind
+                        .value_kind_or_default(ValueKind::Element(RuntimeKind::Static))
+                })
+                .chain(self.derive_arg_value_kinds(&arg_exprs))
+                .collect()
+        } else {
+            self.derive_arg_value_kinds(&arg_exprs)
+        };
         let mut compute_kind =
             application_generator_set.generate_application_compute_kind(&arg_value_kinds);
 
@@ -482,7 +502,7 @@ impl<'a> Analyzer<'a> {
         );
 
         // If the callee could not be resolved, return a compute kind with certain runtime features.
-        let Some(callee) = maybe_callee else {
+        let (Some(callee), fixed_args) = maybe_callee else {
             // The value kind of a call expression with an unresolved callee is not known, so to avoid
             // spurious errors in later analysis where the value is used we assume static.
             // During partial-evaluation, the callable is known the actual return kind will be checked.
@@ -505,6 +525,7 @@ impl<'a> Analyzer<'a> {
                 callable_decl,
                 args_expr_id,
                 expr_type,
+                fixed_args,
             ),
             Global::Udt => {
                 CallComputeKind::Regular(self.analyze_expr_call_with_udt_callee(args_expr_id))
@@ -532,11 +553,6 @@ impl<'a> Analyzer<'a> {
         compute_kind
     }
 
-    fn analyze_expr_closure(expr_type: &Ty) -> ComputeKind {
-        let value_kind = ValueKind::new_dynamic_from_type(expr_type);
-        ComputeKind::new_with_runtime_features(RuntimeFeatureFlags::UseOfClosure, value_kind)
-    }
-
     fn analyze_expr_fail(&mut self, msg_expr_id: ExprId) -> ComputeKind {
         // Visit the message expression to determine its compute kind.
         self.visit_expr(msg_expr_id);
@@ -1627,7 +1643,7 @@ impl<'a> Visitor<'a> for Analyzer<'a> {
             ExprKind::Call(callee_expr_id, args_expr_id) => {
                 self.analyze_expr_call(*callee_expr_id, *args_expr_id, &expr.ty)
             }
-            ExprKind::Closure(_, _) => Self::analyze_expr_closure(&expr.ty),
+            ExprKind::Closure(..) => ComputeKind::Classical,
             ExprKind::Fail(msg_expr_id) => self.analyze_expr_fail(*msg_expr_id),
             ExprKind::Field(record_expr_id, _) => {
                 self.analyze_expr_field(*record_expr_id, &expr.ty)
@@ -2279,29 +2295,32 @@ fn map_input_pattern_to_input_expressions(
     pat_id: StorePatId,
     expr_id: StoreExprId,
     package_store: &impl PackageStoreLookup,
+    skip_ahead: usize,
 ) -> Vec<ExprId> {
     let pat = package_store.get_pat(pat_id);
     match &pat.kind {
         PatKind::Bind(_) | PatKind::Discard => vec![expr_id.expr],
         PatKind::Tuple(pats) => {
+            let pats = &pats[skip_ahead..];
             let expr = package_store.get_expr(expr_id);
-            match &expr.kind {
-                ExprKind::Tuple(exprs) => {
-                    assert!(pats.len() == exprs.len());
-                    let mut input_param_exprs = Vec::<ExprId>::with_capacity(pats.len());
-                    for (local_pat_id, local_expr_id) in pats.iter().zip(exprs.iter()) {
-                        let global_pat_id = StorePatId::from((pat_id.package, *local_pat_id));
-                        let global_expr_id = StoreExprId::from((expr_id.package, *local_expr_id));
-                        let mut sub_input_param_exprs = map_input_pattern_to_input_expressions(
-                            global_pat_id,
-                            global_expr_id,
-                            package_store,
-                        );
-                        input_param_exprs.append(&mut sub_input_param_exprs);
-                    }
-                    input_param_exprs
+            if let ExprKind::Tuple(exprs) = &expr.kind {
+                assert!(pats.len() == exprs.len());
+                let mut input_param_exprs = Vec::<ExprId>::with_capacity(pats.len());
+                for (local_pat_id, local_expr_id) in pats.iter().zip(exprs.iter()) {
+                    let global_pat_id = StorePatId::from((pat_id.package, *local_pat_id));
+                    let global_expr_id = StoreExprId::from((expr_id.package, *local_expr_id));
+                    let mut sub_input_param_exprs = map_input_pattern_to_input_expressions(
+                        global_pat_id,
+                        global_expr_id,
+                        package_store,
+                        0,
+                    );
+                    input_param_exprs.append(&mut sub_input_param_exprs);
                 }
-                _ => panic!("expected tuple expression"),
+                input_param_exprs
+            } else {
+                assert!(pats.len() == 1);
+                vec![expr_id.expr]
             }
         }
     }
diff --git a/compiler/qsc_rca/src/cycle_detection.rs b/compiler/qsc_rca/src/cycle_detection.rs
index e29a4c61..c137b246 100644
--- a/compiler/qsc_rca/src/cycle_detection.rs
+++ b/compiler/qsc_rca/src/cycle_detection.rs
@@ -109,7 +109,8 @@ impl<'a> CycleDetector<'a> {
             .specializations_locals
             .get_mut(local_spec_id)
             .expect("node map should exist");
-        let maybe_callee = try_resolve_callee(callee, self.package_id, self.package, locals_map);
+        let (maybe_callee, _) =
+            try_resolve_callee(callee, self.package_id, self.package, locals_map);
         if let Some(callee) = maybe_callee {
             // We are not interested in visiting callables outside this package.
             if callee.item.package != self.package_id {
diff --git a/compiler/qsc_rca/src/errors.rs b/compiler/qsc_rca/src/errors.rs
index 45408cde..efef75ee 100644
--- a/compiler/qsc_rca/src/errors.rs
+++ b/compiler/qsc_rca/src/errors.rs
@@ -135,11 +135,6 @@ pub enum Error {
     #[diagnostic(code("Qsc.CapabilitiesCk.LoopWithDynamicCondition"))]
     LoopWithDynamicCondition(#[label] Span),
 
-    #[error("cannot use a closure")]
-    #[diagnostic(help("closures are not supported by the current target"))]
-    #[diagnostic(code("Qsc.CapabilitiesCk.UseOfClosure"))]
-    UseOfClosure(#[label] Span),
-
     #[error("cannot use a bool value as an output")]
     #[diagnostic(help("using a bool value as an output is not supported by the current target"))]
     #[diagnostic(code("Qsc.CapabilitiesCk.UseOfBoolOutput"))]
@@ -232,9 +227,6 @@ pub fn generate_errors_from_runtime_features(
     if runtime_features.contains(RuntimeFeatureFlags::LoopWithDynamicCondition) {
         errors.push(Error::LoopWithDynamicCondition(span));
     }
-    if runtime_features.contains(RuntimeFeatureFlags::UseOfClosure) {
-        errors.push(Error::UseOfClosure(span));
-    }
     if runtime_features.contains(RuntimeFeatureFlags::UseOfBoolOutput) {
         errors.push(Error::UseOfBoolOutput(span));
     }
diff --git a/compiler/qsc_rca/src/lib.rs b/compiler/qsc_rca/src/lib.rs
index 559ddb82..fe13f932 100644
--- a/compiler/qsc_rca/src/lib.rs
+++ b/compiler/qsc_rca/src/lib.rs
@@ -756,16 +756,14 @@ bitflags! {
         const ReturnWithinDynamicScope = 1 << 19;
         /// A loop with a dynamic condition.
         const LoopWithDynamicCondition = 1 << 20;
-        /// Use of a closure.
-        const UseOfClosure = 1 << 21;
         /// Use of an advanced type as output of a computation.
-        const UseOfAdvancedOutput = 1 << 22;
+        const UseOfAdvancedOutput = 1 << 21;
         // Use of a `Bool` as output of a computation.
-        const UseOfBoolOutput = 1 << 23;
+        const UseOfBoolOutput = 1 << 22;
         // Use of a `Double` as output of a computation.
-        const UseOfDoubleOutput = 1 << 24;
+        const UseOfDoubleOutput = 1 << 23;
         // Use of an `Int` as output of a computation.
-        const UseOfIntOutput = 1 << 25;
+        const UseOfIntOutput = 1 << 24;
     }
 }
 
@@ -850,9 +848,6 @@ impl RuntimeFeatureFlags {
         if self.contains(RuntimeFeatureFlags::LoopWithDynamicCondition) {
             capabilities |= TargetCapabilityFlags::BackwardsBranching;
         }
-        if self.contains(RuntimeFeatureFlags::UseOfClosure) {
-            capabilities |= TargetCapabilityFlags::HigherLevelConstructs;
-        }
         if self.contains(RuntimeFeatureFlags::UseOfBoolOutput) {
             capabilities |= TargetCapabilityFlags::Adaptive;
         }
diff --git a/compiler/qsc_rir/src/passes/reindex_qubits.rs b/compiler/qsc_rir/src/passes/reindex_qubits.rs
index 1f44f1b1..649048e1 100644
--- a/compiler/qsc_rir/src/passes/reindex_qubits.rs
+++ b/compiler/qsc_rir/src/passes/reindex_qubits.rs
@@ -4,7 +4,7 @@
 #[cfg(test)]
 mod tests;
 
-use std::collections::hash_map::Entry;
+use std::{collections::hash_map::Entry, ops::Sub};
 
 use qsc_data_structures::index_map::IndexMap;
 use rustc_hash::FxHashMap;
@@ -47,7 +47,11 @@ pub fn reindex_qubits(program: &mut Program) {
         used_cx,
         cx_id,
         mresetz_id,
-        highest_used_id: program.num_qubits - 1,
+        // For this calculation, qubit IDs can never be lower than zero but a program may not use
+        // any qubits. Since `highest_used_id` is only needed for remapping pass and a program without any
+        // qubits won't do any remapping, it's safe to treat this as 1 and let `highest_used_id` default
+        // to zero.
+        highest_used_id: program.num_qubits.max(1).sub(1),
     };
 
     let pred_map = build_predecessors_map(program);
diff --git a/compiler/qsc_rir/src/passes/ssa_transform.rs b/compiler/qsc_rir/src/passes/ssa_transform.rs
index 0239459b..d11a0cbe 100644
--- a/compiler/qsc_rir/src/passes/ssa_transform.rs
+++ b/compiler/qsc_rir/src/passes/ssa_transform.rs
@@ -17,12 +17,6 @@ pub fn transform_to_ssa(program: &mut Program, preds: &IndexMap<BlockId, Vec<Blo
     // Ensure that the graph is acyclic before proceeding. Current approach does not support cycles.
     ensure_acyclic(preds);
 
-    // First, remove store instructions and propagate variables through individual blocks.
-    // This produces a per-block map of dynamic variables to their values.
-    // Orphan variables may be left behind where a variable is defined in one block and used in another, which
-    // will be resolved by inserting phi nodes.
-    let mut block_var_map = map_store_to_dominated_ssa(program, preds);
-
     // Get the next available variable ID for use in newly generated phi nodes.
     let mut next_var_id = get_variable_assignments(program)
         .iter()
@@ -30,6 +24,12 @@ pub fn transform_to_ssa(program: &mut Program, preds: &IndexMap<BlockId, Vec<Blo
         .map(|(var_id, _)| var_id.successor())
         .unwrap_or_default();
 
+    // First, remove store instructions and propagate variables through individual blocks.
+    // This produces a per-block map of dynamic variables to their values.
+    // Orphan variables may be left behind where a variable is defined in one block and used in another, which
+    // will be resolved by inserting phi nodes.
+    let mut block_var_map = map_store_to_dominated_ssa(program, preds);
+
     // Insert phi nodes where necessary, mapping any remaining orphaned uses to the new variable
     // created by the phi node.
     // This can be done in one pass because the graph is assumed to be acyclic.
@@ -160,14 +160,14 @@ fn map_store_to_dominated_ssa(
 
 // Propagates stored variables through a block, tracking the latest stored value and replacing
 // usage of the variable with the stored value.
-fn map_variable_use_in_block(block: &mut Block, var_map: &mut impl VariableMapper) {
+fn map_variable_use_in_block(block: &mut Block, var_map: &mut FxHashMap<VariableId, Operand>) {
     let instrs = block.0.drain(..).collect::<Vec<_>>();
 
     for mut instr in instrs {
         match &mut instr {
             // Track the new value of the variable and omit the store instruction.
             Instruction::Store(operand, var) => {
-                var_map.insert(*var, *operand);
+                var_map.insert(var.variable_id, *operand);
                 continue;
             }
 
@@ -176,7 +176,7 @@ fn map_variable_use_in_block(block: &mut Block, var_map: &mut impl VariableMappe
                 *args = args
                     .iter()
                     .map(|arg| match arg {
-                        Operand::Variable(var) => var_map.to_operand(*var),
+                        Operand::Variable(var) => var.map_to_operand(var_map),
                         Operand::Literal(_) => *arg,
                     })
                     .collect();
@@ -184,7 +184,7 @@ fn map_variable_use_in_block(block: &mut Block, var_map: &mut impl VariableMappe
 
             // Replace the branch condition with the new value of the variable.
             Instruction::Branch(var, _, _) => {
-                *var = var_map.to_variable(*var);
+                *var = var.map_to_variable(var_map);
             }
 
             // Two variable instructions, replace left and right operands with new values.
@@ -219,37 +219,35 @@ fn map_variable_use_in_block(block: &mut Block, var_map: &mut impl VariableMappe
 }
 
 impl Operand {
-    fn mapped(&self, var_map: &impl VariableMapper) -> Operand {
+    fn mapped(&self, var_map: &FxHashMap<VariableId, Operand>) -> Operand {
         match self {
             Operand::Literal(_) => *self,
-            Operand::Variable(var) => var_map.to_operand(*var),
+            Operand::Variable(var) => var.map_to_operand(var_map),
         }
     }
 }
 
-trait VariableMapper {
-    fn insert(&mut self, var: Variable, operand: Operand);
-    fn to_operand(&self, var: Variable) -> Operand;
-    fn to_variable(&self, var: Variable) -> Variable;
-}
-
-impl VariableMapper for FxHashMap<VariableId, Operand> {
-    fn insert(&mut self, var: Variable, operand: Operand) {
-        self.insert(var.variable_id, operand);
-    }
-
-    fn to_operand(&self, var: Variable) -> Operand {
-        self.get(&var.variable_id)
-            .copied()
-            .unwrap_or(Operand::Variable(var))
+impl Variable {
+    fn map_to_operand(self, var_map: &FxHashMap<VariableId, Operand>) -> Operand {
+        let mut var = self;
+        while let Some(operand) = var_map.get(&var.variable_id) {
+            if let Operand::Variable(new_var) = operand {
+                var = *new_var;
+            } else {
+                return *operand;
+            }
+        }
+        Operand::Variable(var)
     }
 
-    fn to_variable(&self, var: Variable) -> Variable {
-        self.get(&var.variable_id)
-            .copied()
-            .map_or(var, |operand| match operand {
-                Operand::Literal(_) => panic!("literal not supported in this context"),
-                Operand::Variable(var) => var,
-            })
+    fn map_to_variable(self, var_map: &FxHashMap<VariableId, Operand>) -> Variable {
+        let mut var = self;
+        while let Some(operand) = var_map.get(&var.variable_id) {
+            let Operand::Variable(new_var) = operand else {
+                panic!("literal not supported in this context");
+            };
+            var = *new_var;
+        }
+        var
     }
 }
diff --git a/compiler/qsc_rir/src/passes/type_check.rs b/compiler/qsc_rir/src/passes/type_check.rs
index 757657ff..35a9c2af 100644
--- a/compiler/qsc_rir/src/passes/type_check.rs
+++ b/compiler/qsc_rir/src/passes/type_check.rs
@@ -31,12 +31,16 @@ fn check_instr_types(program: &Program, instr: &Instruction) {
         | Instruction::LogicalOr(opr1, opr2, var)
         | Instruction::BitwiseAnd(opr1, opr2, var)
         | Instruction::BitwiseOr(opr1, opr2, var)
-        | Instruction::BitwiseXor(opr1, opr2, var)
-        | Instruction::Icmp(_, opr1, opr2, var) => {
+        | Instruction::BitwiseXor(opr1, opr2, var) => {
             assert_eq!(opr1.get_type(), opr2.get_type());
             assert_eq!(opr1.get_type(), var.ty);
         }
 
+        Instruction::Icmp(_, opr1, opr2, var) => {
+            assert_eq!(opr1.get_type(), opr2.get_type());
+            assert_eq!(Ty::Boolean, var.ty);
+        }
+
         Instruction::Store(opr, var)
         | Instruction::LogicalNot(opr, var)
         | Instruction::BitwiseNot(opr, var) => {
diff --git a/compiler/qsc_rir/src/rir.rs b/compiler/qsc_rir/src/rir.rs
index e283e73d..7e0dbb63 100644
--- a/compiler/qsc_rir/src/rir.rs
+++ b/compiler/qsc_rir/src/rir.rs
@@ -6,7 +6,7 @@ use qsc_data_structures::{index_map::IndexMap, target::TargetCapabilityFlags};
 use std::fmt::{self, Display, Formatter, Write};
 
 /// The root of the RIR.
-#[derive(Default)]
+#[derive(Default, Clone)]
 pub struct Program {
     pub entry: CallableId,
     pub callables: IndexMap<CallableId, Callable>,
@@ -63,7 +63,7 @@ impl Program {
     }
 }
 
-#[derive(Default)]
+#[derive(Default, Clone, Copy)]
 pub struct Config {
     pub capabilities: TargetCapabilityFlags,
 }
@@ -129,7 +129,7 @@ impl BlockId {
 }
 
 /// A block is a collection of instructions.
-#[derive(Default)]
+#[derive(Default, Clone)]
 pub struct Block(pub Vec<Instruction>);
 
 /// A unique identifier for a callable in a RIR program.
@@ -156,7 +156,7 @@ impl CallableId {
 }
 
 /// A callable.
-#[derive(Debug, Eq, PartialEq)]
+#[derive(Debug, Clone, Eq, PartialEq)]
 pub struct Callable {
     /// The name of the callable.
     pub name: String,
diff --git a/compiler/qsc_rir/src/utils.rs b/compiler/qsc_rir/src/utils.rs
index a6f3c948..f38f2d43 100644
--- a/compiler/qsc_rir/src/utils.rs
+++ b/compiler/qsc_rir/src/utils.rs
@@ -72,6 +72,8 @@ pub fn build_predecessors_map(program: &Program) -> IndexMap<BlockId, Vec<BlockI
 #[must_use]
 pub fn get_variable_assignments(program: &Program) -> IndexMap<VariableId, (BlockId, usize)> {
     let mut assignments = IndexMap::default();
+    let mut has_store = false;
+    let mut has_phi = false;
     for (block_id, block) in program.blocks.iter() {
         for (idx, instr) in block.0.iter().enumerate() {
             match instr {
@@ -97,18 +99,24 @@ pub fn get_variable_assignments(program: &Program) -> IndexMap<VariableId, (Bloc
                         "Duplicate assignment to {:?} in {block_id:?}, instruction {idx}",
                         var.variable_id
                     );
+                    has_phi |= matches!(instr, Instruction::Phi(_, _));
                     assignments.insert(var.variable_id, (block_id, idx));
                 }
+                Instruction::Store(_, var) => {
+                    has_store = true;
+                    assignments.insert(var.variable_id, (block_id, idx));
+                }
+
                 Instruction::Call(_, _, None)
                 | Instruction::Jump(..)
                 | Instruction::Branch(..)
                 | Instruction::Return => {}
-
-                Instruction::Store(..) => {
-                    panic!("Unexpected Store at {block_id:?}, instruction {idx}")
-                }
             }
         }
     }
+    assert!(
+        !(has_store && has_phi),
+        "Program has both store and phi instructions."
+    );
     assignments
 }


Test patch:
diff --git a/compiler/qsc/src/codegen/tests.rs b/compiler/qsc/src/codegen/tests.rs
index df3598f7..f1d021a9 100644
--- a/compiler/qsc/src/codegen/tests.rs
+++ b/compiler/qsc/src/codegen/tests.rs
@@ -625,8 +625,8 @@ mod adaptive_ri_profile {
             block_2:
               br label %block_3
             block_3:
-              %var_2 = phi i64 [0, %block_1], [1, %block_2]
-              call void @__quantum__rt__integer_record_output(i64 %var_2, i8* null)
+              %var_3 = phi i64 [0, %block_1], [1, %block_2]
+              call void @__quantum__rt__integer_record_output(i64 %var_3, i8* null)
               ret void
             }
 
diff --git a/compiler/qsc_partial_eval/tests/calls.rs b/compiler/qsc_partial_eval/tests/calls.rs
index 24e49479..c14c9598 100644
--- a/compiler/qsc_partial_eval/tests/calls.rs
+++ b/compiler/qsc_partial_eval/tests/calls.rs
@@ -1288,3 +1288,29 @@ fn call_to_unresolved_callee_producing_dynamic_value_fails() {
         &expect!["UnexpectedDynamicValue(Span { lo: 298, hi: 305 })"],
     );
 }
+
+#[test]
+fn call_to_unresolved_callee_via_closure_with_dynamic_arg_fails() {
+    let error = get_partial_evaluation_error_with_capabilities(
+        indoc! {"
+        namespace Test {
+            open Microsoft.Quantum.Convert;
+            operation Op() : (Int, Qubit) => Unit {
+                (i, q) => Rx(IntAsDouble(i), q)
+            }
+            @EntryPoint()
+            operation Main() : Unit {
+                use q = Qubit();
+                let i = if MResetZ(q) == One { 1 } else { 0 };
+                let f = Op();
+                f(i, q);
+            }
+        }"},
+        TargetCapabilityFlags::Adaptive | TargetCapabilityFlags::IntegerComputations,
+    );
+
+    assert_error(
+        &error,
+        &expect!["CapabilityError(UseOfDynamicDouble(Span { lo: 302, hi: 309 }))"],
+    );
+}
diff --git a/compiler/qsc_partial_eval/tests/test_utils.rs b/compiler/qsc_partial_eval/tests/test_utils.rs
index 0a588be4..de75525e 100644
--- a/compiler/qsc_partial_eval/tests/test_utils.rs
+++ b/compiler/qsc_partial_eval/tests/test_utils.rs
@@ -9,7 +9,10 @@ use qsc_frontend::compile::{PackageStore as HirPackageStore, SourceMap};
 use qsc_lowerer::{map_hir_package_to_fir, Lowerer};
 use qsc_partial_eval::{partially_evaluate, Error, ProgramEntry};
 use qsc_rca::{Analyzer, PackageStoreComputeProperties};
-use qsc_rir::rir::{BlockId, CallableId, Program};
+use qsc_rir::{
+    passes::check_and_transform,
+    rir::{BlockId, CallableId, Program},
+};
 
 pub fn assert_block_instructions(program: &Program, block_id: BlockId, expected_insts: &Expect) {
     let block = program.get_block(block_id);
@@ -60,7 +63,11 @@ pub fn get_partial_evaluation_error_with_capabilities(
 pub fn get_rir_program(source: &str) -> Program {
     let maybe_program = compile_and_partially_evaluate(source, TargetCapabilityFlags::all());
     match maybe_program {
-        Ok(program) => program,
+        Ok(program) => {
+            // Verify the program can go through transformations.
+            check_and_transform(&mut program.clone());
+            program
+        }
         Err(error) => panic!("partial evaluation failed: {error:?}"),
     }
 }
diff --git a/compiler/qsc_passes/src/capabilitiesck/tests_adaptive.rs b/compiler/qsc_passes/src/capabilitiesck/tests_adaptive.rs
index f4f6c97f..d8cd5395 100644
--- a/compiler/qsc_passes/src/capabilitiesck/tests_adaptive.rs
+++ b/compiler/qsc_passes/src/capabilitiesck/tests_adaptive.rs
@@ -534,18 +534,11 @@ fn loop_with_dynamic_condition_yields_errors() {
 }
 
 #[test]
-fn use_closure_yields_errors() {
+fn use_closure_allowed() {
     check_profile(
         USE_CLOSURE_FUNCTION,
         &expect![[r#"
-            [
-                UseOfClosure(
-                    Span {
-                        lo: 149,
-                        hi: 168,
-                    },
-                ),
-            ]
+            []
         "#]],
     );
 }
diff --git a/compiler/qsc_passes/src/capabilitiesck/tests_adaptive_plus_integers.rs b/compiler/qsc_passes/src/capabilitiesck/tests_adaptive_plus_integers.rs
index b36c52d0..22193eaf 100644
--- a/compiler/qsc_passes/src/capabilitiesck/tests_adaptive_plus_integers.rs
+++ b/compiler/qsc_passes/src/capabilitiesck/tests_adaptive_plus_integers.rs
@@ -432,18 +432,11 @@ fn loop_with_dynamic_condition_yields_errors() {
 }
 
 #[test]
-fn use_closure_yields_errors() {
+fn use_closure_allowed() {
     check_profile(
         USE_CLOSURE_FUNCTION,
         &expect![[r#"
-            [
-                UseOfClosure(
-                    Span {
-                        lo: 149,
-                        hi: 168,
-                    },
-                ),
-            ]
+            []
         "#]],
     );
 }
diff --git a/compiler/qsc_passes/src/capabilitiesck/tests_base.rs b/compiler/qsc_passes/src/capabilitiesck/tests_base.rs
index c45700d5..e92e8a2c 100644
--- a/compiler/qsc_passes/src/capabilitiesck/tests_base.rs
+++ b/compiler/qsc_passes/src/capabilitiesck/tests_base.rs
@@ -672,18 +672,11 @@ fn loop_with_dynamic_condition_yields_errors() {
 }
 
 #[test]
-fn use_closure_yields_errors() {
+fn use_closure_allowed() {
     check_profile(
         USE_CLOSURE_FUNCTION,
         &expect![[r#"
-            [
-                UseOfClosure(
-                    Span {
-                        lo: 149,
-                        hi: 168,
-                    },
-                ),
-            ]
+            []
         "#]],
     );
 }
diff --git a/compiler/qsc_rca/tests/callables.rs b/compiler/qsc_rca/tests/callables.rs
index 051b0604..2d090dd6 100644
--- a/compiler/qsc_rca/tests/callables.rs
+++ b/compiler/qsc_rca/tests/callables.rs
@@ -22,18 +22,12 @@ fn check_rca_for_closure_function_with_classical_captured_value() {
     );
     let package_store_compute_properties = compilation_context.get_compute_properties();
 
-    // Note that a closure is always considered dynamic because we are currently not performing detailed analysis on
-    // them.
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
-                inherent: Quantum: QuantumProperties:
-                    runtime_features: RuntimeFeatureFlags(UseOfClosure)
-                    value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                inherent: Classical
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -50,18 +44,12 @@ fn check_rca_for_closure_function_with_dynamic_captured_value() {
     );
     let package_store_compute_properties = compilation_context.get_compute_properties();
 
-    // Note that only the "use of closure" runtime feature appears because we are currently not performing detailed
-    // analysis on closures.
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
-                inherent: Quantum: QuantumProperties:
-                    runtime_features: RuntimeFeatureFlags(UseOfClosure)
-                    value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                inherent: Classical
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -77,18 +65,12 @@ fn check_rca_for_closure_operation_with_classical_captured_value() {
     );
     let package_store_compute_properties = compilation_context.get_compute_properties();
 
-    // Note that a closure is always considered dynamic because we are currently not performing detailed analysis on
-    // them.
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
-                inherent: Quantum: QuantumProperties:
-                    runtime_features: RuntimeFeatureFlags(UseOfClosure)
-                    value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                inherent: Classical
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -105,18 +87,12 @@ fn check_rca_for_closure_operation_with_dynamic_captured_value() {
     );
     let package_store_compute_properties = compilation_context.get_compute_properties();
 
-    // Note that only the "use of closure" runtime feature appears because we are currently not performing detailed
-    // analysis on closures.
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
-                inherent: Quantum: QuantumProperties:
-                    runtime_features: RuntimeFeatureFlags(UseOfClosure)
-                    value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                inherent: Classical
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
diff --git a/compiler/qsc_rca/tests/calls.rs b/compiler/qsc_rca/tests/calls.rs
index bdeacabb..cca38e21 100644
--- a/compiler/qsc_rca/tests/calls.rs
+++ b/compiler/qsc_rca/tests/calls.rs
@@ -25,12 +25,10 @@ fn check_rca_for_call_to_cyclic_function_with_classical_argument() {
     let package_store_compute_properties = compilation_context.get_compute_properties();
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
                 inherent: Classical
-                dynamic_param_applications: <empty>"#
-        ],
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -52,14 +50,12 @@ fn check_rca_for_call_to_cyclic_function_with_dynamic_argument() {
     let package_store_compute_properties = compilation_context.get_compute_properties();
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
                 inherent: Quantum: QuantumProperties:
                     runtime_features: RuntimeFeatureFlags(UseOfDynamicBool | UseOfDynamicInt | CallToCyclicFunctionWithDynamicArg)
                     value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -80,14 +76,12 @@ fn check_rca_for_call_to_cyclic_operation_with_classical_argument() {
     let package_store_compute_properties = compilation_context.get_compute_properties();
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
                 inherent: Quantum: QuantumProperties:
                     runtime_features: RuntimeFeatureFlags(UseOfDynamicInt | CallToCyclicOperation)
                     value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -109,14 +103,12 @@ fn check_rca_for_call_to_cyclic_operation_with_dynamic_argument() {
     let package_store_compute_properties = compilation_context.get_compute_properties();
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
                 inherent: Quantum: QuantumProperties:
                     runtime_features: RuntimeFeatureFlags(UseOfDynamicBool | UseOfDynamicInt | CallToCyclicOperation)
                     value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -131,18 +123,12 @@ fn check_rca_for_call_to_static_closure_function() {
     );
     let package_store_compute_properties = compilation_context.get_compute_properties();
 
-    // Note that the output of the closure function is dynamic due to closures currently considered always dynamic
-    // because we are not performing detailed analysis on them.
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
-                inherent: Quantum: QuantumProperties:
-                    runtime_features: RuntimeFeatureFlags(UseOfDynamicBool | CallToDynamicCallee | UseOfClosure)
-                    value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                inherent: Classical
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -159,18 +145,14 @@ fn check_rca_for_call_to_dynamic_closure_function() {
     );
     let package_store_compute_properties = compilation_context.get_compute_properties();
 
-    // Note that the "use of dynamic integer" runtime feature is missing because we are currently not performing
-    // detailed analysis on closures.
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
                 inherent: Quantum: QuantumProperties:
-                    runtime_features: RuntimeFeatureFlags(UseOfDynamicBool | CallToDynamicCallee | UseOfClosure)
+                    runtime_features: RuntimeFeatureFlags(UseOfDynamicBool | UseOfDynamicInt | LoopWithDynamicCondition)
                     value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -187,17 +169,14 @@ fn check_rca_for_call_to_static_closure_operation() {
     );
     let package_store_compute_properties = compilation_context.get_compute_properties();
 
-    // Note that closures currently considered always dynamic because we are not performing detailed analysis on them.
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
-        ApplicationsGeneratorSet:
-            inherent: Quantum: QuantumProperties:
-                runtime_features: RuntimeFeatureFlags(CallToDynamicCallee | UseOfClosure)
-                value_kind: Element(Static)
-            dynamic_param_applications: <empty>"#
-        ],
+        &expect![[r#"
+            ApplicationsGeneratorSet:
+                inherent: Quantum: QuantumProperties:
+                    runtime_features: RuntimeFeatureFlags(0x0)
+                    value_kind: Element(Static)
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -214,18 +193,14 @@ fn check_rca_for_call_to_dynamic_closure_operation() {
     );
     let package_store_compute_properties = compilation_context.get_compute_properties();
 
-    // Note that the "use of dynamic bool" and the "use of dynamic double" runtime features are missing because we are
-    // currently not performing detailed analysis on closures.
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
-        ApplicationsGeneratorSet:
-            inherent: Quantum: QuantumProperties:
-                runtime_features: RuntimeFeatureFlags(CallToDynamicCallee | UseOfClosure)
-                value_kind: Element(Static)
-            dynamic_param_applications: <empty>"#
-        ],
+        &expect![[r#"
+            ApplicationsGeneratorSet:
+                inherent: Quantum: QuantumProperties:
+                    runtime_features: RuntimeFeatureFlags(UseOfDynamicDouble)
+                    value_kind: Element(Static)
+                dynamic_param_applications: <empty>"#]],
     );
 }
 
@@ -246,13 +221,11 @@ fn check_rca_for_call_to_operation_with_one_classical_return_and_one_dynamic_ret
     let package_store_compute_properties = compilation_context.get_compute_properties();
     check_last_statement_compute_properties(
         package_store_compute_properties,
-        &expect![
-            r#"
+        &expect![[r#"
             ApplicationsGeneratorSet:
                 inherent: Quantum: QuantumProperties:
                     runtime_features: RuntimeFeatureFlags(UseOfDynamicBool | UseOfDynamicInt | ReturnWithinDynamicScope)
                     value_kind: Element(Dynamic)
-                dynamic_param_applications: <empty>"#
-        ],
+                dynamic_param_applications: <empty>"#]],
     );
 }
diff --git a/compiler/qsc_rir/src/passes/ssa_transform/tests.rs b/compiler/qsc_rir/src/passes/ssa_transform/tests.rs
index 8c5c8ae8..9bb6ad8d 100644
--- a/compiler/qsc_rir/src/passes/ssa_transform/tests.rs
+++ b/compiler/qsc_rir/src/passes/ssa_transform/tests.rs
@@ -2221,3 +2221,121 @@ fn ssa_transform_propagates_updates_from_multiple_predecessors_to_later_single_s
             num_qubits: 0
             num_results: 0"#]].assert_eq(&program.to_string());
 }
+
+#[test]
+fn ssa_transform_maps_store_instrs_that_use_values_from_other_store_instrs() {
+    let mut program = new_program();
+    program.callables.insert(
+        CallableId(1),
+        Callable {
+            name: "dynamic_bool".to_string(),
+            input_type: Vec::new(),
+            output_type: Some(Ty::Boolean),
+            body: None,
+            call_type: CallableType::Regular,
+        },
+    );
+
+    program.blocks.insert(
+        BlockId(0),
+        Block(vec![
+            Instruction::Call(
+                CallableId(1),
+                Vec::new(),
+                Some(Variable {
+                    variable_id: VariableId(0),
+                    ty: Ty::Boolean,
+                }),
+            ),
+            Instruction::Store(
+                Operand::Variable(Variable {
+                    variable_id: VariableId(0),
+                    ty: Ty::Boolean,
+                }),
+                Variable {
+                    variable_id: VariableId(1),
+                    ty: Ty::Boolean,
+                },
+            ),
+            Instruction::Store(
+                Operand::Variable(Variable {
+                    variable_id: VariableId(1),
+                    ty: Ty::Boolean,
+                }),
+                Variable {
+                    variable_id: VariableId(2),
+                    ty: Ty::Boolean,
+                },
+            ),
+            Instruction::LogicalNot(
+                Operand::Variable(Variable {
+                    variable_id: VariableId(2),
+                    ty: Ty::Boolean,
+                }),
+                Variable {
+                    variable_id: VariableId(3),
+                    ty: Ty::Boolean,
+                },
+            ),
+            Instruction::Return,
+        ]),
+    );
+
+    // Before
+    expect![[r#"
+        Program:
+            entry: 0
+            callables:
+                Callable 0: Callable:
+                    name: main
+                    call_type: Regular
+                    input_type: <VOID>
+                    output_type: <VOID>
+                    body: 0
+                Callable 1: Callable:
+                    name: dynamic_bool
+                    call_type: Regular
+                    input_type: <VOID>
+                    output_type: Boolean
+                    body: <NONE>
+            blocks:
+                Block 0: Block:
+                    Variable(0, Boolean) = Call id(1), args( )
+                    Variable(1, Boolean) = Store Variable(0, Boolean)
+                    Variable(2, Boolean) = Store Variable(1, Boolean)
+                    Variable(3, Boolean) = LogicalNot Variable(2, Boolean)
+                    Return
+            config: Config:
+                capabilities: Base
+            num_qubits: 0
+            num_results: 0"#]]
+    .assert_eq(&program.to_string());
+
+    // After
+    transform_program(&mut program);
+    expect![[r#"
+        Program:
+            entry: 0
+            callables:
+                Callable 0: Callable:
+                    name: main
+                    call_type: Regular
+                    input_type: <VOID>
+                    output_type: <VOID>
+                    body: 0
+                Callable 1: Callable:
+                    name: dynamic_bool
+                    call_type: Regular
+                    input_type: <VOID>
+                    output_type: Boolean
+                    body: <NONE>
+            blocks:
+                Block 0: Block:
+                    Variable(0, Boolean) = Call id(1), args( )
+                    Variable(3, Boolean) = LogicalNot Variable(0, Boolean)
+                    Return
+            config: Config:
+                capabilities: TargetCapabilityFlags(Adaptive | IntegerComputations | FloatingPointComputations | BackwardsBranching | HigherLevelConstructs | QubitReset)
+            num_qubits: 0
+            num_results: 0"#]].assert_eq(&program.to_string());
+}