feat: Add a `borrow_array` type replacement pass #975

tatiana-s · 2025-07-17T08:56:55Z

Draft because performance benchmarks with Guppy using this are needed first to see if this is suitable. There are probably a lot of ways that some of the more repetitive code in all the dest functions could be generalised but for now I prioritised getting something working.

Closes #2397 (but should add a new issue for doing this properly in LLVM at some point)

codecov · 2025-07-17T09:00:53Z

Codecov Report

❌ Patch coverage is 97.28850% with 25 lines in your changes missing coverage. Please review.
✅ Project coverage is 80.29%. Comparing base (64412df) to head (5eed713).
⚠️ Report is 1 commits behind head on main.

Files with missing lines	Patch %	Lines
tket-qsystem/src/replace_borrow_arrays.rs	97.68%	15 Missing and 4 partials ⚠️
tket-qsystem/src/replace_bools.rs	94.87%	3 Missing and 1 partial ⚠️
tket-qsystem/src/lib.rs	71.42%	1 Missing and 1 partial ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #975      +/-   ##
==========================================
+ Coverage   79.18%   80.29%   +1.10%     
==========================================
  Files         120      121       +1     
  Lines       14147    15069     +922     
  Branches    13365    14287     +922     
==========================================
+ Hits        11202    12099     +897     
- Misses       2269     2288      +19     
- Partials      676      682       +6

Flag	Coverage Δ
rust	`79.60% <97.28%> (+1.21%)`	⬆️

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

mark-koch

Thanks, must have been quite tedious to write all that 😅

Looks good to me, mostly just a few nits and refactoring suggestions apart from the get lowering comment and missing lowering for conversion ops.

mark-koch · 2025-07-23T10:59:26Z

tket2-hseries/src/replace_borrow_arrays.rs

+        // TODO uncomment once https://github.com/CQCL/hugr/issues/1234 is complete
+        // ensure_no_nonlocal_edges(hugr)?;


This seems to be done?

Not quite sure what's going on here but we "temporarily" added a guppy fix to avoid generating nonlocals, however now Hugr has LocalizeEdges pass, so can we remove the guppy workaround? Not for this PR, but do we have a guppy issue?

Here, I'm not sure it's worth adding an error variant for the existence of nonlocal edges, to me I think this is an assert (a bug in our code) if we have not run LocalizeEdges already (or if there is a bug in LocalizeEdges !).

mark-koch · 2025-07-23T11:00:25Z

tket2-hseries/src/replace_borrow_arrays.rs

+    // pass meant to be run on Guppy-generated HUGRs, which should not emit borrow array
+    // constants that contain empty values. The borrow array extension however does not
+    // guarantee this, so we should handle the case where the array contains empty
+    // values on we add a more specific borrow array value that supports this.


Suggested change

// values on we add a more specific borrow array value that supports this.

// values once we add a more specific borrow array value that supports this.

?

mark-koch · 2025-07-23T11:07:41Z

tket2-hseries/src/replace_borrow_arrays.rs

+    // Unwrap the result: expect that the element was present.
+    let result_ty = vec![opt_elem_ty.clone().into(), arr_type.clone()];
+    let [opt_elem, out_arr] = dfb
+        .build_unwrap_sum(1, either_type(result_ty.clone(), result_ty), result)


Would be nicer to have an unwrap with a custom panic message. E.g. in Guppy we say "Index out of bounds"

mark-koch · 2025-07-23T11:08:49Z

tket2-hseries/src/replace_borrow_arrays.rs

+        .add_array_set(opt_elem_ty.clone().into(), size, arr, idx, nothing)
+        .unwrap();
+
+    // Unwrap the result: expect that the element was present.


Suggested change

// Unwrap the result: expect that the element was present.

// Unwrap the result: expect that the index was in bounds.

mark-koch · 2025-07-23T11:12:09Z

tket2-hseries/src/replace_borrow_arrays.rs

+        .add_array_set(opt_elem_ty.clone().into(), size, arr, idx, opt_elem)
+        .unwrap();
+
+    // Unwrap the result: expect that the slot was empty (none).


Suggested change

// Unwrap the result: expect that the slot was empty (none).

// Unwrap the result: expect that the index was in bounds.

mark-koch · 2025-07-23T12:25:13Z

tket2-hseries/src/replace_borrow_arrays.rs

