quil_rs/program/analysis/
control_flow_graph.rs

1//! Construction and analysis of a control flow graph (CFG) for a Quil program.
2
3// Copyright 2024 Rigetti Computing
4//
5// Licensed under the Apache License, Version 2.0 (the "License");
6// you may not use this file except in compliance with the License.
7// You may obtain a copy of the License at
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the License is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// See the License for the specific language governing permissions and
15// limitations under the License.
16
17use std::{
18    collections::{BTreeMap, HashMap},
19    fmt::Debug,
20};
21
22#[cfg(not(feature = "python"))]
23use optipy::strip_pyo3;
24#[cfg(feature = "stubs")]
25use pyo3_stub_gen::derive::gen_stub_pyclass;
26
27use crate::{
28    instruction::{
29        Instruction, InstructionHandler, Jump, JumpUnless, JumpWhen, Label, MemoryReference, Target,
30    },
31    program::{
32        scheduling::{
33            schedule::{ComputedScheduleError, ComputedScheduleItem, Schedule, TimeSpan, Zero},
34            ScheduleError, ScheduledBasicBlock, Seconds,
35        },
36        ProgramError,
37    },
38    Program,
39};
40
41/// A control flow graph (CFG) is a representation of a program's control flow as a directed graph.
42/// Each node in the graph is a basic block, a sequence of instructions with a single entry point
43/// and a single exit point. The edges in the graph represent control flow between basic blocks.
44#[derive(Clone, Debug, Default)]
45pub struct ControlFlowGraph<'p> {
46    blocks: Vec<BasicBlock<'p>>,
47}
48
49impl<'p> ControlFlowGraph<'p> {
50    /// Returns `true` if the program contains dynamic control flow, i.e. `JUMP-WHEN` or `JUMP-UNLESS`
51    pub fn has_dynamic_control_flow(&self) -> bool {
52        self.blocks
53            .iter()
54            .any(|block| block.terminator().is_dynamic())
55    }
56
57    /// Returns the basic blocks in the control flow graph.
58    pub fn into_blocks(self) -> Vec<BasicBlock<'p>> {
59        self.blocks
60    }
61}
62
63#[derive(Clone, Debug)]
64#[cfg_attr(feature = "stubs", gen_stub_pyclass)]
65#[cfg_attr(
66    feature = "python",
67    pyo3::pyclass(name = "ControlFlowGraph", module = "quil.program", subclass, frozen)
68)]
69pub struct ControlFlowGraphOwned {
70    pub(crate) blocks: Vec<BasicBlockOwned>,
71}
72
73impl From<ControlFlowGraph<'_>> for ControlFlowGraphOwned {
74    fn from(value: ControlFlowGraph) -> Self {
75        let blocks = value
76            .blocks
77            .into_iter()
78            .map(BasicBlockOwned::from)
79            .collect();
80        ControlFlowGraphOwned { blocks }
81    }
82}
83
84impl<'p> From<&'p ControlFlowGraphOwned> for ControlFlowGraph<'p> {
85    fn from(value: &'p ControlFlowGraphOwned) -> Self {
86        let blocks = value.blocks.iter().map(BasicBlock::from).collect();
87        ControlFlowGraph { blocks }
88    }
89}
90
91#[derive(Clone, Debug, Default)]
92pub struct BasicBlock<'p> {
93    /// The label of the basic block, if any. An unlabeled basic block cannot be a target of a jump, but can
94    /// be entered by a [`BasicBlockTerminator::Continue`] from the preceding block or program start.
95    label: Option<&'p Target>,
96
97    /// The instructions within the basic block, not including its terminator.
98    instructions: Vec<&'p Instruction>,
99
100    /// The offset of the start of this block from the containing program, in instruction count.
101    /// For the first block in the program, this is `0`. This counts only "body" instructions, not
102    /// `DEFCAL`, `DEFFRAME`, et al.
103    ///
104    /// This is intended for use in debugging and source mapping.
105    instruction_index_offset: usize,
106
107    /// The terminator of the basic block, which determines the control flow to the next basic block.
108    terminator: BasicBlockTerminator<'p>,
109}
110
111impl<'p> BasicBlock<'p> {
112    pub fn label(&self) -> Option<&'p Target> {
113        self.label
114    }
115
116    pub fn instruction_index_offset(&self) -> usize {
117        self.instruction_index_offset
118    }
119
120    pub fn instructions(&self) -> &[&'p Instruction] {
121        self.instructions.as_ref()
122    }
123
124    pub fn terminator(&self) -> &BasicBlockTerminator<'p> {
125        &self.terminator
126    }
127
128    /// Compute the flattened schedule for this [`BasicBlock`] in terms of seconds,
129    /// using a default built-in calculation for the duration of scheduled instructions.
130    /// See [`BasicBlockOwned::as_schedule`].
131    ///
132    /// # Arguments
133    ///
134    /// * `program` - The program containing this basic block.
135    ///   This is used to retrieve frame and calibration information.
136    ///   Generally, this should be the program
137    ///   from which the block was extracted.
138    ///
139    /// # How it Works
140    ///
141    /// * Expanding each instruction within the block using the program's calibration definitions
142    /// * Resolving the `ScheduleSeconds` of the expanded instructions
143    /// * Mapping calibrated instructions back to the original instructions within this block,
144    ///   such that the block's instruction is represented as a timespan encompassing all of its expanded instructions
145    ///
146    /// # Notes
147    ///
148    /// If the basic block contains gates,
149    /// the program must contain corresponding `DEFCAL`s for those gates.
150    /// Gates do not inherently have durations,
151    /// but rather inherit them from the `PULSE`, `CAPTURE`, `DELAY`,
152    /// and other instructions within their calibrations.
153    /// Without a calibration, a gate's duration cannot be computed.
154    ///
155    /// # Python Example
156    ///
157    /// For Python users, the following example demonstrates construction
158    /// of such a schedule for a simple program
159    /// without explicit control flow (and thus with only one basic block):
160    ///
161    /// ```python
162    /// from quil.program import Program
163    ///
164    /// program = Program.parse("CZ 0 1; CZ 0 2")
165    /// print(program.to_quil())
166    ///
167    /// control_flow_graph = program.control_flow_graph()
168    /// assert control_flow_graph.has_dynamic_control_flow() == False
169    ///
170    /// basic_blocks = control_flow_graph.basic_blocks()
171    /// assert len(basic_blocks) == 1
172    ///
173    /// schedule = blocks[0].as_schedule_seconds(program)
174    /// print(f"Duration = {schedule.duration()}")
175    /// print(schedule.items())
176    /// ```
177    pub fn as_schedule_seconds<H: InstructionHandler>(
178        &self,
179        program: &Program,
180        handler: &H,
181    ) -> Result<Schedule<Seconds>, BasicBlockScheduleError> {
182        self.as_schedule(
183            program,
184            |prog, instr| ScheduledBasicBlock::instruction_duration_seconds(prog, instr, handler),
185            handler,
186        )
187    }
188
189    /// Compute the schedule for this [`BasicBlock`] in terms of a generic unit of time,
190    /// using a provided function to calculate the duration of scheduled instructions in that unit.
191    ///
192    /// # Arguments
193    ///
194    /// * `program` - The program containing this basic block. This is used to retrieve frame
195    ///   and calibration information.
196    /// * `get_duration` - A function that takes a program and an instruction and returns the
197    ///   duration of the instruction in the desired time unit, or `None` if the instruction's
198    ///   duration is not known.
199    ///
200    /// Note: when an instruction is expanded, the "time" of that original instruction includes
201    /// the times of all of the resulting instructions. This may cause gate times to be
202    /// longer than a user might expect.
203    ///
204    /// To understand why, consider a program like this:
205    ///
206    /// ```text
207    /// # One-qubit frame
208    /// DEFFRAME 0 "a":
209    ///     ATTRIBUTE: 1
210    ///
211    /// # Two-qubit frame
212    /// DEFFRAME 0 1 "b":
213    ///     ATTRIBUTE: 1
214    ///
215    /// DEFCAL A 0:
216    ///     PULSE 0 "a" flat(duration: 1.0)
217    ///
218    /// DEFCAL B 0 1:
219    ///     FENCE 1
220    ///     PULSE 0 1 "b" flat(duration: 1.0)
221    ///
222    /// A 0
223    /// B 0 1
224    /// ```
225    ///
226    /// `B 0` will be scheduled from time 0 to time 2, because its inner `FENCE` is scheduled for time 0.
227    /// This may be unexpected if the user expects to see only the timing of the inner `PULSE`.
228    pub fn as_schedule<H, F, Time>(
229        &self,
230        program: &'p Program,
231        get_duration: F,
232        handler: &H,
233    ) -> Result<Schedule<Time>, BasicBlockScheduleError>
234    where
235        H: InstructionHandler,
236        F: Fn(&Program, &Instruction) -> Option<Time>,
237        Time: Clone
238            + Debug
239            + PartialOrd
240            + std::ops::Add<Time, Output = Time>
241            + std::ops::Sub<Time, Output = Time>
242            + Zero,
243    {
244        // 1: expand calibrations and track the source mapping
245        let mut calibrated_to_uncalibrated_instruction_source_mapping = BTreeMap::new();
246        let mut calibrated_block_instructions = Vec::new();
247
248        for (uncalibrated_instruction_index, instruction) in self.instructions.iter().enumerate() {
249            let first_calibrated_instruction_index = calibrated_block_instructions.len();
250            if let Some(expanded) = program.calibrations.expand(instruction, &[])? {
251                calibrated_block_instructions.extend(expanded.into_iter());
252            } else {
253                calibrated_block_instructions.push((*instruction).clone());
254            }
255            calibrated_to_uncalibrated_instruction_source_mapping.insert(
256                first_calibrated_instruction_index,
257                uncalibrated_instruction_index,
258            );
259        }
260
261        let calibrated_block = BasicBlock {
262            label: self.label,
263            instructions: calibrated_block_instructions.iter().collect(),
264            instruction_index_offset: self.instruction_index_offset,
265            terminator: self.terminator.clone(),
266        };
267
268        // 2: attempt to schedule the newly-expanded block
269        let scheduled_self = ScheduledBasicBlock::build(calibrated_block, program, handler)?;
270        let schedule = scheduled_self.as_schedule(program, get_duration)?;
271
272        // 3: map that schedule back to the original instructions from this basic block using the source mapping
273        let uncalibrated_schedule_items_by_instruction_index = schedule
274            .into_items()
275            .into_iter()
276            .fold(HashMap::<usize, TimeSpan<Time>>::new(), |mut map, item| {
277                if let Some((_, uncalibrated_instruction_index)) =
278                    calibrated_to_uncalibrated_instruction_source_mapping
279                        .range(..=item.instruction_index)
280                        .next_back()
281                {
282                    if let Some(existing_time_span) = map.get_mut(uncalibrated_instruction_index) {
283                        *existing_time_span = existing_time_span.clone().union(item.time_span);
284                    } else {
285                        map.insert(*uncalibrated_instruction_index, item.time_span.clone());
286                    }
287                }
288
289                map
290            });
291
292        let schedule_items = uncalibrated_schedule_items_by_instruction_index
293            .into_iter()
294            .map(|(instruction_index, time_span)| ComputedScheduleItem {
295                instruction_index,
296                time_span,
297            })
298            .collect::<Vec<_>>();
299
300        let schedule = Schedule::from(schedule_items);
301        Ok(schedule)
302    }
303}
304
305// TODO (#453): Address large error types.
306#[allow(clippy::large_enum_variant)]
307#[allow(clippy::enum_variant_names)]
308#[derive(Debug, thiserror::Error)]
309pub enum BasicBlockScheduleError {
310    #[error(transparent)]
311    ScheduleError(#[from] ScheduleError),
312
313    #[error(transparent)]
314    ComputedScheduleError(#[from] ComputedScheduleError),
315
316    #[error(transparent)]
317    ProgramError(#[from] ProgramError),
318}
319
320// TODO (#472): The conversions to/from these Owned types and their non-Owned counterparts
321// involves a lot of Cloning, and they're the types exposed by the Python bindings.
322// Can we combine their relevant methods or otherwise avoid the costly conversions?
323#[derive(Clone, Debug)]
324#[cfg_attr(feature = "stubs", gen_stub_pyclass)]
325#[cfg_attr(
326    feature = "python",
327    pyo3::pyclass(name = "BasicBlock", module = "quil.program", subclass)
328)]
329#[cfg_attr(not(feature = "python"), strip_pyo3)]
330pub struct BasicBlockOwned {
331    /// The label of the block, if any.
332    /// This is used to target this block in control flow.
333    #[pyo3(get)]
334    label: Option<Target>,
335    /// A list of the instructions in the block, in order of definition.
336    ///
337    /// This does not include the label or terminator instructions.
338    #[pyo3(get)]
339    instructions: Vec<Instruction>,
340    instruction_index_offset: usize,
341    pub(crate) terminator: BasicBlockTerminatorOwned,
342}
343
344impl From<BasicBlock<'_>> for BasicBlockOwned {
345    fn from(value: BasicBlock) -> Self {
346        let label = value.label.cloned();
347        let instructions = value.instructions.into_iter().cloned().collect();
348        let instruction_index_offset = value.instruction_index_offset;
349        let terminator = value.terminator.into();
350        BasicBlockOwned {
351            label,
352            instructions,
353            instruction_index_offset,
354            terminator,
355        }
356    }
357}
358
359impl<'b> From<&'b BasicBlockOwned> for BasicBlock<'b> {
360    fn from(value: &'b BasicBlockOwned) -> Self {
361        let label = value.label.as_ref();
362        let instructions = value.instructions.iter().collect();
363        let instruction_index_offset = value.instruction_index_offset;
364        let terminator = (&value.terminator).into();
365        BasicBlock {
366            label,
367            instructions,
368            instruction_index_offset,
369            terminator,
370        }
371    }
372}
373
374/// The terminator of a basic block, which determines the control flow to the next basic block.
375#[derive(Clone, Debug, Default)]
376pub enum BasicBlockTerminator<'p> {
377    ConditionalJump {
378        condition: &'p MemoryReference,
379        target: &'p Target,
380        jump_if_condition_zero: bool,
381    },
382    #[default]
383    Continue,
384    Jump {
385        target: &'p Target,
386    },
387    Halt,
388}
389
390impl BasicBlockTerminator<'_> {
391    /// Returns `true` if the terminator is dynamic, i.e. `JUMP-WHEN` or `JUMP-UNLESS`.
392    ///
393    /// Dynamic terminators are those that can change the control flow based on the state of the
394    /// program at runtime, as opposed to static terminators like `JUMP` and `HALT`.
395    pub fn is_dynamic(&self) -> bool {
396        matches!(self, BasicBlockTerminator::ConditionalJump { .. })
397    }
398
399    pub fn into_instruction(self) -> Option<Instruction> {
400        match self {
401            BasicBlockTerminator::ConditionalJump {
402                condition,
403                target,
404                jump_if_condition_zero,
405            } => {
406                if jump_if_condition_zero {
407                    Some(Instruction::JumpUnless(JumpUnless {
408                        condition: condition.clone(),
409                        target: target.clone(),
410                    }))
411                } else {
412                    Some(Instruction::JumpWhen(JumpWhen {
413                        condition: condition.clone(),
414                        target: target.clone(),
415                    }))
416                }
417            }
418            BasicBlockTerminator::Continue => None,
419            BasicBlockTerminator::Jump { target } => Some(Instruction::Jump(Jump {
420                target: target.clone(),
421            })),
422            BasicBlockTerminator::Halt => Some(Instruction::Halt()),
423        }
424    }
425}
426
427#[derive(Clone, Debug, Default)]
428pub enum BasicBlockTerminatorOwned {
429    ConditionalJump {
430        condition: MemoryReference,
431        target: Target,
432        jump_if_condition_zero: bool,
433    },
434    #[default]
435    Continue,
436    Jump {
437        target: Target,
438    },
439    Halt,
440}
441
442impl From<BasicBlockTerminator<'_>> for BasicBlockTerminatorOwned {
443    fn from(value: BasicBlockTerminator) -> Self {
444        match value {
445            BasicBlockTerminator::ConditionalJump {
446                condition,
447                target,
448                jump_if_condition_zero,
449            } => BasicBlockTerminatorOwned::ConditionalJump {
450                condition: condition.clone(),
451                target: target.clone(),
452                jump_if_condition_zero,
453            },
454            BasicBlockTerminator::Continue => BasicBlockTerminatorOwned::Continue,
455            BasicBlockTerminator::Jump { target } => BasicBlockTerminatorOwned::Jump {
456                target: target.clone(),
457            },
458            BasicBlockTerminator::Halt => BasicBlockTerminatorOwned::Halt,
459        }
460    }
461}
462
463impl<'p> From<&'p BasicBlockTerminatorOwned> for BasicBlockTerminator<'p> {
464    fn from(value: &'p BasicBlockTerminatorOwned) -> Self {
465        match value {
466            BasicBlockTerminatorOwned::ConditionalJump {
467                condition,
468                target,
469                jump_if_condition_zero,
470            } => BasicBlockTerminator::ConditionalJump {
471                condition,
472                target,
473                jump_if_condition_zero: *jump_if_condition_zero,
474            },
475            BasicBlockTerminatorOwned::Continue => BasicBlockTerminator::Continue,
476            BasicBlockTerminatorOwned::Jump { target } => BasicBlockTerminator::Jump { target },
477            BasicBlockTerminatorOwned::Halt => BasicBlockTerminator::Halt,
478        }
479    }
480}
481
482impl<'p> From<&'p Program> for ControlFlowGraph<'p> {
483    fn from(value: &'p Program) -> Self {
484        let mut graph = ControlFlowGraph::default();
485
486        let mut current_label = None;
487        let mut current_block_instructions = Vec::new();
488        let mut instruction_index_offset = 0;
489        for instruction in &value.instructions {
490            match instruction {
491                Instruction::Arithmetic(_)
492                | Instruction::BinaryLogic(_)
493                | Instruction::Call(_)
494                | Instruction::Capture(_)
495                | Instruction::Convert(_)
496                | Instruction::Comparison(_)
497                | Instruction::Delay(_)
498                | Instruction::Fence(_)
499                | Instruction::Exchange(_)
500                | Instruction::Gate(_)
501                | Instruction::Load(_)
502                | Instruction::Pragma(_)
503                | Instruction::Measurement(_)
504                | Instruction::Move(_)
505                | Instruction::Nop()
506                | Instruction::Pulse(_)
507                | Instruction::RawCapture(_)
508                | Instruction::Reset(_)
509                | Instruction::SetFrequency(_)
510                | Instruction::SetPhase(_)
511                | Instruction::SetScale(_)
512                | Instruction::ShiftFrequency(_)
513                | Instruction::ShiftPhase(_)
514                | Instruction::Store(_)
515                | Instruction::SwapPhases(_)
516                | Instruction::UnaryLogic(_)
517                | Instruction::Wait() => current_block_instructions.push(instruction),
518
519                Instruction::CalibrationDefinition(_)
520                | Instruction::CircuitDefinition(_)
521                | Instruction::Declaration(_)
522                | Instruction::FrameDefinition(_)
523                | Instruction::GateDefinition(_)
524                | Instruction::Include(_)
525                | Instruction::MeasureCalibrationDefinition(_)
526                | Instruction::WaveformDefinition(_) => {}
527
528                Instruction::Label(Label { target }) => {
529                    if !current_block_instructions.is_empty() || current_label.is_some() {
530                        let block = BasicBlock {
531                            label: current_label.take(),
532                            instructions: std::mem::take(&mut current_block_instructions),
533                            instruction_index_offset,
534                            terminator: BasicBlockTerminator::Continue,
535                        };
536                        // +1 for the label
537                        instruction_index_offset += block.instructions.len() + 1;
538                        graph.blocks.push(block);
539                    }
540
541                    current_label = Some(target);
542                }
543
544                Instruction::Jump(_)
545                | Instruction::JumpUnless(_)
546                | Instruction::JumpWhen(_)
547                | Instruction::Halt() => {
548                    let terminator = match instruction {
549                        Instruction::Jump(jump) => BasicBlockTerminator::Jump {
550                            target: &jump.target,
551                        },
552                        Instruction::JumpUnless(jump_unless) => {
553                            BasicBlockTerminator::ConditionalJump {
554                                condition: &jump_unless.condition,
555                                target: &jump_unless.target,
556                                jump_if_condition_zero: true,
557                            }
558                        }
559                        Instruction::JumpWhen(jump_when) => BasicBlockTerminator::ConditionalJump {
560                            condition: &jump_when.condition,
561                            target: &jump_when.target,
562                            jump_if_condition_zero: false,
563                        },
564                        Instruction::Halt() => BasicBlockTerminator::Halt,
565                        _ => unreachable!(),
566                    };
567                    let block = BasicBlock {
568                        label: current_label.take(),
569                        instructions: std::mem::take(&mut current_block_instructions),
570                        instruction_index_offset,
571                        terminator,
572                    };
573
574                    let label_instruction_offset = if block.label().is_some() { 1 } else { 0 };
575                    // +1 for this terminator instruction
576                    instruction_index_offset +=
577                        block.instructions.len() + 1 + label_instruction_offset;
578
579                    graph.blocks.push(block);
580                }
581            }
582        }
583
584        if !current_block_instructions.is_empty() || current_label.is_some() {
585            let block = BasicBlock {
586                label: current_label.take(),
587                instructions: current_block_instructions,
588                instruction_index_offset,
589                terminator: BasicBlockTerminator::Continue,
590            };
591            graph.blocks.push(block);
592        }
593
594        graph
595    }
596}
597
598impl<'a> TryFrom<&'a Program> for BasicBlock<'a> {
599    type Error = ProgramEmptyOrContainsMultipleBasicBlocks;
600
601    fn try_from(value: &'a Program) -> Result<Self, Self::Error> {
602        let blocks = ControlFlowGraph::from(value).blocks;
603        if blocks.len() == 1 {
604            Ok(blocks.into_iter().next().unwrap())
605        } else {
606            Err(ProgramEmptyOrContainsMultipleBasicBlocks)
607        }
608    }
609}
610
611#[derive(Debug, thiserror::Error)]
612#[error("Program is empty or contains multiple basic blocks")]
613pub struct ProgramEmptyOrContainsMultipleBasicBlocks;
614
615#[cfg(test)]
616mod tests {
617    use crate::instruction::DefaultHandler;
618    use crate::Program;
619    use rstest::rstest;
620
621    use super::*;
622
623    use super::super::test_programs::*;
624
625    #[rstest]
626    #[case(QUIL_AS_TREE)]
627    #[case(QUIL_AS_INVERSE_TREE)]
628    #[case(QUIL_AS_LINEAR)]
629    #[case(QUIL_WITH_DIAMOND)]
630    #[case(QUIL_WITH_SWAP)]
631    #[case(KITCHEN_SINK_QUIL)]
632    fn expect_single_basic_block(#[case] input: &str) {
633        let program: Program = input.parse().unwrap();
634        let _: BasicBlock = (&program).try_into().unwrap();
635    }
636
637    #[rstest]
638    #[case(QUIL_AS_TREE, false)]
639    #[case(QUIL_AS_INVERSE_TREE, false)]
640    #[case(QUIL_AS_LINEAR, false)]
641    #[case(QUIL_WITH_DIAMOND, false)]
642    #[case(KITCHEN_SINK_QUIL, false)]
643    #[case(QUIL_WITH_JUMP, false)]
644    #[case(QUIL_WITH_JUMP_WHEN, true)]
645    #[case(QUIL_WITH_JUMP_UNLESS, true)]
646    fn has_dynamic_control_flow(#[case] input: &str, #[case] expected: bool) {
647        let program: Program = input.parse().unwrap();
648        let graph = ControlFlowGraph::from(&program);
649        let dynamic = graph.has_dynamic_control_flow();
650        assert_eq!(expected, dynamic);
651    }
652
653    #[rstest]
654    #[case(r#"LABEL @a
655JUMP @a
656LABEL @b
657JUMP @b
658LABEL @c
659JUMP @c
660"#, vec![0, 2, 4])]
661    #[case(r#"LABEL @a
662LABEL @b
663LABEL @c
664JUMP @c
665"#, vec![0, 1, 2])]
666    #[case(r#"DEFFRAME 0 "rf":
667    ATTRIBUTE: 1
668DEFCAL X 0:
669    Y 0
670X 0
671"#, vec![0])]
672    fn instruction_index_offset(#[case] input: &str, #[case] expected_block_offsets: Vec<usize>) {
673        let program: Program = input.parse().unwrap();
674        let graph = ControlFlowGraph::from(&program);
675        let blocks = graph.into_blocks();
676        println!("blocks: {blocks:#?}");
677        let actual = blocks
678            .iter()
679            .map(|block| block.instruction_index_offset())
680            .collect::<Vec<_>>();
681
682        assert_eq!(expected_block_offsets, actual);
683    }
684
685    #[test]
686    fn schedule_uncalibrated() {
687        let input = r#"DEFFRAME 0 "a":
688    ATTRIBUTE: 1
689
690DEFFRAME 0 "b":
691    ATTRIBUTE: 1
692
693DEFCAL A 0:
694    NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
695    NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
696    NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
697
698DEFCAL B 0:
699    NONBLOCKING PULSE 0 "b" flat(duration: 10.0)
700
701A 0
702B 0
703FENCE
704B 0
705PULSE 0 "a" flat(duration: 1.0)
706"#;
707
708        let program: Program = input.parse().unwrap();
709        let graph = ControlFlowGraph::from(&program);
710        let blocks = graph.into_blocks();
711        println!("blocks: {blocks:#?}");
712
713        let schedule = blocks[0]
714            .as_schedule_seconds(&program, &DefaultHandler)
715            .unwrap();
716        println!("schedule: {schedule:#?}");
717        assert_eq!(schedule.duration().0, 21.0);
718        let schedule_items = schedule.into_items();
719
720        let schedule_items_by_instruction_index = schedule_items
721            .iter()
722            .map(|item| (item.instruction_index, item.clone()))
723            .collect::<HashMap<_, _>>();
724
725        // `A 0` backed by multiple consecutive instructions should capture all of their times
726        assert_eq!(
727            schedule_items_by_instruction_index[&0]
728                .time_span
729                .start_time()
730                .0,
731            0.0
732        );
733        assert_eq!(
734            schedule_items_by_instruction_index[&0]
735                .time_span
736                .duration()
737                .0,
738            3.0
739        );
740
741        // `B 0` should be scheduled concurrently with `A 0`
742        assert_eq!(
743            schedule_items_by_instruction_index[&1]
744                .time_span
745                .start_time()
746                .0,
747            0.0
748        );
749        assert_eq!(
750            schedule_items_by_instruction_index[&1]
751                .time_span
752                .duration()
753                .0,
754            10.0
755        );
756
757        // `FENCE` should be scheduled after `A 0` and `B 0` and take no time.
758        // It is not included in the schedule items because it has zero duration.
759
760        // `B 0` should be scheduled after `FENCE`
761        assert_eq!(
762            schedule_items_by_instruction_index[&3]
763                .time_span
764                .start_time()
765                .0,
766            10.0
767        );
768        assert_eq!(
769            schedule_items_by_instruction_index[&3]
770                .time_span
771                .duration()
772                .0,
773            10.0
774        );
775
776        // `PULSE 0 "a" flat(duration: 1.0)` should be scheduled after `B 0` as a blocking pulse.
777        assert_eq!(
778            schedule_items_by_instruction_index[&4]
779                .time_span
780                .start_time()
781                .0,
782            20.0
783        );
784        assert_eq!(
785            schedule_items_by_instruction_index[&4]
786                .time_span
787                .duration()
788                .0,
789            1.0
790        );
791    }
792
793    #[test]
794    fn schedule_uncalibrated_cz() {
795        let input = r#"DEFFRAME 0 "flux_tx_cz":
796    TEST: 1
797
798DEFFRAME 1 "flux_tx_iswap":
799    TEST: 1
800
801DEFFRAME 1 "flux_tx_cz":
802    TEST: 1
803
804DEFFRAME 1 "flux_tx_iswap":
805    TEST: 1
806
807DEFFRAME 2 "flux_tx_cz":
808    TEST: 1
809
810DEFFRAME 2 "flux_tx_iswap":
811    TEST: 1
812
813DEFFRAME 3 "flux_tx_cz":
814    TEST: 1
815
816DEFFRAME 3 "flux_tx_iswap":
817    TEST: 1
818
819# Simplified version
820DEFCAL CZ q0 q1:
821    FENCE q0 q1
822    SET-PHASE q0 "flux_tx_cz" 0.0
823    SET-PHASE q1 "flux_tx_iswap" 0.0
824    NONBLOCKING PULSE q0 "flux_tx_cz" erf_square(duration: 6.000000000000001e-08, pad_left: 0, pad_right: 0)
825    NONBLOCKING PULSE q1 "flux_tx_iswap" erf_square(duration: 6.000000000000001e-08, pad_left: 0, pad_right: 0)
826    SHIFT-PHASE q0 "flux_tx_cz" 1.0
827    SHIFT-PHASE q1 "flux_tx_iswap" 1.0
828    FENCE q0 q1
829
830CZ 0 1
831CZ 2 3
832CZ 0 2
833"#;
834
835        let program: Program = input.parse().unwrap();
836        let graph = ControlFlowGraph::from(&program);
837        let blocks = graph.into_blocks();
838        println!("blocks: {blocks:#?}");
839
840        let schedule = blocks[0]
841            .as_schedule_seconds(&program, &DefaultHandler)
842            .unwrap();
843        let mut schedule_items = schedule.into_items();
844        schedule_items.sort_by_key(|item| item.instruction_index);
845
846        assert_eq!(schedule_items.len(), 3);
847
848        insta::assert_debug_snapshot!(schedule_items);
849    }
850}
quil_rs/program/analysis/control_flow_graph.rs

quil_rs/program/analysis/
control_flow_graph.rs
