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