+    // Unpack the array to get the elements as wires
+    let elems = dfb.add_array_unpack(elem_ty.clone(), size, arr).unwrap();


This makes the replacement scale with the array size. Better to use a scan op to wrap the elements into options

I had issues using scan because when I try to define a function on the module builder I get from the DFG builder it doesn't seem to add the function so I can't load it in to use with scan

Mhmm that's not ideal, pinging @acl-cqc

I guess it's ok to play around with for now but I'm sceptical about using this in production since it makes compile-time and binary size scale with arrays sizes...

mark-koch · 2025-07-23T12:26:32Z

tket2-hseries/src/replace_borrow_arrays.rs

+    // Unwrap all the options in the input array.
+    let elems = dfb
+        .add_array_unpack(opt_src_ty.clone().into(), size, inputs[0])
+        .unwrap();


Same here: Better to unpack using a scan

mark-koch · 2025-07-23T12:35:40Z

tket2-hseries/src/replace_borrow_arrays.rs

+        },
+    );
+
+    lw


You're missing the conversion ops from and to regular arrays

mark-koch · 2025-07-23T12:41:34Z

tket2-hseries/src/replace_borrow_arrays.rs

+            move |args| {
+                let [size, elem_ty] = args else {
+                    unreachable!()
+                };
+                Some(borrow_dest(
+                    size.as_nat().unwrap(),
+                    elem_ty.as_runtime().unwrap(),
+                ))
+            }


There's a lot of duplication of this logic. You could consider commoning it up a bit:

