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