Skip to main content

qirc/
codegen.rs

1use std::collections::{HashMap, HashSet};
2use std::f64::consts::PI;
3use std::fmt::{self, Write as _};
4use std::mem;
5
6use crate::ir::*;
7use crate::simulator::matrix::Matrix2;
8use crate::synth::Synth;
9use crate::transpile::{self, GateSet};
10use crate::verify;
11
12pub fn emit_qasm3(program: &Program) -> Result<String, String> {
13    QasmWriter::new(program)?.emit()
14}
15
16struct QasmWriter<'a> {
17    program: &'a Program,
18    out: String,
19    types: Types,
20    reads: HashMap<ValueId, ResultId>,
21    incoming: HashMap<BlockId, Vec<(ValueId, Operand)>>,
22    post: Option<HashMap<BlockId, HashSet<BlockId>>>,
23    outputs: HashMap<(BlockId, usize), usize>,
24    written: HashSet<BlockId>,
25    repeated: bool,
26}
27
28impl<'a> QasmWriter<'a> {
29    fn new(program: &'a Program) -> Result<Self, String> {
30        let mut operands = Vec::new();
31        let mut incoming: HashMap<BlockId, Vec<(ValueId, Operand)>> = HashMap::new();
32        let mut measured: HashMap<ResultId, usize> = HashMap::new();
33
34        for op in program.ops() {
35            operands.extend(op.operands());
36            match op {
37                Op::Assign {
38                    dest,
39                    expr: Expr::Phi(edges),
40                    ..
41                } => {
42                    for (block, operand) in edges {
43                        incoming.entry(*block).or_default().push((*dest, *operand));
44                    }
45                }
46                Op::Assign {
47                    expr: Expr::Const(c),
48                    ..
49                } => operands.push(Operand::Const(*c)),
50                Op::Measure { result, .. } => *measured.entry(*result).or_default() += 1,
51                _ => {}
52            }
53        }
54
55        if operands
56            .iter()
57            .any(|o| matches!(o, Operand::Const(Const::Float(f)) if !f.is_finite()))
58        {
59            return Err("an infinite or NaN constant cannot be written as OpenQASM 3".into());
60        }
61
62        let has_switch = program
63            .blocks
64            .iter()
65            .any(|b| matches!(b.term, Term::Switch { .. }));
66        let post = if has_switch {
67            None
68        } else {
69            post_dominators(program)
70        };
71
72        let looping = looping_blocks(program);
73        if program.blocks.iter().any(|block| {
74            looping.contains(&block.id)
75                && block.ops.iter().any(|op| {
76                    matches!(
77                        op,
78                        Op::RecordOutput {
79                            value: Some(_),
80                            kind: OutputKind::Bool | OutputKind::Int | OutputKind::Double,
81                            ..
82                        }
83                    )
84                })
85        }) {
86            return Err("a value recorded inside a loop cannot be written as OpenQASM 3".into());
87        }
88
89        let idom = verify::immediate_dominators(program);
90        let mut sites = HashMap::new();
91        let mut reads = HashMap::new();
92        for block in &program.blocks {
93            for (index, op) in block.ops.iter().enumerate() {
94                match op {
95                    Op::Measure { result, .. } => {
96                        sites.insert(*result, (block.id, index));
97                    }
98                    Op::Assign {
99                        dest,
100                        expr: Expr::ReadResult(result),
101                        ..
102                    } if measured.get(result) == Some(&1) => {
103                        let before = match sites.get(result) {
104                            Some(&(site, _)) if site != block.id => {
105                                looping.is_empty() && verify::dominates(&idom, site, block.id)
106                            }
107                            Some(&(_, at)) => at < index,
108                            None => false,
109                        };
110                        if before {
111                            reads.insert(*dest, *result);
112                        }
113                    }
114                    _ => {}
115                }
116            }
117        }
118
119        Ok(Self {
120            program,
121            out: String::new(),
122            types: Types::new(program),
123            reads,
124            incoming,
125            post,
126            outputs: HashMap::new(),
127            written: HashSet::new(),
128            repeated: false,
129        })
130    }
131
132    fn emit(mut self) -> Result<String, String> {
133        let program = self.program;
134        self.out
135            .push_str("OPENQASM 3.0;\ninclude \"stdgates.inc\";\n");
136        if program.gates().any(|g| g.kind == GateKind::SXDag) {
137            self.out.push_str("gate sxdg a { inv @ sx a; }\n");
138        }
139        if program
140            .gates()
141            .any(|g| g.kind == GateKind::Z && g.controls.len() == 2)
142        {
143            self.out
144                .push_str("gate ccz a, b, c { h c; ccx a, b, c; h c; }\n");
145        }
146        self.out.push('\n');
147        if program.num_qubits > 0 {
148            writeln!(self.out, "qubit[{}] q;", program.num_qubits).unwrap();
149        }
150        if program.num_results > 0 {
151            writeln!(self.out, "bit[{}] c;", program.num_results).unwrap();
152        }
153        self.declare();
154        self.out.push('\n');
155
156        if program.blocks.is_empty() {
157            return Ok(self.out);
158        }
159        let start = self.out.len();
160        if self.post.is_some() {
161            self.region(program.entry, None, 0)?;
162        }
163        if self.post.is_none() || self.repeated {
164            self.out.truncate(start);
165            self.dispatch()?;
166        }
167        Ok(self.out)
168    }
169
170    fn declare(&mut self) {
171        for op in self.program.ops() {
172            let Op::Assign { dest, ty, expr, .. } = op else {
173                continue;
174            };
175            if self.reads.contains_key(dest) {
176                continue;
177            }
178            declare_var(&mut self.out, *ty, format_args!("v{}", dest.0));
179            if matches!(expr, Expr::Phi(_)) {
180                declare_var(&mut self.out, *ty, format_args!("v{}_in", dest.0));
181            }
182        }
183
184        let mut slots: Vec<_> = self.types.slots.iter().collect();
185        slots.sort_by_key(|(slot, _)| slot.0);
186        for (slot, ty) in slots {
187            declare_var(&mut self.out, *ty, format_args!("s{}", slot.0));
188        }
189
190        for block in &self.program.blocks {
191            for (index, op) in block.ops.iter().enumerate() {
192                if let Op::RecordOutput {
193                    kind: kind @ (OutputKind::Bool | OutputKind::Int | OutputKind::Double),
194                    value: Some(_),
195                    ..
196                } = op
197                {
198                    let number = self.outputs.len();
199                    self.outputs.insert((block.id, index), number);
200                    let ty = match kind {
201                        OutputKind::Bool => "bool",
202                        OutputKind::Double => "float[64]",
203                        _ => "int[64]",
204                    };
205                    writeln!(self.out, "output {ty} out{number};").unwrap();
206                }
207            }
208        }
209    }
210
211    fn region(
212        &mut self,
213        start: BlockId,
214        stop: Option<BlockId>,
215        depth: usize,
216    ) -> Result<(), String> {
217        let program = self.program;
218        let indent = "    ".repeat(depth);
219        let mut current = start;
220
221        while Some(current) != stop {
222            if !self.written.insert(current) {
223                self.repeated = true;
224                return Ok(());
225            }
226            self.body(current, &indent)?;
227
228            match &program.block(current).term {
229                Term::Ret(_) | Term::Unreachable | Term::Switch { .. } => return Ok(()),
230                Term::Br(next) => current = *next,
231                Term::CondBr {
232                    cond,
233                    if_true,
234                    if_false,
235                } => {
236                    let join = self.join(current);
237                    let condition = self.condition(cond);
238                    let taken = self.nested(*if_true, join, depth + 1)?;
239                    let skipped = self.nested(*if_false, join, depth + 1)?;
240                    match (taken.is_empty(), skipped.is_empty()) {
241                        (true, true) => Ok(()),
242                        (false, true) => {
243                            write!(self.out, "{indent}if ({condition}) {{\n{taken}{indent}}}\n")
244                        }
245                        (true, false) => write!(
246                            self.out,
247                            "{indent}if (!({condition})) {{\n{skipped}{indent}}}\n"
248                        ),
249                        (false, false) => write!(
250                            self.out,
251                            "{indent}if ({condition}) {{\n{taken}{indent}}} else {{\n{skipped}{indent}}}\n"
252                        ),
253                    }
254                    .unwrap();
255                    match join {
256                        Some(next) => current = next,
257                        None => return Ok(()),
258                    }
259                }
260            }
261        }
262
263        Ok(())
264    }
265
266    fn nested(
267        &mut self,
268        start: BlockId,
269        stop: Option<BlockId>,
270        depth: usize,
271    ) -> Result<String, String> {
272        let outer = mem::take(&mut self.out);
273        let done = self.region(start, stop, depth);
274        let inner = mem::replace(&mut self.out, outer);
275        done.map(|()| inner)
276    }
277
278    fn dispatch(&mut self) -> Result<(), String> {
279        let program = self.program;
280        let number = |id: &BlockId| id.0 + 1;
281
282        writeln!(self.out, "uint[32] block = {};", number(&program.entry)).unwrap();
283        writeln!(self.out, "while (block != 0) {{").unwrap();
284        for block in &program.blocks {
285            writeln!(self.out, "    if (block == {}) {{", number(&block.id)).unwrap();
286            self.body(block.id, "        ")?;
287            let jump = match &block.term {
288                Term::Ret(_) | Term::Unreachable => "block = 0;".to_string(),
289                Term::Br(next) => format!("block = {};", number(next)),
290                Term::CondBr {
291                    cond,
292                    if_true,
293                    if_false,
294                } => format!(
295                    "if ({}) {{ block = {}; }} else {{ block = {}; }}",
296                    self.condition(cond),
297                    number(if_true),
298                    number(if_false)
299                ),
300                Term::Switch {
301                    scrutinee,
302                    cases,
303                    default,
304                } => {
305                    let key = self.value(scrutinee);
306                    let mut text = String::new();
307                    for (case, target) in cases {
308                        write!(
309                            text,
310                            "if ({key} == {case}) {{ block = {}; }} else ",
311                            number(target)
312                        )
313                        .unwrap();
314                    }
315                    format!("{text}{{ block = {}; }}", number(default))
316                }
317            };
318            writeln!(self.out, "        {jump}\n    }}").unwrap();
319        }
320        writeln!(self.out, "}}").unwrap();
321        Ok(())
322    }
323
324    fn body(&mut self, id: BlockId, indent: &str) -> Result<(), String> {
325        let block = self.program.block(id);
326        for op in &block.ops {
327            if let Op::Assign {
328                dest,
329                expr: Expr::Phi(_),
330                ..
331            } = op
332            {
333                writeln!(self.out, "{indent}v{0} = v{0}_in;", dest.0).unwrap();
334            }
335        }
336        for (index, op) in block.ops.iter().enumerate() {
337            self.op(op, indent)?;
338            if let (Some(number), Op::RecordOutput { value: Some(v), .. }) =
339                (self.outputs.get(&(id, index)), op)
340            {
341                let value = self.value(v);
342                writeln!(self.out, "{indent}out{number} = {value};").unwrap();
343            }
344        }
345        if let Some(edges) = self.incoming.get(&id) {
346            for (dest, operand) in edges {
347                let value = self.value(operand);
348                writeln!(self.out, "{indent}v{}_in = {value};", dest.0).unwrap();
349            }
350        }
351        Ok(())
352    }
353
354    fn op(&mut self, op: &Op, indent: &str) -> Result<(), String> {
355        match op {
356            Op::Gate(gate) => {
357                let params: Vec<String> = gate.params.iter().map(|p| self.angle(p)).collect();
358                writeln!(self.out, "{indent}{}", qasm_gate(gate, &params)).unwrap();
359            }
360            Op::Measure { qubit, result, .. } => {
361                writeln!(
362                    self.out,
363                    "{indent}c[{}] = measure q[{}];",
364                    result.0, qubit.0
365                )
366                .unwrap();
367            }
368            Op::Reset { qubit, .. } => {
369                writeln!(self.out, "{indent}reset q[{}];", qubit.0).unwrap();
370            }
371            Op::Assign { dest, ty, expr, .. } => self.assign(*dest, *ty, expr, indent)?,
372            Op::Store { slot, value, .. } => {
373                let value = self.value(value);
374                writeln!(self.out, "{indent}s{} = {value};", slot.0).unwrap();
375            }
376            Op::RecordOutput { .. } | Op::Message { .. } => {}
377        }
378        Ok(())
379    }
380
381    fn assign(
382        &mut self,
383        dest: ValueId,
384        ty: Scalar,
385        expr: &Expr,
386        indent: &str,
387    ) -> Result<(), String> {
388        if self.reads.contains_key(&dest) {
389            return Ok(());
390        }
391        let name = format!("v{}", dest.0);
392        let rhs = match expr {
393            Expr::Phi(_) => return Ok(()),
394            Expr::Const(c) => self.value(&Operand::Const(*c)),
395            Expr::ReadResult(result) => format!("bool(c[{}])", result.0),
396            Expr::Load(slot) => format!("s{}", slot.0),
397            Expr::Binary { op, lhs, rhs } => self.binary(*op, ty, lhs, rhs)?,
398            Expr::ICmp { pred, ty, lhs, rhs } => self.icmp(*pred, *ty, lhs, rhs),
399            Expr::FCmp { pred, lhs, rhs, .. } => self.fcmp(*pred, lhs, rhs),
400            Expr::Cast { op, from, operand } => self.cast(*op, *from, ty, operand)?,
401            Expr::Select {
402                cond,
403                if_true,
404                if_false,
405            } => {
406                let condition = self.condition(cond);
407                let (a, b) = (self.value(if_true), self.value(if_false));
408                writeln!(
409                    self.out,
410                    "{indent}if ({condition}) {{ {name} = {a}; }} else {{ {name} = {b}; }}"
411                )
412                .unwrap();
413                return Ok(());
414            }
415        };
416        writeln!(self.out, "{indent}{name} = {rhs};").unwrap();
417        Ok(())
418    }
419
420    fn binary(
421        &self,
422        op: BinOp,
423        ty: Scalar,
424        lhs: &Operand,
425        rhs: &Operand,
426    ) -> Result<String, String> {
427        let (a, b) = (self.value(lhs), self.value(rhs));
428
429        if ty == Scalar::Bool {
430            return match op {
431                BinOp::And | BinOp::Mul => Ok(format!("{a} && {b}")),
432                BinOp::Or => Ok(format!("{a} || {b}")),
433                BinOp::Xor | BinOp::Add | BinOp::Sub => Ok(format!("{a} != {b}")),
434                _ => Err(format!(
435                    "`{}` on booleans cannot be written as OpenQASM 3",
436                    op.keyword()
437                )),
438            };
439        }
440
441        let unsigned = |symbol: &str| {
442            let (a, b) = (unsigned(&a, ty), unsigned(&b, ty));
443            wrapped(&format!("int[64]({a} {symbol} {b})"), ty)
444        };
445        Ok(match op {
446            BinOp::FAdd => format!("{a} + {b}"),
447            BinOp::FSub => format!("{a} - {b}"),
448            BinOp::FMul => format!("{a} * {b}"),
449            BinOp::FDiv => format!("{a} / {b}"),
450            BinOp::Add => wrapped(&format!("{a} + {b}"), ty),
451            BinOp::Sub => wrapped(&format!("{a} - {b}"), ty),
452            BinOp::Mul => wrapped(&format!("{a} * {b}"), ty),
453            BinOp::SDiv => wrapped(&format!("{a} / {b}"), ty),
454            BinOp::SRem => format!("{a} % {b}"),
455            BinOp::Shl => wrapped(&format!("{a} << {b}"), ty),
456            BinOp::AShr => format!("{a} >> {b}"),
457            BinOp::And => format!("{a} & {b}"),
458            BinOp::Or => format!("{a} | {b}"),
459            BinOp::Xor => format!("{a} ^ {b}"),
460            BinOp::UDiv => unsigned("/"),
461            BinOp::URem => unsigned("%"),
462            BinOp::LShr => unsigned(">>"),
463            BinOp::FRem => {
464                return Err("a floating point remainder cannot be written as OpenQASM 3".into());
465            }
466        })
467    }
468
469    fn icmp(&self, pred: IntPredicate, ty: Scalar, lhs: &Operand, rhs: &Operand) -> String {
470        let (a, b) = (self.value(lhs), self.value(rhs));
471        let (symbol, signed) = match pred {
472            IntPredicate::Eq => return format!("{a} == {b}"),
473            IntPredicate::Ne => return format!("{a} != {b}"),
474            IntPredicate::Slt => ("<", true),
475            IntPredicate::Sle => ("<=", true),
476            IntPredicate::Sgt => (">", true),
477            IntPredicate::Sge => (">=", true),
478            IntPredicate::Ult => ("<", false),
479            IntPredicate::Ule => ("<=", false),
480            IntPredicate::Ugt => (">", false),
481            IntPredicate::Uge => (">=", false),
482        };
483        let side = |x: &str| match (ty, signed) {
484            (Scalar::Bool, true) => format!("-int[64]({x})"),
485            (Scalar::Bool, false) => format!("int[64]({x})"),
486            (_, true) => x.to_string(),
487            (_, false) => unsigned(x, ty),
488        };
489        format!("{} {symbol} {}", side(&a), side(&b))
490    }
491
492    fn fcmp(&self, pred: FloatPredicate, lhs: &Operand, rhs: &Operand) -> String {
493        let (a, b) = (self.value(lhs), self.value(rhs));
494        match pred {
495            FloatPredicate::True => "true".into(),
496            FloatPredicate::False => "false".into(),
497            FloatPredicate::Oeq => format!("{a} == {b}"),
498            FloatPredicate::Une => format!("{a} != {b}"),
499            FloatPredicate::Ogt => format!("{a} > {b}"),
500            FloatPredicate::Oge => format!("{a} >= {b}"),
501            FloatPredicate::Olt => format!("{a} < {b}"),
502            FloatPredicate::Ole => format!("{a} <= {b}"),
503            FloatPredicate::One => format!("({a} < {b} || {a} > {b})"),
504            FloatPredicate::Ueq => format!("!({a} < {b} || {a} > {b})"),
505            FloatPredicate::Ugt => format!("!({a} <= {b})"),
506            FloatPredicate::Uge => format!("!({a} < {b})"),
507            FloatPredicate::Ult => format!("!({a} >= {b})"),
508            FloatPredicate::Ule => format!("!({a} > {b})"),
509            FloatPredicate::Ord => format!("({a} == {a} && {b} == {b})"),
510            FloatPredicate::Uno => format!("({a} != {a} || {b} != {b})"),
511        }
512    }
513
514    fn cast(
515        &self,
516        op: CastOp,
517        from: Scalar,
518        to: Scalar,
519        operand: &Operand,
520    ) -> Result<String, String> {
521        let x = self.value(operand);
522        let integer = |x: String| match to {
523            Scalar::Bool => format!("({x} & 1) == 1"),
524            _ => wrapped(&x, to),
525        };
526        let float = |x: String| format!("{}({x})", qasm_type(to));
527        Ok(match (op, from) {
528            _ if from == to => x,
529            (CastOp::ZExt | CastOp::UIToFP, Scalar::Bool) if to.is_float() => {
530                float(format!("int[64]({x})"))
531            }
532            (CastOp::SExt | CastOp::SIToFP, Scalar::Bool) if to.is_float() => {
533                float(format!("-int[64]({x})"))
534            }
535            (CastOp::ZExt | CastOp::UIToFP, Scalar::Bool) => format!("int[64]({x})"),
536            (CastOp::SExt | CastOp::SIToFP, Scalar::Bool) => format!("-int[64]({x})"),
537            (CastOp::Trunc | CastOp::SExt, _) => integer(x),
538            (CastOp::ZExt, _) => integer(format!("int[64]({})", unsigned(&x, from))),
539            (CastOp::SIToFP | CastOp::FPExt | CastOp::FPTrunc, _) => float(x),
540            (CastOp::UIToFP, _) => float(unsigned(&x, from)),
541            (CastOp::FPToSI | CastOp::FPToUI, _) => integer(format!("int[64]({x})")),
542            (CastOp::PtrToInt | CastOp::IntToPtr | CastOp::BitCast | CastOp::AddrSpaceCast, _) => {
543                return Err(format!(
544                    "`{}` cannot be written as OpenQASM 3",
545                    op.keyword()
546                ));
547            }
548        })
549    }
550
551    fn condition(&self, cond: &Operand) -> String {
552        let value = self.value(cond);
553        if self.type_of(cond) == Scalar::Bool {
554            value
555        } else {
556            format!("{value} != 0")
557        }
558    }
559
560    fn angle(&self, operand: &Operand) -> String {
561        match operand {
562            Operand::Const(c) => c.as_f64().to_string(),
563            Operand::Value(_) if self.type_of(operand) == Scalar::Double => self.value(operand),
564            Operand::Value(_) => format!("float[64]({})", self.value(operand)),
565        }
566    }
567
568    fn value(&self, operand: &Operand) -> String {
569        match operand {
570            Operand::Const(Const::Bool(b)) => b.to_string(),
571            Operand::Const(Const::Int(i)) if *i < 0 => format!("({i})"),
572            Operand::Const(Const::Int(i)) => i.to_string(),
573            Operand::Const(Const::Float(f)) if *f < 0.0 => format!("({f:?})"),
574            Operand::Const(Const::Float(f)) => format!("{f:?}"),
575            Operand::Value(id) => match self.reads.get(id) {
576                Some(result) => format!("c[{}]", result.0),
577                None => format!("v{}", id.0),
578            },
579        }
580    }
581
582    fn type_of(&self, operand: &Operand) -> Scalar {
583        self.types.of(operand)
584    }
585
586    fn join(&self, block: BlockId) -> Option<BlockId> {
587        let post = self.post.as_ref()?;
588        let own = &post[&block];
589        own.iter()
590            .copied()
591            .filter(|&other| other != block)
592            .find(|other| post[other].len() == own.len() - 1)
593    }
594}
595
596fn qasm_type(ty: Scalar) -> &'static str {
597    match ty {
598        Scalar::Bool => "bool",
599        Scalar::Int(_) => "int[64]",
600        Scalar::Float => "float[32]",
601        Scalar::Double => "float[64]",
602    }
603}
604
605fn declare_var(out: &mut String, ty: Scalar, name: fmt::Arguments) {
606    let zero = match ty {
607        Scalar::Bool => "false",
608        Scalar::Int(_) => "0",
609        _ => "0.0",
610    };
611    writeln!(out, "{} {name} = {zero};", qasm_type(ty)).unwrap();
612}
613
614fn wrapped(x: &str, ty: Scalar) -> String {
615    match ty {
616        Scalar::Int(bits) if bits < 64 => format!("int[64](int[{bits}]({x}))"),
617        _ => x.to_string(),
618    }
619}
620
621fn unsigned(x: &str, ty: Scalar) -> String {
622    match ty {
623        Scalar::Int(bits) if bits < 64 => format!("uint[{bits}]({x})"),
624        _ => format!("uint[64]({x})"),
625    }
626}
627
628fn looping_blocks(program: &Program) -> HashSet<BlockId> {
629    program
630        .blocks
631        .iter()
632        .filter(|block| {
633            let mut stack = block.term.successors();
634            let mut seen = HashSet::new();
635            while let Some(next) = stack.pop() {
636                if next == block.id {
637                    return true;
638                }
639                if seen.insert(next) {
640                    stack.extend(program.block(next).term.successors());
641                }
642            }
643            false
644        })
645        .map(|block| block.id)
646        .collect()
647}
648
649struct Types {
650    values: HashMap<ValueId, Scalar>,
651    slots: HashMap<SlotId, Scalar>,
652}
653
654impl Types {
655    fn new(program: &Program) -> Types {
656        let mut values = HashMap::new();
657        let mut slots = HashMap::new();
658        for op in program.ops() {
659            if let Op::Assign { dest, ty, expr, .. } = op {
660                values.insert(*dest, *ty);
661                if let Expr::Load(slot) = expr {
662                    slots.insert(*slot, *ty);
663                }
664            }
665        }
666        let mut types = Types { values, slots };
667        for op in program.ops() {
668            if let Op::Store { slot, value, .. } = op
669                && !types.slots.contains_key(slot)
670            {
671                let ty = types.of(value);
672                types.slots.insert(*slot, ty);
673            }
674        }
675        types
676    }
677
678    fn of(&self, operand: &Operand) -> Scalar {
679        match operand {
680            Operand::Const(Const::Bool(_)) => Scalar::Bool,
681            Operand::Const(Const::Int(_)) => Scalar::Int(64),
682            Operand::Const(Const::Float(_)) => Scalar::Double,
683            Operand::Value(id) => self.values.get(id).copied().unwrap_or(Scalar::Int(64)),
684        }
685    }
686}
687
688fn post_dominators(program: &Program) -> Option<HashMap<BlockId, HashSet<BlockId>>> {
689    if program.blocks.is_empty() {
690        return Some(HashMap::new());
691    }
692    let mut order = Vec::new();
693    let mut open = HashSet::from([program.entry]);
694    let mut seen = HashSet::from([program.entry]);
695    let mut stack = vec![(program.entry, 0)];
696
697    while let Some(top) = stack.last_mut() {
698        let (block, index) = *top;
699        match program.block(block).term.successors().get(index) {
700            Some(&next) => {
701                top.1 += 1;
702                if open.contains(&next) {
703                    return None;
704                }
705                if seen.insert(next) {
706                    open.insert(next);
707                    stack.push((next, 0));
708                }
709            }
710            None => {
711                stack.pop();
712                open.remove(&block);
713                order.push(block);
714            }
715        }
716    }
717
718    let mut post: HashMap<BlockId, HashSet<BlockId>> = HashMap::new();
719    for block in order {
720        let mut shared: Option<HashSet<BlockId>> = None;
721        for next in program.block(block).term.successors() {
722            let theirs = &post[&next];
723            shared = Some(match shared {
724                Some(set) => set.intersection(theirs).copied().collect(),
725                None => theirs.clone(),
726            });
727        }
728        let mut set = shared.unwrap_or_default();
729        set.insert(block);
730        post.insert(block, set);
731    }
732
733    Some(post)
734}
735
736fn qasm_name(kind: GateKind, controls: usize) -> String {
737    let base = match kind {
738        GateKind::I => "id",
739        GateKind::R1 => "p",
740        other => other.name(),
741    };
742
743    match (controls, base) {
744        (0, _) => base.to_string(),
745        (1, "x") => "cx".into(),
746        (1, "y") => "cy".into(),
747        (1, "z") => "cz".into(),
748        (1, "h") => "ch".into(),
749        (1, "p") => "cp".into(),
750        (1, "rx") => "crx".into(),
751        (1, "ry") => "cry".into(),
752        (1, "rz") => "crz".into(),
753        (1, "swap") => "cswap".into(),
754        (2, "x") => "ccx".into(),
755        (2, "z") => "ccz".into(),
756        (n, _) => format!("{}{base}", "ctrl @ ".repeat(n)),
757    }
758}
759
760fn qasm_gate(gate: &Gate, params: &[String]) -> String {
761    let wires = qasm_wires(gate);
762    if let GateKind::Unitary(m) = gate.kind {
763        let (theta, phi, lambda) = zyz_angles(&Matrix2::from_ir(m));
764        return format!("U({theta}, {phi}, {lambda}) {wires};");
765    }
766    let name = qasm_name(gate.kind, gate.controls.len());
767
768    if params.is_empty() {
769        format!("{name} {wires};")
770    } else {
771        format!("{name}({}) {wires};", params.join(", "))
772    }
773}
774
775fn qasm_wires(gate: &Gate) -> String {
776    gate.wires()
777        .map(|q| format!("q[{}]", q.0))
778        .collect::<Vec<_>>()
779        .join(", ")
780}
781
782pub fn zyz_angles(m: &Matrix2) -> (f64, f64, f64) {
783    let Matrix2 { a, b, c, d } = *m;
784
785    let theta = 2.0 * a.norm().clamp(-1.0, 1.0).acos();
786
787    if b.norm() < 1e-12 && c.norm() < 1e-12 {
788        let phase = (d / a).arg();
789        return (0.0, phase, 0.0);
790    }
791
792    if a.norm() < 1e-12 {
793        return (PI, (c / -b).arg(), 0.0);
794    }
795
796    let phi = (c / a).arg();
797    let lambda = ((-b) / a).arg();
798
799    (theta, phi, lambda)
800}
801
802pub fn emit_qir(program: &Program) -> Result<String, String> {
803    QirEmitter::new(program).emit()
804}
805
806struct QirEmitter<'a> {
807    program: &'a Program,
808    out: String,
809    declarations: Vec<(String, String)>,
810    types: Types,
811    constants: HashMap<ValueId, Const>,
812    blocks: Vec<String>,
813    labels: Vec<String>,
814    prefix: &'static str,
815    legacy: bool,
816    native: Option<(GateSet, Synth)>,
817}
818
819impl<'a> QirEmitter<'a> {
820    fn new(program: &'a Program) -> Self {
821        let constants = program
822            .ops()
823            .filter_map(|op| match op {
824                Op::Assign {
825                    dest,
826                    expr: Expr::Const(c),
827                    ..
828                } => Some((*dest, *c)),
829                _ => None,
830            })
831            .collect();
832        let legacy = program.ops().any(|op| {
833            matches!(
834                op,
835                Op::RecordOutput {
836                    kind: OutputKind::TupleEnd | OutputKind::ArrayEnd,
837                    ..
838                } | Op::RecordOutput {
839                    kind: OutputKind::Tuple | OutputKind::Array,
840                    count: None,
841                    value: None,
842                    ..
843                }
844            )
845        });
846
847        Self {
848            program,
849            out: String::new(),
850            declarations: Vec::new(),
851            types: Types::new(program),
852            constants,
853            blocks: block_names(program),
854            labels: Vec::new(),
855            prefix: if program.name.starts_with("label") {
856                "output"
857            } else {
858                "label"
859            },
860            legacy,
861            native: None,
862        }
863    }
864
865    fn label_ref(&mut self, label: Option<&str>) -> String {
866        let Some(label) = label.filter(|l| !l.is_empty()) else {
867            return "i8* null".into();
868        };
869        let index = match self.labels.iter().position(|l| l == label) {
870            Some(index) => index,
871            None => {
872                self.labels.push(label.to_string());
873                self.labels.len() - 1
874            }
875        };
876        let size = label.len() + 1;
877        format!(
878            "i8* getelementptr inbounds ([{size} x i8], [{size} x i8]* @{}{index}, i64 0, i64 0)",
879            self.prefix
880        )
881    }
882
883    fn declare(&mut self, name: &str, params: &str) {
884        if !self.declarations.iter().any(|(n, _)| n == name) {
885            self.declarations
886                .push((name.to_string(), params.to_string()));
887        }
888    }
889
890    fn operand(&self, operand: &Operand, ty: Scalar) -> String {
891        let constant = match operand {
892            Operand::Const(c) => *c,
893            Operand::Value(id) => match self.constants.get(id) {
894                Some(c) => *c,
895                None if self.types.values.contains_key(id) => return format!("%v{}", id.0),
896                None => return "undef".into(),
897            },
898        };
899        match ty.normalize(constant) {
900            Const::Bool(b) => b.to_string(),
901            Const::Int(i) => i.to_string(),
902            Const::Float(f) => format_double(f),
903        }
904    }
905
906    fn block(&self, id: BlockId) -> &str {
907        &self.blocks[id.index()]
908    }
909
910    fn emit(mut self) -> Result<String, String> {
911        let program = self.program;
912
913        writeln!(self.out, "; ModuleID = '{}'", c_string(&program.name)).unwrap();
914        writeln!(
915            self.out,
916            "source_filename = \"{}\"",
917            c_string(&program.name)
918        )
919        .unwrap();
920        self.out.push('\n');
921        self.out
922            .push_str("%Result = type opaque\n%Qubit = type opaque\n\n");
923
924        let mut body = String::new();
925        for (index, block) in program.blocks.iter().enumerate() {
926            writeln!(body, "{}:", self.block(block.id)).unwrap();
927            if index == 0 {
928                for slot in 0..program.num_slots {
929                    let ty = self
930                        .types
931                        .slots
932                        .get(&SlotId(slot))
933                        .copied()
934                        .unwrap_or(Scalar::Int(64));
935                    writeln!(body, "  %slot{slot} = alloca {ty}").unwrap();
936                }
937            }
938            for op in &block.ops {
939                self.emit_op(op, &mut body)?;
940            }
941            self.emit_terminator(&block.term, &mut body);
942        }
943
944        for (index, label) in self.labels.iter().enumerate() {
945            writeln!(
946                self.out,
947                "@{}{index} = internal constant [{} x i8] c\"{}\\00\"",
948                self.prefix,
949                label.len() + 1,
950                c_string(label)
951            )
952            .unwrap();
953        }
954        if !self.labels.is_empty() {
955            self.out.push('\n');
956        }
957
958        writeln!(
959            self.out,
960            "define void @{}() #0 {{",
961            llvm_name(&program.name)
962        )
963        .unwrap();
964        self.out.push_str(&body);
965        self.out.push_str("}\n\n");
966
967        for (name, params) in &self.declarations {
968            writeln!(self.out, "declare {name}({params})").unwrap();
969        }
970
971        self.out.push('\n');
972        writeln!(
973            self.out,
974            "attributes #0 = {{ \"entry_point\" \"output_labeling_schema\" \"qir_profiles\"=\"{}\" \"required_num_qubits\"=\"{}\" \"required_num_results\"=\"{}\" }}",
975            program.profile.name(),
976            program.num_qubits,
977            program.num_results
978        ).unwrap();
979
980        self.out.push('\n');
981        self.out
982            .push_str("!llvm.module.flags = !{!0, !1, !2, !3}\n\n");
983        self.out
984            .push_str("!0 = !{i32 1, !\"qir_major_version\", i32 1}\n");
985        self.out
986            .push_str("!1 = !{i32 7, !\"qir_minor_version\", i32 0}\n");
987        self.out
988            .push_str("!2 = !{i32 1, !\"dynamic_qubit_management\", i1 false}\n");
989        self.out
990            .push_str("!3 = !{i32 1, !\"dynamic_result_management\", i1 false}\n");
991
992        Ok(self.out)
993    }
994
995    fn emit_op(&mut self, op: &Op, body: &mut String) -> Result<(), String> {
996        match op {
997            Op::Gate(gate) => self.emit_gate(gate, body)?,
998
999            Op::Measure { qubit, result, .. } => {
1000                writeln!(
1001                    body,
1002                    "  call void @__quantum__qis__mz__body({}, {})",
1003                    qubit_ref(*qubit),
1004                    result_ref(*result)
1005                )
1006                .unwrap();
1007                self.declare(
1008                    "void @__quantum__qis__mz__body",
1009                    "%Qubit*, %Result* writeonly",
1010                );
1011            }
1012
1013            Op::Reset { qubit, .. } => {
1014                writeln!(
1015                    body,
1016                    "  call void @__quantum__qis__reset__body({})",
1017                    qubit_ref(*qubit)
1018                )
1019                .unwrap();
1020                self.declare("void @__quantum__qis__reset__body", "%Qubit*");
1021            }
1022
1023            Op::RecordOutput {
1024                kind,
1025                result,
1026                value,
1027                count,
1028                label,
1029                ..
1030            } => {
1031                let open = count.is_none() && value.is_none();
1032                let name = match kind {
1033                    OutputKind::Result => "__quantum__rt__result_record_output",
1034                    OutputKind::Tuple if open => "__quantum__rt__tuple_start_record_output",
1035                    OutputKind::Array if open => "__quantum__rt__array_start_record_output",
1036                    OutputKind::Tuple => "__quantum__rt__tuple_record_output",
1037                    OutputKind::Array => "__quantum__rt__array_record_output",
1038                    OutputKind::TupleEnd => "__quantum__rt__tuple_end_record_output",
1039                    OutputKind::ArrayEnd => "__quantum__rt__array_end_record_output",
1040                    OutputKind::Bool => "__quantum__rt__bool_record_output",
1041                    OutputKind::Int => "__quantum__rt__int_record_output",
1042                    OutputKind::Double => "__quantum__rt__double_record_output",
1043                };
1044
1045                let mut args = Vec::new();
1046                let mut params = Vec::new();
1047                match (result, value, count) {
1048                    (Some(r), _, _) => {
1049                        args.push(result_ref(*r));
1050                        params.push("%Result*".to_string());
1051                    }
1052                    (None, Some(v), _) => {
1053                        let ty = match kind {
1054                            OutputKind::Bool => Scalar::Bool,
1055                            OutputKind::Double => Scalar::Double,
1056                            _ => Scalar::Int(64),
1057                        };
1058                        args.push(format!("{ty} {}", self.operand(v, ty)));
1059                        params.push(ty.to_string());
1060                    }
1061                    (None, None, Some(n)) => {
1062                        args.push(format!("i64 {n}"));
1063                        params.push("i64".into());
1064                    }
1065                    (None, None, None) => {}
1066                }
1067                if !self.legacy {
1068                    args.push(self.label_ref(label.as_deref()));
1069                    params.push("i8*".into());
1070                }
1071                writeln!(body, "  call void @{name}({})", args.join(", ")).unwrap();
1072                self.declare(&format!("void @{name}"), &params.join(", "));
1073            }
1074
1075            Op::Assign { dest, ty, expr, .. } => self.emit_assign(*dest, *ty, expr, body),
1076
1077            Op::Store { slot, value, .. } => {
1078                let ty = self
1079                    .types
1080                    .slots
1081                    .get(slot)
1082                    .copied()
1083                    .unwrap_or(self.types.of(value));
1084                let value = self.operand(value, ty);
1085                writeln!(body, "  store {ty} {value}, ptr %slot{}", slot.0).unwrap();
1086            }
1087
1088            Op::Message { .. } => {}
1089        }
1090        Ok(())
1091    }
1092
1093    fn emit_gate(&mut self, gate: &Gate, body: &mut String) -> Result<(), String> {
1094        if let GateKind::Unitary(matrix) = gate.kind
1095            && gate.controls.is_empty()
1096        {
1097            let (theta, phi, lambda) = zyz_angles(&Matrix2::from_ir(matrix));
1098            for (kind, angle) in [
1099                (GateKind::Rz, lambda),
1100                (GateKind::Ry, theta),
1101                (GateKind::Rz, phi),
1102            ] {
1103                let rotation = Gate {
1104                    kind,
1105                    controls: Vec::new(),
1106                    targets: gate.targets.clone(),
1107                    params: vec![Operand::Const(Const::Float(angle))],
1108                    span: gate.span,
1109                };
1110                self.emit_gate(&rotation, body)?;
1111            }
1112            return Ok(());
1113        }
1114
1115        if let Some(name) = intrinsic(gate) {
1116            let mut args = Vec::new();
1117            let mut params = Vec::new();
1118            for param in &gate.params {
1119                args.push(format!("double {}", self.operand(param, Scalar::Double)));
1120                params.push("double");
1121            }
1122            for qubit in gate.wires() {
1123                args.push(qubit_ref(qubit));
1124                params.push("%Qubit*");
1125            }
1126            writeln!(body, "  call void @{name}({})", args.join(", ")).unwrap();
1127            self.declare(&format!("void @{name}"), &params.join(", "));
1128            return Ok(());
1129        }
1130
1131        let name = format!("{}{}", "c".repeat(gate.controls.len()), gate.kind.name());
1132        if gate.params.iter().any(|p| p.constant().is_none()) {
1133            return Err(format!(
1134                "`{name}` with a runtime angle has no QIR intrinsic"
1135            ));
1136        }
1137        let (set, synth) = self.native.get_or_insert_with(|| {
1138            let set = GateSet::native();
1139            let synth = Synth::new(&set);
1140            (set, synth)
1141        });
1142        let parts = transpile::translate(gate, set, synth)
1143            .filter(|parts| parts.iter().all(|part| intrinsic(part).is_some()))
1144            .ok_or_else(|| {
1145                format!("`{name}` has no QIR intrinsic and cannot be decomposed into one")
1146            })?;
1147        for part in &parts {
1148            self.emit_gate(part, body)?;
1149        }
1150        Ok(())
1151    }
1152
1153    fn emit_assign(&mut self, dest: ValueId, ty: Scalar, expr: &Expr, body: &mut String) {
1154        let name = format!("%v{}", dest.0);
1155
1156        match expr {
1157            Expr::Const(_) => {}
1158
1159            Expr::Load(slot) => {
1160                writeln!(body, "  {name} = load {ty}, ptr %slot{}", slot.0).unwrap();
1161            }
1162
1163            Expr::ReadResult(result) => {
1164                writeln!(
1165                    body,
1166                    "  {name} = call i1 @__quantum__qis__read_result__body({})",
1167                    result_ref(*result)
1168                )
1169                .unwrap();
1170                self.declare("i1 @__quantum__qis__read_result__body", "%Result*");
1171            }
1172
1173            Expr::Binary { op, lhs, rhs } => {
1174                let (a, b) = (self.operand(lhs, ty), self.operand(rhs, ty));
1175                writeln!(body, "  {name} = {} {ty} {a}, {b}", op.keyword()).unwrap();
1176            }
1177
1178            Expr::ICmp {
1179                pred,
1180                ty: operands,
1181                lhs,
1182                rhs,
1183            } => {
1184                let (a, b) = (self.operand(lhs, *operands), self.operand(rhs, *operands));
1185                writeln!(
1186                    body,
1187                    "  {name} = icmp {} {operands} {a}, {b}",
1188                    pred.keyword()
1189                )
1190                .unwrap();
1191            }
1192
1193            Expr::FCmp {
1194                pred,
1195                ty: operands,
1196                lhs,
1197                rhs,
1198            } => {
1199                let (a, b) = (self.operand(lhs, *operands), self.operand(rhs, *operands));
1200                writeln!(
1201                    body,
1202                    "  {name} = fcmp {} {operands} {a}, {b}",
1203                    pred.keyword()
1204                )
1205                .unwrap();
1206            }
1207
1208            Expr::Select {
1209                cond,
1210                if_true,
1211                if_false,
1212            } => {
1213                let c = self.operand(cond, Scalar::Bool);
1214                let (a, b) = (self.operand(if_true, ty), self.operand(if_false, ty));
1215                writeln!(body, "  {name} = select i1 {c}, {ty} {a}, {ty} {b}").unwrap();
1216            }
1217
1218            Expr::Cast { op, from, operand } => {
1219                let value = self.operand(operand, *from);
1220                match cast_instruction(*op, *from, ty) {
1221                    Some(keyword) => {
1222                        writeln!(body, "  {name} = {keyword} {from} {value} to {ty}").unwrap();
1223                    }
1224                    None => {
1225                        writeln!(body, "  {name} = bitcast {ty} {value} to {ty}").unwrap();
1226                    }
1227                }
1228            }
1229
1230            Expr::Phi(incoming) => {
1231                let parts: Vec<String> = incoming
1232                    .iter()
1233                    .map(|(block, operand)| {
1234                        format!("[ {}, %{} ]", self.operand(operand, ty), self.block(*block))
1235                    })
1236                    .collect();
1237                writeln!(body, "  {name} = phi {ty} {}", parts.join(", ")).unwrap();
1238            }
1239        }
1240    }
1241
1242    fn emit_terminator(&self, term: &Term, body: &mut String) {
1243        match term {
1244            Term::Ret(_) => {
1245                writeln!(body, "  ret void").unwrap();
1246            }
1247            Term::Unreachable => {
1248                writeln!(body, "  unreachable").unwrap();
1249            }
1250            Term::Br(target) => {
1251                writeln!(body, "  br label %{}", self.block(*target)).unwrap();
1252            }
1253            Term::CondBr {
1254                cond,
1255                if_true,
1256                if_false,
1257            } => {
1258                writeln!(
1259                    body,
1260                    "  br i1 {}, label %{}, label %{}",
1261                    self.operand(cond, Scalar::Bool),
1262                    self.block(*if_true),
1263                    self.block(*if_false)
1264                )
1265                .unwrap();
1266            }
1267            Term::Switch {
1268                scrutinee,
1269                cases,
1270                default,
1271            } => {
1272                let ty = self.types.of(scrutinee);
1273                writeln!(
1274                    body,
1275                    "  switch {ty} {}, label %{} [",
1276                    self.operand(scrutinee, ty),
1277                    self.block(*default)
1278                )
1279                .unwrap();
1280                for (key, target) in cases {
1281                    let key = self.operand(&Operand::Const(Const::Int(*key)), ty);
1282                    writeln!(body, "    {ty} {key}, label %{}", self.block(*target)).unwrap();
1283                }
1284                writeln!(body, "  ]").unwrap();
1285            }
1286        }
1287    }
1288}
1289
1290fn intrinsic(gate: &Gate) -> Option<&'static str> {
1291    Some(match (gate.kind, gate.controls.len()) {
1292        (GateKind::I, 0) => "__quantum__qis__i__body",
1293        (GateKind::X, 0) => "__quantum__qis__x__body",
1294        (GateKind::Y, 0) => "__quantum__qis__y__body",
1295        (GateKind::Z, 0) => "__quantum__qis__z__body",
1296        (GateKind::H, 0) => "__quantum__qis__h__body",
1297        (GateKind::S, 0) => "__quantum__qis__s__body",
1298        (GateKind::SDag, 0) => "__quantum__qis__s__adj",
1299        (GateKind::T, 0) => "__quantum__qis__t__body",
1300        (GateKind::TDag, 0) => "__quantum__qis__t__adj",
1301        (GateKind::SX, 0) => "__quantum__qis__sx__body",
1302        (GateKind::SXDag, 0) => "__quantum__qis__sx__adj",
1303        (GateKind::Rx, 0) => "__quantum__qis__rx__body",
1304        (GateKind::Ry, 0) => "__quantum__qis__ry__body",
1305        (GateKind::Rz, 0) => "__quantum__qis__rz__body",
1306        (GateKind::R1, 0) => "__quantum__qis__r1__body",
1307        (GateKind::Swap, 0) => "__quantum__qis__swap__body",
1308        (GateKind::X, 1) => "__quantum__qis__cx__body",
1309        (GateKind::Y, 1) => "__quantum__qis__cy__body",
1310        (GateKind::Z, 1) => "__quantum__qis__cz__body",
1311        (GateKind::H, 1) => "__quantum__qis__ch__body",
1312        (GateKind::Rx, 1) => "__quantum__qis__crx__body",
1313        (GateKind::Ry, 1) => "__quantum__qis__cry__body",
1314        (GateKind::Rz, 1) => "__quantum__qis__crz__body",
1315        (GateKind::R1, 1) => "__quantum__qis__cr1__body",
1316        (GateKind::X, 2) => "__quantum__qis__ccx__body",
1317        (GateKind::Z, 2) => "__quantum__qis__ccz__body",
1318        (GateKind::Swap, 1) => "__quantum__qis__cswap__body",
1319        _ => return None,
1320    })
1321}
1322
1323fn cast_instruction(op: CastOp, from: Scalar, to: Scalar) -> Option<&'static str> {
1324    if from == to {
1325        return None;
1326    }
1327    let same_size = from.bits() == to.bits();
1328    Some(match (from.is_float(), to.is_float()) {
1329        (true, true) if to.bits() < from.bits() => "fptrunc",
1330        (true, true) => "fpext",
1331        (true, false) if op == CastOp::BitCast && same_size => "bitcast",
1332        (true, false) if op == CastOp::FPToUI => "fptoui",
1333        (true, false) => "fptosi",
1334        (false, true) if op == CastOp::BitCast && same_size => "bitcast",
1335        (false, true) if op == CastOp::UIToFP => "uitofp",
1336        (false, true) => "sitofp",
1337        _ if to.bits() < from.bits() => "trunc",
1338        _ if op == CastOp::SExt => "sext",
1339        _ => "zext",
1340    })
1341}
1342
1343fn block_names(program: &Program) -> Vec<String> {
1344    let mut used = HashSet::new();
1345    program
1346        .blocks
1347        .iter()
1348        .map(|block| {
1349            let mut name = block.label.clone();
1350            if name.is_empty() || generated(&name) || used.contains(&name) {
1351                name = format!("{}.{}", block.label, block.id.0);
1352            }
1353            used.insert(name.clone());
1354            llvm_name(&name)
1355        })
1356        .collect()
1357}
1358
1359fn generated(name: &str) -> bool {
1360    let digits = |s: &str| !s.is_empty() && s.bytes().all(|b| b.is_ascii_digit());
1361    if let Some(rest) = name.strip_prefix("slot") {
1362        return digits(rest);
1363    }
1364    name.strip_prefix('v')
1365        .is_some_and(|rest| digits(rest.strip_suffix(".f").unwrap_or(rest)))
1366}
1367
1368fn llvm_name(name: &str) -> String {
1369    let plain = name.bytes().next().is_some_and(|b| !b.is_ascii_digit())
1370        && name
1371            .bytes()
1372            .all(|b| b.is_ascii_alphanumeric() || b"-$._".contains(&b));
1373    if plain {
1374        name.to_string()
1375    } else {
1376        format!("\"{}\"", c_string(name))
1377    }
1378}
1379
1380fn c_string(text: &str) -> String {
1381    let mut out = String::new();
1382    for byte in text.bytes() {
1383        match byte {
1384            b' '..=b'~' if byte != b'"' && byte != b'\\' => out.push(byte as char),
1385            _ => write!(out, "\\{byte:02X}").unwrap(),
1386        }
1387    }
1388    out
1389}
1390
1391fn format_double(value: f64) -> String {
1392    format!("0x{:016X}", value.to_bits())
1393}
1394
1395fn qubit_ref(qubit: QubitId) -> String {
1396    format!("%Qubit* inttoptr (i64 {} to %Qubit*)", qubit.0)
1397}
1398
1399fn result_ref(result: ResultId) -> String {
1400    format!("%Result* inttoptr (i64 {} to %Result*)", result.0)
1401}
1402
1403pub fn emit_json(program: &Program) -> String {
1404    let mut out = String::new();
1405
1406    out.push_str("{\n");
1407    writeln!(out, "  \"name\": {},", json_string(&program.name)).unwrap();
1408    writeln!(out, "  \"profile\": {:?},", program.profile.name()).unwrap();
1409    writeln!(out, "  \"qubits\": {},", program.num_qubits).unwrap();
1410    writeln!(out, "  \"results\": {},", program.num_results).unwrap();
1411    writeln!(out, "  \"depth\": {},", program.depth()).unwrap();
1412    writeln!(out, "  \"gateCount\": {},", program.gate_count()).unwrap();
1413    out.push_str("  \"blocks\": [\n");
1414
1415    for (index, block) in program.blocks.iter().enumerate() {
1416        out.push_str("    {\n");
1417        writeln!(out, "      \"label\": {},", json_string(&block.label)).unwrap();
1418        out.push_str("      \"ops\": [\n");
1419
1420        let lines: Vec<String> = block.ops.iter().filter_map(json_op).collect();
1421        out.push_str(&lines.join(",\n"));
1422        if !lines.is_empty() {
1423            out.push('\n');
1424        }
1425
1426        out.push_str("      ],\n");
1427        writeln!(
1428            out,
1429            "      \"terminator\": {}",
1430            json_string(&json_term(program, &block.term))
1431        )
1432        .unwrap();
1433        out.push_str("    }");
1434        if index + 1 < program.blocks.len() {
1435            out.push(',');
1436        }
1437        out.push('\n');
1438    }
1439
1440    out.push_str("  ]\n}\n");
1441    out
1442}
1443
1444fn json_string(text: &str) -> String {
1445    let mut out = String::from("\"");
1446    for c in text.chars() {
1447        match c {
1448            '"' => out.push_str("\\\""),
1449            '\\' => out.push_str("\\\\"),
1450            c if u32::from(c) < 0x20 => write!(out, "\\u{:04x}", u32::from(c)).unwrap(),
1451            c => out.push(c),
1452        }
1453    }
1454    out.push('"');
1455    out
1456}
1457
1458fn json_op(op: &Op) -> Option<String> {
1459    match op {
1460        Op::Gate(gate) => {
1461            let params: Vec<String> = gate
1462                .params
1463                .iter()
1464                .map(|p| match p.constant().map(|c| c.as_f64()) {
1465                    Some(angle) if angle.is_finite() => angle.to_string(),
1466                    _ => "null".into(),
1467                })
1468                .collect();
1469
1470            let controls: Vec<String> = gate.controls.iter().map(|q| q.0.to_string()).collect();
1471            let targets: Vec<String> = gate.targets.iter().map(|q| q.0.to_string()).collect();
1472
1473            Some(format!(
1474                "        {{ \"op\": \"gate\", \"name\": {:?}, \"controls\": [{}], \"targets\": [{}], \"params\": [{}] }}",
1475                gate.kind.name(),
1476                controls.join(", "),
1477                targets.join(", "),
1478                params.join(", ")
1479            ))
1480        }
1481        Op::Measure { qubit, result, .. } => Some(format!(
1482            "        {{ \"op\": \"measure\", \"qubit\": {}, \"result\": {} }}",
1483            qubit.0, result.0
1484        )),
1485        Op::Reset { qubit, .. } => Some(format!(
1486            "        {{ \"op\": \"reset\", \"qubit\": {} }}",
1487            qubit.0
1488        )),
1489        Op::RecordOutput { kind, result, .. } => Some(format!(
1490            "        {{ \"op\": \"record\", \"kind\": {:?}, \"result\": {} }}",
1491            format!("{kind:?}").to_lowercase(),
1492            result.map(|r| r.0.to_string()).unwrap_or("null".into())
1493        )),
1494        Op::Assign { .. } | Op::Store { .. } | Op::Message { .. } => None,
1495    }
1496}
1497
1498fn json_term(program: &Program, term: &Term) -> String {
1499    match term {
1500        Term::Ret(_) => "ret".into(),
1501        Term::Unreachable => "unreachable".into(),
1502        Term::Br(target) => format!("br {}", program.block(*target).label),
1503        Term::CondBr {
1504            if_true, if_false, ..
1505        } => format!(
1506            "condbr {} {}",
1507            program.block(*if_true).label,
1508            program.block(*if_false).label
1509        ),
1510        Term::Switch { default, .. } => format!("switch {}", program.block(*default).label),
1511    }
1512}
1513
1514pub fn emit_circuit(program: &Program) -> String {
1515    if program.num_qubits == 0 {
1516        return "(no qubits)\n".into();
1517    }
1518
1519    let width = program.num_qubits as usize;
1520    let mut wires: Vec<String> = (0..width).map(|i| format!("q{i}: ")).collect();
1521    let label_width = wires.iter().map(|w| w.len()).max().unwrap_or(0);
1522
1523    for wire in &mut wires {
1524        while wire.len() < label_width {
1525            wire.insert(wire.len() - 2, ' ');
1526        }
1527    }
1528
1529    let mut columns: Vec<Vec<String>> = Vec::new();
1530
1531    for block in &program.blocks {
1532        for op in &block.ops {
1533            let mut column = vec!["-".to_string(); width];
1534
1535            match op {
1536                Op::Gate(gate) => {
1537                    for control in &gate.controls {
1538                        if let Some(slot) = column.get_mut(control.index()) {
1539                            *slot = "*".into();
1540                        }
1541                    }
1542                    let symbol = gate_symbol(gate);
1543                    for target in &gate.targets {
1544                        if let Some(slot) = column.get_mut(target.index()) {
1545                            *slot = symbol.clone();
1546                        }
1547                    }
1548                    fill_vertical(&mut column, gate);
1549                }
1550                Op::Measure { qubit, .. } => {
1551                    if let Some(slot) = column.get_mut(qubit.index()) {
1552                        *slot = "M".into();
1553                    }
1554                }
1555                Op::Reset { qubit, .. } => {
1556                    if let Some(slot) = column.get_mut(qubit.index()) {
1557                        *slot = "0".into();
1558                    }
1559                }
1560                _ => continue,
1561            }
1562
1563            columns.push(column);
1564        }
1565    }
1566
1567    let cell_width = columns
1568        .iter()
1569        .flatten()
1570        .map(|c| c.len())
1571        .max()
1572        .unwrap_or(1)
1573        .max(1);
1574
1575    for column in &columns {
1576        for (wire_index, cell) in column.iter().enumerate() {
1577            wires[wire_index].push_str(&center(cell, cell_width));
1578            wires[wire_index].push('-');
1579        }
1580    }
1581
1582    let mut out = String::new();
1583    for wire in wires {
1584        out.push_str(&wire);
1585        out.push('\n');
1586    }
1587    out
1588}
1589
1590fn fill_vertical(column: &mut [String], gate: &Gate) {
1591    let wires: Vec<usize> = gate.wires().map(|q| q.index()).collect();
1592    let (Some(low), Some(high)) = (wires.iter().min(), wires.iter().max()) else {
1593        return;
1594    };
1595
1596    for index in (*low + 1)..*high {
1597        if column.get(index).is_some_and(|c| c == "-") {
1598            column[index] = "|".into();
1599        }
1600    }
1601}
1602
1603fn gate_symbol(gate: &Gate) -> String {
1604    match gate.kind {
1605        GateKind::X if !gate.controls.is_empty() => "+".into(),
1606        GateKind::Swap => "x".into(),
1607        GateKind::Unitary(_) => "U".into(),
1608        other => match gate.constant_angle() {
1609            Some(angle) if other.param_count() > 0 => {
1610                format!("{}({angle:.2})", other.name().to_uppercase())
1611            }
1612            _ => other.name().to_uppercase(),
1613        },
1614    }
1615}
1616
1617fn center(text: &str, width: usize) -> String {
1618    let total = width.saturating_sub(text.len());
1619    let left = total / 2;
1620    format!("{}{text}{}", "-".repeat(left), "-".repeat(total - left))
1621}
1622
1623#[cfg(test)]
1624mod tests {
1625    use super::*;
1626
1627    fn assert_zyz_eq(original: Matrix2) {
1628        let (theta, phi, lambda) = zyz_angles(&original);
1629        let reconstructed = Matrix2::rz(phi)
1630            .multiply(Matrix2::ry(theta))
1631            .multiply(Matrix2::rz(lambda));
1632        let pairs = [
1633            (original.a, reconstructed.a),
1634            (original.b, reconstructed.b),
1635            (original.c, reconstructed.c),
1636            (original.d, reconstructed.d),
1637        ];
1638        let (expected, actual) = pairs
1639            .iter()
1640            .find(|(_, actual)| actual.norm() > 1e-12)
1641            .expect("a unitary has a nonzero matrix element");
1642        let phase = expected / actual;
1643
1644        for (expected, actual) in pairs {
1645            assert!(
1646                (expected - phase * actual).norm() < 1e-12,
1647                "ZYZ reconstruction differs: {original:?} vs {reconstructed:?}"
1648            );
1649        }
1650    }
1651
1652    #[test]
1653    fn zyz_roundtrip() {
1654        for matrix in [
1655            Matrix2::identity(),
1656            Matrix2::x(),
1657            Matrix2::y(),
1658            Matrix2::z(),
1659            Matrix2::h(),
1660            Matrix2::sx(),
1661            Matrix2::rz(0.73)
1662                .multiply(Matrix2::ry(-1.21))
1663                .multiply(Matrix2::rz(2.44)),
1664            Matrix2::rx(0.91).multiply(Matrix2::phase(-0.37)),
1665        ] {
1666            assert_zyz_eq(matrix);
1667        }
1668    }
1669}