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 /// 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. 82 pub fn is_mergeable_for_egraph(func: &Function, inst: Inst) -> bool { 83 let op = func.dfg.insts[inst].opcode(); 84 // We can only merge one-result operators due to the way that GVN 85 // is structured in the egraph implementation. 86 let has_one_result = func.dfg.inst_results(inst).len() == 1; 87 has_one_result 88 // Loads/stores are handled by alias analysis and not 89 // otherwise mergeable. 90 && !op.can_load() 91 && !op.can_store() 92 // Can only have idempotent side-effects. 93 && (!has_side_effect(func, inst) || op.side_effects_idempotent()) 94 } 95 96 /// Does the given instruction have any side-effect as per [has_side_effect], or else is a load, 97 /// but not the get_pinned_reg opcode? 98 pub fn has_lowering_side_effect(func: &Function, inst: Inst) -> bool { 99 let op = func.dfg.insts[inst].opcode(); 100 op != Opcode::GetPinnedReg && (has_side_effect(func, inst) || op.can_load()) 101 } 102 103 /// Is the given instruction a constant value (`iconst`, `fconst`) that can be 104 /// represented in 64 bits? 105 pub fn is_constant_64bit(func: &Function, inst: Inst) -> Option<u64> { 106 let data = &func.dfg.insts[inst]; 107 if data.opcode() == Opcode::Null { 108 return Some(0); 109 } 110 match data { 111 &InstructionData::UnaryImm { imm, .. } => Some(imm.bits() as u64), 112 &InstructionData::UnaryIeee32 { imm, .. } => Some(imm.bits() as u64), 113 &InstructionData::UnaryIeee64 { imm, .. } => Some(imm.bits()), 114 _ => None, 115 } 116 } 117 118 /// Get the address, offset, and access type from the given instruction, if any. 119 pub fn inst_addr_offset_type(func: &Function, inst: Inst) -> Option<(Value, Offset32, Type)> { 120 let data = &func.dfg.insts[inst]; 121 match data { 122 InstructionData::Load { arg, offset, .. } => { 123 let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]); 124 Some((*arg, *offset, ty)) 125 } 126 InstructionData::LoadNoOffset { arg, .. } => { 127 let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]); 128 Some((*arg, 0.into(), ty)) 129 } 130 InstructionData::Store { args, offset, .. } => { 131 let ty = func.dfg.value_type(args[0]); 132 Some((args[1], *offset, ty)) 133 } 134 InstructionData::StoreNoOffset { args, .. } => { 135 let ty = func.dfg.value_type(args[0]); 136 Some((args[1], 0.into(), ty)) 137 } 138 _ => None, 139 } 140 } 141 142 /// Get the store data, if any, from an instruction. 143 pub fn inst_store_data(func: &Function, inst: Inst) -> Option<Value> { 144 let data = &func.dfg.insts[inst]; 145 match data { 146 InstructionData::Store { args, .. } | InstructionData::StoreNoOffset { args, .. } => { 147 Some(args[0]) 148 } 149 _ => None, 150 } 151 } 152 153 /// Determine whether this opcode behaves as a memory fence, i.e., 154 /// prohibits any moving of memory accesses across it. 155 pub fn has_memory_fence_semantics(op: Opcode) -> bool { 156 match op { 157 Opcode::AtomicRmw 158 | Opcode::AtomicCas 159 | Opcode::AtomicLoad 160 | Opcode::AtomicStore 161 | Opcode::Fence 162 | Opcode::Debugtrap => true, 163 Opcode::Call | Opcode::CallIndirect => true, 164 op if op.can_trap() => true, 165 _ => false, 166 } 167 } 168 169 /// Visit all successors of a block with a given visitor closure. The closure 170 /// arguments are the branch instruction that is used to reach the successor, 171 /// the successor block itself, and a flag indicating whether the block is 172 /// branched to via a table entry. 173 pub(crate) fn visit_block_succs<F: FnMut(Inst, Block, bool)>( 174 f: &Function, 175 block: Block, 176 mut visit: F, 177 ) { 178 if let Some(inst) = f.layout.last_inst(block) { 179 match f.dfg.insts[inst].analyze_branch() { 180 BranchInfo::NotABranch => {} 181 BranchInfo::SingleDest(dest) => { 182 visit(inst, dest.block(&f.dfg.value_lists), false); 183 } 184 BranchInfo::Conditional(block_then, block_else) => { 185 visit(inst, block_then.block(&f.dfg.value_lists), false); 186 visit(inst, block_else.block(&f.dfg.value_lists), false); 187 } 188 BranchInfo::Table(table, dest) => { 189 // The default block is reached via a direct conditional branch, 190 // so it is not part of the table. 191 visit(inst, dest, false); 192 193 for &dest in f.jump_tables[table].as_slice() { 194 visit(inst, dest, true); 195 } 196 } 197 } 198 } 199 } 200