regalloc2/
ssa.rs

1/*
2 * Released under the terms of the Apache 2.0 license with LLVM
3 * exception. See `LICENSE` for details.
4 */
5
6//! SSA-related utilities.
7
8use alloc::vec;
9
10use crate::cfg::CFGInfo;
11use crate::{Block, Function, FxHashSet, Inst, OperandKind, RegAllocError, VReg};
12
13pub fn validate_ssa<F: Function>(f: &F, cfginfo: &CFGInfo) -> Result<(), RegAllocError> {
14    // For every block param and inst def, check that this is the only def.
15    let mut defined_in = vec![Block::invalid(); f.num_vregs()];
16    for block in 0..f.num_blocks() {
17        let block = Block::new(block);
18        let mut def = |vreg: VReg, inst| {
19            if vreg.vreg() >= defined_in.len() {
20                trace!("VRegs not numbered consecutively {:?}", vreg);
21                return Err(RegAllocError::SSA(vreg, inst));
22            }
23            if defined_in[vreg.vreg()].is_valid() {
24                trace!("Multiple def constraints for {:?}", vreg);
25                Err(RegAllocError::SSA(vreg, inst))
26            } else {
27                defined_in[vreg.vreg()] = block;
28                Ok(())
29            }
30        };
31        for &param in f.block_params(block) {
32            def(param, Inst::invalid())?;
33        }
34        for inst in f.block_insns(block).iter() {
35            for operand in f.inst_operands(inst) {
36                if let OperandKind::Def = operand.kind() {
37                    def(operand.vreg(), inst)?;
38                }
39            }
40        }
41    }
42
43    // Walk the blocks in arbitrary order. Check, for every use, that
44    // the def is either in the same block in an earlier inst, or is
45    // defined (by inst or blockparam) in some other block that
46    // dominates this one.
47    let mut local = FxHashSet::default();
48    for block in 0..f.num_blocks() {
49        let block = Block::new(block);
50        local.clear();
51        local.extend(f.block_params(block));
52
53        for iix in f.block_insns(block).iter() {
54            let operands = f.inst_operands(iix);
55            for operand in operands {
56                // Fixed registers uses will likely not be SSA, but they also
57                // won't receive assignments.
58                if operand.as_fixed_nonallocatable().is_some() {
59                    continue;
60                }
61
62                match operand.kind() {
63                    OperandKind::Use => {
64                        let def_block = defined_in[operand.vreg().vreg()];
65                        let okay = def_block.is_valid()
66                            && if def_block == block {
67                                local.contains(&operand.vreg())
68                            } else {
69                                cfginfo.dominates(def_block, block)
70                            };
71                        if !okay {
72                            trace!("Invalid use {:?}", operand.vreg());
73                            return Err(RegAllocError::SSA(operand.vreg(), iix));
74                        }
75                    }
76                    OperandKind::Def => {
77                        // Check all the uses in this instruction
78                        // first, before recording its defs below.
79                    }
80                }
81            }
82
83            // In SSA form, an instruction can't use a VReg that it
84            // also defines. So only record this instruction's defs
85            // after its uses have been checked.
86            for operand in operands {
87                if let OperandKind::Def = operand.kind() {
88                    local.insert(operand.vreg());
89                }
90            }
91        }
92    }
93
94    // Check that the length of branch args matches the sum of the
95    // number of blockparams in their succs, and that the end of every
96    // block ends in this branch or in a ret, and that there are no
97    // other branches or rets in the middle of the block.
98    for block in 0..f.num_blocks() {
99        let block = Block::new(block);
100        let insns = f.block_insns(block);
101        for insn in insns.iter() {
102            if insn == insns.last() {
103                if !(f.is_branch(insn) || f.is_ret(insn)) {
104                    trace!("block {:?} is not terminated by a branch or ret!", block);
105                    return Err(RegAllocError::BB(block));
106                }
107                if f.is_branch(insn) {
108                    for (i, &succ) in f.block_succs(block).iter().enumerate() {
109                        let blockparams_in = f.block_params(succ);
110                        let blockparams_out = f.branch_blockparams(block, insn, i);
111                        if blockparams_in.len() != blockparams_out.len() {
112                            trace!(
113                                "Mismatch on block params, found {} expected {}",
114                                blockparams_out.len(),
115                                blockparams_in.len()
116                            );
117                            return Err(RegAllocError::Branch(insn));
118                        }
119                    }
120                }
121            } else {
122                if f.is_branch(insn) || f.is_ret(insn) {
123                    trace!("Block terminator found in the middle of a block");
124                    return Err(RegAllocError::BB(block));
125                }
126            }
127        }
128    }
129
130    // Check that the entry block has no block args: otherwise it is
131    // undefined what their value would be.
132    if f.block_params(f.entry_block()).len() > 0 {
133        trace!("Entry block contains block args");
134        return Err(RegAllocError::BB(f.entry_block()));
135    }
136
137    Ok(())
138}
regalloc2/ssa.rs

regalloc2/
ssa.rs
