Skip to main content

qirc/
ir.rs

1use crate::ast;
2pub use crate::ast::{BinOp, CastOp, FloatPredicate, IntPredicate};
3use crate::diag::Span;
4use std::collections::HashMap;
5use std::fmt;
6
7#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
8pub struct BlockId(pub u32);
9
10#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
11pub struct ValueId(pub u32);
12
13#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
14pub struct QubitId(pub u32);
15
16#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
17pub struct ResultId(pub u32);
18
19#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
20pub struct SlotId(pub u32);
21
22impl BlockId {
23    pub fn index(self) -> usize {
24        self.0 as usize
25    }
26}
27
28impl SlotId {
29    pub fn index(self) -> usize {
30        self.0 as usize
31    }
32}
33
34impl QubitId {
35    pub fn index(self) -> usize {
36        self.0 as usize
37    }
38}
39
40impl ResultId {
41    pub fn index(self) -> usize {
42        self.0 as usize
43    }
44}
45
46#[derive(Clone, Copy, PartialEq, Debug)]
47pub enum Profile {
48    Base,
49    Adaptive,
50    Unrestricted,
51}
52
53impl Profile {
54    pub fn from_attribute(value: &str) -> Profile {
55        match value {
56            "base_profile" | "base" => Profile::Base,
57            "adaptive_profile" | "adaptive" => Profile::Adaptive,
58            _ => Profile::Unrestricted,
59        }
60    }
61
62    pub fn name(self) -> &'static str {
63        match self {
64            Profile::Base => "base_profile",
65            Profile::Adaptive => "adaptive_profile",
66            Profile::Unrestricted => "unrestricted",
67        }
68    }
69
70    pub fn allows_branching(self) -> bool {
71        !matches!(self, Profile::Base)
72    }
73}
74
75#[derive(Clone, Copy, PartialEq, Debug)]
76pub enum Const {
77    Bool(bool),
78    Int(i64),
79    Float(f64),
80}
81
82impl Const {
83    pub fn as_f64(self) -> f64 {
84        match self {
85            Const::Bool(b) => {
86                if b {
87                    1.0
88                } else {
89                    0.0
90                }
91            }
92            Const::Int(i) => i as f64,
93            Const::Float(f) => f,
94        }
95    }
96
97    pub fn as_i64(self) -> i64 {
98        match self {
99            Const::Bool(b) => b as i64,
100            Const::Int(i) => i,
101            Const::Float(f) => f as i64,
102        }
103    }
104
105    pub fn truthy(self) -> bool {
106        match self {
107            Const::Bool(b) => b,
108            Const::Int(i) => i != 0,
109            Const::Float(f) => f != 0.0,
110        }
111    }
112}
113
114#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
115pub enum Scalar {
116    Bool,
117    Int(u32),
118    Float,
119    Double,
120}
121
122impl Scalar {
123    pub fn of(ty: &ast::Ty) -> Scalar {
124        match ty {
125            ast::Ty::Int(1) => Scalar::Bool,
126            ast::Ty::Int(bits) => Scalar::Int((*bits).clamp(2, 64)),
127            ast::Ty::Float => Scalar::Float,
128            ast::Ty::Half | ast::Ty::Double | ast::Ty::X86Fp80 | ast::Ty::Fp128 => Scalar::Double,
129            _ => Scalar::Int(64),
130        }
131    }
132
133    pub fn normalize(self, c: Const) -> Const {
134        match self {
135            Scalar::Bool => Const::Bool(c.as_i64() & 1 == 1),
136            Scalar::Int(bits) => Const::Int(wrap(c.as_i64(), bits)),
137            Scalar::Float => Const::Float(c.as_f64() as f32 as f64),
138            Scalar::Double => Const::Float(c.as_f64()),
139        }
140    }
141
142    pub fn is_float(self) -> bool {
143        matches!(self, Scalar::Float | Scalar::Double)
144    }
145
146    pub fn signed(self, c: Const) -> i64 {
147        match self {
148            Scalar::Bool => -(c.as_i64() & 1),
149            _ => c.as_i64(),
150        }
151    }
152
153    pub fn unsigned(self, c: Const) -> u64 {
154        match self {
155            Scalar::Bool => c.as_i64() as u64 & 1,
156            Scalar::Int(bits) if bits < 64 => c.as_i64() as u64 & ((1 << bits) - 1),
157            _ => c.as_i64() as u64,
158        }
159    }
160
161    pub fn bits(self) -> u32 {
162        match self {
163            Scalar::Bool => 1,
164            Scalar::Int(bits) => bits,
165            Scalar::Float => 32,
166            Scalar::Double => 64,
167        }
168    }
169}
170
171impl fmt::Display for Scalar {
172    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
173        match self {
174            Scalar::Bool => write!(f, "i1"),
175            Scalar::Int(bits) => write!(f, "i{bits}"),
176            Scalar::Float => write!(f, "float"),
177            Scalar::Double => write!(f, "double"),
178        }
179    }
180}
181
182fn wrap(value: i64, bits: u32) -> i64 {
183    if bits >= 64 {
184        return value;
185    }
186    let shift = 64 - bits;
187    (value << shift) >> shift
188}
189
190#[derive(Clone, Copy, PartialEq, Debug)]
191pub enum Operand {
192    Const(Const),
193    Value(ValueId),
194}
195
196impl Operand {
197    pub fn constant(self) -> Option<Const> {
198        match self {
199            Operand::Const(c) => Some(c),
200            Operand::Value(_) => None,
201        }
202    }
203
204    pub fn value(self) -> Option<ValueId> {
205        match self {
206            Operand::Value(v) => Some(v),
207            Operand::Const(_) => None,
208        }
209    }
210
211    pub fn resolve(&self, known: &HashMap<ValueId, Const>) -> Option<Const> {
212        match self {
213            Operand::Const(c) => Some(*c),
214            Operand::Value(id) => known.get(id).copied(),
215        }
216    }
217}
218
219impl BinOp {
220    pub fn apply(self, ty: Scalar, a: Const, b: Const) -> Const {
221        if self.is_float() {
222            let (x, y) = (a.as_f64(), b.as_f64());
223            return ty.normalize(Const::Float(match self {
224                BinOp::FAdd => x + y,
225                BinOp::FSub => x - y,
226                BinOp::FMul => x * y,
227                BinOp::FDiv => x / y,
228                _ => x % y,
229            }));
230        }
231
232        let (x, y) = (ty.signed(a), ty.signed(b));
233        let (ux, uy) = (ty.unsigned(a), ty.unsigned(b));
234        let shift = uy.min(u64::from(ty.bits())) as u32;
235        let value = match self {
236            BinOp::Add => x.wrapping_add(y),
237            BinOp::Sub => x.wrapping_sub(y),
238            BinOp::Mul => x.wrapping_mul(y),
239            BinOp::SDiv if y != 0 => x.wrapping_div(y),
240            BinOp::UDiv if uy != 0 => (ux / uy) as i64,
241            BinOp::SRem if y != 0 => x.wrapping_rem(y),
242            BinOp::URem if uy != 0 => (ux % uy) as i64,
243            BinOp::Shl => x.checked_shl(shift).unwrap_or(0),
244            BinOp::LShr => ux.checked_shr(shift).unwrap_or(0) as i64,
245            BinOp::AShr => x >> shift.min(63),
246            BinOp::And => x & y,
247            BinOp::Or => x | y,
248            BinOp::Xor => x ^ y,
249            _ => 0,
250        };
251        ty.normalize(Const::Int(value))
252    }
253}
254
255impl IntPredicate {
256    pub fn test(self, ty: Scalar, a: Const, b: Const) -> bool {
257        let (sa, sb) = (ty.signed(a), ty.signed(b));
258        let (ua, ub) = (ty.unsigned(a), ty.unsigned(b));
259        match self {
260            IntPredicate::Eq => ua == ub,
261            IntPredicate::Ne => ua != ub,
262            IntPredicate::Sgt => sa > sb,
263            IntPredicate::Sge => sa >= sb,
264            IntPredicate::Slt => sa < sb,
265            IntPredicate::Sle => sa <= sb,
266            IntPredicate::Ugt => ua > ub,
267            IntPredicate::Uge => ua >= ub,
268            IntPredicate::Ult => ua < ub,
269            IntPredicate::Ule => ua <= ub,
270        }
271    }
272}
273
274impl FloatPredicate {
275    pub fn test(self, a: f64, b: f64) -> bool {
276        let ordered = !a.is_nan() && !b.is_nan();
277        match self {
278            FloatPredicate::False => false,
279            FloatPredicate::True => true,
280            FloatPredicate::Ord => ordered,
281            FloatPredicate::Uno => !ordered,
282            FloatPredicate::Oeq => ordered && a == b,
283            FloatPredicate::One => ordered && a != b,
284            FloatPredicate::Ogt => ordered && a > b,
285            FloatPredicate::Oge => ordered && a >= b,
286            FloatPredicate::Olt => ordered && a < b,
287            FloatPredicate::Ole => ordered && a <= b,
288            FloatPredicate::Ueq => !ordered || a == b,
289            FloatPredicate::Une => !ordered || a != b,
290            FloatPredicate::Ugt => !ordered || a > b,
291            FloatPredicate::Uge => !ordered || a >= b,
292            FloatPredicate::Ult => !ordered || a < b,
293            FloatPredicate::Ule => !ordered || a <= b,
294        }
295    }
296}
297
298impl CastOp {
299    pub fn apply(self, from: Scalar, to: Scalar, value: Const) -> Const {
300        let result = match self {
301            CastOp::Trunc | CastOp::SExt => Const::Int(from.signed(value)),
302            CastOp::ZExt => Const::Int(from.unsigned(value) as i64),
303            CastOp::FPToSI => Const::Int(value.as_f64() as i64),
304            CastOp::FPToUI => Const::Int(value.as_f64() as u64 as i64),
305            CastOp::SIToFP => Const::Float(from.signed(value) as f64),
306            CastOp::UIToFP => Const::Float(from.unsigned(value) as f64),
307            CastOp::BitCast => match (from, to) {
308                (Scalar::Double, Scalar::Int(_)) => Const::Int(value.as_f64().to_bits() as i64),
309                (Scalar::Float, Scalar::Int(_)) => {
310                    Const::Int(i64::from((value.as_f64() as f32).to_bits()))
311                }
312                (Scalar::Int(_), Scalar::Double) => {
313                    Const::Float(f64::from_bits(value.as_i64() as u64))
314                }
315                (Scalar::Int(_), Scalar::Float) => {
316                    Const::Float(f64::from(f32::from_bits(value.as_i64() as u32)))
317                }
318                _ => value,
319            },
320            _ => value,
321        };
322        to.normalize(result)
323    }
324}
325
326#[derive(Clone, Debug)]
327pub enum Expr {
328    Const(Const),
329    Binary {
330        op: BinOp,
331        lhs: Operand,
332        rhs: Operand,
333    },
334    ICmp {
335        pred: IntPredicate,
336        ty: Scalar,
337        lhs: Operand,
338        rhs: Operand,
339    },
340    FCmp {
341        pred: FloatPredicate,
342        ty: Scalar,
343        lhs: Operand,
344        rhs: Operand,
345    },
346    Select {
347        cond: Operand,
348        if_true: Operand,
349        if_false: Operand,
350    },
351    Cast {
352        op: CastOp,
353        from: Scalar,
354        operand: Operand,
355    },
356    Phi(Vec<(BlockId, Operand)>),
357    ReadResult(ResultId),
358    Load(SlotId),
359}
360
361impl Expr {
362    pub fn fold(
363        &self,
364        ty: Scalar,
365        mut get: impl FnMut(&Operand) -> Option<Const>,
366    ) -> Option<Const> {
367        match self {
368            Expr::Const(c) => Some(ty.normalize(*c)),
369            Expr::Binary { op, lhs, rhs } => Some(op.apply(ty, get(lhs)?, get(rhs)?)),
370            Expr::ICmp {
371                pred,
372                ty: operands,
373                lhs,
374                rhs,
375            } => Some(Const::Bool(pred.test(*operands, get(lhs)?, get(rhs)?))),
376            Expr::FCmp { pred, lhs, rhs, .. } => Some(Const::Bool(
377                pred.test(get(lhs)?.as_f64(), get(rhs)?.as_f64()),
378            )),
379            Expr::Select {
380                cond,
381                if_true,
382                if_false,
383            } => {
384                let chosen = if get(cond)?.truthy() {
385                    get(if_true)
386                } else {
387                    get(if_false)
388                };
389                Some(ty.normalize(chosen?))
390            }
391            Expr::Cast { op, from, operand } => Some(op.apply(*from, ty, get(operand)?)),
392            Expr::Phi(_) | Expr::ReadResult(_) | Expr::Load(_) => None,
393        }
394    }
395
396    pub fn operands(&self) -> Vec<Operand> {
397        match self {
398            Expr::Const(_) | Expr::ReadResult(_) | Expr::Load(_) => Vec::new(),
399            Expr::Cast { operand, .. } => vec![*operand],
400            Expr::Binary { lhs, rhs, .. }
401            | Expr::ICmp { lhs, rhs, .. }
402            | Expr::FCmp { lhs, rhs, .. } => vec![*lhs, *rhs],
403            Expr::Select {
404                cond,
405                if_true,
406                if_false,
407            } => vec![*cond, *if_true, *if_false],
408            Expr::Phi(incoming) => incoming.iter().map(|(_, o)| *o).collect(),
409        }
410    }
411}
412
413#[derive(Clone, Copy, PartialEq, Debug)]
414pub struct Matrix2 {
415    pub a: (f64, f64),
416    pub b: (f64, f64),
417    pub c: (f64, f64),
418    pub d: (f64, f64),
419}
420
421#[derive(Clone, Copy, PartialEq, Debug)]
422pub enum GateKind {
423    I,
424    X,
425    Y,
426    Z,
427    H,
428    S,
429    SDag,
430    T,
431    TDag,
432    SX,
433    SXDag,
434    Rx,
435    Ry,
436    Rz,
437    R1,
438    Swap,
439    Unitary(Matrix2),
440}
441
442impl GateKind {
443    pub fn arity(self) -> usize {
444        match self {
445            GateKind::Swap => 2,
446            _ => 1,
447        }
448    }
449
450    pub fn param_count(self) -> usize {
451        match self {
452            GateKind::Rx | GateKind::Ry | GateKind::Rz | GateKind::R1 => 1,
453            _ => 0,
454        }
455    }
456
457    pub fn is_self_inverse(self) -> bool {
458        matches!(
459            self,
460            GateKind::I | GateKind::X | GateKind::Y | GateKind::Z | GateKind::H | GateKind::Swap
461        )
462    }
463
464    pub fn adjoint(self) -> Option<GateKind> {
465        Some(match self {
466            GateKind::S => GateKind::SDag,
467            GateKind::SDag => GateKind::S,
468            GateKind::T => GateKind::TDag,
469            GateKind::TDag => GateKind::T,
470            GateKind::SX => GateKind::SXDag,
471            GateKind::SXDag => GateKind::SX,
472            other if other.is_self_inverse() => other,
473            _ => return None,
474        })
475    }
476
477    pub fn name(self) -> &'static str {
478        match self {
479            GateKind::I => "i",
480            GateKind::X => "x",
481            GateKind::Y => "y",
482            GateKind::Z => "z",
483            GateKind::H => "h",
484            GateKind::S => "s",
485            GateKind::SDag => "sdg",
486            GateKind::T => "t",
487            GateKind::TDag => "tdg",
488            GateKind::SX => "sx",
489            GateKind::SXDag => "sxdg",
490            GateKind::Rx => "rx",
491            GateKind::Ry => "ry",
492            GateKind::Rz => "rz",
493            GateKind::R1 => "r1",
494            GateKind::Swap => "swap",
495            GateKind::Unitary(_) => "unitary",
496        }
497    }
498}
499
500#[derive(Clone, Debug)]
501pub struct Gate {
502    pub kind: GateKind,
503    pub controls: Vec<QubitId>,
504    pub targets: Vec<QubitId>,
505    pub params: Vec<Operand>,
506    pub span: Span,
507}
508
509impl Gate {
510    pub fn wires(&self) -> impl Iterator<Item = QubitId> + '_ {
511        self.controls.iter().chain(self.targets.iter()).copied()
512    }
513
514    pub fn is_parameterised(&self) -> bool {
515        self.kind.param_count() > 0
516    }
517
518    pub fn constant_angle(&self) -> Option<f64> {
519        self.params.first()?.constant().map(|c| c.as_f64())
520    }
521
522    pub fn constant_params(&self) -> Vec<f64> {
523        self.params
524            .iter()
525            .filter_map(|p| p.constant().map(|c| c.as_f64()))
526            .collect()
527    }
528}
529
530#[derive(Clone, Copy, PartialEq, Debug)]
531pub enum OutputKind {
532    Result,
533    Bool,
534    Int,
535    Double,
536    Tuple,
537    Array,
538    TupleEnd,
539    ArrayEnd,
540}
541
542#[derive(Clone, Debug)]
543pub enum Op {
544    Gate(Gate),
545    Measure {
546        qubit: QubitId,
547        result: ResultId,
548        span: Span,
549    },
550    Reset {
551        qubit: QubitId,
552        span: Span,
553    },
554    Assign {
555        dest: ValueId,
556        ty: Scalar,
557        expr: Expr,
558        span: Span,
559    },
560    RecordOutput {
561        kind: OutputKind,
562        result: Option<ResultId>,
563        value: Option<Operand>,
564        count: Option<i64>,
565        label: Option<String>,
566        span: Span,
567    },
568    Message {
569        text: String,
570        span: Span,
571    },
572    Store {
573        slot: SlotId,
574        value: Operand,
575        span: Span,
576    },
577}
578
579impl Op {
580    pub fn as_gate(&self) -> Option<&Gate> {
581        match self {
582            Op::Gate(g) => Some(g),
583            _ => None,
584        }
585    }
586
587    pub fn qubits(&self) -> Vec<QubitId> {
588        match self {
589            Op::Gate(gate) => gate.wires().collect(),
590            Op::Measure { qubit, .. } | Op::Reset { qubit, .. } => vec![*qubit],
591            _ => Vec::new(),
592        }
593    }
594
595    pub fn defined_value(&self) -> Option<ValueId> {
596        match self {
597            Op::Assign { dest, .. } => Some(*dest),
598            _ => None,
599        }
600    }
601
602    pub fn operands(&self) -> Vec<Operand> {
603        match self {
604            Op::Gate(gate) => gate.params.clone(),
605            Op::Store { value, .. }
606            | Op::RecordOutput {
607                value: Some(value), ..
608            } => vec![*value],
609            Op::Assign { expr, .. } => expr.operands(),
610            _ => Vec::new(),
611        }
612    }
613}
614
615#[derive(Clone, Debug)]
616pub enum Term {
617    Ret(Option<Operand>),
618    Br(BlockId),
619    CondBr {
620        cond: Operand,
621        if_true: BlockId,
622        if_false: BlockId,
623    },
624    Switch {
625        scrutinee: Operand,
626        cases: Vec<(i64, BlockId)>,
627        default: BlockId,
628    },
629    Unreachable,
630}
631
632impl Term {
633    pub fn successors(&self) -> Vec<BlockId> {
634        match self {
635            Term::Ret(_) | Term::Unreachable => Vec::new(),
636            Term::Br(b) => vec![*b],
637            Term::CondBr {
638                if_true, if_false, ..
639            } => vec![*if_true, *if_false],
640            Term::Switch { cases, default, .. } => {
641                let mut out: Vec<BlockId> = cases.iter().map(|(_, b)| *b).collect();
642                out.push(*default);
643                out
644            }
645        }
646    }
647
648    pub fn operand(&self) -> Option<Operand> {
649        match self {
650            Term::CondBr { cond, .. } => Some(*cond),
651            Term::Switch { scrutinee, .. } => Some(*scrutinee),
652            Term::Ret(operand) => *operand,
653            Term::Br(_) | Term::Unreachable => None,
654        }
655    }
656
657    pub fn operand_mut(&mut self) -> Option<&mut Operand> {
658        match self {
659            Term::CondBr { cond, .. } => Some(cond),
660            Term::Switch { scrutinee, .. } => Some(scrutinee),
661            Term::Ret(operand) => operand.as_mut(),
662            Term::Br(_) | Term::Unreachable => None,
663        }
664    }
665}
666
667#[derive(Clone, Debug)]
668pub struct Block {
669    pub id: BlockId,
670    pub label: String,
671    pub ops: Vec<Op>,
672    pub term: Term,
673    pub span: Span,
674}
675
676impl Block {
677    pub fn gates(&self) -> impl Iterator<Item = &Gate> {
678        self.ops.iter().filter_map(Op::as_gate)
679    }
680}
681
682#[derive(Clone, Debug)]
683pub struct Program {
684    pub name: String,
685    pub profile: Profile,
686    pub num_qubits: u32,
687    pub num_results: u32,
688    pub entry: BlockId,
689    pub blocks: Vec<Block>,
690    pub next_value: u32,
691    pub num_slots: u32,
692}
693
694impl Program {
695    pub fn new(name: impl Into<String>, profile: Profile) -> Self {
696        Self {
697            name: name.into(),
698            profile,
699            num_qubits: 0,
700            num_results: 0,
701            entry: BlockId(0),
702            blocks: Vec::new(),
703            next_value: 0,
704            num_slots: 0,
705        }
706    }
707
708    pub fn block(&self, id: BlockId) -> &Block {
709        &self.blocks[id.index()]
710    }
711
712    pub fn ops(&self) -> impl Iterator<Item = &Op> {
713        self.blocks.iter().flat_map(|b| b.ops.iter())
714    }
715
716    pub fn gates(&self) -> impl Iterator<Item = &Gate> {
717        self.blocks.iter().flat_map(|b| b.gates())
718    }
719
720    pub fn gate_count(&self) -> usize {
721        self.gates().count()
722    }
723
724    pub fn op_count(&self) -> usize {
725        self.blocks.iter().map(|b| b.ops.len()).sum()
726    }
727
728    pub fn measure_count(&self) -> usize {
729        self.ops()
730            .filter(|o| matches!(o, Op::Measure { .. }))
731            .count()
732    }
733
734    pub fn is_straight_line(&self) -> bool {
735        self.blocks.len() == 1 && self.blocks[0].term.successors().is_empty()
736    }
737
738    pub fn depth(&self) -> usize {
739        let mut per_wire: HashMap<QubitId, usize> = HashMap::new();
740        for gate in self.gates() {
741            let level = gate
742                .wires()
743                .map(|q| per_wire.get(&q).copied().unwrap_or(0))
744                .max()
745                .unwrap_or(0)
746                + 1;
747            for wire in gate.wires() {
748                per_wire.insert(wire, level);
749            }
750        }
751        per_wire.into_values().max().unwrap_or(0)
752    }
753
754    pub fn predecessors(&self, id: BlockId) -> Vec<BlockId> {
755        self.blocks
756            .iter()
757            .filter(|b| b.term.successors().contains(&id))
758            .map(|b| b.id)
759            .collect()
760    }
761
762    pub fn reachable(&self) -> Vec<bool> {
763        let mut seen = vec![false; self.blocks.len()];
764        let mut stack = vec![self.entry];
765
766        while let Some(id) = stack.pop() {
767            let index = id.index();
768            if index >= seen.len() || seen[index] {
769                continue;
770            }
771            seen[index] = true;
772            for next in self.blocks[index].term.successors() {
773                stack.push(next);
774            }
775        }
776
777        seen
778    }
779}
780
781impl fmt::Display for Program {
782    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
783        writeln!(
784            f,
785            "program {} [{}] qubits={} results={}",
786            self.name,
787            self.profile.name(),
788            self.num_qubits,
789            self.num_results
790        )?;
791
792        for block in &self.blocks {
793            writeln!(f, "{}:", block.label)?;
794            for op in &block.ops {
795                writeln!(f, "  {}", render_op(op))?;
796            }
797            writeln!(f, "  {}", render_term(self, &block.term))?;
798        }
799
800        Ok(())
801    }
802}
803
804fn render_operand(operand: &Operand) -> String {
805    match operand {
806        Operand::Const(Const::Bool(b)) => b.to_string(),
807        Operand::Const(Const::Int(i)) => i.to_string(),
808        Operand::Const(Const::Float(x)) => format!("{x}"),
809        Operand::Value(v) => format!("%{}", v.0),
810    }
811}
812
813fn render_op(op: &Op) -> String {
814    match op {
815        Op::Gate(gate) => {
816            let mut out = "c".repeat(gate.controls.len());
817            out.push_str(gate.kind.name());
818            if !gate.params.is_empty() {
819                let params: Vec<String> = gate.params.iter().map(render_operand).collect();
820                out.push_str(&format!("({})", params.join(", ")));
821            }
822            let wires = gate
823                .wires()
824                .map(|q| format!("q{}", q.0))
825                .collect::<Vec<_>>();
826            out.push_str(&format!(" {}", wires.join(", ")));
827            out
828        }
829        Op::Measure { qubit, result, .. } => format!("measure q{} -> r{}", qubit.0, result.0),
830        Op::Reset { qubit, .. } => format!("reset q{}", qubit.0),
831        Op::Assign {
832            dest,
833            ty,
834            expr: expr @ Expr::Cast { .. },
835            ..
836        } => format!("%{} = {} to {ty}", dest.0, render_expr(expr)),
837        Op::Assign { dest, expr, .. } => format!("%{} = {}", dest.0, render_expr(expr)),
838        Op::RecordOutput {
839            kind,
840            result,
841            value,
842            label,
843            ..
844        } => {
845            let target = match (result, value) {
846                (Some(r), _) => format!("r{}", r.0),
847                (None, Some(v)) => render_operand(v),
848                (None, None) => "-".into(),
849            };
850            match label {
851                Some(l) => format!("record {kind:?} {target} as {l:?}"),
852                None => format!("record {kind:?} {target}"),
853            }
854        }
855        Op::Message { text, .. } => format!("message {text:?}"),
856        Op::Store { slot, value, .. } => {
857            format!("store s{} = {}", slot.0, render_operand(value))
858        }
859    }
860}
861
862fn render_expr(expr: &Expr) -> String {
863    match expr {
864        Expr::Const(c) => render_operand(&Operand::Const(*c)),
865        Expr::Binary { op, lhs, rhs } => format!(
866            "{} {} {}",
867            op.keyword(),
868            render_operand(lhs),
869            render_operand(rhs)
870        ),
871        Expr::ICmp { pred, lhs, rhs, .. } => format!(
872            "icmp {} {} {}",
873            pred.keyword(),
874            render_operand(lhs),
875            render_operand(rhs)
876        ),
877        Expr::FCmp { pred, lhs, rhs, .. } => format!(
878            "fcmp {} {} {}",
879            pred.keyword(),
880            render_operand(lhs),
881            render_operand(rhs)
882        ),
883        Expr::Select {
884            cond,
885            if_true,
886            if_false,
887        } => format!(
888            "select {} {} {}",
889            render_operand(cond),
890            render_operand(if_true),
891            render_operand(if_false)
892        ),
893        Expr::Cast { op, operand, .. } => format!("{} {}", op.keyword(), render_operand(operand)),
894        Expr::Phi(incoming) => {
895            let parts: Vec<String> = incoming
896                .iter()
897                .map(|(b, o)| format!("[{} {}]", b.0, render_operand(o)))
898                .collect();
899            format!("phi {}", parts.join(" "))
900        }
901        Expr::ReadResult(r) => format!("read r{}", r.0),
902        Expr::Load(slot) => format!("load s{}", slot.0),
903    }
904}
905
906fn render_term(program: &Program, term: &Term) -> String {
907    let label = |id: &BlockId| program.block(*id).label.as_str();
908
909    match term {
910        Term::Ret(None) => "ret".into(),
911        Term::Ret(Some(o)) => format!("ret {}", render_operand(o)),
912        Term::Br(b) => format!("br {}", label(b)),
913        Term::CondBr {
914            cond,
915            if_true,
916            if_false,
917        } => format!(
918            "br {} ? {} : {}",
919            render_operand(cond),
920            label(if_true),
921            label(if_false)
922        ),
923        Term::Switch {
924            scrutinee,
925            cases,
926            default,
927        } => {
928            let parts: Vec<String> = cases
929                .iter()
930                .map(|(v, b)| format!("{v} => {}", label(b)))
931                .collect();
932            format!(
933                "switch {} [{}] else {}",
934                render_operand(scrutinee),
935                parts.join(", "),
936                label(default)
937            )
938        }
939        Term::Unreachable => "unreachable".into(),
940    }
941}
942
943pub(crate) fn keep_marked(ops: &mut Vec<Op>, keep: &[bool]) {
944    let mut keep = keep.iter();
945    ops.retain(|_| keep.next().copied().unwrap_or(true));
946}
947
948#[cfg(test)]
949mod tests {
950    use super::*;
951
952    #[test]
953    fn adjoints() {
954        assert_eq!(GateKind::S.adjoint(), Some(GateKind::SDag));
955        assert_eq!(GateKind::SDag.adjoint(), Some(GateKind::S));
956        assert_eq!(GateKind::T.adjoint(), Some(GateKind::TDag));
957        assert_eq!(GateKind::H.adjoint(), Some(GateKind::H));
958        assert_eq!(GateKind::Rz.adjoint(), None);
959    }
960
961    #[test]
962    fn operands() {
963        let v = |i| Operand::Value(ValueId(i));
964        let two = Operand::Const(Const::Int(2));
965
966        let select = Expr::Select {
967            cond: v(0),
968            if_true: v(1),
969            if_false: two,
970        };
971        assert_eq!(select.operands(), [v(0), v(1), two]);
972
973        let phi = Op::Assign {
974            dest: ValueId(9),
975            ty: Scalar::Int(64),
976            expr: Expr::Phi(vec![(BlockId(0), v(3)), (BlockId(1), v(4))]),
977            span: Span::DUMMY,
978        };
979        assert_eq!(phi.operands(), [v(3), v(4)]);
980
981        assert_eq!(Term::Ret(Some(v(5))).operand(), Some(v(5)));
982        assert_eq!(Term::Br(BlockId(0)).operand(), None);
983    }
984
985    #[test]
986    fn constants() {
987        let known = HashMap::from([(ValueId(0), Const::Float(0.5))]);
988        assert_eq!(
989            Operand::Value(ValueId(0)).resolve(&known),
990            Some(Const::Float(0.5))
991        );
992        assert_eq!(Operand::Value(ValueId(1)).resolve(&known), None);
993
994        let gate = Gate {
995            kind: GateKind::Rz,
996            controls: Vec::new(),
997            targets: vec![QubitId(0)],
998            params: vec![Operand::Const(Const::Int(2)), Operand::Value(ValueId(0))],
999            span: Span::DUMMY,
1000        };
1001        assert_eq!(gate.constant_params(), [2.0]);
1002    }
1003}