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

regalloc2/
ssa.rs
