tket/passes/
guppy.rs

1//! A pass that normalizes the structure of Guppy-generated circuits into something that can be optimized by tket.
2
3use crate::passes::composable::WithScope;
4use crate::passes::const_fold::{ConstFoldError, ConstantFoldPass};
5use crate::passes::dead_funcs::RemoveDeadFuncsError;
6use crate::passes::inline_funcs::{InlineFuncsError, InlineFuncsHeuristic, InlineFunctionsPass};
7use crate::passes::modifier_resolver::{ModifierResolverErrors, ModifierResolverPass};
8use crate::passes::normalize_cfgs::{NormalizeCFGError, NormalizeCFGPass};
9use crate::passes::redundant_order_edges::RedundantOrderEdgesPass;
10use crate::passes::untuple::{UntupleError, UntuplePass};
11use crate::passes::{ComposablePass, InlineDFGsPass, PassScope, RemoveDeadFuncsPass};
12use hugr::Node;
13use hugr::hugr::HugrError;
14use hugr::hugr::hugrmut::HugrMut;
15use hugr::hugr::patch::inline_dfg::InlineDFGError;
16
17use crate::passes::BorrowSquashPass;
18
19/// Normalize the structure of a Guppy-generated circuit into something that can be optimized by tket.
20///
21/// This is a mixture of global optimization passes, and operations that optimize the entrypoint.
22#[derive(Clone, Debug)]
23pub struct NormalizeGuppy {
24    /// Whether to resolve modifier operations.
25    resolve_modifiers: bool,
26    /// Whether to simplify CFG control flow.
27    simplify_cfgs: bool,
28    /// Whether to remove tuple/untuple operations.
29    untuple: bool,
30    /// Whether to constant fold the program.
31    constant_fold: bool,
32    /// Whether to remove dead functions.
33    dead_funcs: bool,
34    /// Whether to inline function calls (converting to DFGs).
35    inline_funcs: Option<InlineFuncsHeuristic>,
36    /// Whether to inline DFG operations.
37    inline_dfgs: bool,
38    /// Whether to squash BorrowArray borrow/return ops
39    squash_borrows: bool,
40    /// Whether to remove redundant order edges.
41    remove_redundant_order_edges: bool,
42
43    /// Where to apply the pass.
44    ///
45    /// Configurable via [`WithScope::with_scope`].
46    scope: PassScope,
47}
48
49impl NormalizeGuppy {
50    /// Set whether to resolve modifier operations.
51    pub fn resolve_modifiers(&mut self, resolve_modifiers: bool) -> &mut Self {
52        self.resolve_modifiers = resolve_modifiers;
53        self
54    }
55    /// Set whether to simplify CFG control flow.
56    pub fn simplify_cfgs(&mut self, simplify_cfgs: bool) -> &mut Self {
57        self.simplify_cfgs = simplify_cfgs;
58        self
59    }
60    /// Set whether to remove tuple/untuple operations.
61    pub fn remove_tuple_untuple(&mut self, untuple: bool) -> &mut Self {
62        self.untuple = untuple;
63        self
64    }
65    /// Set whether to constant fold the program.
66    pub fn constant_folding(&mut self, constant_fold: bool) -> &mut Self {
67        self.constant_fold = constant_fold;
68        self
69    }
70    /// Set whether to remove dead functions.
71    pub fn remove_dead_funcs(&mut self, dead_funcs: bool) -> &mut Self {
72        self.dead_funcs = dead_funcs;
73        self
74    }
75    /// Set whether to inline DFG operations.
76    pub fn inline_dfgs(&mut self, inline: bool) -> &mut Self {
77        self.inline_dfgs = inline;
78        self
79    }
80    /// Set whether to inline Function calls. (Does not include [Self::inline_dfgs]
81    /// but generates DFGs so the latter is strongly recommended.)
82    pub fn inline_funcs(&mut self, inline: Option<InlineFuncsHeuristic>) -> &mut Self {
83        self.inline_funcs = inline;
84        self
85    }
86    /// Set whether to squash BorrowArray borrow/return ops
87    pub fn squash_borrows(&mut self, squash: bool) -> &mut Self {
88        self.squash_borrows = squash;
89        self
90    }
91    /// Set whether to remove redundant order edges.
92    pub fn remove_redundant_order_edges(&mut self, remove: bool) -> &mut Self {
93        self.remove_redundant_order_edges = remove;
94        self
95    }
96}
97
98impl Default for NormalizeGuppy {
99    fn default() -> Self {
100        Self {
101            resolve_modifiers: true,
102            inline_funcs: Some(InlineFuncsHeuristic::default()),
103            simplify_cfgs: true,
104            constant_fold: true,
105            untuple: true,
106            dead_funcs: true,
107            inline_dfgs: true,
108            squash_borrows: true,
109            remove_redundant_order_edges: true,
110            scope: PassScope::default(),
111        }
112    }
113}
114
115impl WithScope for NormalizeGuppy {
116    fn with_scope(mut self, scope: impl Into<crate::passes::PassScope>) -> Self {
117        self.scope = scope.into();
118        self
119    }
120}
121
122impl<H: HugrMut<Node = Node> + 'static> ComposablePass<H> for NormalizeGuppy {
123    type Error = NormalizeGuppyErrors;
124    type Result = ();
125
126    fn run(&self, hugr: &mut H) -> Result<Self::Result, Self::Error> {
127        // Simplify CFGs first, as (until we start removing statically-impossible branches)
128        // nothing else affects CFG structure or creates new opportunities for this.
129        // (Possibly also this may assist modifier resolution??)
130        if self.simplify_cfgs {
131            NormalizeCFGPass::default()
132                .with_scope(self.scope.clone())
133                .run(hugr)?;
134        }
135        // Run modifier resolution
136        if self.resolve_modifiers {
137            ModifierResolverPass::default()
138                .with_scope(self.scope.clone())
139                .run(hugr)?;
140        }
141        // Inline function calls creates many opportunities for optimization by other
142        // passes by producing copies that can be optimized in a specific context
143        if let Some(inline_funcs) = &self.inline_funcs {
144            InlineFunctionsPass::default_with_scope(self.scope.clone())
145                .with_heuristic(inline_funcs.clone())
146                .run(hugr)
147                .map_err(NormalizeGuppyErrors::InlineFuncs)?;
148        }
149        // Clean up after inlining - only to improve compilation speed, not affected by
150        // anything else until we start removing untaken branches.
151        if self.dead_funcs {
152            RemoveDeadFuncsPass::default()
153                .with_scope(self.scope.clone())
154                .run(hugr)?;
155        }
156        // Function inlining produces lots of DFGs, so merge those into their surrounds
157        if self.inline_dfgs {
158            InlineDFGsPass::default()
159                .with_scope(self.scope.clone())
160                .run(hugr)
161                .unwrap_or_else(|e| match e {})
162        }
163        // This should sort out argument marshalling for function calls (esp. inlined ones)
164        if self.untuple {
165            UntuplePass::default_with_scope(self.scope.clone()).run(hugr)?;
166        }
167        // Should propagate through untuple, so could do earlier, but not clear earlier
168        // would be any advantage. Must be before BorrowSquash as that needs constant indices.
169        if self.constant_fold {
170            ConstantFoldPass::default()
171                .with_scope(self.scope.clone())
172                .run(hugr)?;
173        }
174        // Potentially, could (need to) do fixpoint here with untuple,
175        // as both create opportunities for the other
176        if self.squash_borrows {
177            BorrowSquashPass::default()
178                .with_scope(self.scope.clone())
179                .run(hugr)
180                .unwrap_or_else(|e| match e {});
181        }
182        // Remove redundant order edges once all other structural rewrites have been applied.
183        if self.remove_redundant_order_edges {
184            RedundantOrderEdgesPass::default()
185                .with_scope(self.scope.clone())
186                .run(hugr)
187                .map_err(NormalizeGuppyErrors::RedundantOrderEdges)?;
188        }
189
190        Ok(())
191    }
192}
193
194/// Errors that can occur during the guppy-program normalization process.
195#[derive(derive_more::Error, Debug, derive_more::Display, derive_more::From)]
196#[non_exhaustive]
197pub enum NormalizeGuppyErrors {
198    /// Error while resolving modifier operations.
199    ModifierResolver(ModifierResolverErrors),
200    /// Error while simplifying CFG control flow.
201    SimplifyCFG(NormalizeCFGError),
202    /// Error while removing tuple/untuple operations.
203    Untuple(UntupleError),
204    /// Error while constant folding.
205    ConstantFold(ConstFoldError),
206    /// Error while removing dead functions.
207    DeadFuncs(RemoveDeadFuncsError),
208    /// Error while inlining DFG operations.
209    InlineDFGs(InlineDFGError),
210    /// Error while inlining function calls.
211    InlineFuncs(InlineFuncsError),
212    /// Error while removing redundant order edges.
213    #[from(ignore)]
214    RedundantOrderEdges(HugrError),
215}
216
217#[cfg(test)]
218mod test {
219    use hugr::builder::{Dataflow, DataflowHugr, FunctionBuilder};
220    use hugr::extension::prelude::qb_t;
221    use hugr::types::Signature;
222
223    use crate::TketOp;
224
225    use super::*;
226
227    /// Running the pass with all options disabled should still work (and do nothing).
228    #[test]
229    fn test_guppy_pass_noop() {
230        let mut b = FunctionBuilder::new("main", Signature::new_endo(vec![qb_t()])).unwrap();
231        let [q] = b.input_wires_arr();
232        let [q] = b.add_dataflow_op(TketOp::H, [q]).unwrap().outputs_arr();
233        let hugr = b.finish_hugr_with_outputs([q]).unwrap();
234
235        let mut hugr2 = hugr.clone();
236        NormalizeGuppy::default()
237            .resolve_modifiers(false)
238            .simplify_cfgs(false)
239            .remove_tuple_untuple(false)
240            .constant_folding(false)
241            .remove_dead_funcs(false)
242            .inline_dfgs(false)
243            .remove_redundant_order_edges(false)
244            .run(&mut hugr2)
245            .unwrap();
246
247        assert_eq!(hugr2, hugr);
248    }
249}
tket/passes/guppy.rs

tket/passes/
guppy.rs
