regalloc2/
cfg.rs

1/*
2 * Released under the terms of the Apache 2.0 license with LLVM
3 * exception. See `LICENSE` for details.
4 */
5
6//! Lightweight CFG analyses.
7
8use crate::{domtree, postorder, Block, Function, Inst, ProgPoint, RegAllocError};
9use smallvec::{smallvec, SmallVec};
10
11#[derive(Clone, Debug)]
12pub struct CFGInfo {
13    /// Postorder traversal of blocks.
14    pub postorder: Vec<Block>,
15    /// Domtree parents, indexed by block.
16    pub domtree: Vec<Block>,
17    /// For each instruction, the block it belongs to.
18    pub insn_block: Vec<Block>,
19    /// For each block, the first instruction.
20    pub block_entry: Vec<ProgPoint>,
21    /// For each block, the last instruction.
22    pub block_exit: Vec<ProgPoint>,
23    /// For each block, what is the approximate loop depth?
24    ///
25    /// This measure is fully precise iff the input CFG is reducible
26    /// and blocks are in RPO, so that loop backedges are precisely
27    /// those whose block target indices are less than their source
28    /// indices. Otherwise, it will be approximate, but should still
29    /// be usable for heuristic purposes.
30    pub approx_loop_depth: Vec<u32>,
31}
32
33impl CFGInfo {
34    pub fn new<F: Function>(f: &F) -> Result<CFGInfo, RegAllocError> {
35        let postorder = postorder::calculate(f.num_blocks(), f.entry_block(), |block| {
36            f.block_succs(block)
37        });
38        let domtree = domtree::calculate(
39            f.num_blocks(),
40            |block| f.block_preds(block),
41            &postorder[..],
42            f.entry_block(),
43        );
44        let mut insn_block = vec![Block::invalid(); f.num_insts()];
45        let mut block_entry = vec![ProgPoint::before(Inst::invalid()); f.num_blocks()];
46        let mut block_exit = vec![ProgPoint::before(Inst::invalid()); f.num_blocks()];
47        let mut backedge_in = vec![0; f.num_blocks()];
48        let mut backedge_out = vec![0; f.num_blocks()];
49
50        for block in 0..f.num_blocks() {
51            let block = Block::new(block);
52            for inst in f.block_insns(block).iter() {
53                insn_block[inst.index()] = block;
54            }
55            block_entry[block.index()] = ProgPoint::before(f.block_insns(block).first());
56            block_exit[block.index()] = ProgPoint::after(f.block_insns(block).last());
57
58            // Check critical edge condition: if there is more than
59            // one predecessor, each must have only one successor
60            // (this block).
61            let preds = f.block_preds(block).len() + if block == f.entry_block() { 1 } else { 0 };
62            if preds > 1 {
63                for &pred in f.block_preds(block) {
64                    let succs = f.block_succs(pred).len();
65                    if succs > 1 {
66                        return Err(RegAllocError::CritEdge(pred, block));
67                    }
68                }
69            }
70
71            // Check branch-arg condition: if any successors have more
72            // than one predecessor (given above, there will only be
73            // one such successor), then the last instruction of this
74            // block (the branch) cannot have any args other than the
75            // blockparams.
76            let mut require_no_branch_args = false;
77            for &succ in f.block_succs(block) {
78                let preds = f.block_preds(succ).len() + if succ == f.entry_block() { 1 } else { 0 };
79                if preds > 1 {
80                    require_no_branch_args = true;
81                }
82            }
83            if require_no_branch_args {
84                let last = f.block_insns(block).last();
85                if !f.inst_operands(last).is_empty() {
86                    return Err(RegAllocError::DisallowedBranchArg(last));
87                }
88            }
89
90            for &succ in f.block_succs(block) {
91                if succ.index() <= block.index() {
92                    backedge_in[succ.index()] += 1;
93                    backedge_out[block.index()] += 1;
94                }
95            }
96        }
97
98        let mut approx_loop_depth = vec![];
99        let mut backedge_stack: SmallVec<[usize; 4]> = smallvec![];
100        let mut cur_depth = 0;
101        for block in 0..f.num_blocks() {
102            if backedge_in[block] > 0 {
103                cur_depth += 1;
104                backedge_stack.push(backedge_in[block]);
105            }
106
107            approx_loop_depth.push(cur_depth);
108
109            while backedge_stack.len() > 0 && backedge_out[block] > 0 {
110                backedge_out[block] -= 1;
111                *backedge_stack.last_mut().unwrap() -= 1;
112                if *backedge_stack.last().unwrap() == 0 {
113                    cur_depth -= 1;
114                    backedge_stack.pop();
115                }
116            }
117        }
118
119        Ok(CFGInfo {
120            postorder,
121            domtree,
122            insn_block,
123            block_entry,
124            block_exit,
125            approx_loop_depth,
126        })
127    }
128
129    pub fn dominates(&self, a: Block, b: Block) -> bool {
130        domtree::dominates(&self.domtree[..], a, b)
131    }
132}
regalloc2/cfg.rs

regalloc2/
cfg.rs
