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

cranelift_codegen/
inst_predicates.rs
