Repository: microsoft/qsharp
Pull request #1528 (2024-05-15 06:00:39)

Fix debugger scope handling during early returns
Changes introduced in #1442 to enable debugger tracking of variable scopes caused a bug if a program used callables with early returns, namely those returns would not pop any added scopes and later execution would read/write the wrong variable states. This fixes the issue by introducing a debug-only return node that triggers a frame leave handling in the environment. This needs to be debug only because it should not be used during partial evaluation.

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

| Test | Base         | PR               | % |
|------|--------------|------------------|---|
| Array append evaluation | 344.7±6.37µs | **331.0±10.69µs** | **-3.97%** |
| Array literal evaluation | 200.0±4.28µs | **171.4±2.09µs** | **-14.30%** |
| Array update evaluation | 434.9±2.47µs | **412.6±1.53µs** | **-5.13%** |
| Core + Standard library compilation | 20.5±1.17ms | 20.4±1.30ms | -0.49% |
| Deutsch-Jozsa evaluation | **5.1±0.04ms** | 5.2±0.15ms | **+1.96%** |
| Large file parity evaluation | 33.9±0.12ms | **33.7±0.54ms** | **-0.59%** |
| Large input file compilation | 14.4±0.46ms | **13.7±0.36ms** | **-4.86%** |
| Large input file compilation (interpreter) | 51.1±2.08ms | 51.8±1.81ms | +1.37% |
| Large nested iteration | 33.8±0.17ms | **33.1±0.24ms** | **-2.07%** |
| Perform Runtime Capabilities Analysis (RCA) on Deutsch-Jozsa sample | 1616.9±159.20µs | 1638.8±211.67µs | +1.35% |
| Perform Runtime Capabilities Analysis (RCA) on large file sample | **8.2±0.17ms** | 8.4±0.17ms | **+2.44%** |
| Perform Runtime Capabilities Analysis (RCA) on teleport sample | 1495.7±211.15µs | 1487.0±170.75µs | -0.58% |
| Perform Runtime Capabilities Analysis (RCA) on the core and std libraries | 29.0±0.28ms | 28.9±0.17ms | -0.34% |
| Teleport evaluation | 89.1±5.51µs | 90.1±3.51µs | +1.12% |

  </details>
  

Patch:
diff --git a/Cargo.lock b/Cargo.lock
index 1e192269..a057a2fc 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -160,12 +160,13 @@ checksum = "37b2a672a2cb129a2e41c10b1224bb368f9f37a2b16b612598138befd7b37eb5"
 
 [[package]]
 name = "cc"
-version = "1.0.89"
+version = "1.0.97"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "a0ba8f7aaa012f30d5b2861462f6708eccd49c3c39863fe083a308035f63d723"
+checksum = "099a5357d84c4c61eb35fc8eafa9a79a902c2f76911e5747ced4e032edd8d9b4"
 dependencies = [
  "jobserver",
  "libc",
+ "once_cell",
 ]
 
 [[package]]
@@ -545,9 +546,9 @@ checksum = "b1a46d1a171d865aa5f83f92695765caa047a9b4cbae2cbf37dbd613a793fd4c"
 
 [[package]]
 name = "jobserver"
-version = "0.1.28"
+version = "0.1.31"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ab46a6e9526ddef3ae7f787c06f0f2600639ba80ea3eade3d8e670a2230f51d6"
+checksum = "d2b099aaa34a9751c5bf0878add70444e1ed2dd73f347be99003d4577277de6e"
 dependencies = [
  "libc",
 ]
diff --git a/compiler/qsc_eval/src/lib.rs b/compiler/qsc_eval/src/lib.rs
index 67c51a9f..0e405214 100644
--- a/compiler/qsc_eval/src/lib.rs
+++ b/compiler/qsc_eval/src/lib.rs
@@ -359,6 +359,19 @@ impl Env {
         }
     }
 
