1 //! A SSA-building API that handles incomplete CFGs.
2 //!
3 //! The algorithm is based upon Braun M., Buchwald S., Hack S., Leißa R., Mallon C.,
4 //! Zwinkau A. (2013) Simple and Efficient Construction of Static Single Assignment Form.
5 //! In: Jhala R., De Bosschere K. (eds) Compiler Construction. CC 2013.
6 //! Lecture Notes in Computer Science, vol 7791. Springer, Berlin, Heidelberg
7 //!
8 //! <https://link.springer.com/content/pdf/10.1007/978-3-642-37051-9_6.pdf>
9
10 use crate::Variable;
11 use alloc::vec::Vec;
12 use core::convert::TryInto;
13 use core::mem;
14 use cranelift_codegen::cursor::{Cursor, FuncCursor};
15 use cranelift_codegen::entity::SecondaryMap;
16 use cranelift_codegen::ir::immediates::{Ieee32, Ieee64};
17 use cranelift_codegen::ir::instructions::BranchInfo;
18 use cranelift_codegen::ir::types::{F32, F64};
19 use cranelift_codegen::ir::{Block, Function, Inst, InstBuilder, InstructionData, Type, Value};
20 use cranelift_codegen::packed_option::PackedOption;
21 use smallvec::SmallVec;
22
23 /// Structure containing the data relevant the construction of SSA for a given function.
24 ///
25 /// The parameter struct `Variable` corresponds to the way variables are represented in the
26 /// non-SSA language you're translating from.
27 ///
28 /// The SSA building relies on information about the variables used and defined.
29 ///
30 /// This SSA building module allows you to def and use variables on the fly while you are
31 /// constructing the CFG, no need for a separate SSA pass after the CFG is completed.
32 ///
33 /// A basic block is said _filled_ if all the instruction that it contains have been translated,
34 /// and it is said _sealed_ if all of its predecessors have been declared. Only filled predecessors
35 /// can be declared.
36 pub struct SSABuilder {
37 // TODO: Consider a sparse representation rather than SecondaryMap-of-SecondaryMap.
38 /// Records for every variable and for every relevant block, the last definition of
39 /// the variable in the block.
40 variables: SecondaryMap<Variable, SecondaryMap<Block, PackedOption<Value>>>,
41
42 /// Records the position of the basic blocks and the list of values used but not defined in the
43 /// block.
44 ssa_blocks: SecondaryMap<Block, SSABlockData>,
45
46 /// Call stack for use in the `use_var`/`predecessors_lookup` state machine.
47 calls: Vec<Call>,
48 /// Result stack for use in the `use_var`/`predecessors_lookup` state machine.
49 results: Vec<Value>,
50
51 /// Side effects accumulated in the `use_var`/`predecessors_lookup` state machine.
52 side_effects: SideEffects,
53 }
54
55 /// Side effects of a `use_var` or a `seal_block` method call.
56 pub struct SideEffects {
57 /// When we want to append jump arguments to a `br_table` instruction, the critical edge is
58 /// splitted and the newly created `Block`s are signaled here.
59 pub split_blocks_created: Vec<Block>,
60 /// When a variable is used but has never been defined before (this happens in the case of
61 /// unreachable code), a placeholder `iconst` or `fconst` value is added to the right `Block`.
62 /// This field signals if it is the case and return the `Block` to which the initialization has
63 /// been added.
64 pub instructions_added_to_blocks: Vec<Block>,
65 }
66
67 impl SideEffects {
new() -> Self68 fn new() -> Self {
69 Self {
70 split_blocks_created: Vec::new(),
71 instructions_added_to_blocks: Vec::new(),
72 }
73 }
74
is_empty(&self) -> bool75 fn is_empty(&self) -> bool {
76 self.split_blocks_created.is_empty() && self.instructions_added_to_blocks.is_empty()
77 }
78 }
79
80 #[derive(Clone)]
81 struct PredBlock {
82 block: Block,
83 branch: Inst,
84 }
85
86 impl PredBlock {
new(block: Block, branch: Inst) -> Self87 fn new(block: Block, branch: Inst) -> Self {
88 Self { block, branch }
89 }
90 }
91
92 type PredBlockSmallVec = SmallVec<[PredBlock; 4]>;
93
94 #[derive(Clone, Default)]
95 struct SSABlockData {
96 // The predecessors of the Block with the block and branch instruction.
97 predecessors: PredBlockSmallVec,
98 // A block is sealed if all of its predecessors have been declared.
99 sealed: bool,
100 // List of current Block arguments for which an earlier def has not been found yet.
101 undef_variables: Vec<(Variable, Value)>,
102 }
103
104 impl SSABlockData {
add_predecessor(&mut self, pred: Block, inst: Inst)105 fn add_predecessor(&mut self, pred: Block, inst: Inst) {
106 debug_assert!(!self.sealed, "sealed blocks cannot accept new predecessors");
107 self.predecessors.push(PredBlock::new(pred, inst));
108 }
109
remove_predecessor(&mut self, inst: Inst) -> Block110 fn remove_predecessor(&mut self, inst: Inst) -> Block {
111 let pred = self
112 .predecessors
113 .iter()
114 .position(|&PredBlock { branch, .. }| branch == inst)
115 .expect("the predecessor you are trying to remove is not declared");
116 self.predecessors.swap_remove(pred).block
117 }
118 }
119
120 impl SSABuilder {
121 /// Allocate a new blank SSA builder struct. Use the API function to interact with the struct.
new() -> Self122 pub fn new() -> Self {
123 Self {
124 variables: SecondaryMap::with_default(SecondaryMap::new()),
125 ssa_blocks: SecondaryMap::new(),
126 calls: Vec::new(),
127 results: Vec::new(),
128 side_effects: SideEffects::new(),
129 }
130 }
131
132 /// Clears a `SSABuilder` from all its data, letting it in a pristine state without
133 /// deallocating memory.
clear(&mut self)134 pub fn clear(&mut self) {
135 self.variables.clear();
136 self.ssa_blocks.clear();
137 debug_assert!(self.calls.is_empty());
138 debug_assert!(self.results.is_empty());
139 debug_assert!(self.side_effects.is_empty());
140 }
141
142 /// Tests whether an `SSABuilder` is in a cleared state.
is_empty(&self) -> bool143 pub fn is_empty(&self) -> bool {
144 self.variables.is_empty()
145 && self.ssa_blocks.is_empty()
146 && self.calls.is_empty()
147 && self.results.is_empty()
148 && self.side_effects.is_empty()
149 }
150 }
151
152 /// Small enum used for clarity in some functions.
153 #[derive(Debug)]
154 enum ZeroOneOrMore<T> {
155 Zero,
156 One(T),
157 More,
158 }
159
160 /// Cases used internally by `use_var_nonlocal()` for avoiding the borrow checker.
161 #[derive(Debug)]
162 enum UseVarCases {
163 Unsealed(Value),
164 SealedOnePredecessor(Block),
165 SealedMultiplePredecessors(Value, Block),
166 }
167
168 /// States for the `use_var`/`predecessors_lookup` state machine.
169 enum Call {
170 UseVar(Block),
171 FinishSealedOnePredecessor(Block),
172 FinishPredecessorsLookup(Value, Block),
173 }
174
175 /// Emit instructions to produce a zero value in the given type.
emit_zero(ty: Type, mut cur: FuncCursor) -> Value176 fn emit_zero(ty: Type, mut cur: FuncCursor) -> Value {
177 if ty.is_int() {
178 cur.ins().iconst(ty, 0)
179 } else if ty.is_bool() {
180 cur.ins().bconst(ty, false)
181 } else if ty == F32 {
182 cur.ins().f32const(Ieee32::with_bits(0))
183 } else if ty == F64 {
184 cur.ins().f64const(Ieee64::with_bits(0))
185 } else if ty.is_ref() {
186 cur.ins().null(ty)
187 } else if ty.is_vector() {
188 let scalar_ty = ty.lane_type();
189 if scalar_ty.is_int() || scalar_ty.is_bool() {
190 let zero = cur.func.dfg.constants.insert(
191 core::iter::repeat(0)
192 .take(ty.bytes().try_into().unwrap())
193 .collect(),
194 );
195 cur.ins().vconst(ty, zero)
196 } else if scalar_ty == F32 {
197 let scalar = cur.ins().f32const(Ieee32::with_bits(0));
198 cur.ins().splat(ty, scalar)
199 } else if scalar_ty == F64 {
200 let scalar = cur.ins().f64const(Ieee64::with_bits(0));
201 cur.ins().splat(ty, scalar)
202 } else {
203 panic!("unimplemented scalar type: {:?}", ty)
204 }
205 } else {
206 panic!("unimplemented type: {:?}", ty)
207 }
208 }
209
210 /// The following methods are the API of the SSA builder. Here is how it should be used when
211 /// translating to Cranelift IR:
212 ///
213 /// - for each basic block, create a corresponding data for SSA construction with `declare_block`;
214 ///
215 /// - while traversing a basic block and translating instruction, use `def_var` and `use_var`
216 /// to record definitions and uses of variables, these methods will give you the corresponding
217 /// SSA values;
218 ///
219 /// - when all the instructions in a basic block have translated, the block is said _filled_ and
220 /// only then you can add it as a predecessor to other blocks with `declare_block_predecessor`;
221 ///
222 /// - when you have constructed all the predecessor to a basic block,
223 /// call `seal_block` on it with the `Function` that you are building.
224 ///
225 /// This API will give you the correct SSA values to use as arguments of your instructions,
226 /// as well as modify the jump instruction and `Block` parameters to account for the SSA
227 /// Phi functions.
228 ///
229 impl SSABuilder {
230 /// Declares a new definition of a variable in a given basic block.
231 /// The SSA value is passed as an argument because it should be created with
232 /// `ir::DataFlowGraph::append_result`.
def_var(&mut self, var: Variable, val: Value, block: Block)233 pub fn def_var(&mut self, var: Variable, val: Value, block: Block) {
234 self.variables[var][block] = PackedOption::from(val);
235 }
236
237 /// Declares a use of a variable in a given basic block. Returns the SSA value corresponding
238 /// to the current SSA definition of this variable and a list of newly created Blocks that
239 /// are the results of critical edge splitting for `br_table` with arguments.
240 ///
241 /// If the variable has never been defined in this blocks or recursively in its predecessors,
242 /// this method will silently create an initializer with `iconst` or `fconst`. You are
243 /// responsible for making sure that you initialize your variables.
use_var( &mut self, func: &mut Function, var: Variable, ty: Type, block: Block, ) -> (Value, SideEffects)244 pub fn use_var(
245 &mut self,
246 func: &mut Function,
247 var: Variable,
248 ty: Type,
249 block: Block,
250 ) -> (Value, SideEffects) {
251 // First, try Local Value Numbering (Algorithm 1 in the paper).
252 // If the variable already has a known Value in this block, use that.
253 if let Some(var_defs) = self.variables.get(var) {
254 if let Some(val) = var_defs[block].expand() {
255 return (val, SideEffects::new());
256 }
257 }
258
259 // Otherwise, use Global Value Numbering (Algorithm 2 in the paper).
260 // This resolves the Value with respect to its predecessors.
261 debug_assert!(self.calls.is_empty());
262 debug_assert!(self.results.is_empty());
263 debug_assert!(self.side_effects.is_empty());
264
265 // Prepare the 'calls' and 'results' stacks for the state machine.
266 self.use_var_nonlocal(func, var, ty, block);
267
268 let value = self.run_state_machine(func, var, ty);
269 let side_effects = mem::replace(&mut self.side_effects, SideEffects::new());
270
271 (value, side_effects)
272 }
273
274 /// Resolve the minimal SSA Value of `var` in `block` by traversing predecessors.
275 ///
276 /// This function sets up state for `run_state_machine()` but does not execute it.
use_var_nonlocal(&mut self, func: &mut Function, var: Variable, ty: Type, block: Block)277 fn use_var_nonlocal(&mut self, func: &mut Function, var: Variable, ty: Type, block: Block) {
278 // This function is split into two parts to appease the borrow checker.
279 // Part 1: With a mutable borrow of self, update the DataFlowGraph if necessary.
280 let data = &mut self.ssa_blocks[block];
281 let case = if data.sealed {
282 // The block has multiple predecessors so we append a Block parameter that
283 // will serve as a value.
284 if data.predecessors.len() == 1 {
285 // Optimize the common case of one predecessor: no param needed.
286 UseVarCases::SealedOnePredecessor(data.predecessors[0].block)
287 } else {
288 // Break potential cycles by eagerly adding an operandless param.
289 let val = func.dfg.append_block_param(block, ty);
290 UseVarCases::SealedMultiplePredecessors(val, block)
291 }
292 } else {
293 let val = func.dfg.append_block_param(block, ty);
294 data.undef_variables.push((var, val));
295 UseVarCases::Unsealed(val)
296 };
297
298 // Part 2: Prepare SSABuilder state for run_state_machine().
299 match case {
300 UseVarCases::SealedOnePredecessor(pred) => {
301 // Get the Value directly from the single predecessor.
302 self.calls.push(Call::FinishSealedOnePredecessor(block));
303 self.calls.push(Call::UseVar(pred));
304 }
305 UseVarCases::Unsealed(val) => {
306 // Define the operandless param added above to prevent lookup cycles.
307 self.def_var(var, val, block);
308
309 // Nothing more can be known at this point.
310 self.results.push(val);
311 }
312 UseVarCases::SealedMultiplePredecessors(val, block) => {
313 // Define the operandless param added above to prevent lookup cycles.
314 self.def_var(var, val, block);
315
316 // Look up a use_var for each precessor.
317 self.begin_predecessors_lookup(val, block);
318 }
319 }
320 }
321
322 /// For blocks with a single predecessor, once we've determined the value,
323 /// record a local def for it for future queries to find.
finish_sealed_one_predecessor(&mut self, var: Variable, block: Block)324 fn finish_sealed_one_predecessor(&mut self, var: Variable, block: Block) {
325 let val = *self.results.last().unwrap();
326 self.def_var(var, val, block);
327 }
328
329 /// Declares a new basic block to construct corresponding data for SSA construction.
330 /// No predecessors are declared here and the block is not sealed.
331 /// Predecessors have to be added with `declare_block_predecessor`.
declare_block(&mut self, block: Block)332 pub fn declare_block(&mut self, block: Block) {
333 self.ssa_blocks[block] = SSABlockData {
334 predecessors: PredBlockSmallVec::new(),
335 sealed: false,
336 undef_variables: Vec::new(),
337 };
338 }
339
340 /// Declares a new predecessor for a `Block` and record the branch instruction
341 /// of the predecessor that leads to it.
342 ///
343 /// The precedent `Block` must be filled before added as predecessor.
344 /// Note that you must provide no jump arguments to the branch
345 /// instruction when you create it since `SSABuilder` will fill them for you.
346 ///
347 /// Callers are expected to avoid adding the same predecessor more than once in the case
348 /// of a jump table.
declare_block_predecessor(&mut self, block: Block, pred: Block, inst: Inst)349 pub fn declare_block_predecessor(&mut self, block: Block, pred: Block, inst: Inst) {
350 debug_assert!(!self.is_sealed(block));
351 self.ssa_blocks[block].add_predecessor(pred, inst)
352 }
353
354 /// Remove a previously declared Block predecessor by giving a reference to the jump
355 /// instruction. Returns the basic block containing the instruction.
356 ///
357 /// Note: use only when you know what you are doing, this might break the SSA building problem
remove_block_predecessor(&mut self, block: Block, inst: Inst) -> Block358 pub fn remove_block_predecessor(&mut self, block: Block, inst: Inst) -> Block {
359 debug_assert!(!self.is_sealed(block));
360 self.ssa_blocks[block].remove_predecessor(inst)
361 }
362
363 /// Completes the global value numbering for a `Block`, all of its predecessors having been
364 /// already sealed.
365 ///
366 /// This method modifies the function's `Layout` by adding arguments to the `Block`s to
367 /// take into account the Phi function placed by the SSA algorithm.
368 ///
369 /// Returns the list of newly created blocks for critical edge splitting.
seal_block(&mut self, block: Block, func: &mut Function) -> SideEffects370 pub fn seal_block(&mut self, block: Block, func: &mut Function) -> SideEffects {
371 self.seal_one_block(block, func);
372 mem::replace(&mut self.side_effects, SideEffects::new())
373 }
374
375 /// Completes the global value numbering for all unsealed `Block`s in `func`.
376 ///
377 /// It's more efficient to seal `Block`s as soon as possible, during
378 /// translation, but for frontends where this is impractical to do, this
379 /// function can be used at the end of translating all blocks to ensure
380 /// that everything is sealed.
seal_all_blocks(&mut self, func: &mut Function) -> SideEffects381 pub fn seal_all_blocks(&mut self, func: &mut Function) -> SideEffects {
382 // Seal all `Block`s currently in the function. This can entail splitting
383 // and creation of new blocks, however such new blocks are sealed on
384 // the fly, so we don't need to account for them here.
385 for block in self.ssa_blocks.keys() {
386 if !self.is_sealed(block) {
387 self.seal_one_block(block, func);
388 }
389 }
390 mem::replace(&mut self.side_effects, SideEffects::new())
391 }
392
393 /// Helper function for `seal_block` and
394 /// `seal_all_blocks`.
seal_one_block(&mut self, block: Block, func: &mut Function)395 fn seal_one_block(&mut self, block: Block, func: &mut Function) {
396 let block_data = &mut self.ssa_blocks[block];
397 debug_assert!(
398 !block_data.sealed,
399 "Attempting to seal {} which is already sealed.",
400 block
401 );
402
403 // Extract the undef_variables data from the block so that we
404 // can iterate over it without borrowing the whole builder.
405 let undef_vars = mem::replace(&mut block_data.undef_variables, Vec::new());
406
407 // For each undef var we look up values in the predecessors and create a block parameter
408 // only if necessary.
409 for (var, val) in undef_vars {
410 let ty = func.dfg.value_type(val);
411 self.predecessors_lookup(func, val, var, ty, block);
412 }
413 self.mark_block_sealed(block);
414 }
415
416 /// Set the `sealed` flag for `block`.
mark_block_sealed(&mut self, block: Block)417 fn mark_block_sealed(&mut self, block: Block) {
418 // Then we mark the block as sealed.
419 let block_data = &mut self.ssa_blocks[block];
420 debug_assert!(!block_data.sealed);
421 debug_assert!(block_data.undef_variables.is_empty());
422 block_data.sealed = true;
423
424 // We could call data.predecessors.shrink_to_fit() here, if
425 // important, because no further predecessors will be added
426 // to this block.
427 }
428
429 /// Given the local SSA Value of a Variable in a Block, perform a recursive lookup on
430 /// predecessors to determine if it is redundant with another Value earlier in the CFG.
431 ///
432 /// If such a Value exists and is redundant, the local Value is replaced by the
433 /// corresponding non-local Value. If the original Value was a Block parameter,
434 /// the parameter may be removed if redundant. Parameters are placed eagerly by callers
435 /// to avoid infinite loops when looking up a Value for a Block that is in a CFG loop.
436 ///
437 /// Doing this lookup for each Value in each Block preserves SSA form during construction.
438 ///
439 /// Returns the chosen Value.
440 ///
441 /// ## Arguments
442 ///
443 /// `sentinel` is a dummy Block parameter inserted by `use_var_nonlocal()`.
444 /// Its purpose is to allow detection of CFG cycles while traversing predecessors.
445 ///
446 /// The `sentinel: Value` and the `ty: Type` are describing the `var: Variable`
447 /// that is being looked up.
predecessors_lookup( &mut self, func: &mut Function, sentinel: Value, var: Variable, ty: Type, block: Block, ) -> Value448 fn predecessors_lookup(
449 &mut self,
450 func: &mut Function,
451 sentinel: Value,
452 var: Variable,
453 ty: Type,
454 block: Block,
455 ) -> Value {
456 debug_assert!(self.calls.is_empty());
457 debug_assert!(self.results.is_empty());
458 // self.side_effects may be non-empty here so that callers can
459 // accumulate side effects over multiple calls.
460 self.begin_predecessors_lookup(sentinel, block);
461 self.run_state_machine(func, var, ty)
462 }
463
464 /// Set up state for `run_state_machine()` to initiate non-local use lookups
465 /// in all predecessors of `dest_block`, and arrange for a call to
466 /// `finish_predecessors_lookup` once they complete.
begin_predecessors_lookup(&mut self, sentinel: Value, dest_block: Block)467 fn begin_predecessors_lookup(&mut self, sentinel: Value, dest_block: Block) {
468 self.calls
469 .push(Call::FinishPredecessorsLookup(sentinel, dest_block));
470 // Iterate over the predecessors.
471 let mut calls = mem::replace(&mut self.calls, Vec::new());
472 calls.extend(
473 self.predecessors(dest_block)
474 .iter()
475 .rev()
476 .map(|&PredBlock { block: pred, .. }| Call::UseVar(pred)),
477 );
478 self.calls = calls;
479 }
480
481 /// Examine the values from the predecessors and compute a result value, creating
482 /// block parameters as needed.
finish_predecessors_lookup( &mut self, func: &mut Function, sentinel: Value, var: Variable, dest_block: Block, )483 fn finish_predecessors_lookup(
484 &mut self,
485 func: &mut Function,
486 sentinel: Value,
487 var: Variable,
488 dest_block: Block,
489 ) {
490 let mut pred_values: ZeroOneOrMore<Value> = ZeroOneOrMore::Zero;
491
492 // Determine how many predecessors are yielding unique, non-temporary Values.
493 let num_predecessors = self.predecessors(dest_block).len();
494 for &pred_val in self.results.iter().rev().take(num_predecessors) {
495 match pred_values {
496 ZeroOneOrMore::Zero => {
497 if pred_val != sentinel {
498 pred_values = ZeroOneOrMore::One(pred_val);
499 }
500 }
501 ZeroOneOrMore::One(old_val) => {
502 if pred_val != sentinel && pred_val != old_val {
503 pred_values = ZeroOneOrMore::More;
504 break;
505 }
506 }
507 ZeroOneOrMore::More => {
508 break;
509 }
510 }
511 }
512
513 // Those predecessors' Values have been examined: pop all their results.
514 self.results.truncate(self.results.len() - num_predecessors);
515
516 let result_val = match pred_values {
517 ZeroOneOrMore::Zero => {
518 // The variable is used but never defined before. This is an irregularity in the
519 // code, but rather than throwing an error we silently initialize the variable to
520 // 0. This will have no effect since this situation happens in unreachable code.
521 if !func.layout.is_block_inserted(dest_block) {
522 func.layout.append_block(dest_block);
523 }
524 self.side_effects
525 .instructions_added_to_blocks
526 .push(dest_block);
527 let zero = emit_zero(
528 func.dfg.value_type(sentinel),
529 FuncCursor::new(func).at_first_insertion_point(dest_block),
530 );
531 func.dfg.remove_block_param(sentinel);
532 func.dfg.change_to_alias(sentinel, zero);
533 zero
534 }
535 ZeroOneOrMore::One(pred_val) => {
536 // Here all the predecessors use a single value to represent our variable
537 // so we don't need to have it as a block argument.
538 // We need to replace all the occurrences of val with pred_val but since
539 // we can't afford a re-writing pass right now we just declare an alias.
540 // Resolve aliases eagerly so that we can check for cyclic aliasing,
541 // which can occur in unreachable code.
542 let mut resolved = func.dfg.resolve_aliases(pred_val);
543 if sentinel == resolved {
544 // Cycle detected. Break it by creating a zero value.
545 resolved = emit_zero(
546 func.dfg.value_type(sentinel),
547 FuncCursor::new(func).at_first_insertion_point(dest_block),
548 );
549 }
550 func.dfg.remove_block_param(sentinel);
551 func.dfg.change_to_alias(sentinel, resolved);
552 resolved
553 }
554 ZeroOneOrMore::More => {
555 // There is disagreement in the predecessors on which value to use so we have
556 // to keep the block argument. To avoid borrowing `self` for the whole loop,
557 // temporarily detach the predecessors list and replace it with an empty list.
558 let mut preds =
559 mem::replace(self.predecessors_mut(dest_block), PredBlockSmallVec::new());
560 for &mut PredBlock {
561 block: ref mut pred_block,
562 branch: ref mut last_inst,
563 } in &mut preds
564 {
565 // We already did a full `use_var` above, so we can do just the fast path.
566 let ssa_block_map = self.variables.get(var).unwrap();
567 let pred_val = ssa_block_map.get(*pred_block).unwrap().unwrap();
568 let jump_arg = self.append_jump_argument(
569 func,
570 *last_inst,
571 *pred_block,
572 dest_block,
573 pred_val,
574 var,
575 );
576 if let Some((middle_block, middle_jump_inst)) = jump_arg {
577 *pred_block = middle_block;
578 *last_inst = middle_jump_inst;
579 self.side_effects.split_blocks_created.push(middle_block);
580 }
581 }
582 // Now that we're done, move the predecessors list back.
583 debug_assert!(self.predecessors(dest_block).is_empty());
584 *self.predecessors_mut(dest_block) = preds;
585
586 sentinel
587 }
588 };
589
590 self.results.push(result_val);
591 }
592
593 /// Appends a jump argument to a jump instruction, returns block created in case of
594 /// critical edge splitting.
append_jump_argument( &mut self, func: &mut Function, jump_inst: Inst, jump_inst_block: Block, dest_block: Block, val: Value, var: Variable, ) -> Option<(Block, Inst)>595 fn append_jump_argument(
596 &mut self,
597 func: &mut Function,
598 jump_inst: Inst,
599 jump_inst_block: Block,
600 dest_block: Block,
601 val: Value,
602 var: Variable,
603 ) -> Option<(Block, Inst)> {
604 match func.dfg.analyze_branch(jump_inst) {
605 BranchInfo::NotABranch => {
606 panic!("you have declared a non-branch instruction as a predecessor to a block");
607 }
608 // For a single destination appending a jump argument to the instruction
609 // is sufficient.
610 BranchInfo::SingleDest(_, _) => {
611 func.dfg.append_inst_arg(jump_inst, val);
612 None
613 }
614 BranchInfo::Table(jt, default_block) => {
615 // In the case of a jump table, the situation is tricky because br_table doesn't
616 // support arguments.
617 // We have to split the critical edge
618 let middle_block = func.dfg.make_block();
619 func.layout.append_block(middle_block);
620 self.declare_block(middle_block);
621 self.ssa_blocks[middle_block].add_predecessor(jump_inst_block, jump_inst);
622 self.mark_block_sealed(middle_block);
623
624 if let Some(default_block) = default_block {
625 if dest_block == default_block {
626 match func.dfg[jump_inst] {
627 InstructionData::BranchTable {
628 destination: ref mut dest,
629 ..
630 } => {
631 *dest = middle_block;
632 }
633 _ => panic!("should not happen"),
634 }
635 }
636 }
637
638 for old_dest in func.jump_tables[jt].as_mut_slice() {
639 if *old_dest == dest_block {
640 *old_dest = middle_block;
641 }
642 }
643 let mut cur = FuncCursor::new(func).at_bottom(middle_block);
644 let middle_jump_inst = cur.ins().jump(dest_block, &[val]);
645 self.def_var(var, val, middle_block);
646 Some((middle_block, middle_jump_inst))
647 }
648 }
649 }
650
651 /// Returns the list of `Block`s that have been declared as predecessors of the argument.
predecessors(&self, block: Block) -> &[PredBlock]652 fn predecessors(&self, block: Block) -> &[PredBlock] {
653 &self.ssa_blocks[block].predecessors
654 }
655
656 /// Returns whether the given Block has any predecessor or not.
has_any_predecessors(&self, block: Block) -> bool657 pub fn has_any_predecessors(&self, block: Block) -> bool {
658 !self.predecessors(block).is_empty()
659 }
660
661 /// Same as predecessors, but for &mut.
predecessors_mut(&mut self, block: Block) -> &mut PredBlockSmallVec662 fn predecessors_mut(&mut self, block: Block) -> &mut PredBlockSmallVec {
663 &mut self.ssa_blocks[block].predecessors
664 }
665
666 /// Returns `true` if and only if `seal_block` has been called on the argument.
is_sealed(&self, block: Block) -> bool667 pub fn is_sealed(&self, block: Block) -> bool {
668 self.ssa_blocks[block].sealed
669 }
670
671 /// The main algorithm is naturally recursive: when there's a `use_var` in a
672 /// block with no corresponding local defs, it recurses and performs a
673 /// `use_var` in each predecessor. To avoid risking running out of callstack
674 /// space, we keep an explicit stack and use a small state machine rather
675 /// than literal recursion.
run_state_machine(&mut self, func: &mut Function, var: Variable, ty: Type) -> Value676 fn run_state_machine(&mut self, func: &mut Function, var: Variable, ty: Type) -> Value {
677 // Process the calls scheduled in `self.calls` until it is empty.
678 while let Some(call) = self.calls.pop() {
679 match call {
680 Call::UseVar(ssa_block) => {
681 // First we lookup for the current definition of the variable in this block
682 if let Some(var_defs) = self.variables.get(var) {
683 if let Some(val) = var_defs[ssa_block].expand() {
684 self.results.push(val);
685 continue;
686 }
687 }
688 self.use_var_nonlocal(func, var, ty, ssa_block);
689 }
690 Call::FinishSealedOnePredecessor(ssa_block) => {
691 self.finish_sealed_one_predecessor(var, ssa_block);
692 }
693 Call::FinishPredecessorsLookup(sentinel, dest_block) => {
694 self.finish_predecessors_lookup(func, sentinel, var, dest_block);
695 }
696 }
697 }
698 debug_assert_eq!(self.results.len(), 1);
699 self.results.pop().unwrap()
700 }
701 }
702
703 #[cfg(test)]
704 mod tests {
705 use crate::ssa::SSABuilder;
706 use crate::Variable;
707 use cranelift_codegen::cursor::{Cursor, FuncCursor};
708 use cranelift_codegen::entity::EntityRef;
709 use cranelift_codegen::ir::instructions::BranchInfo;
710 use cranelift_codegen::ir::types::*;
711 use cranelift_codegen::ir::{Function, Inst, InstBuilder, JumpTableData, Opcode};
712 use cranelift_codegen::settings;
713 use cranelift_codegen::verify_function;
714
715 #[test]
simple_block()716 fn simple_block() {
717 let mut func = Function::new();
718 let mut ssa = SSABuilder::new();
719 let block0 = func.dfg.make_block();
720 // Here is the pseudo-program we want to translate:
721 // block0:
722 // x = 1;
723 // y = 2;
724 // z = x + y;
725 // z = x + z;
726
727 ssa.declare_block(block0);
728 let x_var = Variable::new(0);
729 let x_ssa = {
730 let mut cur = FuncCursor::new(&mut func);
731 cur.insert_block(block0);
732 cur.ins().iconst(I32, 1)
733 };
734 ssa.def_var(x_var, x_ssa, block0);
735 let y_var = Variable::new(1);
736 let y_ssa = {
737 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
738 cur.ins().iconst(I32, 2)
739 };
740 ssa.def_var(y_var, y_ssa, block0);
741 assert_eq!(ssa.use_var(&mut func, x_var, I32, block0).0, x_ssa);
742 assert_eq!(ssa.use_var(&mut func, y_var, I32, block0).0, y_ssa);
743
744 let z_var = Variable::new(2);
745 let x_use1 = ssa.use_var(&mut func, x_var, I32, block0).0;
746 let y_use1 = ssa.use_var(&mut func, y_var, I32, block0).0;
747 let z1_ssa = {
748 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
749 cur.ins().iadd(x_use1, y_use1)
750 };
751 ssa.def_var(z_var, z1_ssa, block0);
752 assert_eq!(ssa.use_var(&mut func, z_var, I32, block0).0, z1_ssa);
753
754 let x_use2 = ssa.use_var(&mut func, x_var, I32, block0).0;
755 let z_use1 = ssa.use_var(&mut func, z_var, I32, block0).0;
756 let z2_ssa = {
757 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
758 cur.ins().iadd(x_use2, z_use1)
759 };
760 ssa.def_var(z_var, z2_ssa, block0);
761 assert_eq!(ssa.use_var(&mut func, z_var, I32, block0).0, z2_ssa);
762 }
763
764 #[test]
sequence_of_blocks()765 fn sequence_of_blocks() {
766 let mut func = Function::new();
767 let mut ssa = SSABuilder::new();
768 let block0 = func.dfg.make_block();
769 let block1 = func.dfg.make_block();
770 let block2 = func.dfg.make_block();
771 // Here is the pseudo-program we want to translate:
772 // block0:
773 // x = 1;
774 // y = 2;
775 // z = x + y;
776 // brnz y, block1;
777 // jump block1;
778 // block1:
779 // z = x + z;
780 // jump block2;
781 // block2:
782 // y = x + y;
783 {
784 let mut cur = FuncCursor::new(&mut func);
785 cur.insert_block(block0);
786 cur.insert_block(block1);
787 cur.insert_block(block2);
788 }
789
790 // block0
791 ssa.declare_block(block0);
792 ssa.seal_block(block0, &mut func);
793 let x_var = Variable::new(0);
794 let x_ssa = {
795 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
796 cur.ins().iconst(I32, 1)
797 };
798 ssa.def_var(x_var, x_ssa, block0);
799 let y_var = Variable::new(1);
800 let y_ssa = {
801 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
802 cur.ins().iconst(I32, 2)
803 };
804 ssa.def_var(y_var, y_ssa, block0);
805 let z_var = Variable::new(2);
806 let x_use1 = ssa.use_var(&mut func, x_var, I32, block0).0;
807 let y_use1 = ssa.use_var(&mut func, y_var, I32, block0).0;
808 let z1_ssa = {
809 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
810 cur.ins().iadd(x_use1, y_use1)
811 };
812 ssa.def_var(z_var, z1_ssa, block0);
813 let y_use2 = ssa.use_var(&mut func, y_var, I32, block0).0;
814 let brnz_block0_block2: Inst = {
815 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
816 cur.ins().brnz(y_use2, block2, &[])
817 };
818 let jump_block0_block1: Inst = {
819 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
820 cur.ins().jump(block1, &[])
821 };
822
823 assert_eq!(ssa.use_var(&mut func, x_var, I32, block0).0, x_ssa);
824 assert_eq!(ssa.use_var(&mut func, y_var, I32, block0).0, y_ssa);
825 assert_eq!(ssa.use_var(&mut func, z_var, I32, block0).0, z1_ssa);
826
827 // block1
828 ssa.declare_block(block1);
829 ssa.declare_block_predecessor(block1, block0, jump_block0_block1);
830 ssa.seal_block(block1, &mut func);
831
832 let x_use2 = ssa.use_var(&mut func, x_var, I32, block1).0;
833 let z_use1 = ssa.use_var(&mut func, z_var, I32, block1).0;
834 let z2_ssa = {
835 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
836 cur.ins().iadd(x_use2, z_use1)
837 };
838 ssa.def_var(z_var, z2_ssa, block1);
839 let jump_block1_block2: Inst = {
840 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
841 cur.ins().jump(block2, &[])
842 };
843
844 assert_eq!(x_use2, x_ssa);
845 assert_eq!(z_use1, z1_ssa);
846 assert_eq!(ssa.use_var(&mut func, z_var, I32, block1).0, z2_ssa);
847
848 // block2
849 ssa.declare_block(block2);
850 ssa.declare_block_predecessor(block2, block0, brnz_block0_block2);
851 ssa.declare_block_predecessor(block2, block1, jump_block1_block2);
852 ssa.seal_block(block2, &mut func);
853 let x_use3 = ssa.use_var(&mut func, x_var, I32, block2).0;
854 let y_use3 = ssa.use_var(&mut func, y_var, I32, block2).0;
855 let y2_ssa = {
856 let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
857 cur.ins().iadd(x_use3, y_use3)
858 };
859 ssa.def_var(y_var, y2_ssa, block2);
860
861 assert_eq!(x_ssa, x_use3);
862 assert_eq!(y_ssa, y_use3);
863 match func.dfg.analyze_branch(brnz_block0_block2) {
864 BranchInfo::SingleDest(dest, jump_args) => {
865 assert_eq!(dest, block2);
866 assert_eq!(jump_args.len(), 0);
867 }
868 _ => assert!(false),
869 };
870 match func.dfg.analyze_branch(jump_block0_block1) {
871 BranchInfo::SingleDest(dest, jump_args) => {
872 assert_eq!(dest, block1);
873 assert_eq!(jump_args.len(), 0);
874 }
875 _ => assert!(false),
876 };
877 match func.dfg.analyze_branch(jump_block1_block2) {
878 BranchInfo::SingleDest(dest, jump_args) => {
879 assert_eq!(dest, block2);
880 assert_eq!(jump_args.len(), 0);
881 }
882 _ => assert!(false),
883 };
884 }
885
886 #[test]
program_with_loop()887 fn program_with_loop() {
888 let mut func = Function::new();
889 let mut ssa = SSABuilder::new();
890 let block0 = func.dfg.make_block();
891 let block1 = func.dfg.make_block();
892 let block2 = func.dfg.make_block();
893 let block3 = func.dfg.make_block();
894 {
895 let mut cur = FuncCursor::new(&mut func);
896 cur.insert_block(block0);
897 cur.insert_block(block1);
898 cur.insert_block(block2);
899 cur.insert_block(block3);
900 }
901 // Here is the pseudo-program we want to translate:
902 // block0:
903 // x = 1;
904 // y = 2;
905 // z = x + y;
906 // jump block1
907 // block1:
908 // z = z + y;
909 // brnz y, block3;
910 // jump block2;
911 // block2:
912 // z = z - x;
913 // return y
914 // block3:
915 // y = y - x
916 // jump block1
917
918 // block0
919 ssa.declare_block(block0);
920 ssa.seal_block(block0, &mut func);
921 let x_var = Variable::new(0);
922 let x1 = {
923 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
924 cur.ins().iconst(I32, 1)
925 };
926 ssa.def_var(x_var, x1, block0);
927 let y_var = Variable::new(1);
928 let y1 = {
929 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
930 cur.ins().iconst(I32, 2)
931 };
932 ssa.def_var(y_var, y1, block0);
933 let z_var = Variable::new(2);
934 let x2 = ssa.use_var(&mut func, x_var, I32, block0).0;
935 let y2 = ssa.use_var(&mut func, y_var, I32, block0).0;
936 let z1 = {
937 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
938 cur.ins().iadd(x2, y2)
939 };
940 ssa.def_var(z_var, z1, block0);
941 let jump_block0_block1 = {
942 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
943 cur.ins().jump(block1, &[])
944 };
945 assert_eq!(ssa.use_var(&mut func, x_var, I32, block0).0, x1);
946 assert_eq!(ssa.use_var(&mut func, y_var, I32, block0).0, y1);
947 assert_eq!(x2, x1);
948 assert_eq!(y2, y1);
949
950 // block1
951 ssa.declare_block(block1);
952 ssa.declare_block_predecessor(block1, block0, jump_block0_block1);
953 let z2 = ssa.use_var(&mut func, z_var, I32, block1).0;
954 let y3 = ssa.use_var(&mut func, y_var, I32, block1).0;
955 let z3 = {
956 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
957 cur.ins().iadd(z2, y3)
958 };
959 ssa.def_var(z_var, z3, block1);
960 let y4 = ssa.use_var(&mut func, y_var, I32, block1).0;
961 assert_eq!(y4, y3);
962 let brnz_block1_block3 = {
963 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
964 cur.ins().brnz(y4, block3, &[])
965 };
966 let jump_block1_block2 = {
967 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
968 cur.ins().jump(block2, &[])
969 };
970
971 // block2
972 ssa.declare_block(block2);
973 ssa.declare_block_predecessor(block2, block1, jump_block1_block2);
974 ssa.seal_block(block2, &mut func);
975 let z4 = ssa.use_var(&mut func, z_var, I32, block2).0;
976 assert_eq!(z4, z3);
977 let x3 = ssa.use_var(&mut func, x_var, I32, block2).0;
978 let z5 = {
979 let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
980 cur.ins().isub(z4, x3)
981 };
982 ssa.def_var(z_var, z5, block2);
983 let y5 = ssa.use_var(&mut func, y_var, I32, block2).0;
984 assert_eq!(y5, y3);
985 {
986 let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
987 cur.ins().return_(&[y5])
988 };
989
990 // block3
991 ssa.declare_block(block3);
992 ssa.declare_block_predecessor(block3, block1, brnz_block1_block3);
993 ssa.seal_block(block3, &mut func);
994 let y6 = ssa.use_var(&mut func, y_var, I32, block3).0;
995 assert_eq!(y6, y3);
996 let x4 = ssa.use_var(&mut func, x_var, I32, block3).0;
997 assert_eq!(x4, x3);
998 let y7 = {
999 let mut cur = FuncCursor::new(&mut func).at_bottom(block3);
1000 cur.ins().isub(y6, x4)
1001 };
1002 ssa.def_var(y_var, y7, block3);
1003 let jump_block3_block1 = {
1004 let mut cur = FuncCursor::new(&mut func).at_bottom(block3);
1005 cur.ins().jump(block1, &[])
1006 };
1007
1008 // block1 after all predecessors have been visited.
1009 ssa.declare_block_predecessor(block1, block3, jump_block3_block1);
1010 ssa.seal_block(block1, &mut func);
1011 assert_eq!(func.dfg.block_params(block1)[0], z2);
1012 assert_eq!(func.dfg.block_params(block1)[1], y3);
1013 assert_eq!(func.dfg.resolve_aliases(x3), x1);
1014 }
1015
1016 #[test]
br_table_with_args()1017 fn br_table_with_args() {
1018 // This tests the on-demand splitting of critical edges for br_table with jump arguments
1019 //
1020 // Here is the pseudo-program we want to translate:
1021 //
1022 // function %f {
1023 // jt = jump_table [block2, block1]
1024 // block0:
1025 // x = 1;
1026 // br_table x, block2, jt
1027 // block1:
1028 // x = 2
1029 // jump block2
1030 // block2:
1031 // x = x + 1
1032 // return
1033 // }
1034
1035 let mut func = Function::new();
1036 let mut ssa = SSABuilder::new();
1037 let block0 = func.dfg.make_block();
1038 let block1 = func.dfg.make_block();
1039 let block2 = func.dfg.make_block();
1040 let mut jump_table = JumpTableData::new();
1041 jump_table.push_entry(block2);
1042 jump_table.push_entry(block1);
1043 {
1044 let mut cur = FuncCursor::new(&mut func);
1045 cur.insert_block(block0);
1046 cur.insert_block(block1);
1047 cur.insert_block(block2);
1048 }
1049
1050 // block0
1051 let x1 = {
1052 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
1053 cur.ins().iconst(I32, 1)
1054 };
1055 ssa.declare_block(block0);
1056 ssa.seal_block(block0, &mut func);
1057 let x_var = Variable::new(0);
1058 ssa.def_var(x_var, x1, block0);
1059 ssa.use_var(&mut func, x_var, I32, block0).0;
1060 let br_table = {
1061 let jt = func.create_jump_table(jump_table);
1062 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
1063 cur.ins().br_table(x1, block2, jt)
1064 };
1065
1066 // block1
1067 ssa.declare_block(block1);
1068 ssa.declare_block_predecessor(block1, block0, br_table);
1069 ssa.seal_block(block1, &mut func);
1070 let x2 = {
1071 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
1072 cur.ins().iconst(I32, 2)
1073 };
1074 ssa.def_var(x_var, x2, block1);
1075 let jump_block1_block2 = {
1076 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
1077 cur.ins().jump(block2, &[])
1078 };
1079
1080 // block2
1081 ssa.declare_block(block2);
1082 ssa.declare_block_predecessor(block2, block1, jump_block1_block2);
1083 ssa.declare_block_predecessor(block2, block0, br_table);
1084 ssa.seal_block(block2, &mut func);
1085 let x3 = ssa.use_var(&mut func, x_var, I32, block2).0;
1086 let x4 = {
1087 let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
1088 cur.ins().iadd_imm(x3, 1)
1089 };
1090 ssa.def_var(x_var, x4, block2);
1091 {
1092 let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
1093 cur.ins().return_(&[])
1094 };
1095
1096 let flags = settings::Flags::new(settings::builder());
1097 match verify_function(&func, &flags) {
1098 Ok(()) => {}
1099 Err(_errors) => {
1100 #[cfg(feature = "std")]
1101 panic!("{}", _errors);
1102 #[cfg(not(feature = "std"))]
1103 panic!("function failed to verify");
1104 }
1105 }
1106 }
1107
1108 #[test]
undef_values_reordering()1109 fn undef_values_reordering() {
1110 // Here is the pseudo-program we want to translate:
1111 // block0:
1112 // x = 0;
1113 // y = 1;
1114 // z = 2;
1115 // jump block1;
1116 // block1:
1117 // x = z + x;
1118 // y = y - x;
1119 // jump block1;
1120 //
1121 let mut func = Function::new();
1122 let mut ssa = SSABuilder::new();
1123 let block0 = func.dfg.make_block();
1124 let block1 = func.dfg.make_block();
1125 {
1126 let mut cur = FuncCursor::new(&mut func);
1127 cur.insert_block(block0);
1128 cur.insert_block(block1);
1129 }
1130
1131 // block0
1132 ssa.declare_block(block0);
1133 let x_var = Variable::new(0);
1134 ssa.seal_block(block0, &mut func);
1135 let x1 = {
1136 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
1137 cur.ins().iconst(I32, 0)
1138 };
1139 ssa.def_var(x_var, x1, block0);
1140 let y_var = Variable::new(1);
1141 let y1 = {
1142 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
1143 cur.ins().iconst(I32, 1)
1144 };
1145 ssa.def_var(y_var, y1, block0);
1146 let z_var = Variable::new(2);
1147 let z1 = {
1148 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
1149 cur.ins().iconst(I32, 2)
1150 };
1151 ssa.def_var(z_var, z1, block0);
1152 let jump_block0_block1 = {
1153 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
1154 cur.ins().jump(block1, &[])
1155 };
1156
1157 // block1
1158 ssa.declare_block(block1);
1159 ssa.declare_block_predecessor(block1, block0, jump_block0_block1);
1160 let z2 = ssa.use_var(&mut func, z_var, I32, block1).0;
1161 assert_eq!(func.dfg.block_params(block1)[0], z2);
1162 let x2 = ssa.use_var(&mut func, x_var, I32, block1).0;
1163 assert_eq!(func.dfg.block_params(block1)[1], x2);
1164 let x3 = {
1165 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
1166 cur.ins().iadd(x2, z2)
1167 };
1168 ssa.def_var(x_var, x3, block1);
1169 let x4 = ssa.use_var(&mut func, x_var, I32, block1).0;
1170 let y3 = ssa.use_var(&mut func, y_var, I32, block1).0;
1171 assert_eq!(func.dfg.block_params(block1)[2], y3);
1172 let y4 = {
1173 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
1174 cur.ins().isub(y3, x4)
1175 };
1176 ssa.def_var(y_var, y4, block1);
1177 let jump_block1_block1 = {
1178 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
1179 cur.ins().jump(block1, &[])
1180 };
1181 ssa.declare_block_predecessor(block1, block1, jump_block1_block1);
1182 ssa.seal_block(block1, &mut func);
1183 // At sealing the "z" argument disappear but the remaining "x" and "y" args have to be
1184 // in the right order.
1185 assert_eq!(func.dfg.block_params(block1)[1], y3);
1186 assert_eq!(func.dfg.block_params(block1)[0], x2);
1187 }
1188
1189 #[test]
undef()1190 fn undef() {
1191 // Use vars of various types which have not been defined.
1192 let mut func = Function::new();
1193 let mut ssa = SSABuilder::new();
1194 let block0 = func.dfg.make_block();
1195 ssa.declare_block(block0);
1196 ssa.seal_block(block0, &mut func);
1197 let i32_var = Variable::new(0);
1198 let f32_var = Variable::new(1);
1199 let f64_var = Variable::new(2);
1200 let b1_var = Variable::new(3);
1201 let f32x4_var = Variable::new(4);
1202 ssa.use_var(&mut func, i32_var, I32, block0);
1203 ssa.use_var(&mut func, f32_var, F32, block0);
1204 ssa.use_var(&mut func, f64_var, F64, block0);
1205 ssa.use_var(&mut func, b1_var, B1, block0);
1206 ssa.use_var(&mut func, f32x4_var, F32X4, block0);
1207 assert_eq!(func.dfg.num_block_params(block0), 0);
1208 }
1209
1210 #[test]
undef_in_entry()1211 fn undef_in_entry() {
1212 // Use a var which has not been defined. The search should hit the
1213 // top of the entry block, and then fall back to inserting an iconst.
1214 let mut func = Function::new();
1215 let mut ssa = SSABuilder::new();
1216 let block0 = func.dfg.make_block();
1217 ssa.declare_block(block0);
1218 ssa.seal_block(block0, &mut func);
1219 let x_var = Variable::new(0);
1220 assert_eq!(func.dfg.num_block_params(block0), 0);
1221 ssa.use_var(&mut func, x_var, I32, block0);
1222 assert_eq!(func.dfg.num_block_params(block0), 0);
1223 assert_eq!(
1224 func.dfg[func.layout.first_inst(block0).unwrap()].opcode(),
1225 Opcode::Iconst
1226 );
1227 }
1228
1229 #[test]
undef_in_entry_sealed_after()1230 fn undef_in_entry_sealed_after() {
1231 // Use a var which has not been defined, but the block is not sealed
1232 // until afterward. Before sealing, the SSA builder should insert an
1233 // block param; after sealing, it should be removed.
1234 let mut func = Function::new();
1235 let mut ssa = SSABuilder::new();
1236 let block0 = func.dfg.make_block();
1237 ssa.declare_block(block0);
1238 let x_var = Variable::new(0);
1239 assert_eq!(func.dfg.num_block_params(block0), 0);
1240 ssa.use_var(&mut func, x_var, I32, block0);
1241 assert_eq!(func.dfg.num_block_params(block0), 1);
1242 ssa.seal_block(block0, &mut func);
1243 assert_eq!(func.dfg.num_block_params(block0), 0);
1244 assert_eq!(
1245 func.dfg[func.layout.first_inst(block0).unwrap()].opcode(),
1246 Opcode::Iconst
1247 );
1248 }
1249
1250 #[test]
unreachable_use()1251 fn unreachable_use() {
1252 // Here is the pseudo-program we want to translate:
1253 // block0:
1254 // return;
1255 // block1:
1256 // brz x, block1;
1257 // jump block1;
1258 let mut func = Function::new();
1259 let mut ssa = SSABuilder::new();
1260 let block0 = func.dfg.make_block();
1261 let block1 = func.dfg.make_block();
1262 {
1263 let mut cur = FuncCursor::new(&mut func);
1264 cur.insert_block(block0);
1265 cur.insert_block(block1);
1266 }
1267
1268 // block0
1269 ssa.declare_block(block0);
1270 ssa.seal_block(block0, &mut func);
1271 {
1272 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
1273 cur.ins().return_(&[]);
1274 }
1275
1276 // block1
1277 ssa.declare_block(block1);
1278 {
1279 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
1280 let x_var = Variable::new(0);
1281 let x_val = ssa.use_var(&mut cur.func, x_var, I32, block1).0;
1282 let brz = cur.ins().brz(x_val, block1, &[]);
1283 let jump_block1_block1 = cur.ins().jump(block1, &[]);
1284 ssa.declare_block_predecessor(block1, block1, brz);
1285 ssa.declare_block_predecessor(block1, block1, jump_block1_block1);
1286 }
1287 ssa.seal_block(block1, &mut func);
1288
1289 let flags = settings::Flags::new(settings::builder());
1290 match verify_function(&func, &flags) {
1291 Ok(()) => {}
1292 Err(_errors) => {
1293 #[cfg(feature = "std")]
1294 panic!("{}", _errors);
1295 #[cfg(not(feature = "std"))]
1296 panic!("function failed to verify");
1297 }
1298 }
1299 }
1300
1301 #[test]
unreachable_use_with_multiple_preds()1302 fn unreachable_use_with_multiple_preds() {
1303 // Here is the pseudo-program we want to translate:
1304 // block0:
1305 // return;
1306 // block1:
1307 // brz x, block2;
1308 // jump block1;
1309 // block2:
1310 // jump block1;
1311 let mut func = Function::new();
1312 let mut ssa = SSABuilder::new();
1313 let block0 = func.dfg.make_block();
1314 let block1 = func.dfg.make_block();
1315 let block2 = func.dfg.make_block();
1316 {
1317 let mut cur = FuncCursor::new(&mut func);
1318 cur.insert_block(block0);
1319 cur.insert_block(block1);
1320 cur.insert_block(block2);
1321 }
1322
1323 // block0
1324 ssa.declare_block(block0);
1325 ssa.seal_block(block0, &mut func);
1326 {
1327 let mut cur = FuncCursor::new(&mut func).at_bottom(block0);
1328 cur.ins().return_(&[]);
1329 }
1330
1331 // block1
1332 ssa.declare_block(block1);
1333 let brz = {
1334 let mut cur = FuncCursor::new(&mut func).at_bottom(block1);
1335 let x_var = Variable::new(0);
1336 let x_val = ssa.use_var(&mut cur.func, x_var, I32, block1).0;
1337 let brz = cur.ins().brz(x_val, block2, &[]);
1338 let jump_block1_block1 = cur.ins().jump(block1, &[]);
1339 ssa.declare_block_predecessor(block1, block1, jump_block1_block1);
1340 brz
1341 };
1342
1343 // block2
1344 ssa.declare_block(block2);
1345 ssa.declare_block_predecessor(block2, block1, brz);
1346 ssa.seal_block(block2, &mut func);
1347 let jump_block2_block1 = {
1348 let mut cur = FuncCursor::new(&mut func).at_bottom(block2);
1349 cur.ins().jump(block1, &[])
1350 };
1351
1352 // seal block1
1353 ssa.declare_block_predecessor(block1, block2, jump_block2_block1);
1354 ssa.seal_block(block1, &mut func);
1355 let flags = settings::Flags::new(settings::builder());
1356 match verify_function(&func, &flags) {
1357 Ok(()) => {}
1358 Err(_errors) => {
1359 #[cfg(feature = "std")]
1360 panic!("{}", _errors);
1361 #[cfg(not(feature = "std"))]
1362 panic!("function failed to verify");
1363 }
1364 }
1365 }
1366 }
1367