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

regalloc2/
cfg.rs
