1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

/*
 * Released under the terms of the Apache 2.0 license with LLVM
 * exception. See `LICENSE` for details.
 */

//! SSA-related utilities.

use std::collections::HashSet;

use crate::cfg::CFGInfo;
use crate::{Block, Function, Inst, OperandKind, RegAllocError, VReg};

pub fn validate_ssa<F: Function>(f: &F, cfginfo: &CFGInfo) -> Result<(), RegAllocError> {
    // For every block param and inst def, check that this is the only def.
    let mut defined_in = vec![Block::invalid(); f.num_vregs()];
    for block in 0..f.num_blocks() {
        let block = Block::new(block);
        let mut def = |vreg: VReg, inst| {
            if defined_in[vreg.vreg()].is_valid() {
                trace!("Multiple def constraints for {:?}", vreg);
                Err(RegAllocError::SSA(vreg, inst))
            } else {
                defined_in[vreg.vreg()] = block;
                Ok(())
            }
        };
        for &param in f.block_params(block) {
            def(param, Inst::invalid())?;
        }
        for inst in f.block_insns(block).iter() {
            for operand in f.inst_operands(inst) {
                if let OperandKind::Def = operand.kind() {
                    def(operand.vreg(), inst)?;
                }
            }
        }
    }

    // Walk the blocks in arbitrary order. Check, for every use, that
    // the def is either in the same block in an earlier inst, or is
    // defined (by inst or blockparam) in some other block that
    // dominates this one.
    let mut local = HashSet::new();
    for block in 0..f.num_blocks() {
        let block = Block::new(block);
        local.clear();
        local.extend(f.block_params(block));

        for iix in f.block_insns(block).iter() {
            let operands = f.inst_operands(iix);
            for operand in operands {
                // Fixed registers uses will likely not be SSA, but they also
                // won't receive assignments.
                if operand.as_fixed_nonallocatable().is_some() {
                    continue;
                }

                match operand.kind() {
                    OperandKind::Use => {
                        let def_block = defined_in[operand.vreg().vreg()];
                        let okay = def_block.is_valid()
                            && if def_block == block {
                                local.contains(&operand.vreg())
                            } else {
                                cfginfo.dominates(def_block, block)
                            };
                        if !okay {
                            trace!("Invalid use {:?}", operand.vreg());
                            return Err(RegAllocError::SSA(operand.vreg(), iix));
                        }
                    }
                    OperandKind::Def => {
                        // Check all the uses in this instruction
                        // first, before recording its defs below.
                    }
                }
            }

            // In SSA form, an instruction can't use a VReg that it
            // also defines. So only record this instruction's defs
            // after its uses have been checked.
            for operand in operands {
                if let OperandKind::Def = operand.kind() {
                    local.insert(operand.vreg());
                }
            }
        }
    }

    // Check that the length of branch args matches the sum of the
    // number of blockparams in their succs, and that the end of every
    // block ends in this branch or in a ret, and that there are no
    // other branches or rets in the middle of the block.
    for block in 0..f.num_blocks() {
        let block = Block::new(block);
        let insns = f.block_insns(block);
        for insn in insns.iter() {
            if insn == insns.last() {
                if !(f.is_branch(insn) || f.is_ret(insn)) {
                    trace!("block {:?} is not terminated by a branch or ret!", block);
                    return Err(RegAllocError::BB(block));
                }
                if f.is_branch(insn) {
                    for (i, &succ) in f.block_succs(block).iter().enumerate() {
                        let blockparams_in = f.block_params(succ);
                        let blockparams_out = f.branch_blockparams(block, insn, i);
                        if blockparams_in.len() != blockparams_out.len() {
                            trace!(
                                "Mismatch on block params, found {} expected {}",
                                blockparams_out.len(),
                                blockparams_in.len()
                            );
                            return Err(RegAllocError::Branch(insn));
                        }
                    }
                }
            } else {
                if f.is_branch(insn) || f.is_ret(insn) {
                    trace!("Block terminator found in the middle of a block");
                    return Err(RegAllocError::BB(block));
                }
            }
        }
    }

    // Check that the entry block has no block args: otherwise it is
    // undefined what their value would be.
    if f.block_params(f.entry_block()).len() > 0 {
        trace!("Entry block contains block args");
        return Err(RegAllocError::BB(f.entry_block()));
    }

    Ok(())
}