1 //! A frontend for building Cranelift IR from other languages.
2 use crate::ssa::{SSABuilder, SideEffects};
3 use crate::variable::Variable;
4 use cranelift_codegen::cursor::{Cursor, FuncCursor};
5 use cranelift_codegen::entity::{EntitySet, SecondaryMap};
6 use cranelift_codegen::ir;
7 use cranelift_codegen::ir::function::DisplayFunction;
8 use cranelift_codegen::ir::{
9 types, AbiParam, Block, DataFlowGraph, ExtFuncData, ExternalName, FuncRef, Function,
10 GlobalValue, GlobalValueData, Heap, HeapData, Inst, InstBuilder, InstBuilderBase,
11 InstructionData, JumpTable, JumpTableData, LibCall, MemFlags, SigRef, Signature, StackSlot,
12 StackSlotData, Type, Value, ValueLabel, ValueLabelAssignments, ValueLabelStart,
13 };
14 use cranelift_codegen::isa::{TargetFrontendConfig, TargetIsa};
15 use cranelift_codegen::packed_option::PackedOption;
16
17 /// Structure used for translating a series of functions into Cranelift IR.
18 ///
19 /// In order to reduce memory reallocations when compiling multiple functions,
20 /// `FunctionBuilderContext` holds various data structures which are cleared between
21 /// functions, rather than dropped, preserving the underlying allocations.
22 pub struct FunctionBuilderContext {
23 ssa: SSABuilder,
24 blocks: SecondaryMap<Block, BlockData>,
25 types: SecondaryMap<Variable, Type>,
26 }
27
28 /// Temporary object used to build a single Cranelift IR `Function`.
29 pub struct FunctionBuilder<'a> {
30 /// The function currently being built.
31 /// This field is public so the function can be re-borrowed.
32 pub func: &'a mut Function,
33
34 /// Source location to assign to all new instructions.
35 srcloc: ir::SourceLoc,
36
37 func_ctx: &'a mut FunctionBuilderContext,
38 position: PackedOption<Block>,
39 }
40
41 #[derive(Clone, Default)]
42 struct BlockData {
43 /// A Block is "pristine" iff no instructions have been added since the last
44 /// call to `switch_to_block()`.
45 pristine: bool,
46
47 /// A Block is "filled" iff a terminator instruction has been inserted since
48 /// the last call to `switch_to_block()`.
49 ///
50 /// A filled block cannot be pristine.
51 filled: bool,
52
53 /// Count of parameters not supplied implicitly by the SSABuilder.
54 user_param_count: usize,
55 }
56
57 impl FunctionBuilderContext {
58 /// Creates a FunctionBuilderContext structure. The structure is automatically cleared after
59 /// each [`FunctionBuilder`](struct.FunctionBuilder.html) completes translating a function.
new() -> Self60 pub fn new() -> Self {
61 Self {
62 ssa: SSABuilder::new(),
63 blocks: SecondaryMap::new(),
64 types: SecondaryMap::new(),
65 }
66 }
67
clear(&mut self)68 fn clear(&mut self) {
69 self.ssa.clear();
70 self.blocks.clear();
71 self.types.clear();
72 }
73
is_empty(&self) -> bool74 fn is_empty(&self) -> bool {
75 self.ssa.is_empty() && self.blocks.is_empty() && self.types.is_empty()
76 }
77 }
78
79 /// Implementation of the [`InstBuilder`](cranelift_codegen::ir::InstBuilder) that has
80 /// one convenience method per Cranelift IR instruction.
81 pub struct FuncInstBuilder<'short, 'long: 'short> {
82 builder: &'short mut FunctionBuilder<'long>,
83 block: Block,
84 }
85
86 impl<'short, 'long> FuncInstBuilder<'short, 'long> {
new(builder: &'short mut FunctionBuilder<'long>, block: Block) -> Self87 fn new(builder: &'short mut FunctionBuilder<'long>, block: Block) -> Self {
88 Self { builder, block }
89 }
90 }
91
92 impl<'short, 'long> InstBuilderBase<'short> for FuncInstBuilder<'short, 'long> {
data_flow_graph(&self) -> &DataFlowGraph93 fn data_flow_graph(&self) -> &DataFlowGraph {
94 &self.builder.func.dfg
95 }
96
data_flow_graph_mut(&mut self) -> &mut DataFlowGraph97 fn data_flow_graph_mut(&mut self) -> &mut DataFlowGraph {
98 &mut self.builder.func.dfg
99 }
100
101 // This implementation is richer than `InsertBuilder` because we use the data of the
102 // instruction being inserted to add related info to the DFG and the SSA building system,
103 // and perform debug sanity checks.
build(self, data: InstructionData, ctrl_typevar: Type) -> (Inst, &'short mut DataFlowGraph)104 fn build(self, data: InstructionData, ctrl_typevar: Type) -> (Inst, &'short mut DataFlowGraph) {
105 // We only insert the Block in the layout when an instruction is added to it
106 self.builder.ensure_inserted_block();
107
108 let inst = self.builder.func.dfg.make_inst(data.clone());
109 self.builder.func.dfg.make_inst_results(inst, ctrl_typevar);
110 self.builder.func.layout.append_inst(inst, self.block);
111 if !self.builder.srcloc.is_default() {
112 self.builder.func.srclocs[inst] = self.builder.srcloc;
113 }
114
115 if data.opcode().is_branch() {
116 match data.branch_destination() {
117 Some(dest_block) => {
118 // If the user has supplied jump arguments we must adapt the arguments of
119 // the destination block
120 self.builder.declare_successor(dest_block, inst);
121 }
122 None => {
123 // branch_destination() doesn't detect jump_tables
124 // If jump table we declare all entries successor
125 if let InstructionData::BranchTable {
126 table, destination, ..
127 } = data
128 {
129 // Unlike all other jumps/branches, jump tables are
130 // capable of having the same successor appear
131 // multiple times, so we must deduplicate.
132 let mut unique = EntitySet::<Block>::new();
133 for dest_block in self
134 .builder
135 .func
136 .jump_tables
137 .get(table)
138 .expect("you are referencing an undeclared jump table")
139 .iter()
140 .filter(|&dest_block| unique.insert(*dest_block))
141 {
142 // Call `declare_block_predecessor` instead of `declare_successor` for
143 // avoiding the borrow checker.
144 self.builder.func_ctx.ssa.declare_block_predecessor(
145 *dest_block,
146 self.builder.position.unwrap(),
147 inst,
148 );
149 }
150 self.builder.declare_successor(destination, inst);
151 }
152 }
153 }
154 }
155
156 if data.opcode().is_terminator() {
157 self.builder.fill_current_block()
158 }
159 (inst, &mut self.builder.func.dfg)
160 }
161 }
162
163 /// This module allows you to create a function in Cranelift IR in a straightforward way, hiding
164 /// all the complexity of its internal representation.
165 ///
166 /// The module is parametrized by one type which is the representation of variables in your
167 /// origin language. It offers a way to conveniently append instruction to your program flow.
168 /// You are responsible to split your instruction flow into extended blocks (declared with
169 /// `create_block`) whose properties are:
170 ///
171 /// - branch and jump instructions can only point at the top of extended blocks;
172 /// - the last instruction of each block is a terminator instruction which has no natural successor,
173 /// and those instructions can only appear at the end of extended blocks.
174 ///
175 /// The parameters of Cranelift IR instructions are Cranelift IR values, which can only be created
176 /// as results of other Cranelift IR instructions. To be able to create variables redefined multiple
177 /// times in your program, use the `def_var` and `use_var` command, that will maintain the
178 /// correspondence between your variables and Cranelift IR SSA values.
179 ///
180 /// The first block for which you call `switch_to_block` will be assumed to be the beginning of
181 /// the function.
182 ///
183 /// At creation, a `FunctionBuilder` instance borrows an already allocated `Function` which it
184 /// modifies with the information stored in the mutable borrowed
185 /// [`FunctionBuilderContext`](struct.FunctionBuilderContext.html). The function passed in
186 /// argument should be newly created with
187 /// [`Function::with_name_signature()`](Function::with_name_signature), whereas the
188 /// `FunctionBuilderContext` can be kept as is between two function translations.
189 ///
190 /// # Errors
191 ///
192 /// The functions below will panic in debug mode whenever you try to modify the Cranelift IR
193 /// function in a way that violate the coherence of the code. For instance: switching to a new
194 /// `Block` when you haven't filled the current one with a terminator instruction, inserting a
195 /// return instruction with arguments that don't match the function's signature.
196 impl<'a> FunctionBuilder<'a> {
197 /// Creates a new FunctionBuilder structure that will operate on a `Function` using a
198 /// `FunctionBuilderContext`.
new(func: &'a mut Function, func_ctx: &'a mut FunctionBuilderContext) -> Self199 pub fn new(func: &'a mut Function, func_ctx: &'a mut FunctionBuilderContext) -> Self {
200 debug_assert!(func_ctx.is_empty());
201 Self {
202 func,
203 srcloc: Default::default(),
204 func_ctx,
205 position: Default::default(),
206 }
207 }
208
209 /// Get the block that this builder is currently at.
current_block(&self) -> Option<Block>210 pub fn current_block(&self) -> Option<Block> {
211 self.position.expand()
212 }
213
214 /// Set the source location that should be assigned to all new instructions.
set_srcloc(&mut self, srcloc: ir::SourceLoc)215 pub fn set_srcloc(&mut self, srcloc: ir::SourceLoc) {
216 self.srcloc = srcloc;
217 }
218
219 /// Creates a new `Block` and returns its reference.
create_block(&mut self) -> Block220 pub fn create_block(&mut self) -> Block {
221 let block = self.func.dfg.make_block();
222 self.func_ctx.ssa.declare_block(block);
223 self.func_ctx.blocks[block] = BlockData {
224 filled: false,
225 pristine: true,
226 user_param_count: 0,
227 };
228 block
229 }
230
231 /// Insert `block` in the layout *after* the existing block `after`.
insert_block_after(&mut self, block: Block, after: Block)232 pub fn insert_block_after(&mut self, block: Block, after: Block) {
233 self.func.layout.insert_block_after(block, after);
234 }
235
236 /// After the call to this function, new instructions will be inserted into the designated
237 /// block, in the order they are declared. You must declare the types of the Block arguments
238 /// you will use here.
239 ///
240 /// When inserting the terminator instruction (which doesn't have a fallthrough to its immediate
241 /// successor), the block will be declared filled and it will not be possible to append
242 /// instructions to it.
switch_to_block(&mut self, block: Block)243 pub fn switch_to_block(&mut self, block: Block) {
244 // First we check that the previous block has been filled.
245 debug_assert!(
246 self.position.is_none()
247 || self.is_unreachable()
248 || self.is_pristine()
249 || self.is_filled(),
250 "you have to fill your block before switching"
251 );
252 // We cannot switch to a filled block
253 debug_assert!(
254 !self.func_ctx.blocks[block].filled,
255 "you cannot switch to a block which is already filled"
256 );
257
258 // Then we change the cursor position.
259 self.position = PackedOption::from(block);
260 }
261
262 /// Declares that all the predecessors of this block are known.
263 ///
264 /// Function to call with `block` as soon as the last branch instruction to `block` has been
265 /// created. Forgetting to call this method on every block will cause inconsistencies in the
266 /// produced functions.
seal_block(&mut self, block: Block)267 pub fn seal_block(&mut self, block: Block) {
268 let side_effects = self.func_ctx.ssa.seal_block(block, self.func);
269 self.handle_ssa_side_effects(side_effects);
270 }
271
272 /// Effectively calls seal_block on all unsealed blocks in the function.
273 ///
274 /// It's more efficient to seal `Block`s as soon as possible, during
275 /// translation, but for frontends where this is impractical to do, this
276 /// function can be used at the end of translating all blocks to ensure
277 /// that everything is sealed.
seal_all_blocks(&mut self)278 pub fn seal_all_blocks(&mut self) {
279 let side_effects = self.func_ctx.ssa.seal_all_blocks(self.func);
280 self.handle_ssa_side_effects(side_effects);
281 }
282
283 /// In order to use a variable in a `use_var`, you need to declare its type with this method.
declare_var(&mut self, var: Variable, ty: Type)284 pub fn declare_var(&mut self, var: Variable, ty: Type) {
285 debug_assert_eq!(
286 self.func_ctx.types[var],
287 types::INVALID,
288 "variable {:?} is declared twice",
289 var
290 );
291 self.func_ctx.types[var] = ty;
292 }
293
294 /// Returns the Cranelift IR value corresponding to the utilization at the current program
295 /// position of a previously defined user variable.
use_var(&mut self, var: Variable) -> Value296 pub fn use_var(&mut self, var: Variable) -> Value {
297 let (val, side_effects) = {
298 let ty = *self.func_ctx.types.get(var).unwrap_or_else(|| {
299 panic!(
300 "variable {:?} is used but its type has not been declared",
301 var
302 )
303 });
304 debug_assert_ne!(
305 ty,
306 types::INVALID,
307 "variable {:?} is used but its type has not been declared",
308 var
309 );
310 self.func_ctx
311 .ssa
312 .use_var(self.func, var, ty, self.position.unwrap())
313 };
314 self.handle_ssa_side_effects(side_effects);
315 val
316 }
317
318 /// Register a new definition of a user variable. The type of the value must be
319 /// the same as the type registered for the variable.
def_var(&mut self, var: Variable, val: Value)320 pub fn def_var(&mut self, var: Variable, val: Value) {
321 debug_assert_eq!(
322 *self.func_ctx.types.get(var).unwrap_or_else(|| panic!(
323 "variable {:?} is used but its type has not been declared",
324 var
325 )),
326 self.func.dfg.value_type(val),
327 "declared type of variable {:?} doesn't match type of value {}",
328 var,
329 val
330 );
331
332 self.func_ctx.ssa.def_var(var, val, self.position.unwrap());
333 }
334
335 /// Set label for Value
336 ///
337 /// This will not do anything unless `func.dfg.collect_debug_info` is called first.
set_val_label(&mut self, val: Value, label: ValueLabel)338 pub fn set_val_label(&mut self, val: Value, label: ValueLabel) {
339 if let Some(values_labels) = self.func.dfg.values_labels.as_mut() {
340 use crate::hash_map::Entry;
341
342 let start = ValueLabelStart {
343 from: self.srcloc,
344 label,
345 };
346
347 match values_labels.entry(val) {
348 Entry::Occupied(mut e) => match e.get_mut() {
349 ValueLabelAssignments::Starts(starts) => starts.push(start),
350 _ => panic!("Unexpected ValueLabelAssignments at this stage"),
351 },
352 Entry::Vacant(e) => {
353 e.insert(ValueLabelAssignments::Starts(vec![start]));
354 }
355 }
356 }
357 }
358
359 /// Creates a jump table in the function, to be used by `br_table` instructions.
create_jump_table(&mut self, data: JumpTableData) -> JumpTable360 pub fn create_jump_table(&mut self, data: JumpTableData) -> JumpTable {
361 self.func.create_jump_table(data)
362 }
363
364 /// Creates a stack slot in the function, to be used by `stack_load`, `stack_store` and
365 /// `stack_addr` instructions.
create_stack_slot(&mut self, data: StackSlotData) -> StackSlot366 pub fn create_stack_slot(&mut self, data: StackSlotData) -> StackSlot {
367 self.func.create_stack_slot(data)
368 }
369
370 /// Adds a signature which can later be used to declare an external function import.
import_signature(&mut self, signature: Signature) -> SigRef371 pub fn import_signature(&mut self, signature: Signature) -> SigRef {
372 self.func.import_signature(signature)
373 }
374
375 /// Declare an external function import.
import_function(&mut self, data: ExtFuncData) -> FuncRef376 pub fn import_function(&mut self, data: ExtFuncData) -> FuncRef {
377 self.func.import_function(data)
378 }
379
380 /// Declares a global value accessible to the function.
create_global_value(&mut self, data: GlobalValueData) -> GlobalValue381 pub fn create_global_value(&mut self, data: GlobalValueData) -> GlobalValue {
382 self.func.create_global_value(data)
383 }
384
385 /// Declares a heap accessible to the function.
create_heap(&mut self, data: HeapData) -> Heap386 pub fn create_heap(&mut self, data: HeapData) -> Heap {
387 self.func.create_heap(data)
388 }
389
390 /// Returns an object with the [`InstBuilder`](cranelift_codegen::ir::InstBuilder)
391 /// trait that allows to conveniently append an instruction to the current `Block` being built.
ins<'short>(&'short mut self) -> FuncInstBuilder<'short, 'a>392 pub fn ins<'short>(&'short mut self) -> FuncInstBuilder<'short, 'a> {
393 let block = self
394 .position
395 .expect("Please call switch_to_block before inserting instructions");
396 FuncInstBuilder::new(self, block)
397 }
398
399 /// Make sure that the current block is inserted in the layout.
ensure_inserted_block(&mut self)400 pub fn ensure_inserted_block(&mut self) {
401 let block = self.position.unwrap();
402 if self.func_ctx.blocks[block].pristine {
403 if !self.func.layout.is_block_inserted(block) {
404 self.func.layout.append_block(block);
405 }
406 self.func_ctx.blocks[block].pristine = false;
407 } else {
408 debug_assert!(
409 !self.func_ctx.blocks[block].filled,
410 "you cannot add an instruction to a block already filled"
411 );
412 }
413 }
414
415 /// Returns a `FuncCursor` pointed at the current position ready for inserting instructions.
416 ///
417 /// This can be used to insert SSA code that doesn't need to access locals and that doesn't
418 /// need to know about `FunctionBuilder` at all.
cursor(&mut self) -> FuncCursor419 pub fn cursor(&mut self) -> FuncCursor {
420 self.ensure_inserted_block();
421 FuncCursor::new(self.func)
422 .with_srcloc(self.srcloc)
423 .at_bottom(self.position.unwrap())
424 }
425
426 /// Append parameters to the given `Block` corresponding to the function
427 /// parameters. This can be used to set up the block parameters for the
428 /// entry block.
append_block_params_for_function_params(&mut self, block: Block)429 pub fn append_block_params_for_function_params(&mut self, block: Block) {
430 debug_assert!(
431 !self.func_ctx.ssa.has_any_predecessors(block),
432 "block parameters for function parameters should only be added to the entry block"
433 );
434
435 // These parameters count as "user" parameters here because they aren't
436 // inserted by the SSABuilder.
437 let user_param_count = &mut self.func_ctx.blocks[block].user_param_count;
438 for argtyp in &self.func.signature.params {
439 *user_param_count += 1;
440 self.func.dfg.append_block_param(block, argtyp.value_type);
441 }
442 }
443
444 /// Append parameters to the given `Block` corresponding to the function
445 /// return values. This can be used to set up the block parameters for a
446 /// function exit block.
append_block_params_for_function_returns(&mut self, block: Block)447 pub fn append_block_params_for_function_returns(&mut self, block: Block) {
448 // These parameters count as "user" parameters here because they aren't
449 // inserted by the SSABuilder.
450 let user_param_count = &mut self.func_ctx.blocks[block].user_param_count;
451 for argtyp in &self.func.signature.returns {
452 *user_param_count += 1;
453 self.func.dfg.append_block_param(block, argtyp.value_type);
454 }
455 }
456
457 /// Declare that translation of the current function is complete. This
458 /// resets the state of the `FunctionBuilder` in preparation to be used
459 /// for another function.
finalize(&mut self)460 pub fn finalize(&mut self) {
461 // Check that all the `Block`s are filled and sealed.
462 #[cfg(debug_assertions)]
463 {
464 for (block, block_data) in self.func_ctx.blocks.iter() {
465 assert!(
466 block_data.pristine || self.func_ctx.ssa.is_sealed(block),
467 "FunctionBuilder finalized, but block {} is not sealed",
468 block,
469 );
470 assert!(
471 block_data.pristine || block_data.filled,
472 "FunctionBuilder finalized, but block {} is not filled",
473 block,
474 );
475 }
476 }
477
478 // In debug mode, check that all blocks are valid basic blocks.
479 #[cfg(debug_assertions)]
480 {
481 // Iterate manually to provide more helpful error messages.
482 for block in self.func_ctx.blocks.keys() {
483 if let Err((inst, _msg)) = self.func.is_block_basic(block) {
484 let inst_str = self.func.dfg.display_inst(inst, None);
485 panic!("{} failed basic block invariants on {}", block, inst_str);
486 }
487 }
488 }
489
490 // Clear the state (but preserve the allocated buffers) in preparation
491 // for translation another function.
492 self.func_ctx.clear();
493
494 // Reset srcloc and position to initial states.
495 self.srcloc = Default::default();
496 self.position = Default::default();
497 }
498 }
499
500 /// All the functions documented in the previous block are write-only and help you build a valid
501 /// Cranelift IR functions via multiple debug asserts. However, you might need to improve the
502 /// performance of your translation perform more complex transformations to your Cranelift IR
503 /// function. The functions below help you inspect the function you're creating and modify it
504 /// in ways that can be unsafe if used incorrectly.
505 impl<'a> FunctionBuilder<'a> {
506 /// Retrieves all the parameters for a `Block` currently inferred from the jump instructions
507 /// inserted that target it and the SSA construction.
block_params(&self, block: Block) -> &[Value]508 pub fn block_params(&self, block: Block) -> &[Value] {
509 self.func.dfg.block_params(block)
510 }
511
512 /// Retrieves the signature with reference `sigref` previously added with `import_signature`.
signature(&self, sigref: SigRef) -> Option<&Signature>513 pub fn signature(&self, sigref: SigRef) -> Option<&Signature> {
514 self.func.dfg.signatures.get(sigref)
515 }
516
517 /// Creates a parameter for a specific `Block` by appending it to the list of already existing
518 /// parameters.
519 ///
520 /// **Note:** this function has to be called at the creation of the `Block` before adding
521 /// instructions to it, otherwise this could interfere with SSA construction.
append_block_param(&mut self, block: Block, ty: Type) -> Value522 pub fn append_block_param(&mut self, block: Block, ty: Type) -> Value {
523 debug_assert!(
524 self.func_ctx.blocks[block].pristine,
525 "You can't add block parameters after adding any instruction"
526 );
527 debug_assert_eq!(
528 self.func_ctx.blocks[block].user_param_count,
529 self.func.dfg.num_block_params(block)
530 );
531 self.func_ctx.blocks[block].user_param_count += 1;
532 self.func.dfg.append_block_param(block, ty)
533 }
534
535 /// Returns the result values of an instruction.
inst_results(&self, inst: Inst) -> &[Value]536 pub fn inst_results(&self, inst: Inst) -> &[Value] {
537 self.func.dfg.inst_results(inst)
538 }
539
540 /// Changes the destination of a jump instruction after creation.
541 ///
542 /// **Note:** You are responsible for maintaining the coherence with the arguments of
543 /// other jump instructions.
change_jump_destination(&mut self, inst: Inst, new_dest: Block)544 pub fn change_jump_destination(&mut self, inst: Inst, new_dest: Block) {
545 let old_dest = self.func.dfg[inst]
546 .branch_destination_mut()
547 .expect("you want to change the jump destination of a non-jump instruction");
548 let pred = self.func_ctx.ssa.remove_block_predecessor(*old_dest, inst);
549 *old_dest = new_dest;
550 self.func_ctx
551 .ssa
552 .declare_block_predecessor(new_dest, pred, inst);
553 }
554
555 /// Returns `true` if and only if the current `Block` is sealed and has no predecessors declared.
556 ///
557 /// The entry block of a function is never unreachable.
is_unreachable(&self) -> bool558 pub fn is_unreachable(&self) -> bool {
559 let is_entry = match self.func.layout.entry_block() {
560 None => false,
561 Some(entry) => self.position.unwrap() == entry,
562 };
563 !is_entry
564 && self.func_ctx.ssa.is_sealed(self.position.unwrap())
565 && !self
566 .func_ctx
567 .ssa
568 .has_any_predecessors(self.position.unwrap())
569 }
570
571 /// Returns `true` if and only if no instructions have been added since the last call to
572 /// `switch_to_block`.
is_pristine(&self) -> bool573 pub fn is_pristine(&self) -> bool {
574 self.func_ctx.blocks[self.position.unwrap()].pristine
575 }
576
577 /// Returns `true` if and only if a terminator instruction has been inserted since the
578 /// last call to `switch_to_block`.
is_filled(&self) -> bool579 pub fn is_filled(&self) -> bool {
580 self.func_ctx.blocks[self.position.unwrap()].filled
581 }
582
583 /// Returns a displayable object for the function as it is.
584 ///
585 /// Useful for debug purposes. Use it with `None` for standard printing.
586 // Clippy thinks the lifetime that follows is needless, but rustc needs it
587 #[cfg_attr(feature = "cargo-clippy", allow(clippy::needless_lifetimes))]
display<'b, I: Into<Option<&'b dyn TargetIsa>>>(&'b self, isa: I) -> DisplayFunction588 pub fn display<'b, I: Into<Option<&'b dyn TargetIsa>>>(&'b self, isa: I) -> DisplayFunction {
589 self.func.display(isa)
590 }
591 }
592
593 /// Helper functions
594 impl<'a> FunctionBuilder<'a> {
595 /// Calls libc.memcpy
596 ///
597 /// Copies the `size` bytes from `src` to `dest`, assumes that `src + size`
598 /// won't overlap onto `dest`. If `dest` and `src` overlap, the behavior is
599 /// undefined. Applications in which `dest` and `src` might overlap should
600 /// use `call_memmove` instead.
call_memcpy( &mut self, config: TargetFrontendConfig, dest: Value, src: Value, size: Value, )601 pub fn call_memcpy(
602 &mut self,
603 config: TargetFrontendConfig,
604 dest: Value,
605 src: Value,
606 size: Value,
607 ) {
608 let pointer_type = config.pointer_type();
609 let signature = {
610 let mut s = Signature::new(config.default_call_conv);
611 s.params.push(AbiParam::new(pointer_type));
612 s.params.push(AbiParam::new(pointer_type));
613 s.params.push(AbiParam::new(pointer_type));
614 self.import_signature(s)
615 };
616
617 let libc_memcpy = self.import_function(ExtFuncData {
618 name: ExternalName::LibCall(LibCall::Memcpy),
619 signature,
620 colocated: false,
621 });
622
623 self.ins().call(libc_memcpy, &[dest, src, size]);
624 }
625
626 /// Optimised memcpy or memmove for small copies.
627 ///
628 /// # Codegen safety
629 ///
630 /// The following properties must hold to prevent UB:
631 ///
632 /// * `src_align` and `dest_align` are an upper-bound on the alignment of `src` respectively `dest`.
633 /// * If `non_overlapping` is true, then this must be correct.
emit_small_memory_copy( &mut self, config: TargetFrontendConfig, dest: Value, src: Value, size: u64, dest_align: u8, src_align: u8, non_overlapping: bool, mut flags: MemFlags, )634 pub fn emit_small_memory_copy(
635 &mut self,
636 config: TargetFrontendConfig,
637 dest: Value,
638 src: Value,
639 size: u64,
640 dest_align: u8,
641 src_align: u8,
642 non_overlapping: bool,
643 mut flags: MemFlags,
644 ) {
645 // Currently the result of guess work, not actual profiling.
646 const THRESHOLD: u64 = 4;
647
648 if size == 0 {
649 return;
650 }
651
652 let access_size = greatest_divisible_power_of_two(size);
653 assert!(
654 access_size.is_power_of_two(),
655 "`size` is not a power of two"
656 );
657 assert!(
658 access_size >= u64::from(::core::cmp::min(src_align, dest_align)),
659 "`size` is smaller than `dest` and `src`'s alignment value."
660 );
661
662 let (access_size, int_type) = if access_size <= 8 {
663 (access_size, Type::int((access_size * 8) as u16).unwrap())
664 } else {
665 (8, types::I64)
666 };
667
668 let load_and_store_amount = size / access_size;
669
670 if load_and_store_amount > THRESHOLD {
671 let size_value = self.ins().iconst(config.pointer_type(), size as i64);
672 if non_overlapping {
673 self.call_memcpy(config, dest, src, size_value);
674 } else {
675 self.call_memmove(config, dest, src, size_value);
676 }
677 return;
678 }
679
680 flags.set_aligned();
681
682 // Load all of the memory first. This is necessary in case `dest` overlaps.
683 // It can also improve performance a bit.
684 let registers: smallvec::SmallVec<[_; THRESHOLD as usize]> = (0..load_and_store_amount)
685 .map(|i| {
686 let offset = (access_size * i) as i32;
687 (self.ins().load(int_type, flags, src, offset), offset)
688 })
689 .collect();
690
691 for (value, offset) in registers {
692 self.ins().store(flags, value, dest, offset);
693 }
694 }
695
696 /// Calls libc.memset
697 ///
698 /// Writes `size` bytes of i8 value `ch` to memory starting at `buffer`.
call_memset( &mut self, config: TargetFrontendConfig, buffer: Value, ch: Value, size: Value, )699 pub fn call_memset(
700 &mut self,
701 config: TargetFrontendConfig,
702 buffer: Value,
703 ch: Value,
704 size: Value,
705 ) {
706 let pointer_type = config.pointer_type();
707 let signature = {
708 let mut s = Signature::new(config.default_call_conv);
709 s.params.push(AbiParam::new(pointer_type));
710 s.params.push(AbiParam::new(types::I32));
711 s.params.push(AbiParam::new(pointer_type));
712 self.import_signature(s)
713 };
714
715 let libc_memset = self.import_function(ExtFuncData {
716 name: ExternalName::LibCall(LibCall::Memset),
717 signature,
718 colocated: false,
719 });
720
721 let ch = self.ins().uextend(types::I32, ch);
722 self.ins().call(libc_memset, &[buffer, ch, size]);
723 }
724
725 /// Calls libc.memset
726 ///
727 /// Writes `size` bytes of value `ch` to memory starting at `buffer`.
emit_small_memset( &mut self, config: TargetFrontendConfig, buffer: Value, ch: u8, size: u64, buffer_align: u8, mut flags: MemFlags, )728 pub fn emit_small_memset(
729 &mut self,
730 config: TargetFrontendConfig,
731 buffer: Value,
732 ch: u8,
733 size: u64,
734 buffer_align: u8,
735 mut flags: MemFlags,
736 ) {
737 // Currently the result of guess work, not actual profiling.
738 const THRESHOLD: u64 = 4;
739
740 if size == 0 {
741 return;
742 }
743
744 let access_size = greatest_divisible_power_of_two(size);
745 assert!(
746 access_size.is_power_of_two(),
747 "`size` is not a power of two"
748 );
749 assert!(
750 access_size >= u64::from(buffer_align),
751 "`size` is smaller than `dest` and `src`'s alignment value."
752 );
753
754 let (access_size, int_type) = if access_size <= 8 {
755 (access_size, Type::int((access_size * 8) as u16).unwrap())
756 } else {
757 (8, types::I64)
758 };
759
760 let load_and_store_amount = size / access_size;
761
762 if load_and_store_amount > THRESHOLD {
763 let ch = self.ins().iconst(types::I8, i64::from(ch));
764 let size = self.ins().iconst(config.pointer_type(), size as i64);
765 self.call_memset(config, buffer, ch, size);
766 } else {
767 flags.set_aligned();
768
769 let ch = u64::from(ch);
770 let raw_value = if int_type == types::I64 {
771 ch * 0x0101010101010101_u64
772 } else if int_type == types::I32 {
773 ch * 0x01010101_u64
774 } else if int_type == types::I16 {
775 (ch << 8) | ch
776 } else {
777 assert_eq!(int_type, types::I8);
778 ch
779 };
780
781 let value = self.ins().iconst(int_type, raw_value as i64);
782 for i in 0..load_and_store_amount {
783 let offset = (access_size * i) as i32;
784 self.ins().store(flags, value, buffer, offset);
785 }
786 }
787 }
788
789 /// Calls libc.memmove
790 ///
791 /// Copies `size` bytes from memory starting at `source` to memory starting
792 /// at `dest`. `source` is always read before writing to `dest`.
call_memmove( &mut self, config: TargetFrontendConfig, dest: Value, source: Value, size: Value, )793 pub fn call_memmove(
794 &mut self,
795 config: TargetFrontendConfig,
796 dest: Value,
797 source: Value,
798 size: Value,
799 ) {
800 let pointer_type = config.pointer_type();
801 let signature = {
802 let mut s = Signature::new(config.default_call_conv);
803 s.params.push(AbiParam::new(pointer_type));
804 s.params.push(AbiParam::new(pointer_type));
805 s.params.push(AbiParam::new(pointer_type));
806 self.import_signature(s)
807 };
808
809 let libc_memmove = self.import_function(ExtFuncData {
810 name: ExternalName::LibCall(LibCall::Memmove),
811 signature,
812 colocated: false,
813 });
814
815 self.ins().call(libc_memmove, &[dest, source, size]);
816 }
817 }
818
greatest_divisible_power_of_two(size: u64) -> u64819 fn greatest_divisible_power_of_two(size: u64) -> u64 {
820 (size as i64 & -(size as i64)) as u64
821 }
822
823 // Helper functions
824 impl<'a> FunctionBuilder<'a> {
825 /// A Block is 'filled' when a terminator instruction is present.
fill_current_block(&mut self)826 fn fill_current_block(&mut self) {
827 self.func_ctx.blocks[self.position.unwrap()].filled = true;
828 }
829
declare_successor(&mut self, dest_block: Block, jump_inst: Inst)830 fn declare_successor(&mut self, dest_block: Block, jump_inst: Inst) {
831 self.func_ctx
832 .ssa
833 .declare_block_predecessor(dest_block, self.position.unwrap(), jump_inst);
834 }
835
handle_ssa_side_effects(&mut self, side_effects: SideEffects)836 fn handle_ssa_side_effects(&mut self, side_effects: SideEffects) {
837 for split_block in side_effects.split_blocks_created {
838 self.func_ctx.blocks[split_block].filled = true
839 }
840 for modified_block in side_effects.instructions_added_to_blocks {
841 self.func_ctx.blocks[modified_block].pristine = false
842 }
843 }
844 }
845
846 #[cfg(test)]
847 mod tests {
848 use super::greatest_divisible_power_of_two;
849 use crate::frontend::{FunctionBuilder, FunctionBuilderContext};
850 use crate::Variable;
851 use alloc::string::ToString;
852 use cranelift_codegen::entity::EntityRef;
853 use cranelift_codegen::ir::types::*;
854 use cranelift_codegen::ir::{
855 AbiParam, ExternalName, Function, InstBuilder, MemFlags, Signature,
856 };
857 use cranelift_codegen::isa::{CallConv, TargetFrontendConfig};
858 use cranelift_codegen::settings;
859 use cranelift_codegen::verifier::verify_function;
860 use target_lexicon::PointerWidth;
861
sample_function(lazy_seal: bool)862 fn sample_function(lazy_seal: bool) {
863 let mut sig = Signature::new(CallConv::SystemV);
864 sig.returns.push(AbiParam::new(I32));
865 sig.params.push(AbiParam::new(I32));
866
867 let mut fn_ctx = FunctionBuilderContext::new();
868 let mut func = Function::with_name_signature(ExternalName::testcase("sample"), sig);
869 {
870 let mut builder = FunctionBuilder::new(&mut func, &mut fn_ctx);
871
872 let block0 = builder.create_block();
873 let block1 = builder.create_block();
874 let block2 = builder.create_block();
875 let block3 = builder.create_block();
876 let x = Variable::new(0);
877 let y = Variable::new(1);
878 let z = Variable::new(2);
879 builder.declare_var(x, I32);
880 builder.declare_var(y, I32);
881 builder.declare_var(z, I32);
882 builder.append_block_params_for_function_params(block0);
883
884 builder.switch_to_block(block0);
885 if !lazy_seal {
886 builder.seal_block(block0);
887 }
888 {
889 let tmp = builder.block_params(block0)[0]; // the first function parameter
890 builder.def_var(x, tmp);
891 }
892 {
893 let tmp = builder.ins().iconst(I32, 2);
894 builder.def_var(y, tmp);
895 }
896 {
897 let arg1 = builder.use_var(x);
898 let arg2 = builder.use_var(y);
899 let tmp = builder.ins().iadd(arg1, arg2);
900 builder.def_var(z, tmp);
901 }
902 builder.ins().jump(block1, &[]);
903
904 builder.switch_to_block(block1);
905 {
906 let arg1 = builder.use_var(y);
907 let arg2 = builder.use_var(z);
908 let tmp = builder.ins().iadd(arg1, arg2);
909 builder.def_var(z, tmp);
910 }
911 {
912 let arg = builder.use_var(y);
913 builder.ins().brnz(arg, block3, &[]);
914 }
915 builder.ins().jump(block2, &[]);
916
917 builder.switch_to_block(block2);
918 if !lazy_seal {
919 builder.seal_block(block2);
920 }
921 {
922 let arg1 = builder.use_var(z);
923 let arg2 = builder.use_var(x);
924 let tmp = builder.ins().isub(arg1, arg2);
925 builder.def_var(z, tmp);
926 }
927 {
928 let arg = builder.use_var(y);
929 builder.ins().return_(&[arg]);
930 }
931
932 builder.switch_to_block(block3);
933 if !lazy_seal {
934 builder.seal_block(block3);
935 }
936
937 {
938 let arg1 = builder.use_var(y);
939 let arg2 = builder.use_var(x);
940 let tmp = builder.ins().isub(arg1, arg2);
941 builder.def_var(y, tmp);
942 }
943 builder.ins().jump(block1, &[]);
944 if !lazy_seal {
945 builder.seal_block(block1);
946 }
947
948 if lazy_seal {
949 builder.seal_all_blocks();
950 }
951
952 builder.finalize();
953 }
954
955 let flags = settings::Flags::new(settings::builder());
956 // println!("{}", func.display(None));
957 if let Err(errors) = verify_function(&func, &flags) {
958 panic!("{}\n{}", func.display(None), errors)
959 }
960 }
961
962 #[test]
sample()963 fn sample() {
964 sample_function(false)
965 }
966
967 #[test]
sample_with_lazy_seal()968 fn sample_with_lazy_seal() {
969 sample_function(true)
970 }
971
972 /// Helper function to construct a fixed frontend configuration.
systemv_frontend_config() -> TargetFrontendConfig973 fn systemv_frontend_config() -> TargetFrontendConfig {
974 TargetFrontendConfig {
975 default_call_conv: CallConv::SystemV,
976 pointer_width: PointerWidth::U64,
977 }
978 }
979
980 #[test]
memcpy()981 fn memcpy() {
982 let frontend_config = systemv_frontend_config();
983 let mut sig = Signature::new(frontend_config.default_call_conv);
984 sig.returns.push(AbiParam::new(I32));
985
986 let mut fn_ctx = FunctionBuilderContext::new();
987 let mut func = Function::with_name_signature(ExternalName::testcase("sample"), sig);
988 {
989 let mut builder = FunctionBuilder::new(&mut func, &mut fn_ctx);
990
991 let block0 = builder.create_block();
992 let x = Variable::new(0);
993 let y = Variable::new(1);
994 let z = Variable::new(2);
995 builder.declare_var(x, frontend_config.pointer_type());
996 builder.declare_var(y, frontend_config.pointer_type());
997 builder.declare_var(z, I32);
998 builder.append_block_params_for_function_params(block0);
999 builder.switch_to_block(block0);
1000
1001 let src = builder.use_var(x);
1002 let dest = builder.use_var(y);
1003 let size = builder.use_var(y);
1004 builder.call_memcpy(frontend_config, dest, src, size);
1005 builder.ins().return_(&[size]);
1006
1007 builder.seal_all_blocks();
1008 builder.finalize();
1009 }
1010
1011 assert_eq!(
1012 func.display(None).to_string(),
1013 "function %sample() -> i32 system_v {
1014 sig0 = (i64, i64, i64) system_v
1015 fn0 = %Memcpy sig0
1016
1017 block0:
1018 v3 = iconst.i64 0
1019 v1 -> v3
1020 v2 = iconst.i64 0
1021 v0 -> v2
1022 call fn0(v1, v0, v1)
1023 return v1
1024 }
1025 "
1026 );
1027 }
1028
1029 #[test]
small_memcpy()1030 fn small_memcpy() {
1031 let frontend_config = systemv_frontend_config();
1032 let mut sig = Signature::new(frontend_config.default_call_conv);
1033 sig.returns.push(AbiParam::new(I32));
1034
1035 let mut fn_ctx = FunctionBuilderContext::new();
1036 let mut func = Function::with_name_signature(ExternalName::testcase("sample"), sig);
1037 {
1038 let mut builder = FunctionBuilder::new(&mut func, &mut fn_ctx);
1039
1040 let block0 = builder.create_block();
1041 let x = Variable::new(0);
1042 let y = Variable::new(16);
1043 builder.declare_var(x, frontend_config.pointer_type());
1044 builder.declare_var(y, frontend_config.pointer_type());
1045 builder.append_block_params_for_function_params(block0);
1046 builder.switch_to_block(block0);
1047
1048 let src = builder.use_var(x);
1049 let dest = builder.use_var(y);
1050 let size = 8;
1051 builder.emit_small_memory_copy(
1052 frontend_config,
1053 dest,
1054 src,
1055 size,
1056 8,
1057 8,
1058 true,
1059 MemFlags::new(),
1060 );
1061 builder.ins().return_(&[dest]);
1062
1063 builder.seal_all_blocks();
1064 builder.finalize();
1065 }
1066
1067 assert_eq!(
1068 func.display(None).to_string(),
1069 "function %sample() -> i32 system_v {
1070 block0:
1071 v4 = iconst.i64 0
1072 v1 -> v4
1073 v3 = iconst.i64 0
1074 v0 -> v3
1075 v2 = load.i64 aligned v0
1076 store aligned v2, v1
1077 return v1
1078 }
1079 "
1080 );
1081 }
1082
1083 #[test]
not_so_small_memcpy()1084 fn not_so_small_memcpy() {
1085 let frontend_config = systemv_frontend_config();
1086 let mut sig = Signature::new(frontend_config.default_call_conv);
1087 sig.returns.push(AbiParam::new(I32));
1088
1089 let mut fn_ctx = FunctionBuilderContext::new();
1090 let mut func = Function::with_name_signature(ExternalName::testcase("sample"), sig);
1091 {
1092 let mut builder = FunctionBuilder::new(&mut func, &mut fn_ctx);
1093
1094 let block0 = builder.create_block();
1095 let x = Variable::new(0);
1096 let y = Variable::new(16);
1097 builder.declare_var(x, frontend_config.pointer_type());
1098 builder.declare_var(y, frontend_config.pointer_type());
1099 builder.append_block_params_for_function_params(block0);
1100 builder.switch_to_block(block0);
1101
1102 let src = builder.use_var(x);
1103 let dest = builder.use_var(y);
1104 let size = 8192;
1105 builder.emit_small_memory_copy(
1106 frontend_config,
1107 dest,
1108 src,
1109 size,
1110 8,
1111 8,
1112 true,
1113 MemFlags::new(),
1114 );
1115 builder.ins().return_(&[dest]);
1116
1117 builder.seal_all_blocks();
1118 builder.finalize();
1119 }
1120
1121 assert_eq!(
1122 func.display(None).to_string(),
1123 "function %sample() -> i32 system_v {
1124 sig0 = (i64, i64, i64) system_v
1125 fn0 = %Memcpy sig0
1126
1127 block0:
1128 v4 = iconst.i64 0
1129 v1 -> v4
1130 v3 = iconst.i64 0
1131 v0 -> v3
1132 v2 = iconst.i64 8192
1133 call fn0(v1, v0, v2)
1134 return v1
1135 }
1136 "
1137 );
1138 }
1139
1140 #[test]
small_memset()1141 fn small_memset() {
1142 let frontend_config = systemv_frontend_config();
1143 let mut sig = Signature::new(frontend_config.default_call_conv);
1144 sig.returns.push(AbiParam::new(I32));
1145
1146 let mut fn_ctx = FunctionBuilderContext::new();
1147 let mut func = Function::with_name_signature(ExternalName::testcase("sample"), sig);
1148 {
1149 let mut builder = FunctionBuilder::new(&mut func, &mut fn_ctx);
1150
1151 let block0 = builder.create_block();
1152 let y = Variable::new(16);
1153 builder.declare_var(y, frontend_config.pointer_type());
1154 builder.append_block_params_for_function_params(block0);
1155 builder.switch_to_block(block0);
1156
1157 let dest = builder.use_var(y);
1158 let size = 8;
1159 builder.emit_small_memset(frontend_config, dest, 1, size, 8, MemFlags::new());
1160 builder.ins().return_(&[dest]);
1161
1162 builder.seal_all_blocks();
1163 builder.finalize();
1164 }
1165
1166 assert_eq!(
1167 func.display(None).to_string(),
1168 "function %sample() -> i32 system_v {
1169 block0:
1170 v2 = iconst.i64 0
1171 v0 -> v2
1172 v1 = iconst.i64 0x0101_0101_0101_0101
1173 store aligned v1, v0
1174 return v0
1175 }
1176 "
1177 );
1178 }
1179
1180 #[test]
not_so_small_memset()1181 fn not_so_small_memset() {
1182 let frontend_config = systemv_frontend_config();
1183 let mut sig = Signature::new(frontend_config.default_call_conv);
1184 sig.returns.push(AbiParam::new(I32));
1185
1186 let mut fn_ctx = FunctionBuilderContext::new();
1187 let mut func = Function::with_name_signature(ExternalName::testcase("sample"), sig);
1188 {
1189 let mut builder = FunctionBuilder::new(&mut func, &mut fn_ctx);
1190
1191 let block0 = builder.create_block();
1192 let y = Variable::new(16);
1193 builder.declare_var(y, frontend_config.pointer_type());
1194 builder.append_block_params_for_function_params(block0);
1195 builder.switch_to_block(block0);
1196
1197 let dest = builder.use_var(y);
1198 let size = 8192;
1199 builder.emit_small_memset(frontend_config, dest, 1, size, 8, MemFlags::new());
1200 builder.ins().return_(&[dest]);
1201
1202 builder.seal_all_blocks();
1203 builder.finalize();
1204 }
1205
1206 assert_eq!(
1207 func.display(None).to_string(),
1208 "function %sample() -> i32 system_v {
1209 sig0 = (i64, i32, i64) system_v
1210 fn0 = %Memset sig0
1211
1212 block0:
1213 v4 = iconst.i64 0
1214 v0 -> v4
1215 v1 = iconst.i8 1
1216 v2 = iconst.i64 8192
1217 v3 = uextend.i32 v1
1218 call fn0(v0, v3, v2)
1219 return v0
1220 }
1221 "
1222 );
1223 }
1224
1225 #[test]
undef_vector_vars()1226 fn undef_vector_vars() {
1227 let mut sig = Signature::new(CallConv::SystemV);
1228 sig.returns.push(AbiParam::new(I8X16));
1229 sig.returns.push(AbiParam::new(B8X16));
1230 sig.returns.push(AbiParam::new(F32X4));
1231
1232 let mut fn_ctx = FunctionBuilderContext::new();
1233 let mut func = Function::with_name_signature(ExternalName::testcase("sample"), sig);
1234 {
1235 let mut builder = FunctionBuilder::new(&mut func, &mut fn_ctx);
1236
1237 let block0 = builder.create_block();
1238 let a = Variable::new(0);
1239 let b = Variable::new(1);
1240 let c = Variable::new(2);
1241 builder.declare_var(a, I8X16);
1242 builder.declare_var(b, B8X16);
1243 builder.declare_var(c, F32X4);
1244 builder.switch_to_block(block0);
1245
1246 let a = builder.use_var(a);
1247 let b = builder.use_var(b);
1248 let c = builder.use_var(c);
1249 builder.ins().return_(&[a, b, c]);
1250
1251 builder.seal_all_blocks();
1252 builder.finalize();
1253 }
1254
1255 assert_eq!(
1256 func.display(None).to_string(),
1257 "function %sample() -> i8x16, b8x16, f32x4 system_v {
1258 const0 = 0x00000000000000000000000000000000
1259
1260 block0:
1261 v5 = f32const 0.0
1262 v6 = splat.f32x4 v5
1263 v2 -> v6
1264 v4 = vconst.b8x16 const0
1265 v1 -> v4
1266 v3 = vconst.i8x16 const0
1267 v0 -> v3
1268 return v0, v1, v2
1269 }
1270 "
1271 );
1272 }
1273
1274 #[test]
test_greatest_divisible_power_of_two()1275 fn test_greatest_divisible_power_of_two() {
1276 assert_eq!(64, greatest_divisible_power_of_two(64));
1277 assert_eq!(16, greatest_divisible_power_of_two(48));
1278 assert_eq!(8, greatest_divisible_power_of_two(24));
1279 assert_eq!(1, greatest_divisible_power_of_two(25));
1280 }
1281 }
1282