+    pub fn leave_current_frame(&mut self) {
+        let current_frame_id = self
+            .0
+            .last()
+            .expect("should be at least one scope")
+            .frame_id;
+        if current_frame_id == 0 {
+            // Do not remove the global scope.
+            return;
+        }
+        self.0.retain(|scope| scope.frame_id != current_frame_id);
+    }
+
     pub fn bind_variable_in_top_frame(&mut self, local_var_id: LocalVarId, var: Variable) {
         let Some(scope) = self.0.last_mut() else {
             panic!("no frames in scope");
@@ -611,6 +624,11 @@ impl State {
                     env.leave_scope();
                     continue;
                 }
+                Some(ExecGraphNode::RetFrame) => {
+                    self.leave_frame();
+                    env.leave_current_frame();
+                    continue;
+                }
                 Some(ExecGraphNode::PushScope) => {
                     self.push_scope(env);
                     self.idx += 1;
diff --git a/compiler/qsc_fir/src/fir.rs b/compiler/qsc_fir/src/fir.rs
index 5f8d84fc..7ac1dfcc 100644
--- a/compiler/qsc_fir/src/fir.rs
+++ b/compiler/qsc_fir/src/fir.rs
@@ -884,8 +884,6 @@ pub enum ExecGraphNode {
     Bind(PatId),
     /// An expression to execute.
     Expr(ExprId),
-    /// A statement to track for debugging.
-    Stmt(StmtId),
     /// An unconditional jump with to given location.
     Jump(u32),
     /// A conditional jump with to given location, where the jump is only taken if the condition is
@@ -900,6 +898,11 @@ pub enum ExecGraphNode {
     Unit,
     /// The end of the control flow graph.
     Ret,
+    /// The end of the control flow graph plus a pop of the current debug frame. Used instead of `Ret`
+    /// when debugging.
+    RetFrame,
+    /// A statement to track for debugging.
+    Stmt(StmtId),
     /// A push of a new scope, used when tracking variables for debugging.
     PushScope,
     /// A pop of the current scope, used when tracking variables for debugging.
diff --git a/compiler/qsc_lowerer/src/lib.rs b/compiler/qsc_lowerer/src/lib.rs
index 8a238e44..62909495 100644
--- a/compiler/qsc_lowerer/src/lib.rs
+++ b/compiler/qsc_lowerer/src/lib.rs
@@ -32,6 +32,7 @@ pub struct Lowerer {
     assigner: Assigner,
     exec_graph: Vec<ExecGraphNode>,
     enable_debug: bool,
+    ret_node: ExecGraphNode,
 }
 
 impl Default for Lowerer {
@@ -53,19 +54,25 @@ impl Lowerer {
             assigner: Assigner::new(),
             exec_graph: Vec::new(),
             enable_debug: false,
+            ret_node: ExecGraphNode::Ret,
         }
     }
 
     #[must_use]
     pub fn with_debug(mut self, dbg: bool) -> Self {
         self.enable_debug = dbg;
+        if dbg {
+            self.ret_node = ExecGraphNode::RetFrame;
+        } else {
+            self.ret_node = ExecGraphNode::Ret;
+        }
         self
     }
 
     pub fn take_exec_graph(&mut self) -> Vec<ExecGraphNode> {
         self.exec_graph
             .drain(..)
-            .chain(once(ExecGraphNode::Ret))
+            .chain(once(self.ret_node))
             .collect()
     }
 
@@ -248,7 +255,7 @@ impl Lowerer {
             exec_graph: self
                 .exec_graph
                 .drain(..)
-                .chain(once(ExecGraphNode::Ret))
+                .chain(once(self.ret_node))
                 .collect(),
         }
     }
@@ -546,7 +553,7 @@ impl Lowerer {
             }
             hir::ExprKind::Return(expr) => {
                 let expr = self.lower_expr(expr);
-                self.exec_graph.push(ExecGraphNode::Ret);
+                self.exec_graph.push(self.ret_node);
                 fir::ExprKind::Return(expr)
             }
             hir::ExprKind::Tuple(items) => fir::ExprKind::Tuple(
diff --git a/compiler/qsc_partial_eval/src/lib.rs b/compiler/qsc_partial_eval/src/lib.rs
index 61bb2c0f..4a3c2ffc 100644
--- a/compiler/qsc_partial_eval/src/lib.rs
+++ b/compiler/qsc_partial_eval/src/lib.rs
@@ -69,11 +69,9 @@ pub enum Error {
     #[diagnostic(transparent)]
     CapabilityError(CapabilityError),
 
-    #[error("use of unanalyzed dynamic value")]
+    #[error("cannot use a dynamic value returned from a runtime-resolved callable")]
     #[diagnostic(code("Qsc.PartialEval.UnexpectedDynamicValue"))]
-    #[diagnostic(help(
-        "analysis is limited for callables that cannot be uniquely resolved at compile time, try invoking the desired callable directly"
-    ))]
+    #[diagnostic(help("try invoking the desired callable directly"))]
     UnexpectedDynamicValue(#[label] Span),
 
     #[error("partial evaluation failed with error: {0}")]
diff --git a/compiler/qsc_rir/src/passes/remap_block_ids.rs b/compiler/qsc_rir/src/passes/remap_block_ids.rs
index d8bd95ff..d4a4304f 100644
--- a/compiler/qsc_rir/src/passes/remap_block_ids.rs
+++ b/compiler/qsc_rir/src/passes/remap_block_ids.rs
@@ -37,7 +37,7 @@ pub fn remap_block_ids(program: &mut Program) {
         // This effectively remaps all the blocks in the list and updates the mapped id of the current block.
         // This is only safe without cycles, so on a cyclic graph the node is skipped and not remapped.
         if is_acyclic {
-            block_id_map.retain_mut(|id| *id != block_id);
+            block_id_map.retain(|id| *id != block_id);
         } else if block_id_map.contains(&block_id) {
             continue;
         }
@@ -54,6 +54,10 @@ pub fn remap_block_ids(program: &mut Program) {
             // the same blocks back-to-back.
             continue;
         }
+        // Since we are going to extend the blocks to visit using the successors of the current block, we can remove them from
+        // anywhere else in the list to visit so we avoid visiting them multiple times (only the last visit to a block is
+        // significant, so others can be skipped).
+        blocks_to_visit.retain(|id| !successors.contains(id));
         blocks_to_visit.extend(successors);
     }
 
diff --git a/compiler/qsc_rir/src/passes/ssa_transform.rs b/compiler/qsc_rir/src/passes/ssa_transform.rs
index 38be3936..040adad6 100644
--- a/compiler/qsc_rir/src/passes/ssa_transform.rs
+++ b/compiler/qsc_rir/src/passes/ssa_transform.rs
@@ -59,10 +59,10 @@ pub fn transform_to_ssa(program: &mut Program, preds: &IndexMap<BlockId, Vec<Blo
         } else {
             // Check each variable in the first predecessor's variable map, and if any other
             // predecessor has a different value for the variable, a phi node is needed.
-            for (var_id, operand) in block_var_map
+            let first_pred_map = block_var_map
                 .get(*first_pred)
-                .expect("block should have variable map")
-            {
+                .expect("block should have variable map");
+            'var_loop: for (var_id, operand) in first_pred_map {
                 let mut phi_nodes = FxHashMap::default();
 
                 if rest_preds.iter().any(|pred| {
@@ -74,14 +74,20 @@ pub fn transform_to_ssa(program: &mut Program, preds: &IndexMap<BlockId, Vec<Blo
                 }) {
                     // Some predecessors have different values for this variable, so a phi node is needed.
                     // Start with the first predecessor's value and block id, then add the values from the other predecessors.
-                    let mut phi_args = vec![(*operand, *first_pred)];
+                    let mut phi_args = vec![(operand.mapped(first_pred_map), *first_pred)];
                     for pred in rest_preds {
                         let pred_var_map = block_var_map
                             .get(*pred)
                             .expect("block should have variable map");
-                        let mut pred_operand = *pred_var_map
-                            .get(var_id)
-                            .expect("variable should be in predecessor's variable map");
+                        let mut pred_operand = match pred_var_map.get(var_id) {
+                            Some(operand) => *operand,
+                            None => {
+                                // If the variable is not defined in this predecessor, it does not dominate this block.
+                                // Assume it is not used and skip creating a phi node for this variable. If the variable is used,
+                                // the ssa check will detect it and panic later.
+                                continue 'var_loop;
+                            }
+                        };
                         pred_operand = pred_operand.mapped(pred_var_map);
                         phi_args.push((pred_operand, *pred));
                     }


Test patch:
diff --git a/compiler/qsc/src/interpret/tests.rs b/compiler/qsc/src/interpret/tests.rs
index 893a9927..b291521e 100644
--- a/compiler/qsc/src/interpret/tests.rs
+++ b/compiler/qsc/src/interpret/tests.rs
@@ -1580,6 +1580,99 @@ mod given_interpreter {
             assert_eq!(2, bps.len());
         }
 
+        #[test]
+        fn debugger_simple_execution_succeeds() {
+            let source = indoc! { r#"
+            namespace Test {
+                function Hello() : Unit {
+                    Message("hello there...");
+                }
+
+                @EntryPoint()
+                operation Main() : Unit {
+                    Hello()
+                }
+            }"#};
+
+            let sources = SourceMap::new([("test".into(), source.into())], None);
+            let mut debugger = Debugger::new(
+                sources,
+                TargetCapabilityFlags::all(),
+                Encoding::Utf8,
+                LanguageFeatures::default(),
+            )
+            .expect("debugger should be created");
+            let (result, output) = entry(&mut debugger.interpreter);
+            is_unit_with_output_eval_entry(&result, &output, "hello there...");
+        }
+
+        #[test]
+        fn debugger_execution_with_call_to_library_succeeds() {
+            let source = indoc! { r#"
+            namespace Test {
+                open Microsoft.Quantum.Math;
+                @EntryPoint()
+                operation Main() : Int {
+                    Binom(31, 7)
+                }
+            }"#};
+
+            let sources = SourceMap::new([("test".into(), source.into())], None);
+            let mut debugger = Debugger::new(
+                sources,
+                TargetCapabilityFlags::all(),
+                Encoding::Utf8,
+                LanguageFeatures::default(),
+            )
+            .expect("debugger should be created");
+            let (result, output) = entry(&mut debugger.interpreter);
+            is_only_value(&result, &output, &Value::Int(2_629_575));
+        }
+
+        #[test]
+        fn debugger_execution_with_early_return_succeeds() {
+            let source = indoc! { r#"
+            namespace Test {
+                open Microsoft.Quantum.Arrays;
+
+                operation Max20(i : Int) : Int {
+                    if (i > 20) {
+                        return 20;
+                    }
+                    return i;
+                }
+
+                @EntryPoint()
+                operation Main() : Int[] {
+                    ForEach(Max20, [10, 20, 30, 40, 50])
+                }
+            }"#};
+
+            let sources = SourceMap::new([("test".into(), source.into())], None);
+            let mut debugger = Debugger::new(
+                sources,
+                TargetCapabilityFlags::all(),
+                Encoding::Utf8,
+                LanguageFeatures::default(),
+            )
+            .expect("debugger should be created");
+            let (result, output) = entry(&mut debugger.interpreter);
+            is_only_value(
+                &result,
+                &output,
+                &Value::Array(
+                    vec![
+                        Value::Int(10),
+                        Value::Int(20),
+                        Value::Int(20),
+                        Value::Int(20),
+                        Value::Int(20),
+                    ]
+                    .into(),
+                ),
+            );
+        }
+
         #[test]
         fn multiple_namespaces_are_loaded_from_sources_into_eval_context() {
             let source = indoc! { r#"
diff --git a/compiler/qsc_partial_eval/tests/bindings.rs b/compiler/qsc_partial_eval/tests/bindings.rs
index 568dd045..c55f5682 100644
--- a/compiler/qsc_partial_eval/tests/bindings.rs
+++ b/compiler/qsc_partial_eval/tests/bindings.rs
@@ -397,3 +397,89 @@ fn mutable_int_binding_does_generate_store_instruction() {
                 Jump(1)"#]],
     );
 }
+
+#[test]
+fn mutable_variable_in_outer_scope_set_to_mutable_from_inner_scope() {
+    let program = get_rir_program(indoc! {
+        r#"
+        namespace Test {
+            @EntryPoint()
+            operation Main() : Int {
+                use q = Qubit();
+                mutable i = 0;
+                if MResetZ(q) == One {
+                    mutable j = 1;
+                    set i = j;
+                }
+                else {
+                    set i = 2;
+                }
+                return i;
+            }
+        }
+        "#,
+    });
+
+    let measurement_callable_id = CallableId(1);
+    assert_callable(
+        &program,
+        measurement_callable_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__qis__mresetz__body
+                call_type: Measurement
+                input_type:
+                    [0]: Qubit
+                    [1]: Result
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    let read_result_callable_id = CallableId(2);
+    assert_callable(
+        &program,
+        read_result_callable_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__qis__read_result__body
+                call_type: Readout
+                input_type:
+                    [0]: Result
+                output_type: Boolean
+                body: <NONE>"#]],
+    );
+    let output_recording_callable_id = CallableId(3);
+    assert_callable(
+        &program,
+        output_recording_callable_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__rt__int_record_output
+                call_type: OutputRecording
+                input_type:
+                    [0]: Integer
+                    [1]: Pointer
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    assert_blocks(
+        &program,
+        &expect![[r#"
+        Blocks:
+        Block 0:Block:
+            Variable(0, Integer) = Store Integer(0)
+            Call id(1), args( Qubit(0), Result(0), )
+            Variable(1, Boolean) = Call id(2), args( Result(0), )
+            Variable(2, Boolean) = Store Variable(1, Boolean)
+            Branch Variable(2, Boolean), 2, 3
+        Block 1:Block:
+            Call id(3), args( Variable(0, Integer), Pointer, )
+            Return
+        Block 2:Block:
+            Variable(3, Integer) = Store Integer(1)
+            Variable(0, Integer) = Store Integer(1)
+            Jump(1)
+        Block 3:Block:
+            Variable(0, Integer) = Store Integer(2)
+            Jump(1)"#]],
+    );
+}
diff --git a/compiler/qsc_partial_eval/tests/misc.rs b/compiler/qsc_partial_eval/tests/misc.rs
index dce7ffda..a85b6fe4 100644
--- a/compiler/qsc_partial_eval/tests/misc.rs
+++ b/compiler/qsc_partial_eval/tests/misc.rs
@@ -350,8 +350,10 @@ fn large_loop_with_inner_if_completes_eval_and_transform() {
                 use q = Qubit();
                 mutable i = 0;
                 for idx in 0..99 {
-                    if MResetZ(q) == One {
-                        set i += 1;
+                    if i == 0 {
+                        if MResetZ(q) == One {
+                            set i += 1;
+                        }
                     }
                 }
                 return i;
@@ -362,10 +364,10 @@ fn large_loop_with_inner_if_completes_eval_and_transform() {
 
     // Program is expected to be too large to reasonably print out here, so instead verify the last block
     // and the total number of blocks.
-    assert_eq!(program.blocks.iter().count(), 201);
+    assert_eq!(program.blocks.iter().count(), 399);
     assert_block_instructions(
         &program,
-        BlockId(199),
+        BlockId(395),
         &expect![[r#"
             Block:
                 Variable(1, Integer) = Store Integer(100)