cranelift_codegen/legalizer/
mod.rs

1//! Legalize instructions.
2//!
3//! A legal instruction is one that can be mapped directly to a machine code instruction for the
4//! target ISA. The `legalize_function()` function takes as input any function and transforms it
5//! into an equivalent function using only legal instructions.
6//!
7//! The characteristics of legal instructions depend on the target ISA, so any given instruction
8//! can be legal for one ISA and illegal for another.
9//!
10//! Besides transforming instructions, the legalizer also fills out the `function.encodings` map
11//! which provides a legal encoding recipe for every instruction.
12//!
13//! The legalizer does not deal with register allocation constraints. These constraints are derived
14//! from the encoding recipes, and solved later by the register allocator.
15
16use crate::cursor::{Cursor, FuncCursor};
17use crate::flowgraph::ControlFlowGraph;
18use crate::ir::immediates::Imm64;
19use crate::ir::types::{I128, I64};
20use crate::ir::{self, InstBuilder, InstructionData, MemFlags, Value};
21use crate::isa::TargetIsa;
22use crate::trace;
23
24mod globalvalue;
25mod table;
26
27use self::globalvalue::expand_global_value;
28use self::table::expand_table_addr;
29
30fn imm_const(pos: &mut FuncCursor, arg: Value, imm: Imm64, is_signed: bool) -> Value {
31    let ty = pos.func.dfg.value_type(arg);
32    match (ty, is_signed) {
33        (I128, true) => {
34            let imm = pos.ins().iconst(I64, imm);
35            pos.ins().sextend(I128, imm)
36        }
37        (I128, false) => {
38            let imm = pos.ins().iconst(I64, imm);
39            pos.ins().uextend(I128, imm)
40        }
41        _ => pos.ins().iconst(ty.lane_type(), imm),
42    }
43}
44
45/// Perform a simple legalization by expansion of the function, without
46/// platform-specific transforms.
47pub fn simple_legalize(func: &mut ir::Function, cfg: &mut ControlFlowGraph, isa: &dyn TargetIsa) {
48    trace!("Pre-legalization function:\n{}", func.display());
49
50    let mut pos = FuncCursor::new(func);
51    let func_begin = pos.position();
52    pos.set_position(func_begin);
53    while let Some(_block) = pos.next_block() {
54        let mut prev_pos = pos.position();
55        while let Some(inst) = pos.next_inst() {
56            match pos.func.dfg.insts[inst] {
57                // control flow
58                InstructionData::CondTrap {
59                    opcode:
60                        opcode @ (ir::Opcode::Trapnz | ir::Opcode::Trapz | ir::Opcode::ResumableTrapnz),
61                    arg,
62                    code,
63                } => {
64                    expand_cond_trap(inst, &mut pos.func, cfg, opcode, arg, code);
65                }
66
67                // memory and constants
68                InstructionData::UnaryGlobalValue {
69                    opcode: ir::Opcode::GlobalValue,
70                    global_value,
71                } => expand_global_value(inst, &mut pos.func, isa, global_value),
72                InstructionData::StackLoad {
73                    opcode: ir::Opcode::StackLoad,
74                    stack_slot,
75                    offset,
76                } => {
77                    let ty = pos.func.dfg.value_type(pos.func.dfg.first_result(inst));
78                    let addr_ty = isa.pointer_type();
79
80                    let mut pos = FuncCursor::new(pos.func).at_inst(inst);
81                    pos.use_srcloc(inst);
82
83                    let addr = pos.ins().stack_addr(addr_ty, stack_slot, offset);
84
85                    // Stack slots are required to be accessible.
86                    // We can't currently ensure that they are aligned.
87                    let mut mflags = MemFlags::new();
88                    mflags.set_notrap();
89                    pos.func.dfg.replace(inst).load(ty, mflags, addr, 0);
90                }
91                InstructionData::StackStore {
92                    opcode: ir::Opcode::StackStore,
93                    arg,
94                    stack_slot,
95                    offset,
96                } => {
97                    let addr_ty = isa.pointer_type();
98
99                    let mut pos = FuncCursor::new(pos.func).at_inst(inst);
100                    pos.use_srcloc(inst);
101
102                    let addr = pos.ins().stack_addr(addr_ty, stack_slot, offset);
103
104                    // Stack slots are required to be accessible.
105                    // We can't currently ensure that they are aligned.
106                    let mut mflags = MemFlags::new();
107                    mflags.set_notrap();
108                    pos.func.dfg.replace(inst).store(mflags, arg, addr, 0);
109                }
110                InstructionData::DynamicStackLoad {
111                    opcode: ir::Opcode::DynamicStackLoad,
112                    dynamic_stack_slot,
113                } => {
114                    let ty = pos.func.dfg.value_type(pos.func.dfg.first_result(inst));
115                    assert!(ty.is_dynamic_vector());
116                    let addr_ty = isa.pointer_type();
117
118                    let mut pos = FuncCursor::new(pos.func).at_inst(inst);
119                    pos.use_srcloc(inst);
120
121                    let addr = pos.ins().dynamic_stack_addr(addr_ty, dynamic_stack_slot);
122
123                    // Stack slots are required to be accessible and aligned.
124                    let mflags = MemFlags::trusted();
125                    pos.func.dfg.replace(inst).load(ty, mflags, addr, 0);
126                }
127                InstructionData::DynamicStackStore {
128                    opcode: ir::Opcode::DynamicStackStore,
129                    arg,
130                    dynamic_stack_slot,
131                } => {
132                    pos.use_srcloc(inst);
133                    let addr_ty = isa.pointer_type();
134                    let vector_ty = pos.func.dfg.value_type(arg);
135                    assert!(vector_ty.is_dynamic_vector());
136
137                    let addr = pos.ins().dynamic_stack_addr(addr_ty, dynamic_stack_slot);
138
139                    let mut mflags = MemFlags::new();
140                    // Stack slots are required to be accessible and aligned.
141                    mflags.set_notrap();
142                    mflags.set_aligned();
143                    pos.func.dfg.replace(inst).store(mflags, arg, addr, 0);
144                }
145                InstructionData::TableAddr {
146                    opcode: ir::Opcode::TableAddr,
147                    table,
148                    arg,
149                    offset,
150                } => expand_table_addr(isa, inst, &mut pos.func, table, arg, offset),
151
152                InstructionData::BinaryImm64 { opcode, arg, imm } => {
153                    let is_signed = match opcode {
154                        ir::Opcode::IaddImm
155                        | ir::Opcode::IrsubImm
156                        | ir::Opcode::ImulImm
157                        | ir::Opcode::SdivImm
158                        | ir::Opcode::SremImm => true,
159                        _ => false,
160                    };
161
162                    let imm = imm_const(&mut pos, arg, imm, is_signed);
163                    let replace = pos.func.dfg.replace(inst);
164                    match opcode {
165                        // bitops
166                        ir::Opcode::BandImm => {
167                            replace.band(arg, imm);
168                        }
169                        ir::Opcode::BorImm => {
170                            replace.bor(arg, imm);
171                        }
172                        ir::Opcode::BxorImm => {
173                            replace.bxor(arg, imm);
174                        }
175                        // bitshifting
176                        ir::Opcode::IshlImm => {
177                            replace.ishl(arg, imm);
178                        }
179                        ir::Opcode::RotlImm => {
180                            replace.rotl(arg, imm);
181                        }
182                        ir::Opcode::RotrImm => {
183                            replace.rotr(arg, imm);
184                        }
185                        ir::Opcode::SshrImm => {
186                            replace.sshr(arg, imm);
187                        }
188                        ir::Opcode::UshrImm => {
189                            replace.ushr(arg, imm);
190                        }
191                        // math
192                        ir::Opcode::IaddImm => {
193                            replace.iadd(arg, imm);
194                        }
195                        ir::Opcode::IrsubImm => {
196                            // note: arg order reversed
197                            replace.isub(imm, arg);
198                        }
199                        ir::Opcode::ImulImm => {
200                            replace.imul(arg, imm);
201                        }
202                        ir::Opcode::SdivImm => {
203                            replace.sdiv(arg, imm);
204                        }
205                        ir::Opcode::SremImm => {
206                            replace.srem(arg, imm);
207                        }
208                        ir::Opcode::UdivImm => {
209                            replace.udiv(arg, imm);
210                        }
211                        ir::Opcode::UremImm => {
212                            replace.urem(arg, imm);
213                        }
214                        _ => prev_pos = pos.position(),
215                    };
216                }
217
218                // comparisons
219                InstructionData::IntCompareImm {
220                    opcode: ir::Opcode::IcmpImm,
221                    cond,
222                    arg,
223                    imm,
224                } => {
225                    let imm = imm_const(&mut pos, arg, imm, true);
226                    pos.func.dfg.replace(inst).icmp(cond, arg, imm);
227                }
228
229                // Legalize the fused bitwise-plus-not instructions into simpler
230                // instructions to assist with optimizations. Lowering will
231                // pattern match this sequence regardless when architectures
232                // support the instruction natively.
233                InstructionData::Binary { opcode, args } => {
234                    match opcode {
235                        ir::Opcode::BandNot => {
236                            let neg = pos.ins().bnot(args[1]);
237                            pos.func.dfg.replace(inst).band(args[0], neg);
238                        }
239                        ir::Opcode::BorNot => {
240                            let neg = pos.ins().bnot(args[1]);
241                            pos.func.dfg.replace(inst).bor(args[0], neg);
242                        }
243                        ir::Opcode::BxorNot => {
244                            let neg = pos.ins().bnot(args[1]);
245                            pos.func.dfg.replace(inst).bxor(args[0], neg);
246                        }
247                        _ => prev_pos = pos.position(),
248                    };
249                }
250
251                _ => {
252                    prev_pos = pos.position();
253                    continue;
254                }
255            }
256
257            // Legalization implementations require fixpoint loop here.
258            // TODO: fix this.
259            pos.set_position(prev_pos);
260        }
261    }
262
263    trace!("Post-legalization function:\n{}", func.display());
264}
265
266/// Custom expansion for conditional trap instructions.
267fn expand_cond_trap(
268    inst: ir::Inst,
269    func: &mut ir::Function,
270    cfg: &mut ControlFlowGraph,
271    opcode: ir::Opcode,
272    arg: ir::Value,
273    code: ir::TrapCode,
274) {
275    trace!(
276        "expanding conditional trap: {:?}: {}",
277        inst,
278        func.dfg.display_inst(inst)
279    );
280
281    // Parse the instruction.
282    let trapz = match opcode {
283        ir::Opcode::Trapz => true,
284        ir::Opcode::Trapnz | ir::Opcode::ResumableTrapnz => false,
285        _ => panic!("Expected cond trap: {}", func.dfg.display_inst(inst)),
286    };
287
288    // Split the block after `inst`:
289    //
290    //     trapnz arg
291    //     ..
292    //
293    // Becomes:
294    //
295    //     brif arg, new_block_trap, new_block_resume
296    //
297    //   new_block_trap:
298    //     trap
299    //
300    //   new_block_resume:
301    //     ..
302    let old_block = func
303        .layout
304        .inst_block(inst)
305        .expect("Instruction not in layout.");
306    let new_block_trap = func.dfg.make_block();
307    let new_block_resume = func.dfg.make_block();
308
309    // Trapping is a rare event, mark the trapping block as cold.
310    func.layout.set_cold(new_block_trap);
311
312    // Replace trap instruction by the inverted condition.
313    if trapz {
314        func.dfg
315            .replace(inst)
316            .brif(arg, new_block_resume, &[], new_block_trap, &[]);
317    } else {
318        func.dfg
319            .replace(inst)
320            .brif(arg, new_block_trap, &[], new_block_resume, &[]);
321    }
322
323    // Insert the new label and the unconditional trap terminator.
324    let mut pos = FuncCursor::new(func).after_inst(inst);
325    pos.use_srcloc(inst);
326    pos.insert_block(new_block_trap);
327
328    match opcode {
329        ir::Opcode::Trapz | ir::Opcode::Trapnz => {
330            pos.ins().trap(code);
331        }
332        ir::Opcode::ResumableTrapnz => {
333            pos.ins().resumable_trap(code);
334            pos.ins().jump(new_block_resume, &[]);
335        }
336        _ => unreachable!(),
337    }
338
339    // Insert the new label and resume the execution when the trap fails.
340    pos.insert_block(new_block_resume);
341
342    // Finally update the CFG.
343    cfg.recompute_block(pos.func, old_block);
344    cfg.recompute_block(pos.func, new_block_resume);
345    cfg.recompute_block(pos.func, new_block_trap);
346}
cranelift_codegen/legalizer/mod.rs

cranelift_codegen/legalizer/
mod.rs
