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

regalloc2/
ssa.rs