for op_def in BArrayUnsafeOpDef::iter() { w.replace_parametrized_op( borrow_array::EXTENSION.get_op(&op_def.opdef_id()).unwrap(), move |args| { let [size, elem_ty] = args else { unreachable!() }; let size = size.as_nat().unwrap(); let elem_ty = elem_ty.as_runtime().unwrap(); Some(match op_def { BArrayUnsafeOpDef::borrow => borrow_dest(size, elem_ty), BArrayUnsafeOpDef::#return => return_dest(size, elem_ty), ... }) }, ); }

mark-koch · 2025-07-23T12:44:39Z

tket2-hseries/src/replace_borrow_arrays.rs

+}
+
+#[cfg(test)]
+mod tests {


Could you also add a test for array constants?

mark-koch

Thanks! Looks good, happy to merge this

Can you create an issue to use scan instead of array unpacking and link it in the relevant places?

acl-cqc

TBH I feel that if this is passing tests then rather than benchmarking performance first, we should just get this in; and then work on adding benchmarks and improving/optimizing later. (e.g. from serialized Hugrs, so we are not waiting for guppy-main to generate them; and measuring compilation time and size of compiled output, down to whatever level is easy to test - maybe the Hugr input to hugr-llvm, or the LLVM-IR output from hugr-llvm, without running LLVM itself.) @mark-koch what do you think?

acl-cqc · 2025-09-01T14:01:20Z

tket-qsystem/src/replace_bools.rs

+        vec![array_ty.clone(), array_ty],
+    ))
+    .unwrap();
+    // TODO: Find less hacky solution.


Have we lowered drops already? (If not, can we lower to a drop?)

acl-cqc · 2025-09-01T14:03:55Z

tket-qsystem/src/replace_bools.rs

+            let size = size.as_nat().unwrap();
+            let elem_ty = elem_ty.as_runtime().unwrap();
+            if !elem_ty.copyable() {
+                Some(array_clone_dest(size, elem_ty))


Consider (!elem_ty.copyable()).then(|| array_clone_dest(size,elem_ty)) instead of the if...else

tket-qsystem/src/replace_bools.rs

acl-cqc · 2025-09-01T14:08:13Z

tket-qsystem/src/lower_drops.rs

@@ -18,6 +22,28 @@ impl<H: HugrMut<Node = Node>> ComposablePass<H> for LowerDropsPass {

    fn run(&self, hugr: &mut H) -> Result<Self::Result, Self::Error> {
        let mut rt = ReplaceTypes::default();
+
+        // future(bool) is not in the default linearizer handler so we add it here.


I think I favour commoning this up with the equivalent code in replace_bools.rs by making a helper-method that makes a ReplaceTypes with future-bool linearizer already set-up.

Do we still need this? If so, I stand by my previous comment; defining a private helper function is easy enough to do now

acl-cqc · 2025-09-01T14:11:41Z

tket2-hseries/src/replace_borrow_arrays.rs

+        // TODO uncomment once https://github.com/CQCL/hugr/issues/1234 is complete
+        // ensure_no_nonlocal_edges(hugr)?;


Not quite sure what's going on here but we "temporarily" added a guppy fix to avoid generating nonlocals, however now Hugr has LocalizeEdges pass, so can we remove the guppy workaround? Not for this PR, but do we have a guppy issue?

Here, I'm not sure it's worth adding an error variant for the existence of nonlocal edges, to me I think this is an assert (a bug in our code) if we have not run LocalizeEdges already (or if there is a bug in LocalizeEdges !).

mark-koch · 2025-09-01T16:04:27Z

@mark-koch what do you think?

Yeah imo ok to merge and make improvements in follow-up PRs

acl-cqc

Thanks Tatiana, mammoth chunk of work, Rust hugr-building is still painful and you've had to do a lot of it here - well done! 👍 💯 🥇

acl-cqc · 2025-09-03T14:21:19Z

tket-qsystem/src/lib.rs

@@ -44,6 +46,7 @@ pub struct QSystemPass {
    monomorphize: bool,
    force_order: bool,
    lazify: bool,
+    lower_borrow_arrays: bool,


I could super-nit-pick and say that this should be replace_borrow_arrays....or all should be called borrow_array_to_array.....but I won't ;-)

acl-cqc · 2025-09-03T14:26:07Z

tket-qsystem/src/lower_drops.rs

@@ -18,6 +22,28 @@ impl<H: HugrMut<Node = Node>> ComposablePass<H> for LowerDropsPass {

    fn run(&self, hugr: &mut H) -> Result<Self::Result, Self::Error> {
        let mut rt = ReplaceTypes::default();
+
+        // future(bool) is not in the default linearizer handler so we add it here.


Do we still need this? If so, I stand by my previous comment; defining a private helper function is easy enough to do now

acl-cqc · 2025-09-03T14:33:23Z

tket-qsystem/src/replace_borrow_arrays.rs

+        .unwrap();
+
+    // Unwrap the result: expect that the index was in bounds.
+    let result_ty = vec![opt_elem_ty.clone().into(), arr_type.clone()];


[Optional!] Could common up this bounds-check build_expect with the one in return_dest (helper method needs take only dfb, arr_type as the element type can be extracted from that, and result)

acl-cqc · 2025-09-03T14:35:15Z

tket-qsystem/src/replace_borrow_arrays.rs

+
+    // Check all elements are none and then discard array with now droppable elements.
+    let scan_op = ArrayScan::new(opt_elem_ty.clone().into(), Type::UNIT, vec![], size);
+    let unit_map_func = dfb.add_load_value(unit_map_func_value(elem_ty.clone()));


This isn't too bad if one forgets about needing unit_map_func_value 😁 ...ok good stuff 👍

acl-cqc · 2025-09-03T14:38:20Z

tket-qsystem/src/replace_borrow_arrays.rs

+            Tag::new(
+                0,
+                vec![
+                    vec![elem_ty.clone(), arr_type.clone()].into(),


Getting a bit hard to read - do let tys = vec![elem_ty.clone(), arr_type.clone()].into(); earlier and then here you can just vec![tys.clone(), tys] here

acl-cqc · 2025-09-03T14:38:38Z

tket-qsystem/src/replace_borrow_arrays.rs

+            Tag::new(
+                1,
+                vec![
+                    vec![elem_ty.clone(), arr_type.clone()].into(),


and again using the same tys as above

acl-cqc · 2025-09-03T14:40:00Z

tket-qsystem/src/replace_borrow_arrays.rs

+fn option_wrap_func_value(elem_ty: Type) -> Value {
+    let func_hugr = {
+        let mut dfb = DFGBuilder::new(inout_sig(
+            vec![elem_ty.clone()],


nit: can skip vec! if singleton

tatiana-s added 6 commits July 14, 2025 10:42

Add pass

727caf1

Continue adding op dests and tests

ffd73d2

All ops except scan producing valid hugr

893074b

Merge remote-tracking branch 'origin/main' into ts/replace-ba

6ad3dbb

Fix scan

fb6aa60

Turn on pass

19310df

tatiana-s requested a review from a team as a code owner July 17, 2025 08:56

tatiana-s requested a review from cqc-alec July 17, 2025 08:56

tatiana-s marked this pull request as draft July 17, 2025 08:57

tatiana-s removed the request for review from cqc-alec July 17, 2025 08:57

tatiana-s added 2 commits July 23, 2025 10:45

Uncomment

10c33f4

Merge remote-tracking branch 'origin/main' into ts/replace-ba

e516abb

tatiana-s marked this pull request as ready for review July 23, 2025 09:47

tatiana-s requested a review from doug-q July 23, 2025 09:48

mark-koch self-requested a review July 23, 2025 10:04

aborgna-q removed the request for review from doug-q July 23, 2025 10:04

mark-koch reviewed Jul 23, 2025

View reviewed changes

tatiana-s added 5 commits July 25, 2025 12:36

Address comments

fd04416

Merge remote-tracking branch 'origin/main' into ts/replace-ba

e1a57b0

Remove intos

90d8549

Fix

cc894c6

Merge remote-tracking branch 'origin/main' into ts/replace-ba

26e1431

tatiana-s requested a review from mark-koch July 25, 2025 12:00

Merge remote-tracking branch 'origin/main' into ts/replace-ba

f915fdf

tatiana-s requested a review from doug-q July 28, 2025 09:11

ss2165 mentioned this pull request Jul 28, 2025

chore: release #995

Merged

mark-koch approved these changes Jul 30, 2025

View reviewed changes

tatiana-s added 2 commits July 30, 2025 18:04

Merge remote-tracking branch 'origin/main' into ts/replace-ba

fa67e6b

Remove redundant handler

95e0eea

tatiana-s added 9 commits July 30, 2025 19:50

Merge remote-tracking branch 'origin/main' into ts/replace-ba

52f8371

Merge remote-tracking branch 'origin/main' into ts/replace-ba

fd7078c

Try different pass order

866cb4a

Merge remote-tracking branch 'origin/main' into ts/replace-ba

8ba66d1

Fix after merge

30b9fe8

Add clone / discard lowerings

193d8d4

Merge remote-tracking branch 'origin/main' into ts/replace-ba

97956ea

Add future bool handler

b48b69c

Merge remote-tracking branch 'origin/main' into ts/replace-ba

d3ff3f8

acl-cqc reviewed Sep 1, 2025

View reviewed changes

tatiana-s added 3 commits September 3, 2025 13:48

Replace unpacks with scans

60fd02c

Merge remote-tracking branch 'origin/main' into ts/replace-ba

f4dd920

Fixes

7d45d0e

tatiana-s mentioned this pull request Sep 3, 2025

feat!: Use borrow_array instead of value_array for array lowering CQCL/guppylang#1166

Draft

acl-cqc approved these changes Sep 3, 2025

View reviewed changes

tatiana-s added 2 commits September 4, 2025 10:51

Minor fixes

93ae471

Merge remote-tracking branch 'origin/main' into ts/replace-ba

5eed713

tatiana-s added this pull request to the merge queue Sep 4, 2025

Merged via the queue into main with commit ca5f19c Sep 4, 2025
20 checks passed

tatiana-s deleted the ts/replace-ba branch September 4, 2025 10:12

hugrbot mentioned this pull request Sep 4, 2025

chore: release #1064

Draft

		// TODO uncomment once https://github.com/CQCL/hugr/issues/1234 is complete
		// ensure_no_nonlocal_edges(hugr)?;

	// values on we add a more specific borrow array value that supports this.
	// values once we add a more specific borrow array value that supports this.

	// Unwrap the result: expect that the element was present.
	// Unwrap the result: expect that the index was in bounds.

	// Unwrap the result: expect that the slot was empty (none).
	// Unwrap the result: expect that the index was in bounds.

		// Unpack the array to get the elements as wires
		let elems = dfb.add_array_unpack(elem_ty.clone(), size, arr).unwrap();

+                      },
+                  );
+                  lw

feat: Add a borrow_array type replacement pass #975

feat: Add a borrow_array type replacement pass #975

Uh oh!

Conversation

tatiana-s commented Jul 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov bot commented Jul 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

mark-koch left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mark-koch left a comment

Choose a reason for hiding this comment

Uh oh!

acl-cqc left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mark-koch commented Sep 1, 2025

Uh oh!

acl-cqc left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

feat: Add a `borrow_array` type replacement pass #975

feat: Add a `borrow_array` type replacement pass #975

tatiana-s commented Jul 17, 2025 •

edited

Loading

codecov bot commented Jul 17, 2025 •

edited

Loading