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

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

//! SSA-related utilities.

use crate::cfg::CFGInfo;

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

pub fn validate_ssa<F: Function>(f: &F, cfginfo: &CFGInfo) -> Result<(), RegAllocError> {
    // 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. Also check that for every block param and
    // inst def, that this is the only def.
    let mut defined = vec![false; f.num_vregs()];
    for block in 0..f.num_blocks() {
        let block = Block::new(block);
        for blockparam in f.block_params(block) {
            if defined[blockparam.vreg()] {
                return Err(RegAllocError::SSA(*blockparam, Inst::invalid()));
            }
            defined[blockparam.vreg()] = true;
        }
        for iix in f.block_insns(block).iter() {
            let operands = f.inst_operands(iix);
            for operand in operands {
                match operand.kind() {
                    OperandKind::Use => {
                        let def_block = if cfginfo.vreg_def_inst[operand.vreg().vreg()].is_valid() {
                            cfginfo.insn_block[cfginfo.vreg_def_inst[operand.vreg().vreg()].index()]
                        } else {
                            cfginfo.vreg_def_blockparam[operand.vreg().vreg()].0
                        };
                        if def_block.is_invalid() {
                            return Err(RegAllocError::SSA(operand.vreg(), iix));
                        }
                        if !cfginfo.dominates(def_block, block) {
                            return Err(RegAllocError::SSA(operand.vreg(), iix));
                        }
                    }
                    OperandKind::Def => {
                        if defined[operand.vreg().vreg()] {
                            return Err(RegAllocError::SSA(operand.vreg(), iix));
                        }
                        defined[operand.vreg().vreg()] = true;
                    }
                    OperandKind::Mod => {
                        // Mod (modify) operands are not used in SSA,
                        // but can be used by non-SSA code (e.g. with
                        // the regalloc.rs compatibility shim).
                        return Err(RegAllocError::SSA(operand.vreg(), iix));
                    }
                }
            }
        }
    }

    // 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)) {
                    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() {
                            return Err(RegAllocError::Branch(insn));
                        }
                    }
                }
            } else {
                if f.is_branch(insn) || f.is_ret(insn) {
                    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 {
        return Err(RegAllocError::BB(f.entry_block()));
    }

    Ok(())
}