Module Regalloc_interf_graph

Undirected edge between registers

Common interface for edge set implementations.

Legacy representation for edge sets.

Alternative bit matrix representation for edge sets.

Degree tracking

The interference graph type.

Internal representation:

• adj_set: edge set for O(1) membership testing
• adj_list: adjacency lists for iteration (DUPLICATES adj_set information)
• degree: degree counts per register

The duplication between adj_set and adj_list is intentional: adj_set provides fast membership testing while adj_list enables efficient iteration.

Create a new empty interference graph.

The graph size is based on the current register stamp (Reg.For_testing.get_stamp). This ensures it can accommodate all registers that have been allocated so far.

Clear all edges from the graph, resetting it to empty state.

If new registers have been allocated since graph creation (detected via Reg.For_testing.get_stamp), the underlying BitMatrix representation (if used) will be reallocated to accommodate the larger stamp range. EdgeSet grows dynamically so no reallocation is needed.

add_edge graph u v adds an undirected edge between registers u and v.

This function:

• Checks that u ≠ v
• Filters out uninteresting registers (stack-allocated locals, etc.)
• Only adds edges between registers of the same class
• Updates both adj_set and adj_list
• Increments degrees for both endpoints (unless degree is infinite)

Note: Registers with infinite degree (precolored) do not have their adjacency lists updated.

mem_edge graph u v tests whether an edge exists between u and v. This is a fast O(1) operation using the edge set.

adj_list graph reg returns the complete adjacency list for reg. This returns ALL neighbors with no filtering.

iter_adjacent graph reg ~f iterates over all neighbors of reg, applying f to each. No filtering is performed - visits all neighbors.

iter_adjacent_if graph reg ~should_visit ~f iterates over neighbors of reg, applying f only to neighbors where should_visit returns true.

Example:

iter_adjacent_if graph reg
  ~should_visit:(fun r ->
    match State.reg_work_list state r with
    | Select_stack | Coalesced -> false
    | _ -> true)
  ~f:(fun adj -> process adj)

This is the primary mechanism for IRC-specific filtering.

for_all_adjacent graph reg ~f tests whether f holds for all neighbors. Returns true if f returns true for every neighbor.

for_all_adjacent_if graph reg ~should_visit ~f tests whether f holds for all visited neighbors (those where should_visit returns true).

Returns true if f returns true for every visited neighbor. Neighbors that are filtered out (should_visit returns false) are implicitly treated as satisfying the predicate.

degree graph reg returns the degree of reg in the graph. The degree equals the number of edges incident to reg.

set_degree graph reg d directly sets the degree of reg to d.

WARNING: This should be used with extreme care as it can break graph invariants if used incorrectly. Only use when you know what you're doing (e.g., setting to 0 during cleanup, or setting to Degree.infinite for precolored registers).

incr_degree graph reg increments the degree of reg by 1. This operation does NOT affect edges - it only updates the degree counter. Typically used when adding edges in ways that bypass add_edge.

decr_degree graph reg decrements the degree of reg by 1. This operation does NOT affect edges - it only updates the degree counter. Typically used during IRC simplification phase. Does nothing if the degree is infinite.

init_register graph reg initializes storage for reg in the graph. Sets empty adjacency list and degree 0.

This must be called before reg can be used with other graph operations.

init_register_with_infinite_degree graph reg initializes reg with the infinite degree value.

This is used for precolored registers.