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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

//! Instruction predicates/properties, shared by various analyses.
use crate::ir::immediates::Offset32;
use crate::ir::instructions::BranchInfo;
use crate::ir::{Block, DataFlowGraph, Function, Inst, InstructionData, Opcode, Type, Value};
use crate::machinst::ty_bits;
use cranelift_entity::EntityRef;

/// Preserve instructions with used result values.
pub fn any_inst_results_used(inst: Inst, live: &[bool], dfg: &DataFlowGraph) -> bool {
    dfg.inst_results(inst).iter().any(|v| live[v.index()])
}

/// Test whether the given opcode is unsafe to even consider as side-effect-free.
fn trivially_has_side_effects(opcode: Opcode) -> bool {
    opcode.is_call()
        || opcode.is_branch()
        || opcode.is_terminator()
        || opcode.is_return()
        || opcode.can_trap()
        || opcode.other_side_effects()
        || opcode.can_store()
}

/// Load instructions without the `notrap` flag are defined to trap when
/// operating on inaccessible memory, so we can't treat them as side-effect-free even if the loaded
/// value is unused.
fn is_load_with_defined_trapping(opcode: Opcode, data: &InstructionData) -> bool {
    if !opcode.can_load() {
        return false;
    }
    match *data {
        InstructionData::StackLoad { .. } => false,
        InstructionData::Load { flags, .. } => !flags.notrap(),
        _ => true,
    }
}

/// Does the given instruction have any side-effect that would preclude it from being removed when
/// its value is unused?
pub fn has_side_effect(func: &Function, inst: Inst) -> bool {
    let data = &func.dfg[inst];
    let opcode = data.opcode();
    trivially_has_side_effects(opcode) || is_load_with_defined_trapping(opcode, data)
}

/// Does the given instruction have any side-effect as per [has_side_effect], or else is a load,
/// but not the get_pinned_reg opcode?
pub fn has_lowering_side_effect(func: &Function, inst: Inst) -> bool {
    let op = func.dfg[inst].opcode();
    op != Opcode::GetPinnedReg && (has_side_effect(func, inst) || op.can_load())
}

/// Is the given instruction a constant value (`iconst`, `fconst`, `bconst`) that can be
/// represented in 64 bits?
pub fn is_constant_64bit(func: &Function, inst: Inst) -> Option<u64> {
    let data = &func.dfg[inst];
    if data.opcode() == Opcode::Null {
        return Some(0);
    }
    match data {
        &InstructionData::UnaryImm { imm, .. } => Some(imm.bits() as u64),
        &InstructionData::UnaryIeee32 { imm, .. } => Some(imm.bits() as u64),
        &InstructionData::UnaryIeee64 { imm, .. } => Some(imm.bits()),
        &InstructionData::UnaryBool { imm, .. } => {
            let imm = if imm {
                let bits = ty_bits(func.dfg.value_type(func.dfg.inst_results(inst)[0]));

                if bits < 64 {
                    (1u64 << bits) - 1
                } else {
                    u64::MAX
                }
            } else {
                0
            };

            Some(imm)
        }
        _ => None,
    }
}

/// Get the address, offset, and access type from the given instruction, if any.
pub fn inst_addr_offset_type(func: &Function, inst: Inst) -> Option<(Value, Offset32, Type)> {
    let data = &func.dfg[inst];
    match data {
        InstructionData::Load { arg, offset, .. } => {
            let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]);
            Some((*arg, *offset, ty))
        }
        InstructionData::LoadNoOffset { arg, .. } => {
            let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]);
            Some((*arg, 0.into(), ty))
        }
        InstructionData::Store { args, offset, .. } => {
            let ty = func.dfg.value_type(args[0]);
            Some((args[1], *offset, ty))
        }
        InstructionData::StoreNoOffset { args, .. } => {
            let ty = func.dfg.value_type(args[0]);
            Some((args[1], 0.into(), ty))
        }
        _ => None,
    }
}

/// Get the store data, if any, from an instruction.
pub fn inst_store_data(func: &Function, inst: Inst) -> Option<Value> {
    let data = &func.dfg[inst];
    match data {
        InstructionData::Store { args, .. } | InstructionData::StoreNoOffset { args, .. } => {
            Some(args[0])
        }
        _ => None,
    }
}

/// Determine whether this opcode behaves as a memory fence, i.e.,
/// prohibits any moving of memory accesses across it.
pub fn has_memory_fence_semantics(op: Opcode) -> bool {
    match op {
        Opcode::AtomicRmw
        | Opcode::AtomicCas
        | Opcode::AtomicLoad
        | Opcode::AtomicStore
        | Opcode::Fence => true,
        Opcode::Call | Opcode::CallIndirect => true,
        _ => false,
    }
}

/// Visit all successors of a block with a given visitor closure.
pub(crate) fn visit_block_succs<F: FnMut(Inst, Block)>(f: &Function, block: Block, mut visit: F) {
    for inst in f.layout.block_likely_branches(block) {
        if f.dfg[inst].opcode().is_branch() {
            visit_branch_targets(f, inst, &mut visit);
        }
    }
}

fn visit_branch_targets<F: FnMut(Inst, Block)>(f: &Function, inst: Inst, visit: &mut F) {
    match f.dfg[inst].analyze_branch(&f.dfg.value_lists) {
        BranchInfo::NotABranch => {}
        BranchInfo::SingleDest(dest, _) => {
            visit(inst, dest);
        }
        BranchInfo::Table(table, maybe_dest) => {
            if let Some(dest) = maybe_dest {
                visit(inst, dest);
            }
            for &dest in f.jump_tables[table].as_slice() {
                visit(inst, dest);
            }
        }
    }
}