waffle/cfg/
mod.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//! Lightweight CFG analyses.

// Borrowed from regalloc2's cfg.rs, which is also Apache-2.0 with
// LLVM exception.

use crate::declare_entity;
use crate::entity::{EntityRef, EntityVec, PerEntity};
use crate::ir::{Block, FunctionBody, Terminator, Value, ValueDef};
use smallvec::SmallVec;

pub mod domtree;
pub mod postorder;

declare_entity!(RPOIndex, "rpo");

/// Auxiliary analyses of the control-flow graph.
#[derive(Clone, Debug)]
pub struct CFGInfo {
    /// Entry block.
    pub entry: Block,
    /// Blocks that end in return.
    pub return_blocks: Vec<Block>,
    /// Reverse-postorder traversal of blocks.
    pub rpo: EntityVec<RPOIndex, Block>,
    /// Position of each block in RPO, if reachable.
    pub rpo_pos: PerEntity<Block, Option<RPOIndex>>,
    /// Domtree parents, indexed by block.
    pub domtree: PerEntity<Block, Block>,
    /// Domtree children.
    pub domtree_children: PerEntity<Block, DomtreeChildren>,
    /// Defining block for a given value.
    pub def_block: PerEntity<Value, Block>,
    /// Preds for a given block.
    pub preds: PerEntity<Block, SmallVec<[Block; 4]>>,
    /// A given block's position in each predecessor's successor list.
    pub pred_pos: PerEntity<Block, SmallVec<[usize; 4]>>,
}

#[derive(Clone, Debug, Default)]
pub struct DomtreeChildren {
    pub child: Block,
    pub next: Block,
}

pub struct DomtreeChildIter<'a> {
    domtree_children: &'a PerEntity<Block, DomtreeChildren>,
    block: Block,
}

impl<'a> Iterator for DomtreeChildIter<'a> {
    type Item = Block;
    fn next(&mut self) -> Option<Block> {
        if self.block.is_invalid() {
            None
        } else {
            let block = self.block;
            self.block = self.domtree_children[block].next;
            Some(block)
        }
    }
}

impl CFGInfo {
    pub fn new(f: &FunctionBody) -> CFGInfo {
        let mut return_blocks = vec![];
        let mut preds: PerEntity<Block, SmallVec<[Block; 4]>> = PerEntity::default();
        let mut pred_pos: PerEntity<Block, SmallVec<[usize; 4]>> = PerEntity::default();
        for (block_id, block) in f.blocks.entries() {
            if let Terminator::Return { .. } = &block.terminator {
                return_blocks.push(block_id);
            }
            let mut target_idx = 0;
            block.terminator.visit_targets(|target| {
                preds[target.block].push(block_id);
                pred_pos[target.block].push(target_idx);
                target_idx += 1;
            });
        }

        let postorder = postorder::calculate(f.entry, |block| &f.blocks[block].succs[..]);

        let domtree =
            domtree::calculate(|block| &f.blocks[block].preds[..], &postorder[..], f.entry);

        let mut domtree_children: PerEntity<Block, DomtreeChildren> = PerEntity::default();
        for block in f.blocks.iter().rev() {
            let idom = domtree[block];
            if idom.is_valid() {
                let next = domtree_children[idom].child;
                domtree_children[block].next = next;
                domtree_children[idom].child = block;
            }
        }

        let mut def_block: PerEntity<Value, Block> = PerEntity::default();
        for (block, block_def) in f.blocks.entries() {
            for &(_, param) in &block_def.params {
                def_block[param] = block;
            }
            for &value in &block_def.insts {
                def_block[value] = block;
            }
        }
        for value in f.values.iter() {
            let orig_value = f.resolve_alias(value);
            let underlying_value = match &f.values[orig_value] {
                &ValueDef::PickOutput(value, ..) => value,
                _ => orig_value,
            };
            def_block[value] = def_block[underlying_value];
        }

        let mut rpo = postorder;
        rpo.reverse();
        let rpo = EntityVec::from(rpo);
        let mut rpo_pos = PerEntity::default();
        for (rpo, &block) in rpo.entries() {
            rpo_pos[block] = Some(rpo);
        }

        CFGInfo {
            entry: f.entry,
            return_blocks,
            rpo,
            rpo_pos,
            domtree,
            domtree_children,
            def_block,
            preds,
            pred_pos,
        }
    }

    pub fn dominates(&self, a: Block, b: Block) -> bool {
        domtree::dominates(&self.domtree, a, b)
    }

    pub fn dom_children<'a>(&'a self, block: Block) -> DomtreeChildIter<'a> {
        DomtreeChildIter {
            domtree_children: &self.domtree_children,
            block: self.domtree_children[block].child,
        }
    }
}