1 //! Instruction predicates/properties, shared by various analyses.
2 use crate::ir::immediates::Offset32;
3 use crate::ir::instructions::BranchInfo;
4 use crate::ir::{Block, DataFlowGraph, Function, Inst, InstructionData, Opcode, Type, Value};
5 use cranelift_entity::EntityRef;
6 
7 /// Preserve instructions with used result values.
8 pub fn any_inst_results_used(inst: Inst, live: &[bool], dfg: &DataFlowGraph) -> bool {
9     dfg.inst_results(inst).iter().any(|v| live[v.index()])
10 }
11 
12 /// Test whether the given opcode is unsafe to even consider as side-effect-free.
13 #[inline(always)]
14 fn trivially_has_side_effects(opcode: Opcode) -> bool {
15     opcode.is_call()
16         || opcode.is_branch()
17         || opcode.is_terminator()
18         || opcode.is_return()
19         || opcode.can_trap()
20         || opcode.other_side_effects()
21         || opcode.can_store()
22 }
23 
24 /// Load instructions without the `notrap` flag are defined to trap when
25 /// operating on inaccessible memory, so we can't treat them as side-effect-free even if the loaded
26 /// value is unused.
27 #[inline(always)]
28 fn is_load_with_defined_trapping(opcode: Opcode, data: &InstructionData) -> bool {
29     if !opcode.can_load() {
30         return false;
31     }
32     match *data {
33         InstructionData::StackLoad { .. } => false,
34         InstructionData::Load { flags, .. } => !flags.notrap(),
35         _ => true,
36     }
37 }
38 
39 /// Does the given instruction have any side-effect that would preclude it from being removed when
40 /// its value is unused?
41 #[inline(always)]
42 pub fn has_side_effect(func: &Function, inst: Inst) -> bool {
43     let data = &func.dfg.insts[inst];
44     let opcode = data.opcode();
45     trivially_has_side_effects(opcode) || is_load_with_defined_trapping(opcode, data)
46 }
47 
48 /// Does the given instruction behave as a "pure" node with respect to
49 /// aegraph semantics?
50 ///
51 /// - Actual pure nodes (arithmetic, etc)
52 /// - Loads with the `readonly` flag set
53 pub fn is_pure_for_egraph(func: &Function, inst: Inst) -> bool {
54     let is_readonly_load = match func.dfg.insts[inst] {
55         InstructionData::Load {
56             opcode: Opcode::Load,
57             flags,
58             ..
59         } => flags.readonly() && flags.notrap(),
60         _ => false,
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. iadd_cout) 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_readonly_load || (!op.can_load() && !trivially_has_side_effects(op)))
75 }
76 
77 /// Does the given instruction have any side-effect as per [has_side_effect], or else is a load,
78 /// but not the get_pinned_reg opcode?
79 pub fn has_lowering_side_effect(func: &Function, inst: Inst) -> bool {
80     let op = func.dfg.insts[inst].opcode();
81     op != Opcode::GetPinnedReg && (has_side_effect(func, inst) || op.can_load())
82 }
83 
84 /// Is the given instruction a constant value (`iconst`, `fconst`) that can be
85 /// represented in 64 bits?
86 pub fn is_constant_64bit(func: &Function, inst: Inst) -> Option<u64> {
87     let data = &func.dfg.insts[inst];
88     if data.opcode() == Opcode::Null {
89         return Some(0);
90     }
91     match data {
92         &InstructionData::UnaryImm { imm, .. } => Some(imm.bits() as u64),
93         &InstructionData::UnaryIeee32 { imm, .. } => Some(imm.bits() as u64),
94         &InstructionData::UnaryIeee64 { imm, .. } => Some(imm.bits()),
95         _ => None,
96     }
97 }
98 
99 /// Get the address, offset, and access type from the given instruction, if any.
100 pub fn inst_addr_offset_type(func: &Function, inst: Inst) -> Option<(Value, Offset32, Type)> {
101     let data = &func.dfg.insts[inst];
102     match data {
103         InstructionData::Load { arg, offset, .. } => {
104             let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]);
105             Some((*arg, *offset, ty))
106         }
107         InstructionData::LoadNoOffset { arg, .. } => {
108             let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]);
109             Some((*arg, 0.into(), ty))
110         }
111         InstructionData::Store { args, offset, .. } => {
112             let ty = func.dfg.value_type(args[0]);
113             Some((args[1], *offset, ty))
114         }
115         InstructionData::StoreNoOffset { args, .. } => {
116             let ty = func.dfg.value_type(args[0]);
117             Some((args[1], 0.into(), ty))
118         }
119         _ => None,
120     }
121 }
122 
123 /// Get the store data, if any, from an instruction.
124 pub fn inst_store_data(func: &Function, inst: Inst) -> Option<Value> {
125     let data = &func.dfg.insts[inst];
126     match data {
127         InstructionData::Store { args, .. } | InstructionData::StoreNoOffset { args, .. } => {
128             Some(args[0])
129         }
130         _ => None,
131     }
132 }
133 
134 /// Determine whether this opcode behaves as a memory fence, i.e.,
135 /// prohibits any moving of memory accesses across it.
136 pub fn has_memory_fence_semantics(op: Opcode) -> bool {
137     match op {
138         Opcode::AtomicRmw
139         | Opcode::AtomicCas
140         | Opcode::AtomicLoad
141         | Opcode::AtomicStore
142         | Opcode::Fence
143         | Opcode::Debugtrap => true,
144         Opcode::Call | Opcode::CallIndirect => true,
145         op if op.can_trap() => true,
146         _ => false,
147     }
148 }
149 
150 /// Visit all successors of a block with a given visitor closure. The closure
151 /// arguments are the branch instruction that is used to reach the successor,
152 /// the successor block itself, and a flag indicating whether the block is
153 /// branched to via a table entry.
154 pub(crate) fn visit_block_succs<F: FnMut(Inst, Block, bool)>(
155     f: &Function,
156     block: Block,
157     mut visit: F,
158 ) {
159     for inst in f.layout.block_likely_branches(block) {
160         if f.dfg.insts[inst].opcode().is_branch() {
161             visit_branch_targets(f, inst, &mut visit);
162         }
163     }
164 }
165 
166 fn visit_branch_targets<F: FnMut(Inst, Block, bool)>(f: &Function, inst: Inst, visit: &mut F) {
167     match f.dfg.insts[inst].analyze_branch() {
168         BranchInfo::NotABranch => {}
169         BranchInfo::SingleDest(dest) => {
170             visit(inst, dest.block(&f.dfg.value_lists), false);
171         }
172         BranchInfo::Table(table, dest) => {
173             // The default block is reached via a direct conditional branch,
174             // so it is not part of the table.
175             visit(inst, dest, false);
176 
177             for &dest in f.jump_tables[table].as_slice() {
178                 visit(inst, dest, true);
179             }
180         }
181     }
182 }
183