cranelift_codegen/
inst_predicates.rs

1//! Instruction predicates/properties, shared by various analyses.
2use crate::ir::immediates::Offset32;
3use crate::ir::{self, Block, DataFlowGraph, Function, Inst, InstructionData, Opcode, Type, Value};
4use cranelift_entity::EntityRef;
5
6/// Preserve instructions with used result values.
7pub fn any_inst_results_used(inst: Inst, live: &[bool], dfg: &DataFlowGraph) -> bool {
8    dfg.inst_results(inst).iter().any(|v| live[v.index()])
9}
10
11/// Test whether the given opcode is unsafe to even consider as side-effect-free.
12#[inline(always)]
13fn trivially_has_side_effects(opcode: Opcode) -> bool {
14    opcode.is_call()
15        || opcode.is_branch()
16        || opcode.is_terminator()
17        || opcode.is_return()
18        || opcode.can_trap()
19        || opcode.other_side_effects()
20        || opcode.can_store()
21}
22
23/// Load instructions without the `notrap` flag are defined to trap when
24/// operating on inaccessible memory, so we can't treat them as side-effect-free even if the loaded
25/// value is unused.
26#[inline(always)]
27fn is_load_with_defined_trapping(opcode: Opcode, data: &InstructionData) -> bool {
28    if !opcode.can_load() {
29        return false;
30    }
31    match *data {
32        InstructionData::StackLoad { .. } => false,
33        InstructionData::Load { flags, .. } => !flags.notrap(),
34        _ => true,
35    }
36}
37
38/// Does the given instruction have any side-effect that would preclude it from being removed when
39/// its value is unused?
40#[inline(always)]
41pub fn has_side_effect(func: &Function, inst: Inst) -> bool {
42    let data = &func.dfg.insts[inst];
43    let opcode = data.opcode();
44    trivially_has_side_effects(opcode) || is_load_with_defined_trapping(opcode, data)
45}
46
47/// Does the given instruction behave as a "pure" node with respect to
48/// aegraph semantics?
49///
50/// - Actual pure nodes (arithmetic, etc)
51/// - Loads with the `readonly` flag set
52pub fn is_pure_for_egraph(func: &Function, inst: Inst) -> bool {
53    let is_readonly_load = match func.dfg.insts[inst] {
54        InstructionData::Load {
55            opcode: Opcode::Load,
56            flags,
57            ..
58        } => flags.readonly() && flags.notrap(),
59        _ => false,
60    };
61    // Multi-value results do not play nicely with much of the egraph
62    // infrastructure. They are in practice used only for multi-return
63    // calls and some other odd instructions (e.g. iadd_cout) which,
64    // for now, we can afford to leave in place as opaque
65    // side-effecting ops. So if more than one result, then the inst
66    // is "not pure". Similarly, ops with zero results can be used
67    // only for their side-effects, so are never pure. (Or if they
68    // are, we can always trivially eliminate them with no effect.)
69    let has_one_result = func.dfg.inst_results(inst).len() == 1;
70
71    let op = func.dfg.insts[inst].opcode();
72
73    has_one_result && (is_readonly_load || (!op.can_load() && !trivially_has_side_effects(op)))
74}
75
76/// Can the given instruction be merged into another copy of itself?
77/// These instructions may have side-effects, but as long as we retain
78/// the first instance of the instruction, the second and further
79/// instances are redundant if they would produce the same trap or
80/// result.
81pub fn is_mergeable_for_egraph(func: &Function, inst: Inst) -> bool {
82    let op = func.dfg.insts[inst].opcode();
83    // We can only merge one-result operators due to the way that GVN
84    // is structured in the egraph implementation.
85    let has_one_result = func.dfg.inst_results(inst).len() == 1;
86    has_one_result
87        // Loads/stores are handled by alias analysis and not
88        // otherwise mergeable.
89        && !op.can_load()
90        && !op.can_store()
91        // Can only have idempotent side-effects.
92        && (!has_side_effect(func, inst) || op.side_effects_idempotent())
93}
94
95/// Does the given instruction have any side-effect as per [has_side_effect], or else is a load,
96/// but not the get_pinned_reg opcode?
97pub fn has_lowering_side_effect(func: &Function, inst: Inst) -> bool {
98    let op = func.dfg.insts[inst].opcode();
99    op != Opcode::GetPinnedReg && (has_side_effect(func, inst) || op.can_load())
100}
101
102/// Is the given instruction a constant value (`iconst`, `fconst`) that can be
103/// represented in 64 bits?
104pub fn is_constant_64bit(func: &Function, inst: Inst) -> Option<u64> {
105    let data = &func.dfg.insts[inst];
106    if data.opcode() == Opcode::Null {
107        return Some(0);
108    }
109    match data {
110        &InstructionData::UnaryImm { imm, .. } => Some(imm.bits() as u64),
111        &InstructionData::UnaryIeee32 { imm, .. } => Some(imm.bits() as u64),
112        &InstructionData::UnaryIeee64 { imm, .. } => Some(imm.bits()),
113        _ => None,
114    }
115}
116
117/// Get the address, offset, and access type from the given instruction, if any.
118pub fn inst_addr_offset_type(func: &Function, inst: Inst) -> Option<(Value, Offset32, Type)> {
119    let data = &func.dfg.insts[inst];
120    match data {
121        InstructionData::Load { arg, offset, .. } => {
122            let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]);
123            Some((*arg, *offset, ty))
124        }
125        InstructionData::LoadNoOffset { arg, .. } => {
126            let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]);
127            Some((*arg, 0.into(), ty))
128        }
129        InstructionData::Store { args, offset, .. } => {
130            let ty = func.dfg.value_type(args[0]);
131            Some((args[1], *offset, ty))
132        }
133        InstructionData::StoreNoOffset { args, .. } => {
134            let ty = func.dfg.value_type(args[0]);
135            Some((args[1], 0.into(), ty))
136        }
137        _ => None,
138    }
139}
140
141/// Get the store data, if any, from an instruction.
142pub fn inst_store_data(func: &Function, inst: Inst) -> Option<Value> {
143    let data = &func.dfg.insts[inst];
144    match data {
145        InstructionData::Store { args, .. } | InstructionData::StoreNoOffset { args, .. } => {
146            Some(args[0])
147        }
148        _ => None,
149    }
150}
151
152/// Determine whether this opcode behaves as a memory fence, i.e.,
153/// prohibits any moving of memory accesses across it.
154pub fn has_memory_fence_semantics(op: Opcode) -> bool {
155    match op {
156        Opcode::AtomicRmw
157        | Opcode::AtomicCas
158        | Opcode::AtomicLoad
159        | Opcode::AtomicStore
160        | Opcode::Fence
161        | Opcode::Debugtrap => true,
162        Opcode::Call | Opcode::CallIndirect => true,
163        op if op.can_trap() => true,
164        _ => false,
165    }
166}
167
168/// Visit all successors of a block with a given visitor closure. The closure
169/// arguments are the branch instruction that is used to reach the successor,
170/// the successor block itself, and a flag indicating whether the block is
171/// branched to via a table entry.
172pub(crate) fn visit_block_succs<F: FnMut(Inst, Block, bool)>(
173    f: &Function,
174    block: Block,
175    mut visit: F,
176) {
177    if let Some(inst) = f.layout.last_inst(block) {
178        match &f.dfg.insts[inst] {
179            ir::InstructionData::Jump {
180                destination: dest, ..
181            } => {
182                visit(inst, dest.block(&f.dfg.value_lists), false);
183            }
184
185            ir::InstructionData::Brif {
186                blocks: [block_then, block_else],
187                ..
188            } => {
189                visit(inst, block_then.block(&f.dfg.value_lists), false);
190                visit(inst, block_else.block(&f.dfg.value_lists), false);
191            }
192
193            ir::InstructionData::BranchTable { table, .. } => {
194                let pool = &f.dfg.value_lists;
195                let table = &f.stencil.dfg.jump_tables[*table];
196
197                // The default block is reached via a direct conditional branch,
198                // so it is not part of the table. We visit the default block
199                // first explicitly, to mirror the traversal order of
200                // `JumpTableData::all_branches`, and transitively the order of
201                // `InstructionData::branch_destination`.
202                //
203                // Additionally, this case is why we are unable to replace this
204                // whole function with a loop over `branch_destination`: we need
205                // to report which branch targets come from the table vs the
206                // default.
207                visit(inst, table.default_block().block(pool), false);
208
209                for dest in table.as_slice() {
210                    visit(inst, dest.block(pool), true);
211                }
212            }
213
214            inst => debug_assert!(!inst.opcode().is_branch()),
215        }
216    }
217}
cranelift_codegen/inst_predicates.rs

cranelift_codegen/
inst_predicates.rs
