Add control flow graph (CFG)

[kevaundray]

Problem

A CFG is a data structure that shows the flow of control in a program. The nodes of a CFG can be instructions, however since the control flow analysis of instructions that do not affect control flow is uninteresting, we group instructions into basic blocks.

The nodes of the CFG will be basic blocks. The CFG is useful for certain optimizations like loop analysis.

Proposed solution

Implement CFG data structure in a modular way with tests and comments.

Alternatives considered

No response

Additional context

No response

Submission Checklist

• Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

[guipublic]

For the record we already have a CFG implemented in the BasicBlock structure, where blocks have left and right successors.

[joss-aztec]

Cranelift's public cfg interface is as follows:

pub fn new() -> Self // What's the use case for an empty cfg?
pub fn clear(&mut self) // unneeded?
pub fn with_function(func: &Function) -> Self
pub fn compute(&mut self, func: &Function) // unneeded?
pub fn recompute_block(&mut self, func: &Function, block: Block)
pub fn pred_iter(&self, block: Block) -> PredIter // convenient?
pub fn succ_iter(&self, block: Block) -> SuccIter // convenient?
pub fn is_valid(&self) -> bool // unneeded?

Successors are block references and predecessors are pairs of a block reference plus the instruction that led there. Keeping the instruction reference sounds like it could be useful to track (e.g. I see it being checked when block merging).

clear and compute exist for the sake allowing an instance to be reused. is_valid becomes redundant if clear and the ability to expose a new empty cfg is removed. Whether we care about this efficiency is a broader question.

recompute_block is useful if you've modified instructions affecting the successors to a block.

Since we know that our blocks will never have more than two predecessors I wonder if there's a more convenient representation to us. Before we had left and right, but I'm not familiar enough to know how advantageous that was.

Note that cranelift's cfg encapsulates the building/traversal logic via an imported inst_predicates::visit_block_succs function, rather than providing a public interface for orchestrating cfg building externally. It sizes itself according to blocks counted during data flow analysis, and iterates over a functions layout.

Essentially their cfg is tightly coupled to the data entities contained within it. The data required to compute the cfg is passed as a Function struct. If that's acceptable I'd suggest the interface:

// Do we already have a struct for representing functions and their contents?
pub fn with_function(func: &Function) -> Self
pub fn recompute_block(&mut self, func: &Function, block_id: BlockId)
pub fn pred_iter(&self, block_id: BlockId) -> PredIter
pub fn succ_iter(&self, block_id: BlockId) -> SuccIter

However, if we want better decoupling and for cfg building to be driven externally this might be better:

pub fn new() -> Self
pub fn add_edge(from: BlockId, from_inst: InstId, to: BlockId)
pub fn clear_successors(block_id: BlockId)

[joss-aztec]

I've only just twigged that our ir instructions don't encode any control flow concepts, so it's going to have to be the latter interface (i.e. edge building coordinated externally).
Correction: terminators instructions are defined separately.