Struct BlockData 

struct BlockData<'a> {
    pub id: BlockId,
    pub contents: &'a BlockData,
    pub is_loop_header: bool,
    pub is_switch: bool,
    pub is_merge_target: bool,
    pub reverse_postorder: Option<u32>,
    pub immediately_dominates: SmallVec<[BlockId; 2]>,
    pub within_loops: SmallVec<[BlockId; 2]>,
    pub only_reach_error: bool,
    pub shortest_paths: HashMap<BlockId, usize>,
    pub flow: IndexVec<BlockId, Ratio<DynaInt<u64, BigUint>>>,
    pub exit_info: ExitInfo,
}

Fields

id: BlockId

contents: &'a BlockData

is_loop_header: bool

The (unique) entrypoints of each loop. Unique because we error on irreducible cfgs.

is_switch: bool

Whether this block is a switch.

is_merge_target: bool

Blocks that have multiple incoming control-flow edges.

reverse_postorder: Option<u32>

Order in a reverse postorder numbering. None if the block is unreachable.

immediately_dominates: SmallVec<[BlockId; 2]>

Nodes that this block immediately dominates. Sorted by reverse_postorder_id, with largest id first.

within_loops: SmallVec<[BlockId; 2]>

List of loops inside of which this node is (loops are identified by their header). A node is considered inside a loop if it is reachable from the loop header and if it can reach the loop header using only the backwards edges into it (i.e. we don’t count a path that enters the loop header through a forward edge).

Note that we might have to take a backward edge to reach the loop header, e.g.: ’a: loop { // … ’b: loop { // … if true { continue ’a; } else { if true { break ’a; } // This node has to take two backward edges in order to reach the start of 'a. } } }

The restriction on backwards edges is for the following case: loop { loop { .. } // Not in inner loop }

This is sorted by path order from the graph root.

only_reach_error: bool

Node from where we can only reach error nodes (panic, etc.)

shortest_paths: HashMap<BlockId, usize>

List of reachable nodes, with the length of shortest path to them. Includes the current node.

flow: IndexVec<BlockId, Ratio<DynaInt<u64, BigUint>>>

Let’s say we put a quantity of water equal to 1 on the block, and the water flows downards. Whenever there is a branching, the quantity of water gets equally divided between the branches. When the control flows join, we put the water back together. The set below computes the amount of water received by each descendant of the node.

TODO: there must be a known algorithm which computes this, right?… This is exactly this problems: https://stackoverflow.com/questions/78221666/algorithm-for-total-flow-through-weighted-directed-acyclic-graph TODO: the way I compute this is not efficient.

exit_info: ExitInfo

Reconstructed information about loops and switches.

Implementations

impl BlockData<'_>

fn shortest_paths_including_self( &self, ) -> impl Iterator<Item = (BlockId, usize)>

fn shortest_paths_excluding_self( &self, ) -> impl Iterator<Item = (BlockId, usize)>

fn reachable_including_self(&self) -> impl Iterator<Item = BlockId>

fn reachable_excluding_self(&self) -> impl Iterator<Item = BlockId>

fn can_reach_excluding_self(&self, other: BlockId) -> bool

Trait Implementations

impl<'a> Debug for BlockData<'a>

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

Formats the value using the given formatter.