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(
178        &self,
179        program: &Program,
180    ) -> Result<Schedule<Seconds>, BasicBlockScheduleError> {
181        self.as_schedule(
182            program,
183            ScheduledBasicBlock::get_instruction_duration_seconds,
184        )
185    }
186
187    /// Compute the schedule for this [`BasicBlock`] in terms of a generic unit of time,
188    /// using a provided function to calculate the duration of scheduled instructions in that unit.
189    ///
190    /// # Arguments
191    ///
192    /// * `program` - The program containing this basic block. This is used to retrieve frame
193    ///   and calibration information.
194    /// * `get_duration` - A function that takes a program and an instruction and returns the
195    ///   duration of the instruction in the desired time unit, or `None` if the instruction's
196    ///   duration is not known.
197    ///
198    /// Note: when an instruction is expanded, the "time" of that original instruction includes
199    /// the times of all of the resulting instructions. This may cause gate times to be
200    /// longer than a user might expect.
201    ///
202    /// To understand why, consider a program like this:
203    ///
204    /// ```text
205    /// # One-qubit frame
206    /// DEFFRAME 0 "a":
207    ///     ATTRIBUTE: 1
208    ///
209    /// # Two-qubit frame
210    /// DEFFRAME 0 1 "b":
211    ///     ATTRIBUTE: 1
212    ///
213    /// DEFCAL A 0:
214    ///     PULSE 0 "a" flat(duration: 1.0)
215    ///
216    /// DEFCAL B 0 1:
217    ///     FENCE 1
218    ///     PULSE 0 1 "b" flat(duration: 1.0)
219    ///
220    /// A 0
221    /// B 0 1
222    /// ```
223    ///
224    /// `B 0` will be scheduled from time 0 to time 2, because its inner `FENCE` is scheduled for time 0.
225    /// This may be unexpected if the user expects to see only the timing of the inner `PULSE`.
226    pub fn as_schedule<F, Time>(
227        &self,
228        program: &'p Program,
229        get_duration: F,
230    ) -> Result<Schedule<Time>, BasicBlockScheduleError>
231    where
232        F: Fn(&Program, &Instruction) -> Option<Time>,
233        Time: Clone
234            + Debug
235            + PartialOrd
236            + std::ops::Add<Time, Output = Time>
237            + std::ops::Sub<Time, Output = Time>
238            + Zero,
239    {
240        // 1: expand calibrations and track the source mapping
241        let mut calibrated_to_uncalibrated_instruction_source_mapping = BTreeMap::new();
242        let mut calibrated_block_instructions = Vec::new();
243
244        for (uncalibrated_instruction_index, instruction) in self.instructions.iter().enumerate() {
245            let first_calibrated_instruction_index = calibrated_block_instructions.len();
246            if let Some(expanded) = program.calibrations.expand(instruction, &[])? {
247                calibrated_block_instructions.extend(expanded.into_iter());
248            } else {
249                calibrated_block_instructions.push((*instruction).clone());
250            }
251            calibrated_to_uncalibrated_instruction_source_mapping.insert(
252                first_calibrated_instruction_index,
253                uncalibrated_instruction_index,
254            );
255        }
256
257        let calibrated_block = BasicBlock {
258            label: self.label,
259            instructions: calibrated_block_instructions.iter().collect(),
260            instruction_index_offset: self.instruction_index_offset,
261            terminator: self.terminator.clone(),
262        };
263
264        // 2: attempt to schedule the newly-expanded block
265        let mut instruction_handler = InstructionHandler::default();
266        let scheduled_self =
267            ScheduledBasicBlock::build(calibrated_block, program, &mut instruction_handler)?;
268        let schedule = scheduled_self.as_schedule(program, get_duration)?;
269
270        // 3: map that schedule back to the original instructions from this basic block using the source mapping
271        let uncalibrated_schedule_items_by_instruction_index = schedule
272            .into_items()
273            .into_iter()
274            .fold(HashMap::<usize, TimeSpan<Time>>::new(), |mut map, item| {
275                if let Some((_, uncalibrated_instruction_index)) =
276                    calibrated_to_uncalibrated_instruction_source_mapping
277                        .range(..=item.instruction_index)
278                        .next_back()
279                {
280                    if let Some(existing_time_span) = map.get_mut(uncalibrated_instruction_index) {
281                        *existing_time_span = existing_time_span.clone().union(item.time_span);
282                    } else {
283                        map.insert(*uncalibrated_instruction_index, item.time_span.clone());
284                    }
285                }
286
287                map
288            });
289
290        let schedule_items = uncalibrated_schedule_items_by_instruction_index
291            .into_iter()
292            .map(|(instruction_index, time_span)| ComputedScheduleItem {
293                instruction_index,
294                time_span,
295            })
296            .collect::<Vec<_>>();
297
298        let schedule = Schedule::from(schedule_items);
299        Ok(schedule)
300    }
301}
302
303// TODO (#453): Address large error types.
304#[allow(clippy::large_enum_variant)]
305#[allow(clippy::enum_variant_names)]
306#[derive(Debug, thiserror::Error)]
307pub enum BasicBlockScheduleError {
308    #[error(transparent)]
309    ScheduleError(#[from] ScheduleError),
310
311    #[error(transparent)]
312    ComputedScheduleError(#[from] ComputedScheduleError),
313
314    #[error(transparent)]
315    ProgramError(#[from] ProgramError),
316}
317
318// TODO (#472): The conversions to/from these Owned types and their non-Owned counterparts
319// involves a lot of Cloning, and they're the types exposed by the Python bindings.
320// Can we combine their relevant methods or otherwise avoid the costly conversions?
321#[derive(Clone, Debug)]
322#[cfg_attr(feature = "stubs", gen_stub_pyclass)]
323#[cfg_attr(
324    feature = "python",
325    pyo3::pyclass(name = "BasicBlock", module = "quil.program", subclass)
326)]
327#[cfg_attr(not(feature = "python"), strip_pyo3)]
328pub struct BasicBlockOwned {
329    /// The label of the block, if any.
330    /// This is used to target this block in control flow.
331    #[pyo3(get)]
332    label: Option<Target>,
333    /// A list of the instructions in the block, in order of definition.
334    ///
335    /// This does not include the label or terminator instructions.
336    #[pyo3(get)]
337    instructions: Vec<Instruction>,
338    instruction_index_offset: usize,
339    pub(crate) terminator: BasicBlockTerminatorOwned,
340}
341
342impl From<BasicBlock<'_>> for BasicBlockOwned {
343    fn from(value: BasicBlock) -> Self {
344        let label = value.label.cloned();
345        let instructions = value.instructions.into_iter().cloned().collect();
346        let instruction_index_offset = value.instruction_index_offset;
347        let terminator = value.terminator.into();
348        BasicBlockOwned {
349            label,
350            instructions,
351            instruction_index_offset,
352            terminator,
353        }
354    }
355}
356
357impl<'b> From<&'b BasicBlockOwned> for BasicBlock<'b> {
358    fn from(value: &'b BasicBlockOwned) -> Self {
359        let label = value.label.as_ref();
360        let instructions = value.instructions.iter().collect();
361        let instruction_index_offset = value.instruction_index_offset;
362        let terminator = (&value.terminator).into();
363        BasicBlock {
364            label,
365            instructions,
366            instruction_index_offset,
367            terminator,
368        }
369    }
370}
371
372/// The terminator of a basic block, which determines the control flow to the next basic block.
373#[derive(Clone, Debug, Default)]
374pub enum BasicBlockTerminator<'p> {
375    ConditionalJump {
376        condition: &'p MemoryReference,
377        target: &'p Target,
378        jump_if_condition_zero: bool,
379    },
380    #[default]
381    Continue,
382    Jump {
383        target: &'p Target,
384    },
385    Halt,
386}
387
388impl BasicBlockTerminator<'_> {
389    /// Returns `true` if the terminator is dynamic, i.e. `JUMP-WHEN` or `JUMP-UNLESS`.
390    ///
391    /// Dynamic terminators are those that can change the control flow based on the state of the
392    /// program at runtime, as opposed to static terminators like `JUMP` and `HALT`.
393    pub fn is_dynamic(&self) -> bool {
394        matches!(self, BasicBlockTerminator::ConditionalJump { .. })
395    }
396
397    pub fn into_instruction(self) -> Option<Instruction> {
398        match self {
399            BasicBlockTerminator::ConditionalJump {
400                condition,
401                target,
402                jump_if_condition_zero,
403            } => {
404                if jump_if_condition_zero {
405                    Some(Instruction::JumpUnless(JumpUnless {
406                        condition: condition.clone(),
407                        target: target.clone(),
408                    }))
409                } else {
410                    Some(Instruction::JumpWhen(JumpWhen {
411                        condition: condition.clone(),
412                        target: target.clone(),
413                    }))
414                }
415            }
416            BasicBlockTerminator::Continue => None,
417            BasicBlockTerminator::Jump { target } => Some(Instruction::Jump(Jump {
418                target: target.clone(),
419            })),
420            BasicBlockTerminator::Halt => Some(Instruction::Halt()),
421        }
422    }
423}
424
425#[derive(Clone, Debug, Default)]
426pub enum BasicBlockTerminatorOwned {
427    ConditionalJump {
428        condition: MemoryReference,
429        target: Target,
430        jump_if_condition_zero: bool,
431    },
432    #[default]
433    Continue,
434    Jump {
435        target: Target,
436    },
437    Halt,
438}
439
440impl From<BasicBlockTerminator<'_>> for BasicBlockTerminatorOwned {
441    fn from(value: BasicBlockTerminator) -> Self {
442        match value {
443            BasicBlockTerminator::ConditionalJump {
444                condition,
445                target,
446                jump_if_condition_zero,
447            } => BasicBlockTerminatorOwned::ConditionalJump {
448                condition: condition.clone(),
449                target: target.clone(),
450                jump_if_condition_zero,
451            },
452            BasicBlockTerminator::Continue => BasicBlockTerminatorOwned::Continue,
453            BasicBlockTerminator::Jump { target } => BasicBlockTerminatorOwned::Jump {
454                target: target.clone(),
455            },
456            BasicBlockTerminator::Halt => BasicBlockTerminatorOwned::Halt,
457        }
458    }
459}
460
461impl<'p> From<&'p BasicBlockTerminatorOwned> for BasicBlockTerminator<'p> {
462    fn from(value: &'p BasicBlockTerminatorOwned) -> Self {
463        match value {
464            BasicBlockTerminatorOwned::ConditionalJump {
465                condition,
466                target,
467                jump_if_condition_zero,
468            } => BasicBlockTerminator::ConditionalJump {
469                condition,
470                target,
471                jump_if_condition_zero: *jump_if_condition_zero,
472            },
473            BasicBlockTerminatorOwned::Continue => BasicBlockTerminator::Continue,
474            BasicBlockTerminatorOwned::Jump { target } => BasicBlockTerminator::Jump { target },
475            BasicBlockTerminatorOwned::Halt => BasicBlockTerminator::Halt,
476        }
477    }
478}
479
480impl<'p> From<&'p Program> for ControlFlowGraph<'p> {
481    fn from(value: &'p Program) -> Self {
482        let mut graph = ControlFlowGraph::default();
483
484        let mut current_label = None;
485        let mut current_block_instructions = Vec::new();
486        let mut instruction_index_offset = 0;
487        for instruction in &value.instructions {
488            match instruction {
489                Instruction::Arithmetic(_)
490                | Instruction::BinaryLogic(_)
491                | Instruction::Call(_)
492                | Instruction::Capture(_)
493                | Instruction::Convert(_)
494                | Instruction::Comparison(_)
495                | Instruction::Delay(_)
496                | Instruction::Fence(_)
497                | Instruction::Exchange(_)
498                | Instruction::Gate(_)
499                | Instruction::Load(_)
500                | Instruction::Pragma(_)
501                | Instruction::Measurement(_)
502                | Instruction::Move(_)
503                | Instruction::Nop()
504                | Instruction::Pulse(_)
505                | Instruction::RawCapture(_)
506                | Instruction::Reset(_)
507                | Instruction::SetFrequency(_)
508                | Instruction::SetPhase(_)
509                | Instruction::SetScale(_)
510                | Instruction::ShiftFrequency(_)
511                | Instruction::ShiftPhase(_)
512                | Instruction::Store(_)
513                | Instruction::SwapPhases(_)
514                | Instruction::UnaryLogic(_)
515                | Instruction::Wait() => current_block_instructions.push(instruction),
516
517                Instruction::CalibrationDefinition(_)
518                | Instruction::CircuitDefinition(_)
519                | Instruction::Declaration(_)
520                | Instruction::FrameDefinition(_)
521                | Instruction::GateDefinition(_)
522                | Instruction::Include(_)
523                | Instruction::MeasureCalibrationDefinition(_)
524                | Instruction::WaveformDefinition(_) => {}
525
526                Instruction::Label(Label { target }) => {
527                    if !current_block_instructions.is_empty() || current_label.is_some() {
528                        let block = BasicBlock {
529                            label: current_label.take(),
530                            instructions: std::mem::take(&mut current_block_instructions),
531                            instruction_index_offset,
532                            terminator: BasicBlockTerminator::Continue,
533                        };
534                        // +1 for the label
535                        instruction_index_offset += block.instructions.len() + 1;
536                        graph.blocks.push(block);
537                    }
538
539                    current_label = Some(target);
540                }
541
542                Instruction::Jump(_)
543                | Instruction::JumpUnless(_)
544                | Instruction::JumpWhen(_)
545                | Instruction::Halt() => {
546                    let terminator = match instruction {
547                        Instruction::Jump(jump) => BasicBlockTerminator::Jump {
548                            target: &jump.target,
549                        },
550                        Instruction::JumpUnless(jump_unless) => {
551                            BasicBlockTerminator::ConditionalJump {
552                                condition: &jump_unless.condition,
553                                target: &jump_unless.target,
554                                jump_if_condition_zero: true,
555                            }
556                        }
557                        Instruction::JumpWhen(jump_when) => BasicBlockTerminator::ConditionalJump {
558                            condition: &jump_when.condition,
559                            target: &jump_when.target,
560                            jump_if_condition_zero: false,
561                        },
562                        Instruction::Halt() => BasicBlockTerminator::Halt,
563                        _ => unreachable!(),
564                    };
565                    let block = BasicBlock {
566                        label: current_label.take(),
567                        instructions: std::mem::take(&mut current_block_instructions),
568                        instruction_index_offset,
569                        terminator,
570                    };
571
572                    let label_instruction_offset = if block.label().is_some() { 1 } else { 0 };
573                    // +1 for this terminator instruction
574                    instruction_index_offset +=
575                        block.instructions.len() + 1 + label_instruction_offset;
576
577                    graph.blocks.push(block);
578                }
579            }
580        }
581
582        if !current_block_instructions.is_empty() || current_label.is_some() {
583            let block = BasicBlock {
584                label: current_label.take(),
585                instructions: current_block_instructions,
586                instruction_index_offset,
587                terminator: BasicBlockTerminator::Continue,
588            };
589            graph.blocks.push(block);
590        }
591
592        graph
593    }
594}
595
596impl<'a> TryFrom<&'a Program> for BasicBlock<'a> {
597    type Error = ProgramEmptyOrContainsMultipleBasicBlocks;
598
599    fn try_from(value: &'a Program) -> Result<Self, Self::Error> {
600        let blocks = ControlFlowGraph::from(value).blocks;
601        if blocks.len() == 1 {
602            Ok(blocks.into_iter().next().unwrap())
603        } else {
604            Err(ProgramEmptyOrContainsMultipleBasicBlocks)
605        }
606    }
607}
608
609#[derive(Debug, thiserror::Error)]
610#[error("Program is empty or contains multiple basic blocks")]
611pub struct ProgramEmptyOrContainsMultipleBasicBlocks;
612
613#[cfg(test)]
614mod tests {
615    use crate::Program;
616    use rstest::rstest;
617
618    use super::*;
619
620    use super::super::test_programs::*;
621
622    #[rstest]
623    #[case(QUIL_AS_TREE)]
624    #[case(QUIL_AS_INVERSE_TREE)]
625    #[case(QUIL_AS_LINEAR)]
626    #[case(QUIL_WITH_DIAMOND)]
627    #[case(QUIL_WITH_SWAP)]
628    #[case(KITCHEN_SINK_QUIL)]
629    fn expect_single_basic_block(#[case] input: &str) {
630        let program: Program = input.parse().unwrap();
631        let _: BasicBlock = (&program).try_into().unwrap();
632    }
633
634    #[rstest]
635    #[case(QUIL_AS_TREE, false)]
636    #[case(QUIL_AS_INVERSE_TREE, false)]
637    #[case(QUIL_AS_LINEAR, false)]
638    #[case(QUIL_WITH_DIAMOND, false)]
639    #[case(KITCHEN_SINK_QUIL, false)]
640    #[case(QUIL_WITH_JUMP, false)]
641    #[case(QUIL_WITH_JUMP_WHEN, true)]
642    #[case(QUIL_WITH_JUMP_UNLESS, true)]
643    fn has_dynamic_control_flow(#[case] input: &str, #[case] expected: bool) {
644        let program: Program = input.parse().unwrap();
645        let graph = ControlFlowGraph::from(&program);
646        let dynamic = graph.has_dynamic_control_flow();
647        assert_eq!(expected, dynamic);
648    }
649
650    #[rstest]
651    #[case(r#"LABEL @a
652JUMP @a
653LABEL @b
654JUMP @b
655LABEL @c
656JUMP @c
657"#, vec![0, 2, 4])]
658    #[case(r#"LABEL @a
659LABEL @b
660LABEL @c
661JUMP @c
662"#, vec![0, 1, 2])]
663    #[case(r#"DEFFRAME 0 "rf":
664    ATTRIBUTE: 1
665DEFCAL X 0:
666    Y 0
667X 0
668"#, vec![0])]
669    fn instruction_index_offset(#[case] input: &str, #[case] expected_block_offsets: Vec<usize>) {
670        let program: Program = input.parse().unwrap();
671        let graph = ControlFlowGraph::from(&program);
672        let blocks = graph.into_blocks();
673        println!("blocks: {blocks:#?}");
674        let actual = blocks
675            .iter()
676            .map(|block| block.instruction_index_offset())
677            .collect::<Vec<_>>();
678
679        assert_eq!(expected_block_offsets, actual);
680    }
681
682    #[test]
683    fn schedule_uncalibrated() {
684        let input = r#"DEFFRAME 0 "a":
685    ATTRIBUTE: 1
686
687DEFFRAME 0 "b":
688    ATTRIBUTE: 1
689
690DEFCAL A 0:
691    NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
692    NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
693    NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
694
695DEFCAL B 0:
696    NONBLOCKING PULSE 0 "b" flat(duration: 10.0)
697
698A 0
699B 0
700FENCE
701B 0
702PULSE 0 "a" flat(duration: 1.0)
703"#;
704
705        let program: Program = input.parse().unwrap();
706        let graph = ControlFlowGraph::from(&program);
707        let blocks = graph.into_blocks();
708        println!("blocks: {blocks:#?}");
709
710        let schedule = blocks[0].as_schedule_seconds(&program).unwrap();
711        println!("schedule: {schedule:#?}");
712        assert_eq!(schedule.duration().0, 21.0);
713        let schedule_items = schedule.into_items();
714
715        let schedule_items_by_instruction_index = schedule_items
716            .iter()
717            .map(|item| (item.instruction_index, item.clone()))
718            .collect::<HashMap<_, _>>();
719
720        // `A 0` backed by multiple consecutive instructions should capture all of their times
721        assert_eq!(
722            schedule_items_by_instruction_index[&0]
723                .time_span
724                .start_time()
725                .0,
726            0.0
727        );
728        assert_eq!(
729            schedule_items_by_instruction_index[&0]
730                .time_span
731                .duration()
732                .0,
733            3.0
734        );
735
736        // `B 0` should be scheduled concurrently with `A 0`
737        assert_eq!(
738            schedule_items_by_instruction_index[&1]
739                .time_span
740                .start_time()
741                .0,
742            0.0
743        );
744        assert_eq!(
745            schedule_items_by_instruction_index[&1]
746                .time_span
747                .duration()
748                .0,
749            10.0
750        );
751
752        // `FENCE` should be scheduled after `A 0` and `B 0` and take no time.
753        // It is not included in the schedule items because it has zero duration.
754
755        // `B 0` should be scheduled after `FENCE`
756        assert_eq!(
757            schedule_items_by_instruction_index[&3]
758                .time_span
759                .start_time()
760                .0,
761            10.0
762        );
763        assert_eq!(
764            schedule_items_by_instruction_index[&3]
765                .time_span
766                .duration()
767                .0,
768            10.0
769        );
770
771        // `PULSE 0 "a" flat(duration: 1.0)` should be scheduled after `B 0` as a blocking pulse.
772        assert_eq!(
773            schedule_items_by_instruction_index[&4]
774                .time_span
775                .start_time()
776                .0,
777            20.0
778        );
779        assert_eq!(
780            schedule_items_by_instruction_index[&4]
781                .time_span
782                .duration()
783                .0,
784            1.0
785        );
786    }
787
788    #[test]
789    fn schedule_uncalibrated_cz() {
790        let input = r#"DEFFRAME 0 "flux_tx_cz":
791    TEST: 1
792
793DEFFRAME 1 "flux_tx_iswap":
794    TEST: 1
795
796DEFFRAME 1 "flux_tx_cz":
797    TEST: 1
798
799DEFFRAME 1 "flux_tx_iswap":
800    TEST: 1
801
802DEFFRAME 2 "flux_tx_cz":
803    TEST: 1
804
805DEFFRAME 2 "flux_tx_iswap":
806    TEST: 1
807
808DEFFRAME 3 "flux_tx_cz":
809    TEST: 1
810
811DEFFRAME 3 "flux_tx_iswap":
812    TEST: 1
813
814# Simplified version
815DEFCAL CZ q0 q1:
816    FENCE q0 q1
817    SET-PHASE q0 "flux_tx_cz" 0.0
818    SET-PHASE q1 "flux_tx_iswap" 0.0
819    NONBLOCKING PULSE q0 "flux_tx_cz" erf_square(duration: 6.000000000000001e-08, pad_left: 0, pad_right: 0)
820    NONBLOCKING PULSE q1 "flux_tx_iswap" erf_square(duration: 6.000000000000001e-08, pad_left: 0, pad_right: 0)
821    SHIFT-PHASE q0 "flux_tx_cz" 1.0
822    SHIFT-PHASE q1 "flux_tx_iswap" 1.0
823    FENCE q0 q1
824
825CZ 0 1
826CZ 2 3
827CZ 0 2
828"#;
829
830        let program: Program = input.parse().unwrap();
831        let graph = ControlFlowGraph::from(&program);
832        let blocks = graph.into_blocks();
833        println!("blocks: {blocks:#?}");
834
835        let schedule = blocks[0].as_schedule_seconds(&program).unwrap();
836        let mut schedule_items = schedule.into_items();
837        schedule_items.sort_by_key(|item| item.instruction_index);
838
839        assert_eq!(schedule_items.len(), 3);
840
841        insta::assert_debug_snapshot!(schedule_items);
842    }
843}
quil_rs/program/analysis/control_flow_graph.rs

quil_rs/program/analysis/
control_flow_graph.rs
