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 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
//! Instruction predicates/properties, shared by various analyses.
use crate::ir::immediates::Offset32;
use crate::ir::{self, Block, DataFlowGraph, Function, Inst, InstructionData, Opcode, Type, Value};
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.
#[inline(always)]
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.
#[inline(always)]
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?
#[inline(always)]
pub fn has_side_effect(func: &Function, inst: Inst) -> bool {
let data = &func.dfg.insts[inst];
let opcode = data.opcode();
trivially_has_side_effects(opcode) || is_load_with_defined_trapping(opcode, data)
}
/// Does the given instruction behave as a "pure" node with respect to
/// aegraph semantics?
///
/// - Actual pure nodes (arithmetic, etc)
/// - Loads with the `readonly` flag set
pub fn is_pure_for_egraph(func: &Function, inst: Inst) -> bool {
let is_readonly_load = match func.dfg.insts[inst] {
InstructionData::Load {
opcode: Opcode::Load,
flags,
..
} => flags.readonly() && flags.notrap(),
_ => false,
};
// Multi-value results do not play nicely with much of the egraph
// infrastructure. They are in practice used only for multi-return
// calls and some other odd instructions (e.g. iadd_cout) which,
// for now, we can afford to leave in place as opaque
// side-effecting ops. So if more than one result, then the inst
// is "not pure". Similarly, ops with zero results can be used
// only for their side-effects, so are never pure. (Or if they
// are, we can always trivially eliminate them with no effect.)
let has_one_result = func.dfg.inst_results(inst).len() == 1;
let op = func.dfg.insts[inst].opcode();
has_one_result && (is_readonly_load || (!op.can_load() && !trivially_has_side_effects(op)))
}
/// Can the given instruction be merged into another copy of itself?
/// These instructions may have side-effects, but as long as we retain
/// the first instance of the instruction, the second and further
/// instances are redundant if they would produce the same trap or
/// result.
pub fn is_mergeable_for_egraph(func: &Function, inst: Inst) -> bool {
let op = func.dfg.insts[inst].opcode();
// We can only merge one-result operators due to the way that GVN
// is structured in the egraph implementation.
let has_one_result = func.dfg.inst_results(inst).len() == 1;
has_one_result
// Loads/stores are handled by alias analysis and not
// otherwise mergeable.
&& !op.can_load()
&& !op.can_store()
// Can only have idempotent side-effects.
&& (!has_side_effect(func, inst) || op.side_effects_idempotent())
}
/// 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.insts[inst].opcode();
op != Opcode::GetPinnedReg && (has_side_effect(func, inst) || op.can_load())
}
/// Is the given instruction a constant value (`iconst`, `fconst`) that can be
/// represented in 64 bits?
pub fn is_constant_64bit(func: &Function, inst: Inst) -> Option<u64> {
let data = &func.dfg.insts[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()),
_ => 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.insts[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.insts[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
| Opcode::Debugtrap => true,
Opcode::Call | Opcode::CallIndirect => true,
op if op.can_trap() => true,
_ => false,
}
}
/// Visit all successors of a block with a given visitor closure. The closure
/// arguments are the branch instruction that is used to reach the successor,
/// the successor block itself, and a flag indicating whether the block is
/// branched to via a table entry.
pub(crate) fn visit_block_succs<F: FnMut(Inst, Block, bool)>(
f: &Function,
block: Block,
mut visit: F,
) {
if let Some(inst) = f.layout.last_inst(block) {
match &f.dfg.insts[inst] {
ir::InstructionData::Jump {
destination: dest, ..
} => {
visit(inst, dest.block(&f.dfg.value_lists), false);
}
ir::InstructionData::Brif {
blocks: [block_then, block_else],
..
} => {
visit(inst, block_then.block(&f.dfg.value_lists), false);
visit(inst, block_else.block(&f.dfg.value_lists), false);
}
ir::InstructionData::BranchTable { table, .. } => {
let pool = &f.dfg.value_lists;
let table = &f.stencil.dfg.jump_tables[*table];
// The default block is reached via a direct conditional branch,
// so it is not part of the table. We visit the default block
// first explicitly, to mirror the traversal order of
// `JumpTableData::all_branches`, and transitively the order of
// `InstructionData::branch_destination`.
//
// Additionally, this case is why we are unable to replace this
// whole function with a loop over `branch_destination`: we need
// to report which branch targets come from the table vs the
// default.
visit(inst, table.default_block().block(pool), false);
for dest in table.as_slice() {
visit(inst, dest.block(pool), true);
}
}
inst => debug_assert!(!inst.opcode().is_branch()),
}
}
}