Struct CFGContext 

pub struct CFGContext {
    pub edges: HashMap<UOpKey, Arc<UOp>>,
}

Control flow graph context for linearization.

Tracks ordering edges between sibling RANGE operations to ensure proper linearization order when loops are at the same nesting level.

Based on Tinygrad’s CFGContext which tracks three relationships between ranges:

• nested: END y is a dependency of END x AND RANGE x is a dependency of END y
• dependent: END y is a dependency of END x AND RANGE x is NOT a dependency of END y
• independent: END y is NOT a dependency of END x

Control Flow Edges

When multiple ENDs exist at the same nesting level (siblings), they need to be ordered consistently. CFGContext computes edges where:

• Each RANGE points to its predecessor (either the parent’s RANGE or another END)
• Edges ensure sequential execution of sibling loops

Example

RANGE(i) → ... → END(i)   // first loop
RANGE(j) → ... → END(j)   // second loop (sibling)
RANGE(k) → ... → END(k)   // third loop (sibling)

CFGContext edges:
  RANGE(j) → END(i)    // j's RANGE depends on i's END
  RANGE(k) → END(j)    // k's RANGE depends on j's END

Fields

edges: HashMap<UOpKey, Arc<UOp>>

Maps RANGE → predecessor (previous sibling END or parent’s RANGE).

The predecessor is the operation that must complete before this RANGE can begin execution.

Implementations

impl CFGContext

pub fn new(sink: &Arc<UOp>) -> Self

Build a control flow context from a kernel AST.

Analyzes the graph to find sibling ENDs at the same nesting level and creates ordering edges between their RANGEs.

Algorithm (from Tinygrad linearizer.py:59-91)

1. Build transitive deps map (RANGE/END add themselves to deps)
2. Build nesting map: which END/SINK nests each END
3. Group siblings by parent
4. Order siblings by dependency count (fewer deps = earlier)
5. Create edges: RANGE of later sibling → predecessor (END or parent’s RANGE)

pub fn get_predecessor(&self, range: &Arc<UOp>) -> Option<&Arc<UOp>>

Get the predecessor for a given RANGE operation.

Returns Some(predecessor) if this RANGE has a sibling that must execute before it, None if this is the first RANGE at its level.

pub fn has_edges(&self) -> bool

Check if this context has any control flow edges.

Returns true if there are sibling RANGEs that require ordering.

pub fn edge_count(&self) -> usize

Get the number of control flow edges.

Trait Implementations

impl Debug for CFGContext

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for CFGContext

fn default() -> CFGContext

Returns the “default value” for a type.