Repository: rigetti/quil-rs (language: python)

Issue:
Add analysis package
We would like a package for analyzing Quil programs to determine various characteristics without running or simulating them.


Discussion / hints:

Fix patch:
diff --git a/.gitignore b/.gitignore
index b9ebe0d1..deaea770 100644
--- a/.gitignore
+++ b/.gitignore
@@ -6,8 +6,9 @@ node_modules
 # unreviewed insta snapshots
 *.snap.new
 
-# JetBrains Editors
+# IDEs and editors
 .idea/
+.vscode/
 
 # Python artifacts
 *.so
diff --git a/Cargo.lock b/Cargo.lock
index 98fa43f3..6ba49e4f 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -205,9 +205,9 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "54a9bb5758fc5dfe728d1019941681eccaf0cf8a4189b692a0ee2f2ecf90a050"
 dependencies = [
  "heck",
- "proc-macro2 1.0.66",
- "quote 1.0.32",
- "syn 2.0.28",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
+ "syn 2.0.48",
 ]
 
 [[package]]
@@ -337,6 +337,12 @@ version = "0.3.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "a357d28ed41a50f9c765dbfe56cbc04a64e53e5fc58ba79fbc34c10ef3df831f"
 
+[[package]]
+name = "equivalent"
+version = "1.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5"
+
 [[package]]
 name = "errno"
 version = "0.3.2"
@@ -430,9 +436,9 @@ version = "0.3.28"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "89ca545a94061b6365f2c7355b4b32bd20df3ff95f02da9329b34ccc3bd6ee72"
 dependencies = [
- "proc-macro2 1.0.66",
- "quote 1.0.32",
- "syn 2.0.28",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
+ "syn 2.0.48",
 ]
 
 [[package]]
@@ -496,9 +502,9 @@ checksum = "eabb4a44450da02c90444cf74558da904edde8fb4e9035a9a6a4e15445af0bd7"
 
 [[package]]
 name = "hashbrown"
-version = "0.12.3"
+version = "0.14.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "8a9ee70c43aaf417c914396645a0fa852624801b24ebb7ae78fe8272889ac888"
+checksum = "290f1a1d9242c78d09ce40a5e87e7554ee637af1351968159f4952f028f75604"
 
 [[package]]
 name = "heck"
@@ -514,11 +520,11 @@ checksum = "443144c8cdadd93ebf52ddb4056d257f5b52c04d3c804e657d19eb73fc33668b"
 
 [[package]]
 name = "indexmap"
-version = "1.9.3"
+version = "2.2.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "bd070e393353796e801d209ad339e89596eb4c8d430d18ede6a1cced8fafbd99"
+checksum = "824b2ae422412366ba479e8111fd301f7b5faece8149317bb81925979a53f520"
 dependencies = [
- "autocfg",
+ "equivalent",
  "hashbrown",
 ]
 
