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

quil_rs/program/analysis/
control_flow_graph.rs