@@ -569,9 +575,9 @@ dependencies = [
 
 [[package]]
 name = "itertools"
-version = "0.11.0"
+version = "0.12.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b1c173a5686ce8bfa551b3563d0c2170bf24ca44da99c7ca4bfdab5418c3fe57"
+checksum = "ba291022dbbd398a455acf126c1e341954079855bc60dfdda641363bd6922569"
 dependencies = [
  "either",
 ]
@@ -873,9 +879,9 @@ checksum = "de3145af08024dea9fa9914f381a17b8fc6034dfb00f3a84013f7ff43f29ed4c"
 
 [[package]]
 name = "petgraph"
-version = "0.6.3"
+version = "0.6.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "4dd7d28ee937e54fe3080c91faa1c3a46c06de6252988a7f4592ba2310ef22a4"
+checksum = "e1d3afd2628e69da2be385eb6f2fd57c8ac7977ceeff6dc166ff1657b0e386a9"
 dependencies = [
  "fixedbitset",
  "indexmap",
@@ -938,9 +944,9 @@ dependencies = [
 
 [[package]]
 name = "proc-macro2"
-version = "1.0.66"
+version = "1.0.78"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "18fb31db3f9bddb2ea821cde30a9f70117e3f119938b5ee630b7403aa6e2ead9"
+checksum = "e2422ad645d89c99f8f3e6b88a9fdeca7fabeac836b1002371c4367c8f984aae"
 dependencies = [
  "unicode-ident",
 ]
@@ -1021,10 +1027,10 @@ version = "0.20.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "dac53072f717aa1bfa4db832b39de8c875b7c7af4f4a6fe93cdbf9264cf8383b"
 dependencies = [
- "proc-macro2 1.0.66",
+ "proc-macro2 1.0.78",
  "pyo3-macros-backend",
- "quote 1.0.32",
- "syn 2.0.28",
+ "quote 1.0.35",
+ "syn 2.0.48",
 ]
 
 [[package]]
@@ -1034,9 +1040,9 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "7774b5a8282bd4f25f803b1f0d945120be959a36c72e08e7cd031c792fdfd424"
 dependencies = [
  "heck",
- "proc-macro2 1.0.66",
- "quote 1.0.32",
- "syn 2.0.28",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
+ "syn 2.0.48",
 ]
 
 [[package]]
@@ -1047,7 +1053,7 @@ checksum = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0"
 
 [[package]]
 name = "quil-py"
-version = "0.6.1-rc.0"
+version = "0.6.6"
 dependencies = [
  "ndarray",
  "numpy",
@@ -1060,7 +1066,7 @@ dependencies = [
 
 [[package]]
 name = "quil-rs"
-version = "0.22.1-rc.0"
+version = "0.22.6"
 dependencies = [
  "approx",
  "clap",
@@ -1068,7 +1074,7 @@ dependencies = [
  "dot-writer",
  "indexmap",
  "insta",
- "itertools 0.11.0",
+ "itertools 0.12.1",
  "lexical",
  "ndarray",
  "nom",
@@ -1097,11 +1103,11 @@ dependencies = [
 
 [[package]]
 name = "quote"
-version = "1.0.32"
+version = "1.0.35"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "50f3b39ccfb720540debaa0164757101c08ecb8d326b15358ce76a62c7e85965"
+checksum = "291ec9ab5efd934aaf503a6466c5d5251535d108ee747472c3977cc5acc868ef"
 dependencies = [
- "proc-macro2 1.0.66",
+ "proc-macro2 1.0.78",
 ]
 
 [[package]]
@@ -1236,9 +1242,9 @@ dependencies = [
 
 [[package]]
 name = "rstest"
-version = "0.18.1"
+version = "0.18.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "2b96577ca10cb3eade7b337eb46520108a67ca2818a24d0b63f41fd62bc9651c"
+checksum = "97eeab2f3c0a199bc4be135c36c924b6590b88c377d416494288c14f2db30199"
 dependencies = [
  "futures",
  "futures-timer",
@@ -1248,18 +1254,18 @@ dependencies = [
 
 [[package]]
 name = "rstest_macros"
-version = "0.18.1"
+version = "0.18.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "225e674cf31712b8bb15fdbca3ec0c1b9d825c5a24407ff2b7e005fb6a29ba03"
+checksum = "d428f8247852f894ee1be110b375111b586d4fa431f6c46e64ba5a0dcccbe605"
 dependencies = [
  "cfg-if",
  "glob",
- "proc-macro2 1.0.66",
- "quote 1.0.32",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
  "regex",
  "relative-path",
  "rustc_version",
- "syn 2.0.28",
+ "syn 2.0.48",
  "unicode-ident",
 ]
 
@@ -1351,9 +1357,9 @@ version = "1.0.183"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "aafe972d60b0b9bee71a91b92fee2d4fb3c9d7e8f6b179aa99f27203d99a4816"
 dependencies = [
- "proc-macro2 1.0.66",
- "quote 1.0.32",
- "syn 2.0.28",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
+ "syn 2.0.48",
 ]
 
 [[package]]
@@ -1402,24 +1408,24 @@ checksum = "73473c0e59e6d5812c5dfe2a064a6444949f089e20eec9a2e5506596494e4623"
 
 [[package]]
 name = "strum"
-version = "0.24.1"
+version = "0.26.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "063e6045c0e62079840579a7e47a355ae92f60eb74daaf156fb1e84ba164e63f"
+checksum = "723b93e8addf9aa965ebe2d11da6d7540fa2283fcea14b3371ff055f7ba13f5f"
 dependencies = [
  "strum_macros",
 ]
 
 [[package]]
 name = "strum_macros"
-version = "0.24.3"
+version = "0.26.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1e385be0d24f186b4ce2f9982191e7101bb737312ad61c1f2f984f34bcf85d59"
+checksum = "7a3417fc93d76740d974a01654a09777cb500428cc874ca9f45edfe0c4d4cd18"
 dependencies = [
  "heck",
- "proc-macro2 1.0.66",
- "quote 1.0.32",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
  "rustversion",
- "syn 1.0.109",
+ "syn 2.0.48",
 ]
 
 [[package]]
@@ -1435,23 +1441,12 @@ dependencies = [
 
 [[package]]
 name = "syn"
-version = "1.0.109"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "72b64191b275b66ffe2469e8af2c1cfe3bafa67b529ead792a6d0160888b4237"
-dependencies = [
- "proc-macro2 1.0.66",
- "quote 1.0.32",
- "unicode-ident",
-]
-
-[[package]]
-name = "syn"
-version = "2.0.28"
+version = "2.0.48"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "04361975b3f5e348b2189d8dc55bc942f278b2d482a6a0365de5bdd62d351567"
+checksum = "0f3531638e407dfc0814761abb7c00a5b54992b849452a0646b7f65c9f770f3f"
 dependencies = [
- "proc-macro2 1.0.66",
- "quote 1.0.32",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
  "unicode-ident",
 ]
 
@@ -1476,22 +1471,22 @@ dependencies = [
 
 [[package]]
 name = "thiserror"
-version = "1.0.44"
+version = "1.0.56"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "611040a08a0439f8248d1990b111c95baa9c704c805fa1f62104b39655fd7f90"
+checksum = "d54378c645627613241d077a3a79db965db602882668f9136ac42af9ecb730ad"
 dependencies = [
  "thiserror-impl",
 ]
 
 [[package]]
 name = "thiserror-impl"
-version = "1.0.44"
+version = "1.0.56"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "090198534930841fab3a5d1bb637cde49e339654e606195f8d9c76eeb081dc96"
+checksum = "fa0faa943b50f3db30a20aa7e265dbc66076993efed8463e8de414e5d06d3471"
 dependencies = [
- "proc-macro2 1.0.66",
- "quote 1.0.32",
- "syn 2.0.28",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
+ "syn 2.0.48",
 ]
 
 [[package]]
@@ -1595,9 +1590,9 @@ dependencies = [
  "bumpalo",
  "log",
  "once_cell",
- "proc-macro2 1.0.66",
- "quote 1.0.32",
- "syn 2.0.28",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
+ "syn 2.0.48",
  "wasm-bindgen-shared",
 ]
 
@@ -1607,7 +1602,7 @@ version = "0.2.87"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "dee495e55982a3bd48105a7b947fd2a9b4a8ae3010041b9e0faab3f9cd028f1d"
 dependencies = [
- "quote 1.0.32",
+ "quote 1.0.35",
  "wasm-bindgen-macro-support",
 ]
 
@@ -1617,9 +1612,9 @@ version = "0.2.87"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "54681b18a46765f095758388f2d0cf16eb8d4169b639ab575a8f5693af210c7b"
 dependencies = [
- "proc-macro2 1.0.66",
- "quote 1.0.32",
- "syn 2.0.28",
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
+ "syn 2.0.48",
  "wasm-bindgen-backend",
  "wasm-bindgen-shared",
 ]
diff --git a/Cargo.toml b/Cargo.toml
index ee33a75c..f9018547 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,4 +8,4 @@ codegen-units = 1
 
 [workspace.dependencies]
 ndarray = { version = "0.15.6", features = ["approx-0_5"] }
-strum = { version = "0.24.1", features = ["derive"] }
+strum = { version = "0.26.0", features = ["derive"] }
diff --git a/quil-py/quil/program/__init__.pyi b/quil-py/quil/program/__init__.pyi
index eb057568..6127d47e 100644
--- a/quil-py/quil/program/__init__.pyi
+++ b/quil-py/quil/program/__init__.pyi
@@ -175,6 +175,110 @@ class Program:
         while ensuring that unique value is not already in use within the program.
         """
         ...
+    def control_flow_graph(self) -> "ControlFlowGraph":
+        """
+        Return the `control flow graph`_ of the program.
+
+        .. _control flow graph: https://en.wikipedia.org/wiki/Control-flow_graph
+        """
+
+@final
+class BasicBlock:
+    def as_schedule_seconds(self, program: Program) -> ScheduleSeconds:
+        """
+        Return the ``ScheduleSeconds`` representing the timing of the instructions within the block.
+
+        This schedule is computed by:
+
+        * Expanding each instruction within the block using the program's calibration definitions
+        * Resolving the `ScheduleSeconds` of the expanded instructions
+        * Mapping calibrated instructions back to the original instructions within this block, such that the
+          block's instruction is represented as a timespan encompassing all of its expanded instructions
+
+        Note: the schedule will not include instructions with zero duration (such as `FENCE`).
+
+        :param program: The program containing the calibrations to be used to schedule this block. Generally,
+            this should be the program from which the block was extracted.
+
+        The following example demonstrates construction of such a schedule for a simple program without explicit control
+        flow (and thus with only one basic block):
+
+        .. example-code::
+
+            .. code-block:: python
+
+                from quil.program import Program
+
+                program = Program.parse("CZ 0 1; CZ 0 2")
+
+                print(program.to_quil())
+
+                control_flow_graph = program.control_flow_graph()
+                assert control_flow_graph.has_dynamic_control_flow() == False
+
+                basic_blocks = control_flow_graph.basic_blocks()
+                assert len(basic_blocks) == 1
+
+                schedule = blocks[0].as_schedule_seconds(program, False)
+                print(f"Duration = {schedule.duration()}")
+
+                print(schedule.items())
+
+
+        Note: when an instruction is expanded, the "time" of that original instruction includes
+        the times of all of the resulting instructions. This may cause gate times to be
+        longer than a user might expect.
+
+        To understand why, consider a program like this:
+
+        .. example-code::
+
+            .. code-block:: text
+
+                # One-qubit frame
+                DEFFRAME 0 "a":
+                    ATTRIBUTE: 1
+
+                # Two-qubit frame
+                DEFFRAME 0 1 "b":
+                    ATTRIBUTE: 1
+
+                DEFCAL A 0:
+                    PULSE 0 "a" flat(duration: 1.0)
+
+                DEFCAL B 0 1:
+                    FENCE 1
+                    PULSE 0 1 "b" flat(duration: 1.0)
+
+                A 0
+                B 0 1
+
+        `B 0` will be scheduled from time 0 to time 2, because its inner `FENCE` is scheduled for time 0.
+        This may be unexpected if the user expects to see only the timing of the inner `PULSE`.
+        """
+    def gate_depth(self, gate_minimum_qubit_count: int) -> int:
+        """
+        Returns the length of the longest path from an initial instruction (one with no prerequisite instructions) to a final
+        instruction (one with no dependent instructions), where the length of a path is the number of gate instructions in the path.
+
+        :param gate_minimum_qubit_count: The minimum number of qubits in a gate for it to be counted in the depth.
+        """
+    def label(self) -> Optional[Target]:
+        """
+        Return the label of the block, if any. This is used to target this block in control flow.
+        """
+    def instructions(self) -> List[Instruction]:
+        """
+        Return a list of the instructions in the block, in order of definition.
+
+        This does not include the label or terminator instructions.
+        """
+    def terminator(self) -> Optional[Instruction]:
+        """
+        Return the control flow terminator instruction of the block, if any.
+
+        If this is ``None``, the implicit behavior is to "continue" to the subsequent block.
+        """
 
 @final
 class CalibrationSet:
@@ -238,6 +342,84 @@ class CalibrationSet:
         """
         ...
 
+
+@final
+class ScheduleSecondsItem:
+    """
+    A single item within a fixed schedule, representing a single instruction within a basic block.
+    """
+    @property
+    def instruction_index(self) -> int:
+        """
+        The index of the instruction within the basic block.
+        """
+    @property
+    def time_span(self) -> TimeSpanSeconds:
+        """
+        The time span during which the instruction is scheduled.
+        """
+
+
+@final
+class ControlFlowGraph:
+    """
+    Representation of a control flow graph (CFG) for a Quil program.
+
+    The CFG is a directed graph where each node is a basic block and each edge is a control flow
+    transition between two basic blocks.
+    """
+
+    def has_dynamic_control_flow(self) -> bool: 
+        """
+        Return ``True`` if the program has dynamic control flow, i.e. contains a conditional branch instruction.
+
+        ``False`` does not imply that there is only one basic block in the program. Multiple basic blocks may have
+        non-conditional control flow among them, in which the execution order is deterministic and does not depend
+        on program state. This may be a sequence of basic blocks with fixed `JUMP`s or without explicit terminators.
+        """
+    def basic_blocks(self) -> List["BasicBlock"]: 
+        """
+        Return a list of all the basic blocks in the control flow graph, in order of definition.
+        """
+
+@final
+class ScheduleSeconds:
+    def items(self) -> List[ScheduleSecondsItem]:
+        """
+        All the items in the schedule, in unspecified order.
+        """
+    def duration(self) -> float:
+        """
+        The duration of the schedule, in seconds.
+
+        This is the maximum of the end time of all the items.
+        """
+
+@final
+class TimeSpanSeconds:
+    """
+    Representation of a time span in seconds.
+    """
+    @property
+    def start(self) -> float:
+        """
+        The start time of the time span, in seconds.
+
+        This is relative to the start of the scheduling context (such as the basic block).
+        """
+    @property
+    def duration(self) -> float:
+        """
+        The duration of the time span, in seconds.
+        """
+    @property
+    def end(self) -> float:
+        """
+        The end time of the time span, in seconds.
+
+        This is the sum of the start time and duration.
+        """
+
 @final
 class FrameSet:
     @staticmethod
diff --git a/quil-py/src/program/analysis.rs b/quil-py/src/program/analysis.rs
new file mode 100644
index 00000000..547f294f
--- /dev/null
+++ b/quil-py/src/program/analysis.rs
@@ -0,0 +1,90 @@
+use pyo3::exceptions::PyValueError;
+use quil_rs::program::analysis::{
+    BasicBlock, BasicBlockOwned, BasicBlockScheduleError, ControlFlowGraph, ControlFlowGraphOwned,
+    QubitGraph, QubitGraphError,
+};
+use rigetti_pyo3::{
+    impl_repr, py_wrap_error, py_wrap_type, pyo3::prelude::*, wrap_error, PyWrapper, ToPythonError,
+};
+
+use crate::instruction::{PyInstruction, PyTarget};
+
+use super::{scheduling::PyScheduleSeconds, PyProgram};
+
+py_wrap_type! {
+    PyControlFlowGraph(ControlFlowGraphOwned) as "ControlFlowGraph"
+}
+
+impl_repr!(PyControlFlowGraph);
+
+#[pymethods]
+impl PyControlFlowGraph {
+    pub fn has_dynamic_control_flow(&self) -> bool {
+        ControlFlowGraph::from(self.as_inner()).has_dynamic_control_flow()
+    }
+
+    pub fn basic_blocks(&self) -> Vec<PyBasicBlock> {
+        ControlFlowGraph::from(self.as_inner())
+            .into_blocks()
+            .into_iter()
+            .map(BasicBlockOwned::from)
+            .map(PyBasicBlock::from)
+            .collect()
+    }
+}
+
+py_wrap_type! {
+    PyBasicBlock(BasicBlockOwned) as "BasicBlock"
+}
+impl_repr!(PyBasicBlock);
+
+wrap_error!(RustBasicBlockScheduleError(BasicBlockScheduleError));
+py_wrap_error!(
+    quil,
+    RustBasicBlockScheduleError,
+    PyBasicBlockScheduleError,
+    PyValueError
+);
+
+wrap_error!(RustQubitGraphError(QubitGraphError));
+py_wrap_error!(quil, RustQubitGraphError, PyQubitGraphError, PyValueError);
+
+#[pymethods]
+impl PyBasicBlock {
+    pub fn as_schedule_seconds(&self, program: &PyProgram) -> PyResult<PyScheduleSeconds> {
+        BasicBlock::from(self.as_inner())
+            .as_schedule_seconds(program.as_inner())
+            .map(|v| v.into())
+            .map_err(RustBasicBlockScheduleError::from)
+            .map_err(RustBasicBlockScheduleError::to_py_err)
+    }
+
+    pub fn gate_depth(&self, gate_minimum_qubit_count: usize) -> PyResult<usize> {
+        let block = BasicBlock::from(self.as_inner());
+        QubitGraph::try_from(&block)
+            .map(|graph| graph.gate_depth(gate_minimum_qubit_count))
+            .map_err(RustQubitGraphError::from)
+            .map_err(RustQubitGraphError::to_py_err)
+    }
+
+    pub fn instructions(&self) -> Vec<PyInstruction> {
+        BasicBlock::from(self.as_inner())
+            .instructions()
+            .iter()
+            .copied()
+            .map(PyInstruction::from)
+            .collect()
+    }
+
+    pub fn label(&self) -> Option<PyTarget> {
+        BasicBlock::from(self.as_inner()).label().map(|l| l.into())
+    }
+
+    pub fn terminator(&self) -> Option<PyInstruction> {
+        BasicBlock::from(self.as_inner())
+            .terminator()
+            .clone()
+            .into_instruction()
+            .map(PyInstruction::from)
+    }
+}
diff --git a/quil-py/src/program/mod.rs b/quil-py/src/program/mod.rs
index 5b3f6bf8..6a0ac92a 100644
--- a/quil-py/src/program/mod.rs
+++ b/quil-py/src/program/mod.rs
@@ -6,7 +6,10 @@ use std::{
 use numpy::{PyArray2, ToPyArray};
 use quil_rs::{
     instruction::{Instruction, QubitPlaceholder, TargetPlaceholder, Waveform},
-    program::{CalibrationSet, FrameSet, MemoryRegion},
+    program::{
+        analysis::{ControlFlowGraph, ControlFlowGraphOwned},
+        CalibrationSet, FrameSet, MemoryRegion,
+    },
     Program,
 };
 use rigetti_pyo3::{
@@ -30,11 +33,17 @@ use crate::{
     },
 };
 
+use self::{
+    analysis::{PyBasicBlock, PyControlFlowGraph},
+    scheduling::{PyScheduleSeconds, PyScheduleSecondsItem, PyTimeSpanSeconds},
+};
 pub use self::{calibration::PyCalibrationSet, frame::PyFrameSet, memory::PyMemoryRegion};
 
+mod analysis;
 mod calibration;
 mod frame;
 mod memory;
+mod scheduling;
 
 wrap_error!(ProgramError(quil_rs::program::ProgramError));
 py_wrap_error!(quil, ProgramError, PyProgramError, PyValueError);
@@ -73,6 +82,10 @@ impl PyProgram {
         Self(self.as_inner().clone())
     }
 
+    pub fn control_flow_graph(&self) -> PyControlFlowGraph {
+        ControlFlowGraphOwned::from(ControlFlowGraph::from(self.as_inner())).into()
+    }
+
     #[getter]
     pub fn body_instructions<'a>(&self, py: Python<'a>) -> PyResult<&'a PyList> {
         Ok(PyList::new(
@@ -360,5 +373,5 @@ impl PyProgram {
 }
 
 create_init_submodule! {
-    classes: [ PyFrameSet, PyProgram, PyCalibrationSet, PyMemoryRegion ],
+    classes: [ PyFrameSet, PyProgram, PyCalibrationSet, PyMemoryRegion, PyBasicBlock, PyControlFlowGraph, PyScheduleSeconds, PyScheduleSecondsItem, PyTimeSpanSeconds ],
 }
diff --git a/quil-py/src/program/scheduling.rs b/quil-py/src/program/scheduling.rs
new file mode 100644
index 00000000..7970a576
--- /dev/null
+++ b/quil-py/src/program/scheduling.rs
@@ -0,0 +1,78 @@
+use pyo3::exceptions::PyValueError;
+use quil_rs::program::scheduling::{
+    ComputedScheduleError, ComputedScheduleItem, ScheduleSeconds, Seconds, TimeSpan,
+};
+use rigetti_pyo3::{
+    impl_repr, py_wrap_error, py_wrap_type, pyo3::prelude::*, wrap_error, PyWrapper,
+};
+
+wrap_error!(RustComputedScheduleError(ComputedScheduleError));
+py_wrap_error!(
+    quil,
+    RustComputedScheduleError,
+    PyComputedScheduleError,
+    PyValueError
+);
+py_wrap_type! {
+    PyScheduleSeconds(ScheduleSeconds) as "ScheduleSeconds"
+}
+
+impl_repr!(PyScheduleSeconds);
+
+#[pymethods]
+impl PyScheduleSeconds {
+    pub fn items(&self) -> Vec<PyScheduleSecondsItem> {
+        self.as_inner()
+            .items()
+            .iter()
+            .map(PyScheduleSecondsItem::from)
+            .collect()
+    }
+
+    pub fn duration(&self) -> f64 {
+        self.as_inner().duration().0
+    }
+}
+
+py_wrap_type! {
+    PyScheduleSecondsItem(ComputedScheduleItem<Seconds>) as "ScheduleSecondsItem"
+}
+
+impl_repr!(PyScheduleSecondsItem);
+
+#[pymethods]
+impl PyScheduleSecondsItem {
+    #[getter]
+    pub fn time_span(&self) -> PyTimeSpanSeconds {
+        (&self.as_inner().time_span).into()
+    }
+
+    #[getter]
+    pub fn instruction_index(&self) -> usize {
+        self.as_inner().instruction_index
+    }
+}
+
+py_wrap_type! {
+    PyTimeSpanSeconds(TimeSpan<Seconds>) as "TimeSpanSeconds"
+}
+
+impl_repr!(PyTimeSpanSeconds);
+
+#[pymethods]
+impl PyTimeSpanSeconds {
+    #[getter]
+    pub fn start(&self) -> f64 {
+        self.as_inner().start_time().0
+    }
+
+    #[getter]
+    pub fn duration(&self) -> f64 {
+        self.as_inner().duration().0
+    }
+
+    #[getter]
+    pub fn end(&self) -> f64 {
+        self.as_inner().end().0
+    }
+}
diff --git a/quil-rs/Cargo.toml b/quil-rs/Cargo.toml
index 0c5681d4..bb332737 100644
--- a/quil-rs/Cargo.toml
+++ b/quil-rs/Cargo.toml
@@ -12,19 +12,19 @@ categories = ["parser-implementations", "science", "compilers", "emulators"]
 [dependencies]
 approx = { version = "0.5.1", features = ["num-complex"] }
 dot-writer = { version = "0.1.2", optional = true }
-indexmap = "1.6.1"
-itertools = "0.11.0"
+indexmap = "2.2.2"
+itertools = "0.12.1"
 lexical = "6.1.1"
 ndarray.workspace = true
 nom = "7.1.1"
 nom_locate = "4.0.0"
 num-complex = "0.4.0"
 once_cell = "1.17.1"
-petgraph = "0.6.2"
+petgraph = "0.6.4"
 regex = "1.7.1"
 serde = { version = "1.0.125", features = ["derive"] }
 strum.workspace = true
-thiserror = "1.0.37"
+thiserror = "1.0.56"
 
 [dev-dependencies]
 clap = { version = "4.3.19", features = ["derive", "string"] }
@@ -34,7 +34,7 @@ petgraph = "0.6.2"
 proptest = "1.0.0"
 proptest-derive = "0.3.0"
 rand = "0.8.5"
-rstest = "0.18.1"
+rstest = "0.18.2"
 
 # These are described in the crate README.md
 [features]
diff --git a/quil-rs/benches/scheduled_program_from_program.rs b/quil-rs/benches/scheduled_program_from_program.rs
index 5e722c3d..ced3c17f 100644
--- a/quil-rs/benches/scheduled_program_from_program.rs
+++ b/quil-rs/benches/scheduled_program_from_program.rs
@@ -1,5 +1,5 @@
 use criterion::{black_box, criterion_group, criterion_main, BatchSize, Criterion};
-use quil_rs::{instruction::InstructionHandler, program::graph::ScheduledProgram};
+use quil_rs::{instruction::InstructionHandler, program::scheduling::ScheduledProgram};
 use std::str::FromStr;
 
 mod corpus;
diff --git a/quil-rs/src/expression/mod.rs b/quil-rs/src/expression/mod.rs
index 311832f6..dd37ed97 100644
--- a/quil-rs/src/expression/mod.rs
+++ b/quil-rs/src/expression/mod.rs
@@ -1021,7 +1021,7 @@ mod tests {
 
     #[test]
     fn specific_simplification_tests() {
-        for (input, expected) in vec![
+        for (input, expected) in [
             ("pi", Expression::Number(PI.into())),
             ("pi/2", Expression::Number((PI / 2.0).into())),
             ("pi * pi", Expression::Number((PI.powi(2)).into())),
@@ -1042,7 +1042,7 @@ mod tests {
 
     #[test]
     fn specific_to_real_tests() {
-        for (input, expected) in vec![
+        for (input, expected) in [
             (Expression::PiConstant, Ok(PI)),
             (Expression::Number(Complex64 { re: 1.0, im: 0.0 }), Ok(1.0)),
             (
diff --git a/quil-rs/src/instruction/control_flow.rs b/quil-rs/src/instruction/control_flow.rs
index ab22fba1..40200f75 100644
--- a/quil-rs/src/instruction/control_flow.rs
+++ b/quil-rs/src/instruction/control_flow.rs
@@ -25,7 +25,7 @@ impl Quil for Label {
     }
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash, strum::EnumTryAs)]
 pub enum Target {
     Fixed(String),
     Placeholder(TargetPlaceholder),
diff --git a/quil-rs/src/instruction/frame.rs b/quil-rs/src/instruction/frame.rs
index 8b53fe88..ab4c8e9d 100644
--- a/quil-rs/src/instruction/frame.rs
+++ b/quil-rs/src/instruction/frame.rs
@@ -10,7 +10,7 @@ use crate::{
     quil::Quil,
 };
 
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash, strum::EnumTryAs)]
 pub enum AttributeValue {
     String(String),
     Expression(Expression),
diff --git a/quil-rs/src/instruction/qubit.rs b/quil-rs/src/instruction/qubit.rs
index 73c54eba..8239ec77 100644
--- a/quil-rs/src/instruction/qubit.rs
+++ b/quil-rs/src/instruction/qubit.rs
@@ -2,7 +2,7 @@ use std::sync::Arc;
 
 use crate::quil::{Quil, ToQuilError};
 
-#[derive(Clone, Debug, Eq, Hash, PartialEq, PartialOrd, Ord)]
+#[derive(Clone, Debug, Eq, Hash, PartialEq, PartialOrd, Ord, strum::EnumTryAs)]
 pub enum Qubit {
     Fixed(u64),
     Placeholder(QubitPlaceholder),
diff --git a/quil-rs/src/program/analysis/control_flow_graph.rs b/quil-rs/src/program/analysis/control_flow_graph.rs
new file mode 100644
index 00000000..98f60170
--- /dev/null
+++ b/quil-rs/src/program/analysis/control_flow_graph.rs
@@ -0,0 +1,772 @@
+//! Construction and analysis of a control flow graph (CFG) for a Quil program.
+
+// Copyright 2024 Rigetti Computing
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+use std::{
+    collections::{BTreeMap, HashMap},
+    fmt::Debug,
+};
+
+use crate::{
+    instruction::{
+        Instruction, InstructionHandler, Jump, JumpUnless, JumpWhen, Label, MemoryReference, Target,
+    },
+    program::{
+        scheduling::{
+            schedule::{ComputedScheduleError, ComputedScheduleItem, Schedule, TimeSpan, Zero},
+            ScheduleError, ScheduledBasicBlock, Seconds,
+        },
+        ProgramError,
+    },
+    Program,
+};
+
+/// A control flow graph (CFG) is a representation of a program's control flow as a directed graph.
+/// Each node in the graph is a basic block, a sequence of instructions with a single entry point
+/// and a single exit point. The edges in the graph represent control flow between basic blocks.
+#[derive(Clone, Debug, Default)]
+pub struct ControlFlowGraph<'p> {
+    blocks: Vec<BasicBlock<'p>>,
+}
+
+impl<'p> ControlFlowGraph<'p> {
+    /// Returns `true` if the program contains dynamic control flow, i.e. `JUMP-WHEN` or `JUMP-UNLESS`
+    pub fn has_dynamic_control_flow(&self) -> bool {
+        self.blocks
+            .iter()
+            .any(|block| block.terminator().is_dynamic())
+    }
+
+    /// Returns the basic blocks in the control flow graph.
+    pub fn into_blocks(self) -> Vec<BasicBlock<'p>> {
+        self.blocks
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct ControlFlowGraphOwned {
+    blocks: Vec<BasicBlockOwned>,
+}
+
+impl From<ControlFlowGraph<'_>> for ControlFlowGraphOwned {
+    fn from(value: ControlFlowGraph) -> Self {
+        let blocks = value
+            .blocks
+            .into_iter()
+            .map(BasicBlockOwned::from)
+            .collect();
+        ControlFlowGraphOwned { blocks }
+    }
+}
+
+impl<'p> From<&'p ControlFlowGraphOwned> for ControlFlowGraph<'p> {
+    fn from(value: &'p ControlFlowGraphOwned) -> Self {
+        let blocks = value.blocks.iter().map(BasicBlock::from).collect();
+        ControlFlowGraph { blocks }
+    }
+}
+
+#[derive(Clone, Debug, Default)]
+pub struct BasicBlock<'p> {
+    /// The label of the basic block, if any. An unlabeled basic block cannot be a target of a jump, but can
+    /// be entered by a [`BasicBlockTerminator::Continue`] from the preceding block or program start.
+    label: Option<&'p Target>,
+
+    /// The instructions within the basic block, not including its terminator.
+    instructions: Vec<&'p Instruction>,
+
+    /// The offset of the start of this block from the containing program, in instruction count.
+    /// For the first block in the program, this is `0`. This counts only "body" instructions, not
+    /// `DEFCAL`, `DEFFRAME`, et al.
+    ///
+    /// This is intended for use in debugging and source mapping.
+    instruction_index_offset: usize,
+
+    /// The terminator of the basic block, which determines the control flow to the next basic block.
+    terminator: BasicBlockTerminator<'p>,
+}
+
+impl<'p> BasicBlock<'p> {
+    pub fn label(&self) -> Option<&'p Target> {
+        self.label
+    }
+
+    pub fn instruction_index_offset(&self) -> usize {
+        self.instruction_index_offset
+    }
+
+    pub fn instructions(&self) -> &[&'p Instruction] {
+        self.instructions.as_ref()
+    }
+
+    pub fn terminator(&self) -> &BasicBlockTerminator<'p> {
+        &self.terminator
+    }
+
+    /// Compute the flattened schedule for this [`BasicBlock`] in terms of seconds,
+    /// using a default built-in calculation for the duration of scheduled instructions.
+    ///
+    /// # Arguments
+    ///
+    /// * `program` - The program containing this basic block. This is used to retrieve frame
+    ///   and calibration information.
+    pub fn as_schedule_seconds(
+        &self,
+        program: &Program,
+    ) -> Result<Schedule<Seconds>, BasicBlockScheduleError> {
+        self.as_schedule(
+            program,
+            ScheduledBasicBlock::get_instruction_duration_seconds,
+        )
+    }
+
+    /// Compute the schedule for this [`BasicBlock`] in terms of a generic unit of time,
+    /// using a provided function to calculate the duration of scheduled instructions in that unit.
+    ///
+    /// # Arguments
+    ///
+    /// * `program` - The program containing this basic block. This is used to retrieve frame
+    ///   and calibration information.
+    /// * `get_duration` - A function that takes a program and an instruction and returns the
+    ///   duration of the instruction in the desired time unit, or `None` if the instruction's
+    ///   duration is not known.
+    ///
+    /// Note: when an instruction is expanded, the "time" of that original instruction includes
+    /// the times of all of the resulting instructions. This may cause gate times to be
+    /// longer than a user might expect.
+    ///
+    /// To understand why, consider a program like this:
+    ///
+    /// ```text
+    /// # One-qubit frame
+    /// DEFFRAME 0 "a":
+    ///     ATTRIBUTE: 1
+    ///
+    /// # Two-qubit frame
+    /// DEFFRAME 0 1 "b":
+    ///     ATTRIBUTE: 1
+    ///
+    /// DEFCAL A 0:
+    ///     PULSE 0 "a" flat(duration: 1.0)
+    ///
+    /// DEFCAL B 0 1:
+    ///     FENCE 1
+    ///     PULSE 0 1 "b" flat(duration: 1.0)
+    ///
+    /// A 0
+    /// B 0 1
+    /// ```
+    ///
+    /// `B 0` will be scheduled from time 0 to time 2, because its inner `FENCE` is scheduled for time 0.
+    /// This may be unexpected if the user expects to see only the timing of the inner `PULSE`.
+    pub fn as_schedule<F, Time>(
+        &self,
+        program: &'p Program,
+        get_duration: F,
+    ) -> Result<Schedule<Time>, BasicBlockScheduleError>
+    where
+        F: Fn(&Program, &Instruction) -> Option<Time>,
+        Time: Clone
+            + Debug
+            + PartialOrd
+            + std::ops::Add<Time, Output = Time>
+            + std::ops::Sub<Time, Output = Time>
+            + Zero,
+    {
+        // 1: expand calibrations and track the source mapping
+        let mut calibrated_to_uncalibrated_instruction_source_mapping = BTreeMap::new();
+        let mut calibrated_block_instructions = Vec::new();
+
+        for (uncalibrated_instruction_index, instruction) in self.instructions.iter().enumerate() {
+            let first_calibrated_instruction_index = calibrated_block_instructions.len();
+            if let Some(expanded) = program.calibrations.expand(instruction, &[])? {
+                calibrated_block_instructions.extend(expanded.into_iter());
+            } else {
+                calibrated_block_instructions.push((*instruction).clone());
+            }
+            calibrated_to_uncalibrated_instruction_source_mapping.insert(
+                first_calibrated_instruction_index,
+                uncalibrated_instruction_index,
+            );
+        }
+
+        let calibrated_block = BasicBlock {
+            label: self.label,
+            instructions: calibrated_block_instructions.iter().collect(),
+            instruction_index_offset: self.instruction_index_offset,
+            terminator: self.terminator.clone(),
+        };
+
+        // 2: attempt to schedule the newly-expanded block
+        let mut instruction_handler = InstructionHandler::default();
+        let scheduled_self =
+            ScheduledBasicBlock::build(calibrated_block, program, &mut instruction_handler)?;
+        let schedule = scheduled_self.as_schedule(program, get_duration)?;
+
+        // 3: map that schedule back to the original instructions from this basic block using the source mapping
+        let uncalibrated_schedule_items_by_instruction_index = schedule
+            .into_items()
+            .into_iter()
+            .fold(HashMap::<usize, TimeSpan<Time>>::new(), |mut map, item| {
+                if let Some((_, uncalibrated_instruction_index)) =
+                    calibrated_to_uncalibrated_instruction_source_mapping
+                        .range(..=item.instruction_index)
+                        .next_back()
+                {
+                    if let Some(existing_time_span) = map.get_mut(uncalibrated_instruction_index) {
+                        *existing_time_span = existing_time_span.clone().union(item.time_span);
+                    } else {
+                        map.insert(*uncalibrated_instruction_index, item.time_span.clone());
+                    }
+                }
+
+                map
+            });
+
+        let schedule_items = uncalibrated_schedule_items_by_instruction_index
+            .into_iter()
+            .map(|(instruction_index, time_span)| ComputedScheduleItem {
+                instruction_index,
+                time_span,
+            })
+            .collect::<Vec<_>>();
+
+        let schedule = Schedule::from(schedule_items);
+        Ok(schedule)
+    }
+}
+
+#[allow(clippy::enum_variant_names)]
+#[derive(Debug, thiserror::Error)]
+pub enum BasicBlockScheduleError {
+    #[error(transparent)]
+    ScheduleError(#[from] ScheduleError),
+
+    #[error(transparent)]
+    ComputedScheduleError(#[from] ComputedScheduleError),
+
+    #[error(transparent)]
+    ProgramError(#[from] ProgramError),
+}
+
+#[derive(Clone, Debug)]
+pub struct BasicBlockOwned {
+    label: Option<Target>,
+    instructions: Vec<Instruction>,
+    instruction_index_offset: usize,
+    terminator: BasicBlockTerminatorOwned,
+}
+
+impl From<BasicBlock<'_>> for BasicBlockOwned {
+    fn from(value: BasicBlock) -> Self {
+        let label = value.label.cloned();
+        let instructions = value.instructions.into_iter().cloned().collect();
+        let instruction_index_offset = value.instruction_index_offset;
+        let terminator = value.terminator.into();
+        BasicBlockOwned {
+            label,
+            instructions,
+            instruction_index_offset,
+            terminator,
+        }
+    }
+}
+
+impl<'b> From<&'b BasicBlockOwned> for BasicBlock<'b> {
+    fn from(value: &'b BasicBlockOwned) -> Self {
+        let label = value.label.as_ref();
+        let instructions = value.instructions.iter().collect();
+        let instruction_index_offset = value.instruction_index_offset;
+        let terminator = (&value.terminator).into();
+        BasicBlock {
+            label,
+            instructions,
+            instruction_index_offset,
+            terminator,
+        }
+    }
+}
+
+/// The terminator of a basic block, which determines the control flow to the next basic block.
+#[derive(Clone, Debug, Default)]
+pub enum BasicBlockTerminator<'p> {
+    ConditionalJump {
+        condition: &'p MemoryReference,
+        target: &'p Target,
+        jump_if_condition_zero: bool,
+    },
+    #[default]
+    Continue,
+    Jump {
+        target: &'p Target,
+    },
+    Halt,
+}
+
+impl BasicBlockTerminator<'_> {
+    /// Returns `true` if the terminator is dynamic, i.e. `JUMP-WHEN` or `JUMP-UNLESS`.
+    ///
+    /// Dynamic terminators are those that can change the control flow based on the state of the
+    /// program at runtime, as opposed to static terminators like `JUMP` and `HALT`.
+    pub fn is_dynamic(&self) -> bool {
+        matches!(self, BasicBlockTerminator::ConditionalJump { .. })
+    }
+
+    pub fn into_instruction(self) -> Option<Instruction> {
+        match self {
+            BasicBlockTerminator::ConditionalJump {
+                condition,
+                target,
+                jump_if_condition_zero,
+            } => {
+                if jump_if_condition_zero {
+                    Some(Instruction::JumpUnless(JumpUnless {
+                        condition: condition.clone(),
+                        target: target.clone(),
+                    }))
+                } else {
+                    Some(Instruction::JumpWhen(JumpWhen {
+                        condition: condition.clone(),
+                        target: target.clone(),
+                    }))
+                }
+            }
+            BasicBlockTerminator::Continue => None,
+            BasicBlockTerminator::Jump { target } => Some(Instruction::Jump(Jump {
+                target: target.clone(),
+            })),
+            BasicBlockTerminator::Halt => Some(Instruction::Halt),
+        }
+    }
+}
+
+#[derive(Clone, Debug, Default)]
+pub enum BasicBlockTerminatorOwned {
+    ConditionalJump {
+        condition: MemoryReference,
+        target: Target,
+        jump_if_condition_zero: bool,
+    },
+    #[default]
+    Continue,
+    Jump {
+        target: Target,
+    },
+    Halt,
+}
+
+impl<'p> From<BasicBlockTerminator<'p>> for BasicBlockTerminatorOwned {
+    fn from(value: BasicBlockTerminator) -> Self {
+        match value {
+            BasicBlockTerminator::ConditionalJump {
+                condition,
+                target,
+                jump_if_condition_zero,
+            } => BasicBlockTerminatorOwned::ConditionalJump {
+                condition: condition.clone(),
+                target: target.clone(),
+                jump_if_condition_zero,
+            },
+            BasicBlockTerminator::Continue => BasicBlockTerminatorOwned::Continue,
+            BasicBlockTerminator::Jump { target } => BasicBlockTerminatorOwned::Jump {
+                target: target.clone(),
+            },
+            BasicBlockTerminator::Halt => BasicBlockTerminatorOwned::Halt,
+        }
+    }
+}
+
+impl<'p> From<&'p BasicBlockTerminatorOwned> for BasicBlockTerminator<'p> {
+    fn from(value: &'p BasicBlockTerminatorOwned) -> Self {
+        match value {
+            BasicBlockTerminatorOwned::ConditionalJump {
+                condition,
+                target,
+                jump_if_condition_zero,
+            } => BasicBlockTerminator::ConditionalJump {
+                condition,
+                target,
+                jump_if_condition_zero: *jump_if_condition_zero,
+            },
+            BasicBlockTerminatorOwned::Continue => BasicBlockTerminator::Continue,
+            BasicBlockTerminatorOwned::Jump { target } => BasicBlockTerminator::Jump { target },
+            BasicBlockTerminatorOwned::Halt => BasicBlockTerminator::Halt,
+        }
+    }
+}
+
+impl<'p> From<&'p Program> for ControlFlowGraph<'p> {
+    fn from(value: &'p Program) -> Self {
+        let mut graph = ControlFlowGraph::default();
+
+        let mut current_label = None;
+        let mut current_block_instructions = Vec::new();
+        let mut instruction_index_offset = 0;
+        for instruction in &value.instructions {
+            match instruction {
+                Instruction::Arithmetic(_)
+                | Instruction::BinaryLogic(_)
+                | Instruction::Capture(_)
+                | Instruction::Convert(_)
+                | Instruction::Comparison(_)
+                | Instruction::Delay(_)
+                | Instruction::Fence(_)
+                | Instruction::Exchange(_)
+                | Instruction::Gate(_)
+                | Instruction::Load(_)
+                | Instruction::Pragma(_)
+                | Instruction::Measurement(_)
+                | Instruction::Move(_)
+                | Instruction::Nop
+                | Instruction::Pulse(_)
+                | Instruction::RawCapture(_)
+                | Instruction::Reset(_)
+                | Instruction::SetFrequency(_)
+                | Instruction::SetPhase(_)
+                | Instruction::SetScale(_)
+                | Instruction::ShiftFrequency(_)
+                | Instruction::ShiftPhase(_)
+                | Instruction::Store(_)
+                | Instruction::SwapPhases(_)
+                | Instruction::UnaryLogic(_)
+                | Instruction::Wait => current_block_instructions.push(instruction),
+
+                Instruction::CalibrationDefinition(_)
+                | Instruction::CircuitDefinition(_)
+                | Instruction::Declaration(_)
+                | Instruction::FrameDefinition(_)
+                | Instruction::GateDefinition(_)
+                | Instruction::Include(_)
+                | Instruction::MeasureCalibrationDefinition(_)
+                | Instruction::WaveformDefinition(_) => {}
+
+                Instruction::Label(Label { target }) => {
+                    if !current_block_instructions.is_empty() || current_label.is_some() {
+                        let block = BasicBlock {
+                            label: current_label.take(),
+                            instructions: std::mem::take(&mut current_block_instructions),
+                            instruction_index_offset,
+                            terminator: BasicBlockTerminator::Continue,
+                        };
+                        // +1 for the label
+                        instruction_index_offset += block.instructions.len() + 1;
+                        graph.blocks.push(block);
+                    }
+
+                    current_label = Some(target);
+                }
+
+                Instruction::Jump(_)
+                | Instruction::JumpUnless(_)
+                | Instruction::JumpWhen(_)
+                | Instruction::Halt => {
+                    let terminator = match instruction {
+                        Instruction::Jump(jump) => BasicBlockTerminator::Jump {
+                            target: &jump.target,
+                        },
+                        Instruction::JumpUnless(jump_unless) => {
+                            BasicBlockTerminator::ConditionalJump {
+                                condition: &jump_unless.condition,
+                                target: &jump_unless.target,
+                                jump_if_condition_zero: true,
+                            }
+                        }
+                        Instruction::JumpWhen(jump_when) => BasicBlockTerminator::ConditionalJump {
+                            condition: &jump_when.condition,
+                            target: &jump_when.target,
+                            jump_if_condition_zero: false,
+                        },
+                        Instruction::Halt => BasicBlockTerminator::Halt,
+                        _ => unreachable!(),
+                    };
+                    let block = BasicBlock {
+                        label: current_label.take(),
+                        instructions: std::mem::take(&mut current_block_instructions),
+                        instruction_index_offset,
+                        terminator,
+                    };
+
+                    let label_instruction_offset = if block.label().is_some() { 1 } else { 0 };
+                    // +1 for this terminator instruction
+                    instruction_index_offset +=
+                        block.instructions.len() + 1 + label_instruction_offset;
+
+                    graph.blocks.push(block);
+                }
+            }
+        }
+
+        if !current_block_instructions.is_empty() || current_label.is_some() {
+            let block = BasicBlock {
+                label: current_label.take(),
+                instructions: current_block_instructions,
+                instruction_index_offset,
+                terminator: BasicBlockTerminator::Continue,
+            };
+            graph.blocks.push(block);
+        }
+
+        graph
+    }
+}
+
+impl<'a> TryFrom<&'a Program> for BasicBlock<'a> {
+    type Error = ProgramEmptyOrContainsMultipleBasicBlocks;
+
+    fn try_from(value: &'a Program) -> Result<Self, Self::Error> {
+        let blocks = ControlFlowGraph::from(value).blocks;
+        if blocks.len() == 1 {
+            Ok(blocks.into_iter().next().unwrap())
+        } else {
+            Err(ProgramEmptyOrContainsMultipleBasicBlocks)
+        }
+    }
+}
+
+#[derive(Debug, thiserror::Error)]
+#[error("Program is empty or contains multiple basic blocks")]
+pub struct ProgramEmptyOrContainsMultipleBasicBlocks;
+
+#[cfg(test)]
+mod tests {
+    use crate::Program;
+    use rstest::rstest;
+
+    use super::*;
+
+    use super::super::test_programs::*;
+
+    #[rstest]
+    #[case(QUIL_AS_TREE)]
+    #[case(QUIL_AS_INVERSE_TREE)]
+    #[case(QUIL_AS_LINEAR)]
+    #[case(QUIL_WITH_DIAMOND)]
+    #[case(QUIL_WITH_SWAP)]
+    #[case(KITCHEN_SINK_QUIL)]
+    fn expect_single_basic_block(#[case] input: &str) {
+        let program: Program = input.parse().unwrap();
+        let _: BasicBlock = (&program).try_into().unwrap();
+    }
+
+    #[rstest]
+    #[case(QUIL_AS_TREE, false)]
+    #[case(QUIL_AS_INVERSE_TREE, false)]
+    #[case(QUIL_AS_LINEAR, false)]
+    #[case(QUIL_WITH_DIAMOND, false)]
+    #[case(KITCHEN_SINK_QUIL, false)]
+    #[case(QUIL_WITH_JUMP, false)]
+    #[case(QUIL_WITH_JUMP_WHEN, true)]
+    #[case(QUIL_WITH_JUMP_UNLESS, true)]
+    fn has_dynamic_control_flow(#[case] input: &str, #[case] expected: bool) {
+        let program: Program = input.parse().unwrap();
+        let graph = ControlFlowGraph::from(&program);
+        let dynamic = graph.has_dynamic_control_flow();
+        assert_eq!(expected, dynamic);
+    }
+
+    #[rstest]
+    #[case(r#"LABEL @a
+JUMP @a
+LABEL @b
+JUMP @b
+LABEL @c
+JUMP @c
+"#, vec![0, 2, 4])]
+    #[case(r#"LABEL @a
+LABEL @b
+LABEL @c
+JUMP @c
+"#, vec![0, 1, 2])]
+    #[case(r#"DEFFRAME 0 "rf":
+    ATTRIBUTE: 1
+DEFCAL X 0:
+    Y 0
+X 0
+"#, vec![0])]
+    fn instruction_index_offset(#[case] input: &str, #[case] expected_block_offsets: Vec<usize>) {
+        let program: Program = input.parse().unwrap();
+        let graph = ControlFlowGraph::from(&program);
+        let blocks = graph.into_blocks();
+        println!("blocks: {:#?}", blocks);
+        let actual = blocks
+            .iter()
+            .map(|block| block.instruction_index_offset())
+            .collect::<Vec<_>>();
+
+        assert_eq!(expected_block_offsets, actual);
+    }
+
+    #[test]
+    fn schedule_uncalibrated() {
+        let input = r#"DEFFRAME 0 "a":
+    ATTRIBUTE: 1
+
+DEFFRAME 0 "b":
+    ATTRIBUTE: 1
+
+DEFCAL A 0:
+    NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
+    NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
+    NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
+
+DEFCAL B 0:
+    NONBLOCKING PULSE 0 "b" flat(duration: 10.0)
+
+A 0
+B 0
+FENCE
+B 0
+PULSE 0 "a" flat(duration: 1.0)
+"#;
+
+        let program: Program = input.parse().unwrap();
+        let graph = ControlFlowGraph::from(&program);
+        let blocks = graph.into_blocks();
+        println!("blocks: {:#?}", blocks);
+
+        let schedule = blocks[0].as_schedule_seconds(&program).unwrap();
+        println!("schedule: {:#?}", schedule);
+        assert_eq!(schedule.duration().0, 21.0);
+        let schedule_items = schedule.into_items();
+
+        let schedule_items_by_instruction_index = schedule_items
+            .iter()
+            .map(|item| (item.instruction_index, item.clone()))
+            .collect::<HashMap<_, _>>();
+
+        // `A 0` backed by multiple consecutive instructions should capture all of their times
+        assert_eq!(
+            schedule_items_by_instruction_index[&0]
+                .time_span
+                .start_time()
+                .0,
+            0.0
+        );
+        assert_eq!(
+            schedule_items_by_instruction_index[&0]
+                .time_span
+                .duration()
+                .0,
+            3.0
+        );
+
+        // `B 0` should be scheduled concurrently with `A 0`
+        assert_eq!(
+            schedule_items_by_instruction_index[&1]
+                .time_span
+                .start_time()
+                .0,
+            0.0
+        );
+        assert_eq!(
+            schedule_items_by_instruction_index[&1]
+                .time_span
+                .duration()
+                .0,
+            10.0
+        );
+
+        // `FENCE` should be scheduled after `A 0` and `B 0` and take no time.
+        // It is not included in the schedule items because it has zero duration.
+
+        // `B 0` should be scheduled after `FENCE`
+        assert_eq!(
+            schedule_items_by_instruction_index[&3]
+                .time_span
+                .start_time()
+                .0,
+            10.0
+        );
+        assert_eq!(
+            schedule_items_by_instruction_index[&3]
+                .time_span
+                .duration()
+                .0,
+            10.0
+        );
+
+        // `PULSE 0 "a" flat(duration: 1.0)` should be scheduled after `B 0` as a blocking pulse.
+        assert_eq!(
+            schedule_items_by_instruction_index[&4]
+                .time_span
+                .start_time()
+                .0,
+            20.0
+        );
+        assert_eq!(
+            schedule_items_by_instruction_index[&4]
+                .time_span
+                .duration()
+                .0,
+            1.0
+        );
+    }
+
+    #[test]
+    fn schedule_uncalibrated_cz() {
+        let input = r#"DEFFRAME 0 "flux_tx_cz":
+    TEST: 1
+
+DEFFRAME 1 "flux_tx_iswap":
+    TEST: 1
+
+DEFFRAME 1 "flux_tx_cz":
+    TEST: 1
+
+DEFFRAME 1 "flux_tx_iswap":
+    TEST: 1
+
+DEFFRAME 2 "flux_tx_cz":
+    TEST: 1
+
+DEFFRAME 2 "flux_tx_iswap":
+    TEST: 1
+
+DEFFRAME 3 "flux_tx_cz":
+    TEST: 1
+
+DEFFRAME 3 "flux_tx_iswap":
+    TEST: 1
+
+# Simplified version
+DEFCAL CZ q0 q1:
+    FENCE q0 q1
+    SET-PHASE q0 "flux_tx_cz" 0.0
+    SET-PHASE q1 "flux_tx_iswap" 0.0
+    NONBLOCKING PULSE q0 "flux_tx_cz" erf_square(duration: 6.000000000000001e-08)
+    NONBLOCKING PULSE q1 "flux_tx_iswap" erf_square(duration: 6.000000000000001e-08)
+    SHIFT-PHASE q0 "flux_tx_cz" 1.0
+    SHIFT-PHASE q1 "flux_tx_iswap" 1.0
+    FENCE q0 q1
+
+CZ 0 1
+CZ 2 3
+CZ 0 2
+"#;
+
+        let program: Program = input.parse().unwrap();
+        let graph = ControlFlowGraph::from(&program);
+        let blocks = graph.into_blocks();
+        println!("blocks: {:#?}", blocks);
+
+        let schedule = blocks[0].as_schedule_seconds(&program).unwrap();
+        let mut schedule_items = schedule.into_items();
+        schedule_items.sort_by_key(|item| item.instruction_index);
+
+        assert_eq!(schedule_items.len(), 3);
+
+        insta::assert_debug_snapshot!(schedule_items);
+    }
+}
diff --git a/quil-rs/src/program/analysis/mod.rs b/quil-rs/src/program/analysis/mod.rs
new file mode 100644
index 00000000..cc2be7f5
--- /dev/null
+++ b/quil-rs/src/program/analysis/mod.rs
@@ -0,0 +1,27 @@
+//! This module contains analysis tools for Quil programs.
+
+// Copyright 2024 Rigetti Computing
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+mod control_flow_graph;
+mod qubit_graph;
+
+pub use control_flow_graph::{
+    BasicBlock, BasicBlockOwned, BasicBlockScheduleError, BasicBlockTerminator,
+    BasicBlockTerminatorOwned, ControlFlowGraph, ControlFlowGraphOwned,
+};
+pub use qubit_graph::{QubitGraph, QubitGraphError};
+
+#[cfg(test)]
+pub(crate) mod test_programs;
diff --git a/quil-rs/src/program/analysis/qubit_graph.rs b/quil-rs/src/program/analysis/qubit_graph.rs
new file mode 100644
index 00000000..c7d3c945
--- /dev/null
+++ b/quil-rs/src/program/analysis/qubit_graph.rs
@@ -0,0 +1,255 @@
+//! The `QubitGraph` is a logical execution/dependency graph of
+//! instructions with respect to gates on shared qubits.
+
+// Copyright 2024 Rigetti Computing
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+use std::collections::HashMap;
+
+use crate::instruction::{Instruction, InstructionHandler, InstructionRole};
+use crate::quil::Quil;
+use petgraph::{graph::DiGraph, Direction};
+
+use super::BasicBlock;
+
+#[derive(Debug, thiserror::Error)]
+pub enum QubitGraphError {
+    #[error("Unsupported instruction: {}", .0.to_quil_or_debug())]
+    UnsupportedInstruction(Instruction),
+}
+
+/// QubitGraph is a logical execution/dependency graph of instructions.  Pragma, RF Control, and Control Flow instructions
+/// are not supported. It is a directed graph *from* the first instructions (the set of instructions that do not depend
+/// on prior instructions) *to* the last instructions (the set of instructions that are not prerequisites for any later
+/// instructions).
+///
+/// Nodes are instructions; edges link subsequent instructions which use a shared qubit.
+#[derive(Debug)]
+pub struct QubitGraph<'a> {
+    graph: DiGraph<&'a Instruction, ()>,
+}
+
+impl<'a> QubitGraph<'a> {
+    pub(crate) fn new(
+        instructions: impl Iterator<Item = &'a Instruction>,
+    ) -> Result<Self, QubitGraphError> {
+        let mut last_instruction_for_qubit = HashMap::new();
+        let mut graph = DiGraph::new();
+        let mut handler = InstructionHandler::default();
+
+        for instruction in instructions {
+            match handler.role_for_instruction(instruction) {
+                InstructionRole::ClassicalCompute => {
+                    if let Instruction::Pragma(_) = instruction {
+                        return Err(QubitGraphError::UnsupportedInstruction(instruction.clone()));
+                    }
+                } // Valid, mostly ignored
+                InstructionRole::ControlFlow => match &instruction {
+                    Instruction::Jump(_)
+                    | Instruction::JumpWhen(_)
+                    | Instruction::JumpUnless(_) => {
+                        return Err(QubitGraphError::UnsupportedInstruction(instruction.clone()))
+                    }
+                    _ => {}
+                },
+                InstructionRole::ProgramComposition => {} // Valid, includes Gate, etc.,
+                InstructionRole::RFControl => {
+                    return Err(QubitGraphError::UnsupportedInstruction(instruction.clone()))
+                }
+            }
+
+            let qubits: Vec<_> = instruction.get_qubits().into_iter().collect();
+
+            let node = graph.add_node(instruction);
+
+            for qubit in qubits {
+                if let Some(last_instruction) = last_instruction_for_qubit.insert(qubit, node) {
+                    graph.add_edge(last_instruction, node, ());
+                }
+            }
+        }
+
+        Ok(Self { graph })
+    }
+
+    /// Fold over all paths over the graph, starting from sources (nodes with no incoming edges),
+    /// and ending at sinks (nodes with no outgoing edges).
+    ///
+    /// The `f` function is called for each instruction in each path, with the current accumulator value and the current
+    /// instruction.
+    ///
+    /// # Examples
+    ///
+    /// ## Tree
+    ///
+    /// ```text
+    /// CNOT 0 1
+    /// X 0
+    /// H 1
+    /// ```
+    ///
+    /// 1. `CNOT 0 1` is visited with the initial value, and a new accumulator `A` is returned from `f`.
+    /// 2. `X 0` is visited with accumulator `A`, and a result value `B` is returned from `f`.
+    /// 3. `H 1` is visited with accumulator `A`, and a second result value `C` is returned from `f`.
+    /// 4. The result values are collected into a [`Vec`] and returned as `[B, C]`.
+    ///
+    /// ## Diamond
+    ///
+    /// If the program graph forms a diamond shape (i.e. multiple paths converge to a single node), the `f` function
+    /// will be called multiple times with the same instruction, but with potentially different accumulator values.
+    ///
+    /// ```text
+    /// CNOT 0 1
+    /// X 0
+    /// H 1
+    /// CNOT 1 0
+    /// ```
+    ///
+    /// 1. `CNOT 0 1` is visited with the initial value, and a new accumulator `A` is returned from `f`.
+    /// 2. `X 0` is visited with accumulator `A`, and a new accumulator `B` is returned from `f`.
+    /// 3. `H 1` is visited with accumulator `A`, and a new accumulator `C` is returned from `f`.
+    /// 4. `CNOT 1 0` is visited with accumulator `B`, and a result value `D` is returned from `f`.
+    /// 5. `CNOT 1 0` is visited with accumulator `C`, and a result value `E` is returned from `f`.
+    /// 5. The result values are collected into a [`Vec`] and returned as `[D, E]`.
+    fn path_fold<T, F>(&self, initial_value: T, mut f: F) -> Vec<T>
+    where
+        T: Clone + std::fmt::Debug,
+        F: FnMut(T, &Instruction) -> T,
+    {
+        let nodes: Vec<_> = self.graph.externals(Direction::Incoming).collect();
+        let mut stack = vec![(initial_value, nodes)];
+        let mut result = Vec::new();
+
+        while let Some((acc, nodes)) = stack.pop() {
+            if nodes.is_empty() {
+                result.push(acc);
+                continue;
+            }
+
+            for node in nodes {
+                let instruction = &self.graph[node];
+                let value = f(acc.clone(), instruction);
+                stack.push((
+                    value,
+                    self.graph
+                        .neighbors_directed(node, Direction::Outgoing)
+                        .collect(),
+                ));
+            }
+        }
+
+        result
+    }
+
+    /// Returns the length of the longest path from an initial instruction (one with no prerequisite instructions) to a final
+    /// instruction (one with no dependent instructions), where the length of a path is the number of gate instructions in the path.
+    ///
+    /// # Arguments
+    ///
+    /// * `gate_minimum_qubit_count` - The minimum number of qubits in a gate for it to be counted in the depth.
+    pub fn gate_depth(&self, gate_minimum_qubit_count: usize) -> usize {
+        let path_lengths = self.path_fold(0, |depth: usize, instruction: &Instruction| -> usize {
+            if let Instruction::Gate(gate) = instruction {
+                if gate.qubits.len() >= gate_minimum_qubit_count {
+                    return depth + 1;
+                }
+            }
+            depth
+        });
+        path_lengths.into_iter().max().unwrap_or_default()
+    }
+}
+
+impl<'a> TryFrom<&'_ BasicBlock<'a>> for QubitGraph<'a> {
+    type Error = QubitGraphError;
+
+    fn try_from(block: &BasicBlock<'a>) -> Result<Self, Self::Error> {
+        QubitGraph::new(block.instructions().iter().copied())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::Program;
+    use rstest::rstest;
+
+    use super::*;
+
+    use super::super::test_programs::*;
+
+    #[rstest]
+    #[case(QUIL_AS_TREE, 2)]
+    #[case(QUIL_AS_INVERSE_TREE, 2)]
+    #[case(QUIL_AS_LINEAR, 4)]
+    #[case(QUIL_WITH_DIAMOND, 6)]
+    #[case(QUIL_WITH_SWAP, 3)]
+    #[case(KITCHEN_SINK_QUIL, 2)]
+    fn gate_depth(#[case] input: &str, #[case] expected: usize) {
+        let program: Program = input.parse().unwrap();
+        let block: BasicBlock = (&program).try_into().unwrap();
+        let graph: QubitGraph = (&block).try_into().unwrap();
+        let depth = graph.gate_depth(1);
+        assert_eq!(expected, depth);
+    }
+
+    #[rstest]
+    #[case(QUIL_AS_TREE, 1)]
+    #[case(QUIL_AS_INVERSE_TREE, 1)]
+    #[case(QUIL_AS_LINEAR, 0)]
+    #[case(QUIL_WITH_DIAMOND, 2)]
+    #[case(QUIL_WITH_SWAP, 1)]
+    #[case(KITCHEN_SINK_QUIL, 1)]
+    fn multiqubit_gate_depth(#[case] input: &str, #[case] expected: usize) {
+        let program: Program = input.parse().unwrap();
+        let block: BasicBlock = (&program).try_into().unwrap();
+        let graph: QubitGraph = (&block).try_into().unwrap();
+        let depth = graph.gate_depth(2);
+        assert_eq!(expected, depth);
+    }
+
+    #[rstest]
+    #[case(QUIL_AS_TREE, Some(2))]
+    #[case(QUIL_AS_INVERSE_TREE, Some(2))]
+    #[case(QUIL_AS_LINEAR, Some(4))]
+    #[case(QUIL_WITH_DIAMOND, Some(6))]
+    #[case(QUIL_WITH_SWAP, Some(3))]
+    #[case(KITCHEN_SINK_QUIL, Some(2))]
+    #[case(QUIL_WITH_JUMP, None)]
+    #[case(QUIL_WITH_JUMP_WHEN, None)]
+    #[case(QUIL_WITH_JUMP_UNLESS, None)]
+    fn gate_depth_conditional(#[case] input: &str, #[case] expected: Option<usize>) {
+        let program: Program = input.parse().unwrap();
+        let block = (&program).try_into();
+        let block: BasicBlock = match block {
+            Ok(block) => block,
+            Err(_) => {
+                if expected.is_none() {
+                    return;
+                } else {
+                    panic!("Expected block, got error");
+                }
+            }
+        };
+
+        let maybe_graph: Result<QubitGraph, _> = (&block).try_into();
+        match maybe_graph {
+            Ok(graph) => {
+                let depth = graph.gate_depth(1);
+                assert_eq!(expected, Some(depth));
+            }
+            Err(_) => {
+                assert_eq!(expected, None)
+            }
+        }
+    }
+}
diff --git a/quil-rs/src/program/calibration.rs b/quil-rs/src/program/calibration.rs
index 282a8115..ad7b18e8 100644
--- a/quil-rs/src/program/calibration.rs
+++ b/quil-rs/src/program/calibration.rs
@@ -17,6 +17,7 @@ use std::collections::HashMap;
 use itertools::FoldWhile::{Continue, Done};
 use itertools::Itertools;
 
+use crate::instruction::Fence;
 use crate::quil::Quil;
 use crate::{
     expression::Expression,
@@ -145,7 +146,8 @@ impl CalibrationSet {
                                 | Instruction::Pulse(Pulse {
                                     frame: FrameIdentifier { qubits, .. },
                                     ..
-                                }) => {
+                                })
+                                | Instruction::Fence(Fence { qubits }) => {
                                     // Swap all qubits for their concrete implementations
                                     for qubit in qubits {
                                         match qubit {
@@ -537,6 +539,15 @@ mod tests {
             "RZ(pi) 0\n",
         )
     )]
+    #[case(
+        "FenceVariableQubit",
+        concat!(
+            "DEFCAL FENCES q0 q1:\n",
+            "    FENCE q0\n",
+            "    FENCE q1\n",
+            "FENCES 0 1\n",
+        )
+    )]
     fn test_expansion(#[case] description: &str, #[case] input: &str) {
         let program = Program::from_str(input).unwrap();
         let calibrated_program = program.expand_calibrations().unwrap();
diff --git a/quil-rs/src/program/mod.rs b/quil-rs/src/program/mod.rs
index e8f18333..19572cca 100644
--- a/quil-rs/src/program/mod.rs
+++ b/quil-rs/src/program/mod.rs
@@ -35,11 +35,12 @@ pub use self::frame::FrameSet;
 pub use self::frame::MatchedFrames;
 pub use self::memory::{MemoryAccesses, MemoryRegion};
 
+pub mod analysis;
 mod calibration;
 mod error;
 pub(crate) mod frame;
-pub mod graph;
 mod memory;
+pub mod scheduling;
 pub mod type_check;
 
 #[derive(Debug, thiserror::Error, PartialEq)]
@@ -62,9 +63,6 @@ pub enum ProgramError {
 
 type Result<T> = std::result::Result<T, ProgramError>;
 
-#[cfg(feature = "graphviz-dot")]
-pub mod graphviz_dot;
-
 /// A Quil Program instance describes a quantum program with metadata used in execution.
 ///
 /// This contains not only instructions which are executed in turn on the quantum processor, but
@@ -239,7 +237,6 @@ impl Program {
     pub fn expand_calibrations(&self) -> Result<Self> {
         let mut expanded_instructions: Vec<Instruction> = vec![];
 
-        // TODO: Do this more efficiently, possibly with Vec::splice
         for instruction in &self.instructions {
             match self.calibrations.expand(instruction, &[])? {
                 Some(expanded) => {
@@ -326,13 +323,7 @@ impl Program {
 
     /// Consume the [`Program`] to return all of the instructions which constitute it.
     pub fn into_instructions(self) -> Vec<Instruction> {
-        let capacity = self.memory_regions.len()
-            + self.frames.len()
-            + self.waveforms.len()
-            + self.gate_definitions.len()
-            + self.instructions.len();
-
-        let mut instructions: Vec<Instruction> = Vec::with_capacity(capacity);
+        let mut instructions: Vec<Instruction> = Vec::with_capacity(self.len());
 
         instructions.extend(self.memory_regions.into_iter().map(|(name, descriptor)| {
             Instruction::Declaration(Declaration {
@@ -564,15 +555,21 @@ impl Program {
         Box::new(move |key| qubit_resolutions.get(key).copied())
     }
 
-    /// Return a copy of all of the instructions which constitute this [`Program`].
-    pub fn to_instructions(&self) -> Vec<Instruction> {
-        let capacity = self.memory_regions.len()
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    pub fn len(&self) -> usize {
+        self.memory_regions.len()
             + self.frames.len()
             + self.waveforms.len()
             + self.gate_definitions.len()
-            + self.instructions.len();
+            + self.instructions.len()
+    }
 
-        let mut instructions: Vec<Instruction> = Vec::with_capacity(capacity);
+    /// Return a copy of all of the instructions which constitute this [`Program`].
+    pub fn to_instructions(&self) -> Vec<Instruction> {
+        let mut instructions: Vec<Instruction> = Vec::with_capacity(self.len());
 
         instructions.extend(self.memory_regions.iter().map(|(name, descriptor)| {
             Instruction::Declaration(Declaration {
diff --git a/quil-rs/src/program/graph.rs b/quil-rs/src/program/scheduling/graph.rs
similarity index 69%
rename from quil-rs/src/program/graph.rs
rename to quil-rs/src/program/scheduling/graph.rs
index 45a2e0c9..a67806c6 100644
--- a/quil-rs/src/program/graph.rs
+++ b/quil-rs/src/program/scheduling/graph.rs
@@ -16,17 +16,16 @@
 
 use std::collections::{HashMap, HashSet};
 
-use indexmap::IndexMap;
 use petgraph::graphmap::GraphMap;
 use petgraph::Directed;
 
-use crate::instruction::{
-    FrameIdentifier, Instruction, InstructionHandler, Jump, JumpUnless, JumpWhen, Label,
-    MemoryReference, Target,
+use crate::instruction::{FrameIdentifier, Instruction, InstructionHandler, Target};
+use crate::program::analysis::{
+    BasicBlock, BasicBlockOwned, BasicBlockTerminator, ControlFlowGraph,
 };
-use crate::{instruction::InstructionRole, program::Program};
+use crate::{instruction::InstructionRole, program::Program, quil::Quil};
 
-pub use super::memory::MemoryAccessType;
+pub use crate::program::memory::MemoryAccessType;
 
 #[derive(Debug, Clone)]
 pub enum ScheduleErrorVariant {
@@ -35,7 +34,8 @@ pub enum ScheduleErrorVariant {
     UnschedulableInstruction,
 }
 
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, thiserror::Error)]
+#[error("Error scheduling instruction {}: {}: {variant:?}", .instruction_index.map(|i| i.to_string()).unwrap_or(String::from("")), .instruction.to_quil_or_debug())]
 pub struct ScheduleError {
     pub instruction_index: Option<usize>,
     pub instruction: Instruction,
@@ -191,26 +191,16 @@ macro_rules! add_dependency {
 
 pub type DependencyGraph = GraphMap<ScheduledGraphNode, HashSet<ExecutionDependency>, Directed>;
 
-/// An InstructionBlock of a ScheduledProgram is a group of instructions, identified by a string label,
-/// which include no control flow instructions aside from an (optional) terminating control
-/// flow instruction.
+/// A [`ScheduledBasicBlock`] is a wrapper around a [`BasicBlock`] which includes a graph expressing the vector clock
+/// among the instructions according to the Quil specification.
+///
+/// If instruction A blocks instruction B (because of shared use of a frame), then there will be an edge from A to B
+/// in the graph.
 #[derive(Clone, Debug)]
-pub struct InstructionBlock<'a> {
-    pub instructions: Vec<&'a Instruction>,
+pub struct ScheduledBasicBlock<'a> {
+    basic_block: BasicBlock<'a>,
     pub(super) graph: DependencyGraph,
-    pub terminator: BlockTerminator<'a>,
 }
-
-impl<'a> Default for InstructionBlock<'a> {
-    fn default() -> Self {
-        Self {
-            instructions: Default::default(),
-            graph: Default::default(),
-            terminator: BlockTerminator::Continue,
-        }
-    }
-}
-
 /// PreviousNodes is a structure which helps maintain ordering among instructions which operate on a given frame.
 /// It works similarly to a multiple-reader-single-writer queue, where an instruction which "uses" a frame is like
 /// a writer and an instruction which blocks that frame is like a reader. Multiple instructions may concurrently
@@ -289,11 +279,10 @@ impl PreviousNodes {
     }
 }
 
-impl<'a> InstructionBlock<'a> {
+impl<'a> ScheduledBasicBlock<'a> {
+    /// Build a scheduled basic block from a basic block and a program.
     pub fn build(
-        // The set of instructions in the block, a subset of the `program`.
-        instructions: Vec<&'a Instruction>,
-        terminator: Option<BlockTerminator<'a>>,
+        basic_block: BasicBlock<'a>,
         program: &'a Program,
         custom_handler: &mut InstructionHandler,
     ) -> ScheduleResult<Self> {
@@ -312,7 +301,7 @@ impl<'a> InstructionBlock<'a> {
         // NOTE: this may be refined to serialize by memory region offset rather than by entire region.
         let mut pending_memory_access: HashMap<String, MemoryAccessQueue> = HashMap::new();
 
-        for (index, &instruction) in instructions.iter().enumerate() {
+        for (index, &instruction) in basic_block.instructions().iter().enumerate() {
             let node = graph.add_node(ScheduledGraphNode::InstructionIndex(index));
 
             match custom_handler.role_for_instruction(instruction) {
@@ -440,107 +429,48 @@ impl<'a> InstructionBlock<'a> {
             add_dependency!(graph, dependency.node_id => ScheduledGraphNode::BlockEnd, execution_dependency);
         }
 
-        Ok(InstructionBlock {
-            graph,
-            instructions,
-            terminator: terminator.unwrap_or(BlockTerminator::Continue),
-        })
+        Ok(ScheduledBasicBlock { graph, basic_block })
     }
 
     pub fn get_dependency_graph(&self) -> &DependencyGraph {
         &self.graph
     }
 
+    pub fn instructions(&'a self) -> &[&'a Instruction] {
+        self.basic_block.instructions()
+    }
+
     /// Return a particular-indexed instruction (if present).
     pub fn get_instruction(&self, node_id: usize) -> Option<&Instruction> {
-        self.instructions.get(node_id).copied()
+        self.instructions().get(node_id).copied()
+    }
+
+    pub fn label(&self) -> Option<&Target> {
+        self.basic_block.label()
     }
 
     /// Return the count of executable instructions in this block.
     pub fn len(&self) -> usize {
-        self.instructions.len()
+        self.instructions().len()
     }
 
     /// Return true if this block contains no executable instructions.
     pub fn is_empty(&self) -> bool {
-        self.instructions.is_empty()
+        self.instructions().is_empty()
     }
 
-    pub fn set_exit_condition(&mut self, terminator: BlockTerminator<'a>) {
-        self.terminator = terminator;
+    pub fn terminator(&self) -> &BasicBlockTerminator {
+        self.basic_block.terminator()
     }
-}
 
-#[derive(Clone, Debug, PartialEq)]
-pub enum BlockTerminator<'a> {
-    Conditional {
-        condition: &'a MemoryReference,
-        target: &'a str,
-        jump_if_condition_true: bool,
-    },
-    Unconditional {
-        target: &'a str,
-    },
-    Continue,
-    Halt,
+    pub fn basic_block(&self) -> &BasicBlock<'a> {
+        &self.basic_block
+    }
 }
 
 #[derive(Clone, Debug)]
 pub struct ScheduledProgram<'a> {
-    /// All blocks within the ScheduledProgram, keyed on string label.
-    pub blocks: IndexMap<String, InstructionBlock<'a>>,
-}
-
-/// Builds an [`InstructionBlock`] from provided instructions, terminator, and program, then tracks
-/// the block and its label, and resets the instruction list and label for a future block to use.
-///
-/// The "working block" is that being traversed within the program, accumulating instructions located
-/// between control instructions (such as `LABEL` and 'JUMP`). When such a control instruction is reached,
-/// this function performs the work to close out and store the instructions in the current "working block"
-/// and then reset the state to prepare for the next block.
-///
-/// # Errors
-///
-/// If an error occurs, `working_instructions` and/or `working_label` may have been emptied and
-/// cannot be relied on to be unchanged.
-fn terminate_working_block<'a>(
-    terminator: Option<BlockTerminator<'a>>,
-    working_instructions: &mut Vec<&'a Instruction>,
-    blocks: &mut IndexMap<String, InstructionBlock<'a>>,
-    working_label: &mut Option<&'a str>,
-    program: &'a Program,
-    instruction_index: Option<usize>,
-    custom_handler: &mut InstructionHandler,
-) -> ScheduleResult<()> {
-    // If this "block" has no instructions and no terminator, it's not worth storing - skip it
-    if working_instructions.is_empty() && terminator.is_none() && working_label.is_none() {
-        return Ok(());
-    }
-
-    // This leaves working_instructions and working_label in their respective "empty" states.
-    let block = InstructionBlock::build(
-        std::mem::take(working_instructions),
-        terminator,
-        program,
-        custom_handler,
-    )?;
-
-    let label = working_label
-        .take()
-        .map(String::from)
-        .unwrap_or_else(|| ScheduledProgram::generate_autoincremented_label(blocks));
-
-    if blocks.insert(label.clone(), block).is_some() {
-        return Err(ScheduleError {
-            instruction_index,
-            instruction: Instruction::Label(Label {
-                target: Target::Fixed(label),
-            }),
-            variant: ScheduleErrorVariant::DuplicateLabel,
-        });
-    }
-
-    Ok(())
+    basic_blocks: Vec<ScheduledBasicBlock<'a>>,
 }
 
 impl<'a> ScheduledProgram<'a> {
@@ -550,176 +480,60 @@ impl<'a> ScheduledProgram<'a> {
         program: &'a Program,
         custom_handler: &mut InstructionHandler,
     ) -> ScheduleResult<Self> {
-        let mut working_label = None;
-        let mut working_instructions: Vec<&'a Instruction> = vec![];
-        let mut blocks = IndexMap::new();
-
-        for (index, instruction) in program.body_instructions().enumerate() {
-            let instruction_index = Some(index);
-            match instruction {
-                Instruction::Arithmetic(_)
-                | Instruction::Comparison(_)
-                | Instruction::BinaryLogic(_)
-                | Instruction::Convert(_)
-                | Instruction::UnaryLogic(_)
-                | Instruction::Capture(_)
-                | Instruction::Delay(_)
-                | Instruction::Fence(_)
-                | Instruction::Include(_)
-                | Instruction::Move(_)
-                | Instruction::Nop
-                | Instruction::Exchange(_)
-                | Instruction::Load(_)
-                | Instruction::Store(_)
-                | Instruction::Pulse(_)
-                | Instruction::SetFrequency(_)
-                | Instruction::SetPhase(_)
-                | Instruction::SetScale(_)
-                | Instruction::ShiftFrequency(_)
-                | Instruction::ShiftPhase(_)
-                | Instruction::SwapPhases(_)
-                | Instruction::RawCapture(_)
-                | Instruction::Reset(_)
-                | Instruction::Wait => {
-                    working_instructions.push(instruction);
-                }
-                Instruction::CalibrationDefinition(_)
-                | Instruction::CircuitDefinition(_)
-                | Instruction::Declaration(_)
-                | Instruction::GateDefinition(_)
-                | Instruction::FrameDefinition(_)
-                | Instruction::MeasureCalibrationDefinition(_)
-                | Instruction::WaveformDefinition(_) => {}
-                Instruction::Pragma(_) => {
-                    working_instructions.push(instruction);
-                }
-                Instruction::Label(Label {
-                    target: Target::Fixed(value),
-                }) => {
-                    terminate_working_block(
-                        None as Option<BlockTerminator>,
-                        &mut working_instructions,
-                        &mut blocks,
-                        &mut working_label,
-                        program,
-                        instruction_index,
-                        custom_handler,
-                    )?;
-
-                    working_label = Some(value);
-                }
-                Instruction::Jump(Jump {
-                    target: Target::Fixed(target),
-                }) => {
-                    terminate_working_block(
-                        Some(BlockTerminator::Unconditional { target }),
-                        &mut working_instructions,
-                        &mut blocks,
-                        &mut working_label,
-                        program,
-                        instruction_index,
-                        custom_handler,
-                    )?;
-                }
-                Instruction::JumpWhen(JumpWhen {
-                    target: Target::Fixed(target),
-                    condition,
-                }) => {
-                    terminate_working_block(
-                        Some(BlockTerminator::Conditional {
-                            target,
-                            condition,
-                            jump_if_condition_true: true,
-                        }),
-                        &mut working_instructions,
-                        &mut blocks,
-                        &mut working_label,
-                        program,
-                        instruction_index,
-                        custom_handler,
-                    )?;
-                }
-                Instruction::JumpUnless(JumpUnless {
-                    target: Target::Fixed(target),
-                    condition,
-                }) => {
-                    terminate_working_block(
-                        Some(BlockTerminator::Conditional {
-                            target,
-                            condition,
-                            jump_if_condition_true: false,
-                        }),
-                        &mut working_instructions,
-                        &mut blocks,
-                        &mut working_label,
-                        program,
-                        instruction_index,
-                        custom_handler,
-                    )?;
-                }
-                Instruction::Halt => terminate_working_block(
-                    Some(BlockTerminator::Halt),
-                    &mut working_instructions,
-                    &mut blocks,
-                    &mut working_label,
-                    program,
-                    instruction_index,
-                    custom_handler,
-                )?,
-                Instruction::Gate(_)
-                | Instruction::Measurement(_)
-                | Instruction::Label(Label {
-                    target: Target::Placeholder(_),
-                })
-                | Instruction::Jump(_)
-                | Instruction::JumpWhen(_)
-                | Instruction::JumpUnless(_) => {
-                    return Err(ScheduleError {
-                        instruction_index,
-                        instruction: instruction.clone(),
-                        variant: ScheduleErrorVariant::UncalibratedInstruction,
-                    })
-                }
-            };
-        }
+        let control_flow_graph = ControlFlowGraph::from(program);
+        Ok(Self {
+            basic_blocks: control_flow_graph
+                .into_blocks()
+                .into_iter()
+                .map(|block| ScheduledBasicBlock::build(block, program, custom_handler))
+                .collect::<ScheduleResult<Vec<_>>>()?,
+        })
+    }
+
+    pub fn basic_blocks(&self) -> &[ScheduledBasicBlock<'_>] {
+        self.basic_blocks.as_ref()
+    }
+
+    pub fn into_basic_blocks(self) -> Vec<ScheduledBasicBlock<'a>> {
+        self.basic_blocks
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct ScheduledBasicBlockOwned {
+    basic_block: BasicBlockOwned,
+    graph: DependencyGraph,
+}
 
-        terminate_working_block(
-            None as Option<BlockTerminator>,
-            &mut working_instructions,
-            &mut blocks,
-            &mut working_label,
-            program,
-            None,
-            custom_handler,
-        )?;
-
-        Ok(ScheduledProgram { blocks })
+impl<'a> From<&'a ScheduledBasicBlockOwned> for ScheduledBasicBlock<'a> {
+    fn from(block: &'a ScheduledBasicBlockOwned) -> Self {
+        Self {
+            basic_block: (&block.basic_block).into(),
+            graph: block.graph.clone(),
+        }
     }
+}
 
-    fn generate_autoincremented_label(block_labels: &IndexMap<String, InstructionBlock>) -> String {
-        let mut suffix = 0;
-        let mut label = format!("block_{suffix}");
-        while block_labels.get(&label).is_some() {
-            suffix += 1;
-            label = format!("block_{suffix}");
+impl<'a> From<ScheduledBasicBlock<'a>> for ScheduledBasicBlockOwned {
+    fn from(block: ScheduledBasicBlock) -> Self {
+        Self {
+            basic_block: block.basic_block.into(),
+            graph: block.graph.clone(),
         }
-        label
     }
 }
 
 #[cfg(test)]
 mod tests {
-    use super::*;
-    use crate::instruction::Pragma;
-    use crate::program::{MatchedFrames, MemoryAccesses};
-
     #[cfg(feature = "graphviz-dot")]
     mod custom_handler {
-        use super::*;
+        use super::super::*;
 
+        use crate::instruction::Pragma;
         use crate::instruction::PragmaArgument;
         use crate::program::frame::FrameMatchCondition;
-        use crate::program::graphviz_dot::tests::build_dot_format_snapshot_test_case;
+        use crate::program::scheduling::graphviz_dot::tests::build_dot_format_snapshot_test_case;
+        use crate::program::{MatchedFrames, MemoryAccesses};
 
         /// Generates a custom [`InstructionHandler`] that specially handles two `PRAGMA` instructions:
         ///
diff --git a/quil-rs/src/program/graphviz_dot.rs b/quil-rs/src/program/scheduling/graphviz_dot.rs
similarity index 73%
rename from quil-rs/src/program/graphviz_dot.rs
rename to quil-rs/src/program/scheduling/graphviz_dot.rs
index e3249ec9..f555b292 100644
--- a/quil-rs/src/program/graphviz_dot.rs
+++ b/quil-rs/src/program/scheduling/graphviz_dot.rs
@@ -17,14 +17,19 @@
 use dot_writer::{Attributes, DotWriter, Shape, Style};
 
 use crate::{
-    program::graph::{
-        BlockTerminator, ExecutionDependency, InstructionBlock, MemoryAccessType,
-        ScheduledGraphNode, ScheduledProgram,
+    instruction::Target,
+    program::{
+        analysis::BasicBlockTerminator,
+        scheduling::graph::{
+            ExecutionDependency, MemoryAccessType, ScheduledBasicBlock, ScheduledGraphNode,
+        },
     },
     quil::Quil,
 };
 
-impl<'a> InstructionBlock<'a> {
+use super::graph::ScheduledProgram;
+
+impl<'a> ScheduledBasicBlock<'a> {
     /// Given a [`dot_writer::Scope`] representing a subgraph/cluster, write the timing graph for this block into it.
     /// Uses the `node_prefix` argument for namespacing so that node IDs remain unique within the overall graph.
     fn write_dot_format(&self, cluster: &mut dot_writer::Scope, node_prefix: &str) {
@@ -50,7 +55,7 @@ impl<'a> InstructionBlock<'a> {
                         .set_label(&escape_label(&format!(
                             "[{}] {}",
                             index,
-                            self.instructions.get(*index).unwrap().to_quil_or_debug()
+                            self.instructions().get(*index).unwrap().to_quil_or_debug()
                         )));
                 }
             };
@@ -83,6 +88,41 @@ impl<'a> InstructionBlock<'a> {
     }
 }
 
+#[derive(Debug, PartialEq)]
+enum DotFormatBlockLabel<'p> {
+    Unlabeled { index: usize },
+    Labeled(&'p Target),
+}
+
+impl<'p> DotFormatBlockLabel<'p> {
+    fn from_label_or_index(label: Option<&'p Target>, index: usize) -> Self {
+        label
+            .map(DotFormatBlockLabel::Labeled)
+            .unwrap_or(DotFormatBlockLabel::Unlabeled { index })
+    }
+}
+
+impl<'p> From<&'p Target> for DotFormatBlockLabel<'p> {
+    fn from(target: &'p Target) -> Self {
+        DotFormatBlockLabel::Labeled(target)
+    }
+}
+
+impl<'p> From<usize> for DotFormatBlockLabel<'p> {
+    fn from(index: usize) -> Self {
+        DotFormatBlockLabel::Unlabeled { index }
+    }
+}
+
+impl std::fmt::Display for DotFormatBlockLabel<'_> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            DotFormatBlockLabel::Unlabeled { index } => write!(f, "block_{}", index),
+            DotFormatBlockLabel::Labeled(label) => write!(f, "{}", label.to_quil_or_debug()),
+        }
+    }
+}
+
 impl<'a> ScheduledProgram<'a> {
     /// Return a DOT format string (as bytes) for use with Graphviz.
     ///
@@ -100,91 +140,125 @@ impl<'a> ScheduledProgram<'a> {
             writer.set_pretty_print(true);
             let mut digraph = writer.digraph();
 
-            let mut iter = self.blocks.iter().peekable();
-            if let Some((first_label, _)) = iter.peek() {
+            let blocks = self.basic_blocks();
+            println!("blocks: {:?}", blocks);
+            let mut iter = blocks.iter().enumerate().peekable();
+            if let Some((index, first_block)) = iter.peek() {
+                let block_node_label = first_block
+                    .basic_block()
+                    .label()
+                    .map(DotFormatBlockLabel::from)
+                    .unwrap_or(DotFormatBlockLabel::from(*index));
                 digraph.edge(
                     "entry",
-                    get_node_id(&ScheduledGraphNode::BlockStart, first_label),
+                    get_node_id(
+                        &ScheduledGraphNode::BlockStart,
+                        &block_node_label.to_string(),
+                    ),
                 );
             }
             digraph.node_named("entry").set_label("Entry Point");
 
-            while let Some((label, block)) = iter.next() {
-                let node_prefix = label;
+            while let Some((index, scheduled_basic_block)) = iter.next() {
+                let block_node_label = scheduled_basic_block
+                    .basic_block()
+                    .label()
+                    .map(DotFormatBlockLabel::from)
+                    .unwrap_or(DotFormatBlockLabel::from(index));
+                let string_label = block_node_label.to_string();
                 {
                     let mut cluster = digraph.cluster();
-                    cluster.set_label(label);
+                    cluster.set_label(&string_label);
                     cluster.node_attributes().set_style(Style::Filled);
 
-                    block.write_dot_format(&mut cluster, node_prefix);
+                    scheduled_basic_block.write_dot_format(&mut cluster, &string_label);
                 }
 
-                let next_block_label = iter.peek().map(|(next_label, _)| (*next_label).clone());
+                let next_index_and_block = iter.peek();
                 let terminator_source_label =
-                    get_node_id(&ScheduledGraphNode::BlockEnd, node_prefix);
-                match &block.terminator {
-                    BlockTerminator::Conditional {
+                    get_node_id(&ScheduledGraphNode::BlockEnd, &string_label);
+                match &scheduled_basic_block.terminator() {
+                    BasicBlockTerminator::ConditionalJump {
                         condition,
                         target,
-                        jump_if_condition_true,
+                        jump_if_condition_zero,
                     } => {
-                        let equality_operators = if *jump_if_condition_true {
-                            ("==", "!=")
+                        let (condition_met, condition_unmet) = if *jump_if_condition_zero {
+                            ("== 0", "!= 0")
                         } else {
-                            ("!=", "==")
+                            ("!= 0", "== 0")
                         };
                         digraph
                             .edge(
                                 &terminator_source_label,
-                                get_node_id(&ScheduledGraphNode::BlockStart, target),
+                                get_node_id(
+                                    &ScheduledGraphNode::BlockStart,
+                                    &DotFormatBlockLabel::from(*target).to_string(),
+                                ),
                             )
                             .attributes()
                             .set_label(
-                                format!(
-                                    "if {} {} 0",
-                                    condition.to_quil_or_debug(),
-                                    equality_operators.0
-                                )
-                                .as_str(),
+                                format!("if {} {}", condition.to_quil_or_debug(), condition_met)
+                                    .as_str(),
                             );
-                        if let Some(next_label) = next_block_label {
+                        if let Some((next_index, next_block)) = next_index_and_block {
+                            let next_block_prefix = DotFormatBlockLabel::from_label_or_index(
+                                next_block.label(),
+                                *next_index,
+                            )
+                            .to_string();
                             digraph
                                 .edge(
                                     &terminator_source_label,
-                                    get_node_id(&ScheduledGraphNode::BlockStart, &next_label),
+                                    get_node_id(
+                                        &ScheduledGraphNode::BlockStart,
+                                        &next_block_prefix,
+                                    ),
                                 )
                                 .attributes()
                                 .set_label(
                                     format!(
-                                        "if {} {} 0",
+                                        "if {} {}",
                                         condition.to_quil_or_debug(),
-                                        equality_operators.1
+                                        condition_unmet
                                     )
                                     .as_str(),
                                 );
                         };
                     }
-                    BlockTerminator::Unconditional { target } => {
+                    BasicBlockTerminator::Jump { target } => {
                         digraph
                             .edge(
                                 &terminator_source_label,
-                                get_node_id(&ScheduledGraphNode::BlockStart, target),
+                                get_node_id(
+                                    &ScheduledGraphNode::BlockStart,
+                                    &DotFormatBlockLabel::from(*target).to_string(),
+                                ),
                             )
                             .attributes()
                             .set_label("always");
                     }
-                    BlockTerminator::Continue => {
-                        if let Some(next_label) = next_block_label {
+                    BasicBlockTerminator::Continue => {
+                        if let Some((next_index, next_block)) = next_index_and_block {
+                            let node_label: DotFormatBlockLabel<'_> =
+                                DotFormatBlockLabel::from_label_or_index(
+                                    next_block.label(),
+                                    *next_index,
+                                );
+
                             digraph
                                 .edge(
                                     &terminator_source_label,
-                                    get_node_id(&ScheduledGraphNode::BlockStart, &next_label),
+                                    get_node_id(
+                                        &ScheduledGraphNode::BlockStart,
+                                        &node_label.to_string(),
+                                    ),
                                 )
                                 .attributes()
                                 .set_label("always");
                         };
                     }
-                    BlockTerminator::Halt => {}
+                    BasicBlockTerminator::Halt => {}
                 }
             }
         }
@@ -232,7 +306,7 @@ pub(crate) mod tests {
         /// diffs closely to determine if it's only a matter of reformatting.
         macro_rules! build_dot_format_snapshot_test_case {
             ($name: ident, $input: expr) => {
-                crate::program::graphviz_dot::tests::build_dot_format_snapshot_test_case!(
+                crate::program::scheduling::graphviz_dot::tests::build_dot_format_snapshot_test_case!(
                     $name,
                     $input,
                     &mut InstructionHandler::default(),
@@ -241,7 +315,7 @@ pub(crate) mod tests {
             ($name: ident, $input:expr, $handler: expr $(,)?) => {
                 #[test]
                 fn $name() {
-                    use crate::program::graph::ScheduledProgram;
+                    use crate::program::scheduling::graph::ScheduledProgram;
                     const FRAME_DEFINITIONS: &'static str = "
 DEFFRAME 0 \"rf\":
     INITIAL-FREQUENCY: 1e6
@@ -263,7 +337,7 @@ DEFFRAME 0 1 \"cz\":
                     let scheduled_program =
                         ScheduledProgram::from_program(&program, $handler).unwrap();
 
-                    for block in scheduled_program.blocks.values() {
+                    for block in scheduled_program.basic_blocks() {
                         let graph = block.get_dependency_graph();
                         assert!(
                             !petgraph::algo::is_cyclic_directed(graph),
diff --git a/quil-rs/src/program/scheduling/mod.rs b/quil-rs/src/program/scheduling/mod.rs
new file mode 100644
index 00000000..25f339c5
--- /dev/null
+++ b/quil-rs/src/program/scheduling/mod.rs
@@ -0,0 +1,15 @@
+pub(crate) mod graph;
+pub(crate) mod schedule;
+
+#[cfg(feature = "graphviz-dot")]
+pub(crate) mod graphviz_dot;
+
+pub use graph::{
+    DependencyGraph, ExecutionDependency, MemoryAccessType, ScheduleError, ScheduleErrorVariant,
+    ScheduleResult, ScheduledBasicBlock, ScheduledBasicBlockOwned, ScheduledGraphNode,
+    ScheduledProgram,
+};
+
+pub use schedule::{
+    ComputedScheduleError, ComputedScheduleItem, Schedule, ScheduleSeconds, Seconds, TimeSpan,
+};
diff --git a/quil-rs/src/program/scheduling/schedule.rs b/quil-rs/src/program/scheduling/schedule.rs
new file mode 100644
index 00000000..58d762c9
--- /dev/null
+++ b/quil-rs/src/program/scheduling/schedule.rs
@@ -0,0 +1,494 @@
+//! A Schedule represents a flattening of the [`DependencyGraph`] into a linear sequence of
+//! instructions, with each instruction assigned a start time and duration.
+
+use std::collections::HashMap;
+
+use itertools::Itertools;
+use petgraph::{
+    visit::{EdgeFiltered, Topo},
+    Direction,
+};
+
+use crate::{
+    instruction::{
+        AttributeValue, Capture, Delay, Instruction, Pulse, RawCapture, WaveformInvocation,
+    },
+    quil::Quil,
+    Program,
+};
+
+use super::{ExecutionDependency, ScheduledBasicBlock, ScheduledGraphNode};
+
+#[derive(Clone, Debug, Default, PartialEq, PartialOrd)]
+pub struct Seconds(pub f64);
+
+impl std::ops::Add<Seconds> for Seconds {
+    type Output = Seconds;
+
+    fn add(self, rhs: Seconds) -> Self::Output {
+        Self(rhs.0 + self.0)
+    }
+}
+
+impl std::ops::Sub<Seconds> for Seconds {
+    type Output = Seconds;
+
+    fn sub(self, rhs: Seconds) -> Self::Output {
+        Self(self.0 - rhs.0)
+    }
+}
+
+pub trait Zero: PartialEq + Sized {
+    fn zero() -> Self;
+
+    fn is_zero(&self) -> bool {
+        self == &Self::zero()
+    }
+}
+
+impl Zero for Seconds {
+    fn zero() -> Self {
+        Self(0.0)
+    }
+}
+
+#[derive(Clone, Debug, PartialEq)]
+pub struct Schedule<TimeUnit> {
+    items: Vec<ComputedScheduleItem<TimeUnit>>,
+    /// The total duration of the block. This is the end time of the schedule when it starts at `TimeUnit::zero()`
+    duration: TimeUnit,
+}
+
+impl<TimeUnit> Schedule<TimeUnit> {
+    pub fn duration(&self) -> &TimeUnit {
+        &self.duration
+    }
+
+    pub fn items(&self) -> &[ComputedScheduleItem<TimeUnit>] {
+        self.items.as_ref()
+    }
+
+    pub fn into_items(self) -> Vec<ComputedScheduleItem<TimeUnit>> {
+        self.items
+    }
+}
+
+impl<TimeUnit: Clone + PartialOrd + std::ops::Add<TimeUnit, Output = TimeUnit> + Zero>
+    From<Vec<ComputedScheduleItem<TimeUnit>>> for Schedule<TimeUnit>
+{
+    fn from(items: Vec<ComputedScheduleItem<TimeUnit>>) -> Self {
+        let duration = items
+            .iter()
+            .map(|item| item.time_span.start_time.clone() + item.time_span.duration.clone())
+            .fold(TimeUnit::zero(), |acc, el| if el > acc { el } else { acc });
+        Self { items, duration }
+    }
+}
+
+impl<TimeUnit: Zero> Default for Schedule<TimeUnit> {
+    fn default() -> Self {
+        Self {
+            items: Default::default(),
+            duration: TimeUnit::zero(),
+        }
+    }
+}
+
+pub type ScheduleSeconds = Schedule<Seconds>;
+
+#[derive(Clone, Debug, PartialEq)]
+pub struct ComputedScheduleItem<TimeUnit> {
+    pub time_span: TimeSpan<TimeUnit>,
+    pub instruction_index: usize,
+}
+
+#[derive(Debug, thiserror::Error)]
+pub enum ComputedScheduleError {
+    #[error("unknown duration for instruction {}", instruction.to_quil_or_debug())]
+    UnknownDuration { instruction: Instruction },
+
+    #[error("internal error: invalid dependency graph")]
+    InvalidDependencyGraph,
+}
+
+pub type ComputedScheduleResult<T> = Result<T, ComputedScheduleError>;
+
+/// Represents a span of time, for some unit of time
+#[derive(Clone, Debug, PartialEq)]
+pub struct TimeSpan<TimeUnit> {
+    /// The inclusive start time of the described item
+    pub start_time: TimeUnit,
+
+    /// The described item's continuous duration
+    pub duration: TimeUnit,
+}
+
+impl<TimeUnit> TimeSpan<TimeUnit> {
+    pub fn start_time(&self) -> &TimeUnit {
+        &self.start_time
+    }
+
+    pub fn duration(&self) -> &TimeUnit {
+        &self.duration
+    }
+}
+
+impl<TimeUnit: Clone + std::ops::Add<TimeUnit, Output = TimeUnit>> TimeSpan<TimeUnit> {
+    pub fn end(&self) -> TimeUnit {
+        self.start_time.clone() + self.duration.clone()
+    }
+}
+
+impl<
+        TimeUnit: Clone
+            + PartialOrd
+            + std::ops::Add<TimeUnit, Output = TimeUnit>
+            + std::ops::Sub<TimeUnit, Output = TimeUnit>,
+    > TimeSpan<TimeUnit>
+{
+    pub(crate) fn union(self, rhs: Self) -> Self {
+        let start_time = if rhs.start_time < self.start_time {
+            rhs.start_time.clone()
+        } else {
+            self.start_time.clone()
+        };
+
+        let self_end_time = self.start_time.clone() + self.duration;
+        let rhs_end_time = rhs.start_time + rhs.duration;
+        let end_time = if self_end_time < rhs_end_time {
+            rhs_end_time
+        } else {
+            self_end_time
+        };
+
+        Self {
+            duration: end_time - start_time.clone(),
+            start_time,
+        }
+    }
+}
+
+impl<'p> ScheduledBasicBlock<'p> {
+    /// Return the duration of a scheduled Quil instruction:
+    ///
+    /// * For PULSE and CAPTURE, this is the duration of the waveform at the frame's sample rate
+    /// * For DELAY and RAW-CAPTURE, it's the named duration
+    /// * For supporting instructions like SET-*, SHIFT-*, and FENCE, it's 0
+    ///
+    /// Return `None` for other instructions.
+    pub(crate) fn get_instruction_duration_seconds(
+        program: &Program,
+        instruction: &Instruction,
+    ) -> Option<Seconds> {
+        match instruction {
+            Instruction::Capture(Capture { waveform, .. })
+            | Instruction::Pulse(Pulse { waveform, .. }) => {
+                Self::get_waveform_duration_seconds(program, instruction, waveform)
+            }
+            Instruction::Delay(Delay { duration, .. })
+            | Instruction::RawCapture(RawCapture { duration, .. }) => {
+                duration.to_real().ok().map(Seconds)
+            }
+            Instruction::Fence(_)
+            | Instruction::SetFrequency(_)
+            | Instruction::SetPhase(_)
+            | Instruction::SetScale(_)
+            | Instruction::ShiftFrequency(_)
+            | Instruction::ShiftPhase(_)
+            | Instruction::SwapPhases(_) => Some(Seconds(0.0)),
+            _ => None,
+        }
+    }
+
+    /// Return the duration of a Quil waveform:
+    ///
+    /// If the waveform is defined in the program with `DEFWAVEFORM`, the duration is the sample count
+    /// divided by the sample rate.
+    ///
+    /// Otherwise, it's the `duration` parameter of the waveform invocation. This relies on the assumption that
+    /// all template waveforms in use have such a parameter in units of seconds.
+    fn get_waveform_duration_seconds(
+        program: &Program,
+        instruction: &Instruction,
+        waveform_invocation: &WaveformInvocation,
+    ) -> Option<Seconds> {
+        if let Some(definition) = program.waveforms.get(&waveform_invocation.name) {
+            let sample_count = definition.matrix.len();
+            let common_sample_rate =
+                program
+                    .get_frames_for_instruction(instruction)
+                    .and_then(|frames| {
+                        frames
+                            .used
+                            .into_iter()
+                            .filter_map(|frame| {
+                                program
+                                    .frames
+                                    .get(frame)
+                                    .and_then(|frame_definition| {
+                                        frame_definition.get("SAMPLE-RATE")
+                                    })
+                                    .and_then(|sample_rate_expression| match sample_rate_expression
+                                    {
+                                        AttributeValue::String(_) => None,
+                                        AttributeValue::Expression(expression) => Some(expression),
+                                    })
+                                    .and_then(|expression| expression.to_real().ok())
+                            })
+                            .all_equal_value()
+                            .ok()
+                    });
+
+            common_sample_rate
+                .map(|sample_rate| sample_count as f64 / sample_rate)
+                .map(Seconds)
+        } else {
+            waveform_invocation
+                .parameters
+                .get("duration")
+                .and_then(|v| v.to_real().ok())
+                .map(Seconds)
+        }
+    }
+
+    /// Compute the flattened schedule for this [`ScheduledBasicBlock`] in terms of seconds,
+    /// using a default built-in calculation for the duration of scheduled instructions.
+    pub fn as_schedule_seconds(
+        &self,
+        program: &Program,
+    ) -> ComputedScheduleResult<ScheduleSeconds> {
+        self.as_schedule(program, Self::get_instruction_duration_seconds)
+    }
+
+    /// Compute the flattened schedule for this [`ScheduledBasicBlock`] using a user-provided
+    /// closure for computation of instruction duration.
+    ///
+    /// Return an error if the schedule cannot be computed from the information provided.
+    pub fn as_schedule<
+        F,
+        TimeUnit: Clone + PartialOrd + std::ops::Add<TimeUnit, Output = TimeUnit> + Zero,
+    >(
+        &self,
+        program: &'p Program,
+        get_duration: F,
+    ) -> ComputedScheduleResult<Schedule<TimeUnit>>
+    where
+        F: Fn(&'p Program, &'p Instruction) -> Option<TimeUnit>,
+    {
+        let mut schedule = Schedule::default();
+        let mut end_time_by_instruction_index = HashMap::<usize, TimeUnit>::new();
+
+        let graph_filtered = EdgeFiltered::from_fn(&self.graph, |(_, _, dependencies)| {
+            dependencies.contains(&ExecutionDependency::Scheduled)
+        });
+        let mut topo = Topo::new(&graph_filtered);
+
+        while let Some(instruction_node) = topo.next(&graph_filtered) {
+            if let ScheduledGraphNode::InstructionIndex(index) = instruction_node {
+                let instruction = *self
+                    .basic_block()
+                    .instructions()
+                    .get(index)
+                    .ok_or_else(|| ComputedScheduleError::InvalidDependencyGraph)?;
+                let duration = get_duration(program, instruction).ok_or(
+                    ComputedScheduleError::UnknownDuration {
+                        instruction: instruction.clone(),
+                    },
+                )?;
+
+                let latest_previous_instruction_scheduler_end_time = self
+                    .graph
+                    .edges_directed(instruction_node, Direction::Incoming)
+                    .filter_map(|(source, _, dependencies)| {
+                        if dependencies.contains(&ExecutionDependency::Scheduled) {
+                            match source {
+                                ScheduledGraphNode::BlockStart => Ok(Some(TimeUnit::zero())),
+                                ScheduledGraphNode::InstructionIndex(previous_index) => {
+                                    end_time_by_instruction_index
+                                        .get(&previous_index)
+                                        .cloned()
+                                        .ok_or(ComputedScheduleError::InvalidDependencyGraph)
+                                        .map(Some)
+                                }
+                                ScheduledGraphNode::BlockEnd => unreachable!(),
+                            }
+                        } else {
+                            Ok(None)
+                        }
+                        .transpose()
+                    })
+                    .collect::<Result<Vec<TimeUnit>, _>>()?
+                    .into_iter()
+                    // this implementation allows us to require PartialOrd instead of Ord (required for `.max()`),
+                    // which is convenient for f64
+                    .fold(TimeUnit::zero(), |acc, el| if el > acc { el } else { acc });
+
+                let start_time = latest_previous_instruction_scheduler_end_time;
+                let end_time = start_time.clone() + duration.clone();
+                if schedule.duration < end_time {
+                    schedule.duration = end_time.clone();
+                }
+
+                end_time_by_instruction_index.insert(index, end_time);
+                schedule.items.push(ComputedScheduleItem {
+                    time_span: TimeSpan {
+                        start_time,
+                        duration,
+                    },
+                    instruction_index: index,
+                });
+            }
+        }
+
+        Ok(schedule)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use core::panic;
+    use std::str::FromStr;
+
+    use crate::{instruction::InstructionHandler, program::scheduling::TimeSpan, Program};
+
+    #[rstest::rstest]
+    #[case("CAPTURE 0 \"a\" flat(duration: 1.0) ro", Some(1.0))]
+    #[case("DELAY 0 \"a\" 1.0", Some(1.0))]
+    #[case("FENCE", Some(0.0))]
+    #[case("PULSE 0 \"a\" flat(duration: 1.0)", Some(1.0))]
+    #[case("RAW-CAPTURE 0 \"a\" 1.0 ro", Some(1.0))]
+    #[case("RESET", None)]
+    #[case("SET-FREQUENCY 0 \"a\" 1.0", Some(0.0))]
+    #[case("SET-PHASE 0 \"a\" 1.0", Some(0.0))]
+    #[case("SET-SCALE 0 \"a\" 1.0", Some(0.0))]
+    #[case("SHIFT-FREQUENCY 0 \"a\" 1.0", Some(0.0))]
+    #[case("SHIFT-PHASE 0 \"a\" 1.0", Some(0.0))]
+    #[case("SWAP-PHASES 0 \"a\" 0 \"b\"", Some(0.0))]
+    fn instruction_duration_seconds(
+        #[case] input_program: &str,
+        #[case] expected_duration: Option<f64>,
+    ) {
+        let empty_program = Program::new();
+        let program = Program::from_str(input_program)
+            .map_err(|e| e.to_string())
+            .unwrap();
+        let instruction = program.into_instructions().remove(0);
+        let duration =
+            crate::program::scheduling::ScheduledBasicBlock::get_instruction_duration_seconds(
+                &empty_program,
+                &instruction,
+            );
+        assert_eq!(
+            expected_duration.map(crate::program::scheduling::Seconds),
+            duration
+        );
+    }
+
+    #[rstest::rstest]
+    #[case(
+        r#"FENCE
+FENCE
+FENCE
+"#,
+        Ok(vec![0.0, 0.0, 0.0])
+    )]
+    #[case(
+        r#"DEFFRAME 0 "a":
+    SAMPLE-RATE: 1e9
+PULSE 0 "a" flat(duration: 1.0)
+PULSE 0 "a" flat(duration: 1.0)
+PULSE 0 "a" flat(duration: 1.0)
+"#,
+        Ok(vec![0.0, 1.0, 2.0])
+    )]
+    #[case(
+        r#"DEFFRAME 0 "a":
+    SAMPLE-RATE: 1e9
+DEFFRAME 0 "b":
+    SAMPLE-RATE: 1e9
+NONBLOCKING PULSE 0 "a" flat(duration: 1.0)
+NONBLOCKING PULSE 0 "b" flat(duration: 10.0)
+FENCE
+PULSE 0 "a" flat(duration: 1.0)
+FENCE
+PULSE 0 "a" flat(duration: 1.0)
+"#,
+        Ok(vec![0.0, 0.0, 10.0, 10.0, 11.0, 11.0])
+    )]
+    #[case(
+        r#"DEFFRAME 0 "a":
+    SAMPLE-RATE: 1e9
+DEFFRAME 0 "b":
+    SAMPLE-RATE: 1e9
+DELAY 0 "a" 1.0
+SET-PHASE 0 "a" 1.0
+SHIFT-PHASE 0 "a" 1.0
+SWAP-PHASES 0 "a" 0 "b"
+SET-FREQUENCY 0 "a" 1.0
+SHIFT-FREQUENCY 0 "a" 1.0
+SET-SCALE 0 "a" 1.0
+FENCE
+PULSE 0 "a" flat(duration: 1.0)
+"#,
+        Ok(vec![0.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0])
+    )]
+    #[case("RESET", Err(()))]
+    fn schedule_seconds(#[case] input_program: &str, #[case] expected_times: Result<Vec<f64>, ()>) {
+        let program: Program = input_program.parse().unwrap();
+        let block: crate::program::analysis::BasicBlock = (&program).try_into().unwrap();
+        let mut handler = InstructionHandler::default();
+        let scheduled_block =
+            crate::program::scheduling::ScheduledBasicBlock::build(block, &program, &mut handler)
+                .unwrap();
+        match (
+            scheduled_block.as_schedule_seconds(&program),
+            expected_times,
+        ) {
+            (Ok(schedule), Ok(expected_times)) => {
+                let times = schedule
+                    .items()
+                    .iter()
+                    .map(|item| item.time_span.start_time.0)
+                    .collect::<Vec<_>>();
+                assert_eq!(expected_times, times);
+            }
+            (Err(_), Err(_)) => {}
+            (Ok(schedule), Err(_)) => {
+                let times = schedule
+                    .items()
+                    .iter()
+                    .map(|item| item.time_span.start_time.0)
+                    .collect::<Vec<_>>();
+                panic!("expected error, got {:?}", times);
+            }
+            (Err(error), Ok(_)) => {
+                panic!("expected success, got error: {error}")
+            }
+        }
+    }
+
+    #[rstest::rstest]
+    #[case::identical((0, 10), (0, 10), (0, 10))]
+    #[case::adjacent((0, 1), (1, 1), (0, 2))]
+    #[case::disjoint((0, 10), (20, 10), (0, 30))]
+    #[case::disjoint_reverse((20, 10), (0, 10), (0, 30))]
+    fn time_span_union(
+        #[case] a: (usize, usize),
+        #[case] b: (usize, usize),
+        #[case] expected: (usize, usize),
+    ) {
+        let a = TimeSpan {
+            start_time: a.0,
+            duration: a.1,
+        };
+        let b = TimeSpan {
+            start_time: b.0,
+            duration: b.1,
+        };
+        let expected = TimeSpan {
+            start_time: expected.0,
+            duration: expected.1,
+        };
+        assert_eq!(expected, a.union(b));
+    }
+}


Test patch:
diff --git a/quil-py/test/program/test_program.py b/quil-py/test/program/test_program.py
index 8dd92358..ac541bfb 100644
--- a/quil-py/test/program/test_program.py
+++ b/quil-py/test/program/test_program.py
@@ -52,6 +52,116 @@ def target_resolver(target: TargetPlaceholder) -> Optional[str]:
 
     assert program.to_quil() == "H 9\nJUMP @test\n"
 
+def test_single_block_control_flow_analysis():
+    program = Program.parse(
+        """
+DECLARE ro BIT[2]
+H 0
+CNOT 0 1
+MEASURE 0 ro[0]
+MEASURE 1 ro[1]
+""")
+    assert program.get_used_qubits() == {Qubit.from_fixed(0), Qubit.from_fixed(1)}
+    cfg = program.control_flow_graph()
+    blocks = cfg.basic_blocks()
+    assert len(blocks) == 1
+    assert blocks[0].terminator() == None
+    block_program = Program()
+    block_program.add_instructions(blocks[0].instructions())
+    assert block_program.to_quil() == """H 0
+CNOT 0 1
+MEASURE 0 ro[0]
+MEASURE 1 ro[1]
+"""
+
+def test_multi_block_control_flow_analysis():
+    program = Program.parse(
+        """
+DECLARE ro BIT[1]
+LABEL @start
+MEASURE 0 ro[0]
+JUMP-UNLESS @end ro[0]
+X 0
+JUMP @start
+LABEL @end
+HALT
+""")
+    assert program.get_used_qubits() == {Qubit.from_fixed(0)}
+    cfg = program.control_flow_graph()
+
+    assert cfg.has_dynamic_control_flow()
+
+    blocks = cfg.basic_blocks()
+    assert len(blocks) == 3
+
+def test_basic_block_fixed_schedule():
+    """
+    Test that a simple, realistic program can be scheduled as expected.
+    """
+
+    program = Program.parse(
+        """DEFFRAME 0 "flux_tx_cz":
+    TEST: 1
+
+DEFFRAME 1 "flux_tx_iswap":
+    TEST: 1
+
+DEFFRAME 1 "flux_tx_cz":
+    TEST: 1
+
+DEFFRAME 1 "flux_tx_iswap":
+    TEST: 1
+
+DEFFRAME 2 "flux_tx_cz":
+    TEST: 1
+
+DEFFRAME 2 "flux_tx_iswap":
+    TEST: 1
+
+DEFFRAME 3 "flux_tx_cz":
+    TEST: 1
+
+DEFFRAME 3 "flux_tx_iswap":
+    TEST: 1
+
+# Simplified version
+DEFCAL CZ q0 q1:
+    FENCE q0 q1
+    SET-PHASE q0 "flux_tx_cz" 0.0
+    SET-PHASE q1 "flux_tx_iswap" 0.0
+    NONBLOCKING PULSE q0 "flux_tx_cz" erf_square(duration: 6.000000000000001e-08)
+    NONBLOCKING PULSE q1 "flux_tx_iswap" erf_square(duration: 6.000000000000001e-08)
+    SHIFT-PHASE q0 "flux_tx_cz" 1.0
+    SHIFT-PHASE q1 "flux_tx_iswap" 1.0
+    FENCE q0 q1
+
+CZ 0 1
+CZ 2 3
+CZ 0 2
+""")
+    cfg = program.control_flow_graph()
+    blocks = cfg.basic_blocks()
+    assert len(blocks) == 1
+    block = blocks[0]
+
+    schedule = block.as_schedule_seconds(program)
+    items = schedule.items()
+
+    # One for each CZ
+    assert len(items) == 3
+
+    items = { item.instruction_index: item for item in items }
+
+    # The first CZ should start at 0
+    assert items[0].time_span.start == 0.0
+
+    # The first CZ should start and end at the same times
+    assert items[0].time_span.start == items[1].time_span.start
+    assert items[0].time_span.duration == items[1].time_span.duration
+
+    # The third CZ should start when the first and second ones end and be of the same duration
+    assert items[0].time_span.start + items[0].time_span.duration == items[2].time_span.start
+    assert items[0].time_span.duration == items[2].time_span.duration
 
 def test_filter_instructions(snapshot: SnapshotAssertion):
     input = """DECLARE foo REAL[1]
diff --git a/quil-rs/src/program/analysis/snapshots/quil_rs__program__analysis__control_flow_graph__tests__schedule_uncalibrated_cz.snap b/quil-rs/src/program/analysis/snapshots/quil_rs__program__analysis__control_flow_graph__tests__schedule_uncalibrated_cz.snap
new file mode 100644
index 00000000..be61cb3a
--- /dev/null
+++ b/quil-rs/src/program/analysis/snapshots/quil_rs__program__analysis__control_flow_graph__tests__schedule_uncalibrated_cz.snap
@@ -0,0 +1,39 @@
+---
+source: quil-rs/src/program/analysis/control_flow_graph.rs
+expression: schedule_items
+---
+[
+    ComputedScheduleItem {
+        time_span: TimeSpan {
+            start_time: Seconds(
+                0.0,
+            ),
+            duration: Seconds(
+                6.000000000000001e-8,
+            ),
+        },
+        instruction_index: 0,
+    },
+    ComputedScheduleItem {
+        time_span: TimeSpan {
+            start_time: Seconds(
+                0.0,
+            ),
+            duration: Seconds(
+                6.000000000000001e-8,
+            ),
+        },
+        instruction_index: 1,
+    },
+    ComputedScheduleItem {
+        time_span: TimeSpan {
+            start_time: Seconds(
+                6.000000000000001e-8,
+            ),
+            duration: Seconds(
+                6.000000000000001e-8,
+            ),
+        },
+        instruction_index: 2,
+    },
+]
diff --git a/quil-rs/src/program/analysis/test_programs.rs b/quil-rs/src/program/analysis/test_programs.rs
new file mode 100644
index 00000000..daee0d97
--- /dev/null
+++ b/quil-rs/src/program/analysis/test_programs.rs
@@ -0,0 +1,95 @@
+pub const QUIL_WITH_DIAMOND: &str = r"
+CNOT 0 1
+X 0
+X 1
+X 1
+X 1
+X 1
+CNOT 1 0";
+
+pub const QUIL_AS_TREE: &str = r"
+CNOT 0 1
+X 0
+H 1";
+
+pub const QUIL_AS_INVERSE_TREE: &str = r"
+X 0
+H 1
+CNOT 0 1";
+
+pub const QUIL_AS_LINEAR: &str = r"
+X 0
+X 0
+X 0
+X 0";
+
+pub const QUIL_WITH_SWAP: &str = r"
+X 0
+X 1
+SWAP 0 1
+X 1
+X 0";
+
+pub const QUIL_WITH_JUMP: &str = r"
+LABEL @label
+X 0
+X 1
+JUMP @label
+X 1
+X 0";
+
+pub const QUIL_WITH_JUMP_WHEN: &str = r"
+LABEL @label
+X 0
+X 1
+JUMP-WHEN @label ro
+X 1
+X 0";
+
+pub const QUIL_WITH_JUMP_UNLESS: &str = r"
+LABEL @label
+X 0
+X 1
+JUMP-UNLESS @label ro
+X 1
+X 0";
+
+pub const KITCHEN_SINK_QUIL: &str = "DECLARE ro BIT[1]
+DEFGATE HADAMARD AS MATRIX:
+\t(1/sqrt(2)),(1/sqrt(2))
+\t(1/sqrt(2)),((-1)/sqrt(2))
+
+DEFGATE RX(%theta) AS MATRIX:
+\tcos((%theta/2)),((-1i)*sin((%theta/2)))
+\t((-1i)*sin((%theta/2))),cos((%theta/2))
+
+DEFGATE Name AS PERMUTATION:
+\t1, 0
+
+DEFCIRCUIT SIMPLE:
+\tX 0
+\tX 1
+
+RX 0
+CZ 0 1
+MEASURE 0 ro[0]
+DEFCAL X 0:
+\tPULSE 0 \"xy\" my_waveform()
+
+DEFCAL RX(%theta) 0:
+\tPULSE 0 \"xy\" my_waveform()
+
+DEFCAL MEASURE 0 dest:
+\tDECLARE iq REAL[2]
+\tCAPTURE 0 \"out\" flat(duration: 1000000, iqs: (2+3i)) iq[0]
+
+DEFFRAME 0 \"xy\":
+\tSAMPLE-RATE: 3000
+
+DEFFRAME 0 \"xy\":
+\tDIRECTION: \"rx\"
+\tCENTER-FREQUENCY: 1000
+\tHARDWARE-OBJECT: \"some object\"
+\tINITIAL-FREQUENCY: 2000
+\tSAMPLE-RATE: 3000
+";
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graph__tests__custom_handler__mixed_pragmas_and_pulses.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graph__tests__custom_handler__mixed_pragmas_and_pulses.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graph__tests__custom_handler__mixed_pragmas_and_pulses.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graph__tests__custom_handler__mixed_pragmas_and_pulses.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graph__tests__custom_handler__only_pragmas_with_frames.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graph__tests__custom_handler__only_pragmas_with_frames.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graph__tests__custom_handler__only_pragmas_with_frames.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graph__tests__custom_handler__only_pragmas_with_frames.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graph__tests__custom_handler__only_pragmas_without_frames.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graph__tests__custom_handler__only_pragmas_without_frames.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graph__tests__custom_handler__only_pragmas_without_frames.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graph__tests__custom_handler__only_pragmas_without_frames.snap
diff --git a/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__active_reset_single_frame.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__active_reset_single_frame.snap
new file mode 100644
index 00000000..e6307e79
--- /dev/null
+++ b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__active_reset_single_frame.snap
@@ -0,0 +1,50 @@
+---
+source: quil-rs/src/program/scheduling/graphviz_dot.rs
+expression: dot_format
+---
+digraph {
+  entry -> "@measure_start";
+  entry [label="Entry Point"];
+  subgraph cluster_0 {
+    label="@measure";
+    node [style="filled"];
+    "@measure_start" [shape=circle, label="start"];
+    "@measure_start" -> "@measure_0" [label="ordering
+timing"];
+    "@measure_start" -> "@measure_1" [label="ordering
+timing"];
+    "@measure_start" -> "@measure_end" [label="ordering"];
+    "@measure_0" [shape=rectangle, label="[0] NONBLOCKING PULSE 0 \"ro_tx\" test(duration: 1000000)"];
+    "@measure_0" -> "@measure_end" [label="ordering
+timing"];
+    "@measure_1" [shape=rectangle, label="[1] NONBLOCKING CAPTURE 0 \"ro_rx\" test(duration: 1000000) ro[0]"];
+    "@measure_1" -> "@measure_end" [label="await capture
+ordering
+timing"];
+    "@measure_end" [shape=circle, label="end"];
+  }
+  "@measure_end" -> "@end_start" [label="if ro[0] != 0"];
+  "@measure_end" -> "@feedback_start" [label="if ro[0] == 0"];
+  subgraph cluster_1 {
+    label="@feedback";
+    node [style="filled"];
+    "@feedback_start" [shape=circle, label="start"];
+    "@feedback_start" -> "@feedback_0" [label="ordering
+timing"];
+    "@feedback_start" -> "@feedback_end" [label="ordering
+timing"];
+    "@feedback_0" [shape=rectangle, label="[0] PULSE 0 \"rf\" test(duration: 1000000)"];
+    "@feedback_0" -> "@feedback_end" [label="ordering
+timing"];
+    "@feedback_end" [shape=circle, label="end"];
+  }
+  "@feedback_end" -> "@measure_start" [label="always"];
+  subgraph cluster_2 {
+    label="@end";
+    node [style="filled"];
+    "@end_start" [shape=circle, label="start"];
+    "@end_start" -> "@end_end" [label="ordering"];
+    "@end_end" [shape=circle, label="end"];
+  }
+}
+
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__blocking_2q_pulse.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__blocking_2q_pulse.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__blocking_2q_pulse.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__blocking_2q_pulse.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__blocking_pulses_after_nonblocking.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__blocking_pulses_after_nonblocking.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__blocking_pulses_after_nonblocking.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__blocking_pulses_after_nonblocking.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__blocking_pulses_wrap_nonblocking.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__blocking_pulses_wrap_nonblocking.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__blocking_pulses_wrap_nonblocking.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__blocking_pulses_wrap_nonblocking.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__chained_pulses.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__chained_pulses.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__chained_pulses.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__chained_pulses.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__different_frames_blocking.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__different_frames_blocking.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__different_frames_blocking.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__different_frames_blocking.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__different_frames_nonblocking.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__different_frames_nonblocking.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__different_frames_nonblocking.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__different_frames_nonblocking.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__fence_all.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__fence_all.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__fence_all.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__fence_all.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__fence_all_with_nonblocking_pulses.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__fence_all_with_nonblocking_pulses.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__fence_all_with_nonblocking_pulses.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__fence_all_with_nonblocking_pulses.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__fence_one_wrapper.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__fence_one_wrapper.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__fence_one_wrapper.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__fence_one_wrapper.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__fence_wrapper.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__fence_wrapper.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__fence_wrapper.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__fence_wrapper.snap
diff --git a/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__jump.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__jump.snap
new file mode 100644
index 00000000..b5ab1860
--- /dev/null
+++ b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__jump.snap
@@ -0,0 +1,51 @@
+---
+source: quil-rs/src/program/scheduling/graphviz_dot.rs
+expression: dot_format
+---
+digraph {
+  entry -> "@first-block_start";
+  entry [label="Entry Point"];
+  subgraph cluster_0 {
+    label="@first-block";
+    node [style="filled"];
+    "@first-block_start" [shape=circle, label="start"];
+    "@first-block_start" -> "@first-block_0" [label="ordering
+timing"];
+    "@first-block_start" -> "@first-block_end" [label="ordering
+timing"];
+    "@first-block_0" [shape=rectangle, label="[0] PULSE 0 \"rf\" test(duration: 1000000)"];
+    "@first-block_0" -> "@first-block_end" [label="ordering
+timing"];
+    "@first-block_end" [shape=circle, label="end"];
+  }
+  "@first-block_end" -> "@third-block_start" [label="if ro[0] == 0"];
+  "@first-block_end" -> "@second-block_start" [label="if ro[0] != 0"];
+  subgraph cluster_1 {
+    label="@second-block";
+    node [style="filled"];
+    "@second-block_start" [shape=circle, label="start"];
+    "@second-block_start" -> "@second-block_0" [label="ordering
+timing"];
+    "@second-block_start" -> "@second-block_end" [label="ordering
+timing"];
+    "@second-block_0" [shape=rectangle, label="[0] PULSE 0 \"rf\" test(duration: 1000000)"];
+    "@second-block_0" -> "@second-block_end" [label="ordering
+timing"];
+    "@second-block_end" [shape=circle, label="end"];
+  }
+  "@second-block_end" -> "@third-block_start" [label="always"];
+  subgraph cluster_2 {
+    label="@third-block";
+    node [style="filled"];
+    "@third-block_start" [shape=circle, label="start"];
+    "@third-block_start" -> "@third-block_0" [label="ordering
+timing"];
+    "@third-block_start" -> "@third-block_end" [label="ordering
+timing"];
+    "@third-block_0" [shape=rectangle, label="[0] PULSE 0 \"rf\" test(duration: 1000000)"];
+    "@third-block_0" -> "@third-block_end" [label="ordering
+timing"];
+    "@third-block_end" [shape=circle, label="end"];
+  }
+}
+
diff --git a/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__labels_only.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__labels_only.snap
new file mode 100644
index 00000000..6547747c
--- /dev/null
+++ b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__labels_only.snap
@@ -0,0 +1,32 @@
+---
+source: quil-rs/src/program/scheduling/graphviz_dot.rs
+expression: dot_format
+---
+digraph {
+  entry -> "@a_start";
+  entry [label="Entry Point"];
+  subgraph cluster_0 {
+    label="@a";
+    node [style="filled"];
+    "@a_start" [shape=circle, label="start"];
+    "@a_start" -> "@a_end" [label="ordering"];
+    "@a_end" [shape=circle, label="end"];
+  }
+  "@a_end" -> "@b_start" [label="always"];
+  subgraph cluster_1 {
+    label="@b";
+    node [style="filled"];
+    "@b_start" [shape=circle, label="start"];
+    "@b_start" -> "@b_end" [label="ordering"];
+    "@b_end" [shape=circle, label="end"];
+  }
+  "@b_end" -> "@c_start" [label="always"];
+  subgraph cluster_2 {
+    label="@c";
+    node [style="filled"];
+    "@c_start" [shape=circle, label="start"];
+    "@c_start" -> "@c_end" [label="ordering"];
+    "@c_end" [shape=circle, label="end"];
+  }
+}
+
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__multiple_classical_instructions.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__multiple_classical_instructions.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__multiple_classical_instructions.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__multiple_classical_instructions.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__parametric_pulse.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__parametric_pulse.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__parametric_pulse.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__parametric_pulse.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__parametric_pulses_using_capture_results.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__parametric_pulses_using_capture_results.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__parametric_pulses_using_capture_results.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__parametric_pulses_using_capture_results.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__pulse_after_capture.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__pulse_after_capture.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__pulse_after_capture.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__pulse_after_capture.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__pulse_after_set_frequency.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__pulse_after_set_frequency.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__pulse_after_set_frequency.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__pulse_after_set_frequency.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__simple_capture.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__simple_capture.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__simple_capture.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__simple_capture.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__simple_memory_access.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__simple_memory_access.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__simple_memory_access.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__simple_memory_access.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__single_dependency.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__single_dependency.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__single_dependency.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__single_dependency.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__single_instruction.snap b/quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__single_instruction.snap
similarity index 100%
rename from quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__single_instruction.snap
rename to quil-rs/src/program/scheduling/snapshots/quil_rs__program__scheduling__graphviz_dot__tests__graph__single_instruction.snap
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@FenceVariableQubit.snap b/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@FenceVariableQubit.snap
new file mode 100644
index 00000000..9bfdddf9
--- /dev/null
+++ b/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@FenceVariableQubit.snap
@@ -0,0 +1,10 @@
+---
+source: quil-rs/src/program/calibration.rs
+expression: calibrated_program.to_quil_or_debug()
+---
+DEFCAL FENCES q0 q1:
+	FENCE q0
+	FENCE q1
+FENCE 0
+FENCE 1
+
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__active_reset_single_frame.snap b/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__active_reset_single_frame.snap
deleted file mode 100644
index de3b22ed..00000000
--- a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__active_reset_single_frame.snap
+++ /dev/null
@@ -1,50 +0,0 @@
----
-source: src/program/graphviz_dot.rs
-expression: dot_format
----
-digraph {
-  entry -> "measure_start";
-  entry [label="Entry Point"];
-  subgraph cluster_0 {
-    label="measure";
-    node [style="filled"];
-    "measure_start" [shape=circle, label="start"];
-    "measure_start" -> "measure_0" [label="ordering
-timing"];
-    "measure_start" -> "measure_1" [label="ordering
-timing"];
-    "measure_start" -> "measure_end" [label="ordering"];
-    "measure_0" [shape=rectangle, label="[0] NONBLOCKING PULSE 0 \"ro_tx\" test(duration: 1000000)"];
-    "measure_0" -> "measure_end" [label="ordering
-timing"];
-    "measure_1" [shape=rectangle, label="[1] NONBLOCKING CAPTURE 0 \"ro_rx\" test(duration: 1000000) ro[0]"];
-    "measure_1" -> "measure_end" [label="await capture
-ordering
-timing"];
-    "measure_end" [shape=circle, label="end"];
-  }
-  "measure_end" -> "end_start" [label="if ro[0] == 0"];
-  "measure_end" -> "feedback_start" [label="if ro[0] != 0"];
-  subgraph cluster_1 {
-    label="feedback";
-    node [style="filled"];
-    "feedback_start" [shape=circle, label="start"];
-    "feedback_start" -> "feedback_0" [label="ordering
-timing"];
-    "feedback_start" -> "feedback_end" [label="ordering
-timing"];
-    "feedback_0" [shape=rectangle, label="[0] PULSE 0 \"rf\" test(duration: 1000000)"];
-    "feedback_0" -> "feedback_end" [label="ordering
-timing"];
-    "feedback_end" [shape=circle, label="end"];
-  }
-  "feedback_end" -> "measure_start" [label="always"];
-  subgraph cluster_2 {
-    label="end";
-    node [style="filled"];
-    "end_start" [shape=circle, label="start"];
-    "end_start" -> "end_end" [label="ordering"];
-    "end_end" [shape=circle, label="end"];
-  }
-}
-
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__jump.snap b/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__jump.snap
deleted file mode 100644
index 4de76305..00000000
--- a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__jump.snap
+++ /dev/null
@@ -1,51 +0,0 @@
----
-source: src/program/graphviz_dot.rs
-expression: dot_format
----
-digraph {
-  entry -> "first-block_start";
-  entry [label="Entry Point"];
-  subgraph cluster_0 {
-    label="first-block";
-    node [style="filled"];
-    "first-block_start" [shape=circle, label="start"];
-    "first-block_start" -> "first-block_0" [label="ordering
-timing"];
-    "first-block_start" -> "first-block_end" [label="ordering
-timing"];
-    "first-block_0" [shape=rectangle, label="[0] PULSE 0 \"rf\" test(duration: 1000000)"];
-    "first-block_0" -> "first-block_end" [label="ordering
-timing"];
-    "first-block_end" [shape=circle, label="end"];
-  }
-  "first-block_end" -> "third-block_start" [label="if ro[0] != 0"];
-  "first-block_end" -> "second-block_start" [label="if ro[0] == 0"];
-  subgraph cluster_1 {
-    label="second-block";
-    node [style="filled"];
-    "second-block_start" [shape=circle, label="start"];
-    "second-block_start" -> "second-block_0" [label="ordering
-timing"];
-    "second-block_start" -> "second-block_end" [label="ordering
-timing"];
-    "second-block_0" [shape=rectangle, label="[0] PULSE 0 \"rf\" test(duration: 1000000)"];
-    "second-block_0" -> "second-block_end" [label="ordering
-timing"];
-    "second-block_end" [shape=circle, label="end"];
-  }
-  "second-block_end" -> "third-block_start" [label="always"];
-  subgraph cluster_2 {
-    label="third-block";
-    node [style="filled"];
-    "third-block_start" [shape=circle, label="start"];
-    "third-block_start" -> "third-block_0" [label="ordering
-timing"];
-    "third-block_start" -> "third-block_end" [label="ordering
-timing"];
-    "third-block_0" [shape=rectangle, label="[0] PULSE 0 \"rf\" test(duration: 1000000)"];
-    "third-block_0" -> "third-block_end" [label="ordering
-timing"];
-    "third-block_end" [shape=circle, label="end"];
-  }
-}
-
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__labels_only.snap b/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__labels_only.snap
deleted file mode 100644
index b610baeb..00000000
--- a/quil-rs/src/program/snapshots/quil_rs__program__graphviz_dot__tests__graph__labels_only.snap
+++ /dev/null
@@ -1,32 +0,0 @@
----
-source: src/program/graphviz_dot.rs
-expression: dot_format
----
-digraph {
-  entry -> "a_start";
-  entry [label="Entry Point"];
-  subgraph cluster_0 {
-    label="a";
-    node [style="filled"];
-    "a_start" [shape=circle, label="start"];
-    "a_start" -> "a_end" [label="ordering"];
-    "a_end" [shape=circle, label="end"];
-  }
-  "a_end" -> "b_start" [label="always"];
-  subgraph cluster_1 {
-    label="b";
-    node [style="filled"];
-    "b_start" [shape=circle, label="start"];
-    "b_start" -> "b_end" [label="ordering"];
-    "b_end" [shape=circle, label="end"];
-  }
-  "b_end" -> "c_start" [label="always"];
-  subgraph cluster_2 {
-    label="c";
-    node [style="filled"];
-    "c_start" [shape=circle, label="start"];
-    "c_start" -> "c_end" [label="ordering"];
-    "c_end" [shape=circle, label="end"];
-  }
-}
-