1 //! Data flow graph tracking Instructions, Values, and blocks.
2
3 use crate::entity::{self, PrimaryMap, SecondaryMap};
4 use crate::ir;
5 use crate::ir::builder::ReplaceBuilder;
6 use crate::ir::extfunc::ExtFuncData;
7 use crate::ir::instructions::{BranchInfo, CallInfo, InstructionData};
8 use crate::ir::{types, ConstantData, ConstantPool, Immediate};
9 use crate::ir::{
10 Block, FuncRef, Inst, SigRef, Signature, Type, Value, ValueLabelAssignments, ValueList,
11 ValueListPool,
12 };
13 use crate::isa::TargetIsa;
14 use crate::packed_option::ReservedValue;
15 use crate::write::write_operands;
16 use crate::HashMap;
17 use alloc::vec::Vec;
18 use core::fmt;
19 use core::iter;
20 use core::mem;
21 use core::ops::{Index, IndexMut};
22 use core::u16;
23
24 #[cfg(feature = "enable-serde")]
25 use serde::{Deserialize, Serialize};
26
27 /// A data flow graph defines all instructions and basic blocks in a function as well as
28 /// the data flow dependencies between them. The DFG also tracks values which can be either
29 /// instruction results or block parameters.
30 ///
31 /// The layout of blocks in the function and of instructions in each block is recorded by the
32 /// `Layout` data structure which forms the other half of the function representation.
33 ///
34 #[derive(Clone)]
35 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
36 pub struct DataFlowGraph {
37 /// Data about all of the instructions in the function, including opcodes and operands.
38 /// The instructions in this map are not in program order. That is tracked by `Layout`, along
39 /// with the block containing each instruction.
40 insts: PrimaryMap<Inst, InstructionData>,
41
42 /// List of result values for each instruction.
43 ///
44 /// This map gets resized automatically by `make_inst()` so it is always in sync with the
45 /// primary `insts` map.
46 results: SecondaryMap<Inst, ValueList>,
47
48 /// basic blocks in the function and their parameters.
49 ///
50 /// This map is not in program order. That is handled by `Layout`, and so is the sequence of
51 /// instructions contained in each block.
52 blocks: PrimaryMap<Block, BlockData>,
53
54 /// Memory pool of value lists.
55 ///
56 /// The `ValueList` references into this pool appear in many places:
57 ///
58 /// - Instructions in `insts` that don't have room for their entire argument list inline.
59 /// - Instruction result values in `results`.
60 /// - block parameters in `blocks`.
61 pub value_lists: ValueListPool,
62
63 /// Primary value table with entries for all values.
64 values: PrimaryMap<Value, ValueData>,
65
66 /// Function signature table. These signatures are referenced by indirect call instructions as
67 /// well as the external function references.
68 pub signatures: PrimaryMap<SigRef, Signature>,
69
70 /// The pre-legalization signature for each entry in `signatures`, if any.
71 pub old_signatures: SecondaryMap<SigRef, Option<Signature>>,
72
73 /// External function references. These are functions that can be called directly.
74 pub ext_funcs: PrimaryMap<FuncRef, ExtFuncData>,
75
76 /// Saves Value labels.
77 pub values_labels: Option<HashMap<Value, ValueLabelAssignments>>,
78
79 /// Constants used within the function
80 pub constants: ConstantPool,
81
82 /// Stores large immediates that otherwise will not fit on InstructionData
83 pub immediates: PrimaryMap<Immediate, ConstantData>,
84 }
85
86 impl DataFlowGraph {
87 /// Create a new empty `DataFlowGraph`.
new() -> Self88 pub fn new() -> Self {
89 Self {
90 insts: PrimaryMap::new(),
91 results: SecondaryMap::new(),
92 blocks: PrimaryMap::new(),
93 value_lists: ValueListPool::new(),
94 values: PrimaryMap::new(),
95 signatures: PrimaryMap::new(),
96 old_signatures: SecondaryMap::new(),
97 ext_funcs: PrimaryMap::new(),
98 values_labels: None,
99 constants: ConstantPool::new(),
100 immediates: PrimaryMap::new(),
101 }
102 }
103
104 /// Clear everything.
clear(&mut self)105 pub fn clear(&mut self) {
106 self.insts.clear();
107 self.results.clear();
108 self.blocks.clear();
109 self.value_lists.clear();
110 self.values.clear();
111 self.signatures.clear();
112 self.old_signatures.clear();
113 self.ext_funcs.clear();
114 self.values_labels = None;
115 self.constants.clear();
116 self.immediates.clear();
117 }
118
119 /// Get the total number of instructions created in this function, whether they are currently
120 /// inserted in the layout or not.
121 ///
122 /// This is intended for use with `SecondaryMap::with_capacity`.
num_insts(&self) -> usize123 pub fn num_insts(&self) -> usize {
124 self.insts.len()
125 }
126
127 /// Returns `true` if the given instruction reference is valid.
inst_is_valid(&self, inst: Inst) -> bool128 pub fn inst_is_valid(&self, inst: Inst) -> bool {
129 self.insts.is_valid(inst)
130 }
131
132 /// Get the total number of basic blocks created in this function, whether they are
133 /// currently inserted in the layout or not.
134 ///
135 /// This is intended for use with `SecondaryMap::with_capacity`.
num_blocks(&self) -> usize136 pub fn num_blocks(&self) -> usize {
137 self.blocks.len()
138 }
139
140 /// Returns `true` if the given block reference is valid.
block_is_valid(&self, block: Block) -> bool141 pub fn block_is_valid(&self, block: Block) -> bool {
142 self.blocks.is_valid(block)
143 }
144
145 /// Get the total number of values.
num_values(&self) -> usize146 pub fn num_values(&self) -> usize {
147 self.values.len()
148 }
149
150 /// Starts collection of debug information.
collect_debug_info(&mut self)151 pub fn collect_debug_info(&mut self) {
152 if self.values_labels.is_none() {
153 self.values_labels = Some(HashMap::new());
154 }
155 }
156 }
157
158 /// Resolve value aliases.
159 ///
160 /// Find the original SSA value that `value` aliases, or None if an
161 /// alias cycle is detected.
maybe_resolve_aliases(values: &PrimaryMap<Value, ValueData>, value: Value) -> Option<Value>162 fn maybe_resolve_aliases(values: &PrimaryMap<Value, ValueData>, value: Value) -> Option<Value> {
163 let mut v = value;
164
165 // Note that values may be empty here.
166 for _ in 0..=values.len() {
167 if let ValueData::Alias { original, .. } = values[v] {
168 v = original;
169 } else {
170 return Some(v);
171 }
172 }
173
174 None
175 }
176
177 /// Resolve value aliases.
178 ///
179 /// Find the original SSA value that `value` aliases.
resolve_aliases(values: &PrimaryMap<Value, ValueData>, value: Value) -> Value180 fn resolve_aliases(values: &PrimaryMap<Value, ValueData>, value: Value) -> Value {
181 if let Some(v) = maybe_resolve_aliases(values, value) {
182 v
183 } else {
184 panic!("Value alias loop detected for {}", value);
185 }
186 }
187
188 /// Iterator over all Values in a DFG
189 pub struct Values<'a> {
190 inner: entity::Iter<'a, Value, ValueData>,
191 }
192
193 /// Check for non-values
valid_valuedata(data: &ValueData) -> bool194 fn valid_valuedata(data: &ValueData) -> bool {
195 if let ValueData::Alias {
196 ty: types::INVALID,
197 original,
198 } = *data
199 {
200 if original == Value::reserved_value() {
201 return false;
202 }
203 }
204 true
205 }
206
207 impl<'a> Iterator for Values<'a> {
208 type Item = Value;
209
next(&mut self) -> Option<Self::Item>210 fn next(&mut self) -> Option<Self::Item> {
211 self.inner
212 .by_ref()
213 .find(|kv| valid_valuedata(kv.1))
214 .map(|kv| kv.0)
215 }
216 }
217
218 /// Handling values.
219 ///
220 /// Values are either block parameters or instruction results.
221 impl DataFlowGraph {
222 /// Allocate an extended value entry.
make_value(&mut self, data: ValueData) -> Value223 fn make_value(&mut self, data: ValueData) -> Value {
224 self.values.push(data)
225 }
226
227 /// Get an iterator over all values.
values<'a>(&'a self) -> Values228 pub fn values<'a>(&'a self) -> Values {
229 Values {
230 inner: self.values.iter(),
231 }
232 }
233
234 /// Check if a value reference is valid.
value_is_valid(&self, v: Value) -> bool235 pub fn value_is_valid(&self, v: Value) -> bool {
236 self.values.is_valid(v)
237 }
238
239 /// Get the type of a value.
value_type(&self, v: Value) -> Type240 pub fn value_type(&self, v: Value) -> Type {
241 self.values[v].ty()
242 }
243
244 /// Get the definition of a value.
245 ///
246 /// This is either the instruction that defined it or the Block that has the value as an
247 /// parameter.
value_def(&self, v: Value) -> ValueDef248 pub fn value_def(&self, v: Value) -> ValueDef {
249 match self.values[v] {
250 ValueData::Inst { inst, num, .. } => ValueDef::Result(inst, num as usize),
251 ValueData::Param { block, num, .. } => ValueDef::Param(block, num as usize),
252 ValueData::Alias { original, .. } => {
253 // Make sure we only recurse one level. `resolve_aliases` has safeguards to
254 // detect alias loops without overrunning the stack.
255 self.value_def(self.resolve_aliases(original))
256 }
257 }
258 }
259
260 /// Determine if `v` is an attached instruction result / block parameter.
261 ///
262 /// An attached value can't be attached to something else without first being detached.
263 ///
264 /// Value aliases are not considered to be attached to anything. Use `resolve_aliases()` to
265 /// determine if the original aliased value is attached.
value_is_attached(&self, v: Value) -> bool266 pub fn value_is_attached(&self, v: Value) -> bool {
267 use self::ValueData::*;
268 match self.values[v] {
269 Inst { inst, num, .. } => Some(&v) == self.inst_results(inst).get(num as usize),
270 Param { block, num, .. } => Some(&v) == self.block_params(block).get(num as usize),
271 Alias { .. } => false,
272 }
273 }
274
275 /// Resolve value aliases.
276 ///
277 /// Find the original SSA value that `value` aliases.
resolve_aliases(&self, value: Value) -> Value278 pub fn resolve_aliases(&self, value: Value) -> Value {
279 resolve_aliases(&self.values, value)
280 }
281
282 /// Resolve all aliases among inst's arguments.
283 ///
284 /// For each argument of inst which is defined by an alias, replace the
285 /// alias with the aliased value.
resolve_aliases_in_arguments(&mut self, inst: Inst)286 pub fn resolve_aliases_in_arguments(&mut self, inst: Inst) {
287 for arg in self.insts[inst].arguments_mut(&mut self.value_lists) {
288 let resolved = resolve_aliases(&self.values, *arg);
289 if resolved != *arg {
290 *arg = resolved;
291 }
292 }
293 }
294
295 /// Turn a value into an alias of another.
296 ///
297 /// Change the `dest` value to behave as an alias of `src`. This means that all uses of `dest`
298 /// will behave as if they used that value `src`.
299 ///
300 /// The `dest` value can't be attached to an instruction or block.
change_to_alias(&mut self, dest: Value, src: Value)301 pub fn change_to_alias(&mut self, dest: Value, src: Value) {
302 debug_assert!(!self.value_is_attached(dest));
303 // Try to create short alias chains by finding the original source value.
304 // This also avoids the creation of loops.
305 let original = self.resolve_aliases(src);
306 debug_assert_ne!(
307 dest, original,
308 "Aliasing {} to {} would create a loop",
309 dest, src
310 );
311 let ty = self.value_type(original);
312 debug_assert_eq!(
313 self.value_type(dest),
314 ty,
315 "Aliasing {} to {} would change its type {} to {}",
316 dest,
317 src,
318 self.value_type(dest),
319 ty
320 );
321 debug_assert_ne!(ty, types::INVALID);
322
323 self.values[dest] = ValueData::Alias { ty, original };
324 }
325
326 /// Replace the results of one instruction with aliases to the results of another.
327 ///
328 /// Change all the results of `dest_inst` to behave as aliases of
329 /// corresponding results of `src_inst`, as if calling change_to_alias for
330 /// each.
331 ///
332 /// After calling this instruction, `dest_inst` will have had its results
333 /// cleared, so it likely needs to be removed from the graph.
334 ///
replace_with_aliases(&mut self, dest_inst: Inst, src_inst: Inst)335 pub fn replace_with_aliases(&mut self, dest_inst: Inst, src_inst: Inst) {
336 debug_assert_ne!(
337 dest_inst, src_inst,
338 "Replacing {} with itself would create a loop",
339 dest_inst
340 );
341 debug_assert_eq!(
342 self.results[dest_inst].len(&self.value_lists),
343 self.results[src_inst].len(&self.value_lists),
344 "Replacing {} with {} would produce a different number of results.",
345 dest_inst,
346 src_inst
347 );
348
349 for (&dest, &src) in self.results[dest_inst]
350 .as_slice(&self.value_lists)
351 .iter()
352 .zip(self.results[src_inst].as_slice(&self.value_lists))
353 {
354 let original = src;
355 let ty = self.value_type(original);
356 debug_assert_eq!(
357 self.value_type(dest),
358 ty,
359 "Aliasing {} to {} would change its type {} to {}",
360 dest,
361 src,
362 self.value_type(dest),
363 ty
364 );
365 debug_assert_ne!(ty, types::INVALID);
366
367 self.values[dest] = ValueData::Alias { ty, original };
368 }
369
370 self.clear_results(dest_inst);
371 }
372 }
373
374 /// Where did a value come from?
375 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
376 pub enum ValueDef {
377 /// Value is the n'th result of an instruction.
378 Result(Inst, usize),
379 /// Value is the n'th parameter to a block.
380 Param(Block, usize),
381 }
382
383 impl ValueDef {
384 /// Unwrap the instruction where the value was defined, or panic.
unwrap_inst(&self) -> Inst385 pub fn unwrap_inst(&self) -> Inst {
386 self.inst().expect("Value is not an instruction result")
387 }
388
389 /// Get the instruction where the value was defined, if any.
inst(&self) -> Option<Inst>390 pub fn inst(&self) -> Option<Inst> {
391 match *self {
392 Self::Result(inst, _) => Some(inst),
393 _ => None,
394 }
395 }
396
397 /// Unwrap the block there the parameter is defined, or panic.
unwrap_block(&self) -> Block398 pub fn unwrap_block(&self) -> Block {
399 match *self {
400 Self::Param(block, _) => block,
401 _ => panic!("Value is not a block parameter"),
402 }
403 }
404
405 /// Get the program point where the value was defined.
pp(self) -> ir::ExpandedProgramPoint406 pub fn pp(self) -> ir::ExpandedProgramPoint {
407 self.into()
408 }
409
410 /// Get the number component of this definition.
411 ///
412 /// When multiple values are defined at the same program point, this indicates the index of
413 /// this value.
num(self) -> usize414 pub fn num(self) -> usize {
415 match self {
416 Self::Result(_, n) | Self::Param(_, n) => n,
417 }
418 }
419 }
420
421 /// Internal table storage for extended values.
422 #[derive(Clone, Debug)]
423 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
424 enum ValueData {
425 /// Value is defined by an instruction.
426 Inst { ty: Type, num: u16, inst: Inst },
427
428 /// Value is a block parameter.
429 Param { ty: Type, num: u16, block: Block },
430
431 /// Value is an alias of another value.
432 /// An alias value can't be linked as an instruction result or block parameter. It is used as a
433 /// placeholder when the original instruction or block has been rewritten or modified.
434 Alias { ty: Type, original: Value },
435 }
436
437 impl ValueData {
ty(&self) -> Type438 fn ty(&self) -> Type {
439 match *self {
440 ValueData::Inst { ty, .. }
441 | ValueData::Param { ty, .. }
442 | ValueData::Alias { ty, .. } => ty,
443 }
444 }
445 }
446
447 /// Instructions.
448 ///
449 impl DataFlowGraph {
450 /// Create a new instruction.
451 ///
452 /// The type of the first result is indicated by `data.ty`. If the instruction produces
453 /// multiple results, also call `make_inst_results` to allocate value table entries.
make_inst(&mut self, data: InstructionData) -> Inst454 pub fn make_inst(&mut self, data: InstructionData) -> Inst {
455 let n = self.num_insts() + 1;
456 self.results.resize(n);
457 self.insts.push(data)
458 }
459
460 /// Returns an object that displays `inst`.
display_inst<'a, I: Into<Option<&'a dyn TargetIsa>>>( &'a self, inst: Inst, isa: I, ) -> DisplayInst<'a>461 pub fn display_inst<'a, I: Into<Option<&'a dyn TargetIsa>>>(
462 &'a self,
463 inst: Inst,
464 isa: I,
465 ) -> DisplayInst<'a> {
466 DisplayInst(self, isa.into(), inst)
467 }
468
469 /// Get all value arguments on `inst` as a slice.
inst_args(&self, inst: Inst) -> &[Value]470 pub fn inst_args(&self, inst: Inst) -> &[Value] {
471 self.insts[inst].arguments(&self.value_lists)
472 }
473
474 /// Get all value arguments on `inst` as a mutable slice.
inst_args_mut(&mut self, inst: Inst) -> &mut [Value]475 pub fn inst_args_mut(&mut self, inst: Inst) -> &mut [Value] {
476 self.insts[inst].arguments_mut(&mut self.value_lists)
477 }
478
479 /// Get the fixed value arguments on `inst` as a slice.
inst_fixed_args(&self, inst: Inst) -> &[Value]480 pub fn inst_fixed_args(&self, inst: Inst) -> &[Value] {
481 let num_fixed_args = self[inst]
482 .opcode()
483 .constraints()
484 .num_fixed_value_arguments();
485 &self.inst_args(inst)[..num_fixed_args]
486 }
487
488 /// Get the fixed value arguments on `inst` as a mutable slice.
inst_fixed_args_mut(&mut self, inst: Inst) -> &mut [Value]489 pub fn inst_fixed_args_mut(&mut self, inst: Inst) -> &mut [Value] {
490 let num_fixed_args = self[inst]
491 .opcode()
492 .constraints()
493 .num_fixed_value_arguments();
494 &mut self.inst_args_mut(inst)[..num_fixed_args]
495 }
496
497 /// Get the variable value arguments on `inst` as a slice.
inst_variable_args(&self, inst: Inst) -> &[Value]498 pub fn inst_variable_args(&self, inst: Inst) -> &[Value] {
499 let num_fixed_args = self[inst]
500 .opcode()
501 .constraints()
502 .num_fixed_value_arguments();
503 &self.inst_args(inst)[num_fixed_args..]
504 }
505
506 /// Get the variable value arguments on `inst` as a mutable slice.
inst_variable_args_mut(&mut self, inst: Inst) -> &mut [Value]507 pub fn inst_variable_args_mut(&mut self, inst: Inst) -> &mut [Value] {
508 let num_fixed_args = self[inst]
509 .opcode()
510 .constraints()
511 .num_fixed_value_arguments();
512 &mut self.inst_args_mut(inst)[num_fixed_args..]
513 }
514
515 /// Create result values for an instruction that produces multiple results.
516 ///
517 /// Instructions that produce no result values only need to be created with `make_inst`,
518 /// otherwise call `make_inst_results` to allocate value table entries for the results.
519 ///
520 /// The result value types are determined from the instruction's value type constraints and the
521 /// provided `ctrl_typevar` type for polymorphic instructions. For non-polymorphic
522 /// instructions, `ctrl_typevar` is ignored, and `INVALID` can be used.
523 ///
524 /// The type of the first result value is also set, even if it was already set in the
525 /// `InstructionData` passed to `make_inst`. If this function is called with a single-result
526 /// instruction, that is the only effect.
make_inst_results(&mut self, inst: Inst, ctrl_typevar: Type) -> usize527 pub fn make_inst_results(&mut self, inst: Inst, ctrl_typevar: Type) -> usize {
528 self.make_inst_results_reusing(inst, ctrl_typevar, iter::empty())
529 }
530
531 /// Create result values for `inst`, reusing the provided detached values.
532 ///
533 /// Create a new set of result values for `inst` using `ctrl_typevar` to determine the result
534 /// types. Any values provided by `reuse` will be reused. When `reuse` is exhausted or when it
535 /// produces `None`, a new value is created.
make_inst_results_reusing<I>( &mut self, inst: Inst, ctrl_typevar: Type, reuse: I, ) -> usize where I: Iterator<Item = Option<Value>>,536 pub fn make_inst_results_reusing<I>(
537 &mut self,
538 inst: Inst,
539 ctrl_typevar: Type,
540 reuse: I,
541 ) -> usize
542 where
543 I: Iterator<Item = Option<Value>>,
544 {
545 let mut reuse = reuse.fuse();
546
547 self.results[inst].clear(&mut self.value_lists);
548
549 // Get the call signature if this is a function call.
550 if let Some(sig) = self.call_signature(inst) {
551 // Create result values corresponding to the call return types.
552 debug_assert_eq!(
553 self.insts[inst].opcode().constraints().num_fixed_results(),
554 0
555 );
556 let num_results = self.signatures[sig].returns.len();
557 for res_idx in 0..num_results {
558 let ty = self.signatures[sig].returns[res_idx].value_type;
559 if let Some(Some(v)) = reuse.next() {
560 debug_assert_eq!(self.value_type(v), ty, "Reused {} is wrong type", ty);
561 self.attach_result(inst, v);
562 } else {
563 self.append_result(inst, ty);
564 }
565 }
566 num_results
567 } else {
568 // Create result values corresponding to the opcode's constraints.
569 let constraints = self.insts[inst].opcode().constraints();
570 let num_results = constraints.num_fixed_results();
571 for res_idx in 0..num_results {
572 let ty = constraints.result_type(res_idx, ctrl_typevar);
573 if let Some(Some(v)) = reuse.next() {
574 debug_assert_eq!(self.value_type(v), ty, "Reused {} is wrong type", ty);
575 self.attach_result(inst, v);
576 } else {
577 self.append_result(inst, ty);
578 }
579 }
580 num_results
581 }
582 }
583
584 /// Create a `ReplaceBuilder` that will replace `inst` with a new instruction in place.
replace(&mut self, inst: Inst) -> ReplaceBuilder585 pub fn replace(&mut self, inst: Inst) -> ReplaceBuilder {
586 ReplaceBuilder::new(self, inst)
587 }
588
589 /// Detach the list of result values from `inst` and return it.
590 ///
591 /// This leaves `inst` without any result values. New result values can be created by calling
592 /// `make_inst_results` or by using a `replace(inst)` builder.
detach_results(&mut self, inst: Inst) -> ValueList593 pub fn detach_results(&mut self, inst: Inst) -> ValueList {
594 self.results[inst].take()
595 }
596
597 /// Clear the list of result values from `inst`.
598 ///
599 /// This leaves `inst` without any result values. New result values can be created by calling
600 /// `make_inst_results` or by using a `replace(inst)` builder.
clear_results(&mut self, inst: Inst)601 pub fn clear_results(&mut self, inst: Inst) {
602 self.results[inst].clear(&mut self.value_lists)
603 }
604
605 /// Attach an existing value to the result value list for `inst`.
606 ///
607 /// The `res` value is appended to the end of the result list.
608 ///
609 /// This is a very low-level operation. Usually, instruction results with the correct types are
610 /// created automatically. The `res` value must not be attached to anything else.
attach_result(&mut self, inst: Inst, res: Value)611 pub fn attach_result(&mut self, inst: Inst, res: Value) {
612 debug_assert!(!self.value_is_attached(res));
613 let num = self.results[inst].push(res, &mut self.value_lists);
614 debug_assert!(num <= u16::MAX as usize, "Too many result values");
615 let ty = self.value_type(res);
616 self.values[res] = ValueData::Inst {
617 ty,
618 num: num as u16,
619 inst,
620 };
621 }
622
623 /// Replace an instruction result with a new value of type `new_type`.
624 ///
625 /// The `old_value` must be an attached instruction result.
626 ///
627 /// The old value is left detached, so it should probably be changed into something else.
628 ///
629 /// Returns the new value.
replace_result(&mut self, old_value: Value, new_type: Type) -> Value630 pub fn replace_result(&mut self, old_value: Value, new_type: Type) -> Value {
631 let (num, inst) = match self.values[old_value] {
632 ValueData::Inst { num, inst, .. } => (num, inst),
633 _ => panic!("{} is not an instruction result value", old_value),
634 };
635 let new_value = self.make_value(ValueData::Inst {
636 ty: new_type,
637 num,
638 inst,
639 });
640 let num = num as usize;
641 let attached = mem::replace(
642 self.results[inst]
643 .get_mut(num, &mut self.value_lists)
644 .expect("Replacing detached result"),
645 new_value,
646 );
647 debug_assert_eq!(
648 attached,
649 old_value,
650 "{} wasn't detached from {}",
651 old_value,
652 self.display_inst(inst, None)
653 );
654 new_value
655 }
656
657 /// Append a new instruction result value to `inst`.
append_result(&mut self, inst: Inst, ty: Type) -> Value658 pub fn append_result(&mut self, inst: Inst, ty: Type) -> Value {
659 let res = self.values.next_key();
660 let num = self.results[inst].push(res, &mut self.value_lists);
661 debug_assert!(num <= u16::MAX as usize, "Too many result values");
662 self.make_value(ValueData::Inst {
663 ty,
664 inst,
665 num: num as u16,
666 })
667 }
668
669 /// Append a new value argument to an instruction.
670 ///
671 /// Panics if the instruction doesn't support arguments.
append_inst_arg(&mut self, inst: Inst, new_arg: Value)672 pub fn append_inst_arg(&mut self, inst: Inst, new_arg: Value) {
673 let mut branch_values = self.insts[inst]
674 .take_value_list()
675 .expect("the instruction doesn't have value arguments");
676 branch_values.push(new_arg, &mut self.value_lists);
677 self.insts[inst].put_value_list(branch_values)
678 }
679
680 /// Get the first result of an instruction.
681 ///
682 /// This function panics if the instruction doesn't have any result.
first_result(&self, inst: Inst) -> Value683 pub fn first_result(&self, inst: Inst) -> Value {
684 self.results[inst]
685 .first(&self.value_lists)
686 .expect("Instruction has no results")
687 }
688
689 /// Test if `inst` has any result values currently.
has_results(&self, inst: Inst) -> bool690 pub fn has_results(&self, inst: Inst) -> bool {
691 !self.results[inst].is_empty()
692 }
693
694 /// Return all the results of an instruction.
inst_results(&self, inst: Inst) -> &[Value]695 pub fn inst_results(&self, inst: Inst) -> &[Value] {
696 self.results[inst].as_slice(&self.value_lists)
697 }
698
699 /// Get the call signature of a direct or indirect call instruction.
700 /// Returns `None` if `inst` is not a call instruction.
call_signature(&self, inst: Inst) -> Option<SigRef>701 pub fn call_signature(&self, inst: Inst) -> Option<SigRef> {
702 match self.insts[inst].analyze_call(&self.value_lists) {
703 CallInfo::NotACall => None,
704 CallInfo::Direct(f, _) => Some(self.ext_funcs[f].signature),
705 CallInfo::Indirect(s, _) => Some(s),
706 }
707 }
708
709 /// Check if `inst` is a branch.
analyze_branch(&self, inst: Inst) -> BranchInfo710 pub fn analyze_branch(&self, inst: Inst) -> BranchInfo {
711 self.insts[inst].analyze_branch(&self.value_lists)
712 }
713
714 /// Compute the type of an instruction result from opcode constraints and call signatures.
715 ///
716 /// This computes the same sequence of result types that `make_inst_results()` above would
717 /// assign to the created result values, but it does not depend on `make_inst_results()` being
718 /// called first.
719 ///
720 /// Returns `None` if asked about a result index that is too large.
compute_result_type( &self, inst: Inst, result_idx: usize, ctrl_typevar: Type, ) -> Option<Type>721 pub fn compute_result_type(
722 &self,
723 inst: Inst,
724 result_idx: usize,
725 ctrl_typevar: Type,
726 ) -> Option<Type> {
727 let constraints = self.insts[inst].opcode().constraints();
728 let num_fixed_results = constraints.num_fixed_results();
729
730 if result_idx < num_fixed_results {
731 return Some(constraints.result_type(result_idx, ctrl_typevar));
732 }
733
734 // Not a fixed result, try to extract a return type from the call signature.
735 self.call_signature(inst).and_then(|sigref| {
736 self.signatures[sigref]
737 .returns
738 .get(result_idx - num_fixed_results)
739 .map(|&arg| arg.value_type)
740 })
741 }
742
743 /// Get the controlling type variable, or `INVALID` if `inst` isn't polymorphic.
ctrl_typevar(&self, inst: Inst) -> Type744 pub fn ctrl_typevar(&self, inst: Inst) -> Type {
745 let constraints = self[inst].opcode().constraints();
746
747 if !constraints.is_polymorphic() {
748 types::INVALID
749 } else if constraints.requires_typevar_operand() {
750 // Not all instruction formats have a designated operand, but in that case
751 // `requires_typevar_operand()` should never be true.
752 self.value_type(
753 self[inst]
754 .typevar_operand(&self.value_lists)
755 .expect("Instruction format doesn't have a designated operand, bad opcode."),
756 )
757 } else {
758 self.value_type(self.first_result(inst))
759 }
760 }
761 }
762
763 /// Allow immutable access to instructions via indexing.
764 impl Index<Inst> for DataFlowGraph {
765 type Output = InstructionData;
766
index(&self, inst: Inst) -> &InstructionData767 fn index(&self, inst: Inst) -> &InstructionData {
768 &self.insts[inst]
769 }
770 }
771
772 /// Allow mutable access to instructions via indexing.
773 impl IndexMut<Inst> for DataFlowGraph {
index_mut(&mut self, inst: Inst) -> &mut InstructionData774 fn index_mut(&mut self, inst: Inst) -> &mut InstructionData {
775 &mut self.insts[inst]
776 }
777 }
778
779 /// basic blocks.
780 impl DataFlowGraph {
781 /// Create a new basic block.
make_block(&mut self) -> Block782 pub fn make_block(&mut self) -> Block {
783 self.blocks.push(BlockData::new())
784 }
785
786 /// Get the number of parameters on `block`.
num_block_params(&self, block: Block) -> usize787 pub fn num_block_params(&self, block: Block) -> usize {
788 self.blocks[block].params.len(&self.value_lists)
789 }
790
791 /// Get the parameters on `block`.
block_params(&self, block: Block) -> &[Value]792 pub fn block_params(&self, block: Block) -> &[Value] {
793 self.blocks[block].params.as_slice(&self.value_lists)
794 }
795
796 /// Get the types of the parameters on `block`.
block_param_types(&self, block: Block) -> Vec<Type>797 pub fn block_param_types(&self, block: Block) -> Vec<Type> {
798 self.block_params(block)
799 .iter()
800 .map(|&v| self.value_type(v))
801 .collect()
802 }
803
804 /// Append a parameter with type `ty` to `block`.
append_block_param(&mut self, block: Block, ty: Type) -> Value805 pub fn append_block_param(&mut self, block: Block, ty: Type) -> Value {
806 let param = self.values.next_key();
807 let num = self.blocks[block].params.push(param, &mut self.value_lists);
808 debug_assert!(num <= u16::MAX as usize, "Too many parameters on block");
809 self.make_value(ValueData::Param {
810 ty,
811 num: num as u16,
812 block,
813 })
814 }
815
816 /// Removes `val` from `block`'s parameters by swapping it with the last parameter on `block`.
817 /// Returns the position of `val` before removal.
818 ///
819 /// *Important*: to ensure O(1) deletion, this method swaps the removed parameter with the
820 /// last `block` parameter. This can disrupt all the branch instructions jumping to this
821 /// `block` for which you have to change the branch argument order if necessary.
822 ///
823 /// Panics if `val` is not a block parameter.
swap_remove_block_param(&mut self, val: Value) -> usize824 pub fn swap_remove_block_param(&mut self, val: Value) -> usize {
825 let (block, num) = if let ValueData::Param { num, block, .. } = self.values[val] {
826 (block, num)
827 } else {
828 panic!("{} must be a block parameter", val);
829 };
830 self.blocks[block]
831 .params
832 .swap_remove(num as usize, &mut self.value_lists);
833 if let Some(last_arg_val) = self.blocks[block]
834 .params
835 .get(num as usize, &self.value_lists)
836 {
837 // We update the position of the old last arg.
838 if let ValueData::Param {
839 num: ref mut old_num,
840 ..
841 } = self.values[last_arg_val]
842 {
843 *old_num = num;
844 } else {
845 panic!("{} should be a Block parameter", last_arg_val);
846 }
847 }
848 num as usize
849 }
850
851 /// Removes `val` from `block`'s parameters by a standard linear time list removal which
852 /// preserves ordering. Also updates the values' data.
remove_block_param(&mut self, val: Value)853 pub fn remove_block_param(&mut self, val: Value) {
854 let (block, num) = if let ValueData::Param { num, block, .. } = self.values[val] {
855 (block, num)
856 } else {
857 panic!("{} must be a block parameter", val);
858 };
859 self.blocks[block]
860 .params
861 .remove(num as usize, &mut self.value_lists);
862 for index in num..(self.num_block_params(block) as u16) {
863 match self.values[self.blocks[block]
864 .params
865 .get(index as usize, &self.value_lists)
866 .unwrap()]
867 {
868 ValueData::Param { ref mut num, .. } => {
869 *num -= 1;
870 }
871 _ => panic!(
872 "{} must be a block parameter",
873 self.blocks[block]
874 .params
875 .get(index as usize, &self.value_lists)
876 .unwrap()
877 ),
878 }
879 }
880 }
881
882 /// Append an existing value to `block`'s parameters.
883 ///
884 /// The appended value can't already be attached to something else.
885 ///
886 /// In almost all cases, you should be using `append_block_param()` instead of this method.
attach_block_param(&mut self, block: Block, param: Value)887 pub fn attach_block_param(&mut self, block: Block, param: Value) {
888 debug_assert!(!self.value_is_attached(param));
889 let num = self.blocks[block].params.push(param, &mut self.value_lists);
890 debug_assert!(num <= u16::MAX as usize, "Too many parameters on block");
891 let ty = self.value_type(param);
892 self.values[param] = ValueData::Param {
893 ty,
894 num: num as u16,
895 block,
896 };
897 }
898
899 /// Replace a block parameter with a new value of type `ty`.
900 ///
901 /// The `old_value` must be an attached block parameter. It is removed from its place in the list
902 /// of parameters and replaced by a new value of type `new_type`. The new value gets the same
903 /// position in the list, and other parameters are not disturbed.
904 ///
905 /// The old value is left detached, so it should probably be changed into something else.
906 ///
907 /// Returns the new value.
replace_block_param(&mut self, old_value: Value, new_type: Type) -> Value908 pub fn replace_block_param(&mut self, old_value: Value, new_type: Type) -> Value {
909 // Create new value identical to the old one except for the type.
910 let (block, num) = if let ValueData::Param { num, block, .. } = self.values[old_value] {
911 (block, num)
912 } else {
913 panic!("{} must be a block parameter", old_value);
914 };
915 let new_arg = self.make_value(ValueData::Param {
916 ty: new_type,
917 num,
918 block,
919 });
920
921 self.blocks[block]
922 .params
923 .as_mut_slice(&mut self.value_lists)[num as usize] = new_arg;
924 new_arg
925 }
926
927 /// Detach all the parameters from `block` and return them as a `ValueList`.
928 ///
929 /// This is a quite low-level operation. Sensible things to do with the detached block parameters
930 /// is to put them back on the same block with `attach_block_param()` or change them into aliases
931 /// with `change_to_alias()`.
detach_block_params(&mut self, block: Block) -> ValueList932 pub fn detach_block_params(&mut self, block: Block) -> ValueList {
933 self.blocks[block].params.take()
934 }
935 }
936
937 /// Contents of a basic block.
938 ///
939 /// Parameters on a basic block are values that dominate everything in the block. All
940 /// branches to this block must provide matching arguments, and the arguments to the entry block must
941 /// match the function arguments.
942 #[derive(Clone)]
943 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
944 struct BlockData {
945 /// List of parameters to this block.
946 params: ValueList,
947 }
948
949 impl BlockData {
new() -> Self950 fn new() -> Self {
951 Self {
952 params: ValueList::new(),
953 }
954 }
955 }
956
957 /// Object that can display an instruction.
958 pub struct DisplayInst<'a>(&'a DataFlowGraph, Option<&'a dyn TargetIsa>, Inst);
959
960 impl<'a> fmt::Display for DisplayInst<'a> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result961 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
962 let dfg = self.0;
963 let isa = self.1;
964 let inst = self.2;
965
966 if let Some((first, rest)) = dfg.inst_results(inst).split_first() {
967 write!(f, "{}", first)?;
968 for v in rest {
969 write!(f, ", {}", v)?;
970 }
971 write!(f, " = ")?;
972 }
973
974 let typevar = dfg.ctrl_typevar(inst);
975 if typevar.is_invalid() {
976 write!(f, "{}", dfg[inst].opcode())?;
977 } else {
978 write!(f, "{}.{}", dfg[inst].opcode(), typevar)?;
979 }
980 write_operands(f, dfg, isa, inst)
981 }
982 }
983
984 /// Parser routines. These routines should not be used outside the parser.
985 impl DataFlowGraph {
986 /// Set the type of a value. This is only for use in the parser, which needs
987 /// to create invalid values for index padding which may be reassigned later.
988 #[cold]
set_value_type_for_parser(&mut self, v: Value, t: Type)989 fn set_value_type_for_parser(&mut self, v: Value, t: Type) {
990 assert_eq!(
991 self.value_type(v),
992 types::INVALID,
993 "this function is only for assigning types to previously invalid values"
994 );
995 match self.values[v] {
996 ValueData::Inst { ref mut ty, .. }
997 | ValueData::Param { ref mut ty, .. }
998 | ValueData::Alias { ref mut ty, .. } => *ty = t,
999 }
1000 }
1001
1002 /// Create result values for `inst`, reusing the provided detached values.
1003 /// This is similar to `make_inst_results_reusing` except it's only for use
1004 /// in the parser, which needs to reuse previously invalid values.
1005 #[cold]
make_inst_results_for_parser( &mut self, inst: Inst, ctrl_typevar: Type, reuse: &[Value], ) -> usize1006 pub fn make_inst_results_for_parser(
1007 &mut self,
1008 inst: Inst,
1009 ctrl_typevar: Type,
1010 reuse: &[Value],
1011 ) -> usize {
1012 // Get the call signature if this is a function call.
1013 if let Some(sig) = self.call_signature(inst) {
1014 assert_eq!(
1015 self.insts[inst].opcode().constraints().num_fixed_results(),
1016 0
1017 );
1018 for res_idx in 0..self.signatures[sig].returns.len() {
1019 let ty = self.signatures[sig].returns[res_idx].value_type;
1020 if let Some(v) = reuse.get(res_idx) {
1021 self.set_value_type_for_parser(*v, ty);
1022 }
1023 }
1024 } else {
1025 let constraints = self.insts[inst].opcode().constraints();
1026 for res_idx in 0..constraints.num_fixed_results() {
1027 let ty = constraints.result_type(res_idx, ctrl_typevar);
1028 if let Some(v) = reuse.get(res_idx) {
1029 self.set_value_type_for_parser(*v, ty);
1030 }
1031 }
1032 }
1033
1034 self.make_inst_results_reusing(inst, ctrl_typevar, reuse.iter().map(|x| Some(*x)))
1035 }
1036
1037 /// Similar to `append_block_param`, append a parameter with type `ty` to
1038 /// `block`, but using value `val`. This is only for use by the parser to
1039 /// create parameters with specific values.
1040 #[cold]
append_block_param_for_parser(&mut self, block: Block, ty: Type, val: Value)1041 pub fn append_block_param_for_parser(&mut self, block: Block, ty: Type, val: Value) {
1042 let num = self.blocks[block].params.push(val, &mut self.value_lists);
1043 assert!(num <= u16::MAX as usize, "Too many parameters on block");
1044 self.values[val] = ValueData::Param {
1045 ty,
1046 num: num as u16,
1047 block,
1048 };
1049 }
1050
1051 /// Create a new value alias. This is only for use by the parser to create
1052 /// aliases with specific values, and the printer for testing.
1053 #[cold]
make_value_alias_for_serialization(&mut self, src: Value, dest: Value)1054 pub fn make_value_alias_for_serialization(&mut self, src: Value, dest: Value) {
1055 assert_ne!(src, Value::reserved_value());
1056 assert_ne!(dest, Value::reserved_value());
1057
1058 let ty = if self.values.is_valid(src) {
1059 self.value_type(src)
1060 } else {
1061 // As a special case, if we can't resolve the aliasee yet, use INVALID
1062 // temporarily. It will be resolved later in parsing.
1063 types::INVALID
1064 };
1065 let data = ValueData::Alias { ty, original: src };
1066 self.values[dest] = data;
1067 }
1068
1069 /// If `v` is already defined as an alias, return its destination value.
1070 /// Otherwise return None. This allows the parser to coalesce identical
1071 /// alias definitions, and the printer to identify an alias's immediate target.
1072 #[cold]
value_alias_dest_for_serialization(&self, v: Value) -> Option<Value>1073 pub fn value_alias_dest_for_serialization(&self, v: Value) -> Option<Value> {
1074 if let ValueData::Alias { original, .. } = self.values[v] {
1075 Some(original)
1076 } else {
1077 None
1078 }
1079 }
1080
1081 /// Compute the type of an alias. This is only for use in the parser.
1082 /// Returns false if an alias cycle was encountered.
1083 #[cold]
set_alias_type_for_parser(&mut self, v: Value) -> bool1084 pub fn set_alias_type_for_parser(&mut self, v: Value) -> bool {
1085 if let Some(resolved) = maybe_resolve_aliases(&self.values, v) {
1086 let old_ty = self.value_type(v);
1087 let new_ty = self.value_type(resolved);
1088 if old_ty == types::INVALID {
1089 self.set_value_type_for_parser(v, new_ty);
1090 } else {
1091 assert_eq!(old_ty, new_ty);
1092 }
1093 true
1094 } else {
1095 false
1096 }
1097 }
1098
1099 /// Create an invalid value, to pad the index space. This is only for use by
1100 /// the parser to pad out the value index space.
1101 #[cold]
make_invalid_value_for_parser(&mut self)1102 pub fn make_invalid_value_for_parser(&mut self) {
1103 let data = ValueData::Alias {
1104 ty: types::INVALID,
1105 original: Value::reserved_value(),
1106 };
1107 self.make_value(data);
1108 }
1109
1110 /// Check if a value reference is valid, while being aware of aliases which
1111 /// may be unresolved while parsing.
1112 #[cold]
value_is_valid_for_parser(&self, v: Value) -> bool1113 pub fn value_is_valid_for_parser(&self, v: Value) -> bool {
1114 if !self.value_is_valid(v) {
1115 return false;
1116 }
1117 if let ValueData::Alias { ty, .. } = self.values[v] {
1118 ty != types::INVALID
1119 } else {
1120 true
1121 }
1122 }
1123 }
1124
1125 #[cfg(test)]
1126 mod tests {
1127 use super::*;
1128 use crate::cursor::{Cursor, FuncCursor};
1129 use crate::ir::types;
1130 use crate::ir::{Function, InstructionData, Opcode, TrapCode};
1131 use alloc::string::ToString;
1132
1133 #[test]
make_inst()1134 fn make_inst() {
1135 let mut dfg = DataFlowGraph::new();
1136
1137 let idata = InstructionData::UnaryImm {
1138 opcode: Opcode::Iconst,
1139 imm: 0.into(),
1140 };
1141 let inst = dfg.make_inst(idata);
1142
1143 dfg.make_inst_results(inst, types::I32);
1144 assert_eq!(inst.to_string(), "inst0");
1145 assert_eq!(
1146 dfg.display_inst(inst, None).to_string(),
1147 "v0 = iconst.i32 0"
1148 );
1149
1150 // Immutable reference resolution.
1151 {
1152 let immdfg = &dfg;
1153 let ins = &immdfg[inst];
1154 assert_eq!(ins.opcode(), Opcode::Iconst);
1155 }
1156
1157 // Results.
1158 let val = dfg.first_result(inst);
1159 assert_eq!(dfg.inst_results(inst), &[val]);
1160
1161 assert_eq!(dfg.value_def(val), ValueDef::Result(inst, 0));
1162 assert_eq!(dfg.value_type(val), types::I32);
1163
1164 // Replacing results.
1165 assert!(dfg.value_is_attached(val));
1166 let v2 = dfg.replace_result(val, types::F64);
1167 assert!(!dfg.value_is_attached(val));
1168 assert!(dfg.value_is_attached(v2));
1169 assert_eq!(dfg.inst_results(inst), &[v2]);
1170 assert_eq!(dfg.value_def(v2), ValueDef::Result(inst, 0));
1171 assert_eq!(dfg.value_type(v2), types::F64);
1172 }
1173
1174 #[test]
no_results()1175 fn no_results() {
1176 let mut dfg = DataFlowGraph::new();
1177
1178 let idata = InstructionData::Trap {
1179 opcode: Opcode::Trap,
1180 code: TrapCode::User(0),
1181 };
1182 let inst = dfg.make_inst(idata);
1183 assert_eq!(dfg.display_inst(inst, None).to_string(), "trap user0");
1184
1185 // Result slice should be empty.
1186 assert_eq!(dfg.inst_results(inst), &[]);
1187 }
1188
1189 #[test]
block()1190 fn block() {
1191 let mut dfg = DataFlowGraph::new();
1192
1193 let block = dfg.make_block();
1194 assert_eq!(block.to_string(), "block0");
1195 assert_eq!(dfg.num_block_params(block), 0);
1196 assert_eq!(dfg.block_params(block), &[]);
1197 assert!(dfg.detach_block_params(block).is_empty());
1198 assert_eq!(dfg.num_block_params(block), 0);
1199 assert_eq!(dfg.block_params(block), &[]);
1200
1201 let arg1 = dfg.append_block_param(block, types::F32);
1202 assert_eq!(arg1.to_string(), "v0");
1203 assert_eq!(dfg.num_block_params(block), 1);
1204 assert_eq!(dfg.block_params(block), &[arg1]);
1205
1206 let arg2 = dfg.append_block_param(block, types::I16);
1207 assert_eq!(arg2.to_string(), "v1");
1208 assert_eq!(dfg.num_block_params(block), 2);
1209 assert_eq!(dfg.block_params(block), &[arg1, arg2]);
1210
1211 assert_eq!(dfg.value_def(arg1), ValueDef::Param(block, 0));
1212 assert_eq!(dfg.value_def(arg2), ValueDef::Param(block, 1));
1213 assert_eq!(dfg.value_type(arg1), types::F32);
1214 assert_eq!(dfg.value_type(arg2), types::I16);
1215
1216 // Swap the two block parameters.
1217 let vlist = dfg.detach_block_params(block);
1218 assert_eq!(dfg.num_block_params(block), 0);
1219 assert_eq!(dfg.block_params(block), &[]);
1220 assert_eq!(vlist.as_slice(&dfg.value_lists), &[arg1, arg2]);
1221 dfg.attach_block_param(block, arg2);
1222 let arg3 = dfg.append_block_param(block, types::I32);
1223 dfg.attach_block_param(block, arg1);
1224 assert_eq!(dfg.block_params(block), &[arg2, arg3, arg1]);
1225 }
1226
1227 #[test]
replace_block_params()1228 fn replace_block_params() {
1229 let mut dfg = DataFlowGraph::new();
1230
1231 let block = dfg.make_block();
1232 let arg1 = dfg.append_block_param(block, types::F32);
1233
1234 let new1 = dfg.replace_block_param(arg1, types::I64);
1235 assert_eq!(dfg.value_type(arg1), types::F32);
1236 assert_eq!(dfg.value_type(new1), types::I64);
1237 assert_eq!(dfg.block_params(block), &[new1]);
1238
1239 dfg.attach_block_param(block, arg1);
1240 assert_eq!(dfg.block_params(block), &[new1, arg1]);
1241
1242 let new2 = dfg.replace_block_param(arg1, types::I8);
1243 assert_eq!(dfg.value_type(arg1), types::F32);
1244 assert_eq!(dfg.value_type(new2), types::I8);
1245 assert_eq!(dfg.block_params(block), &[new1, new2]);
1246
1247 dfg.attach_block_param(block, arg1);
1248 assert_eq!(dfg.block_params(block), &[new1, new2, arg1]);
1249
1250 let new3 = dfg.replace_block_param(new2, types::I16);
1251 assert_eq!(dfg.value_type(new1), types::I64);
1252 assert_eq!(dfg.value_type(new2), types::I8);
1253 assert_eq!(dfg.value_type(new3), types::I16);
1254 assert_eq!(dfg.block_params(block), &[new1, new3, arg1]);
1255 }
1256
1257 #[test]
swap_remove_block_params()1258 fn swap_remove_block_params() {
1259 let mut dfg = DataFlowGraph::new();
1260
1261 let block = dfg.make_block();
1262 let arg1 = dfg.append_block_param(block, types::F32);
1263 let arg2 = dfg.append_block_param(block, types::F32);
1264 let arg3 = dfg.append_block_param(block, types::F32);
1265 assert_eq!(dfg.block_params(block), &[arg1, arg2, arg3]);
1266
1267 dfg.swap_remove_block_param(arg1);
1268 assert_eq!(dfg.value_is_attached(arg1), false);
1269 assert_eq!(dfg.value_is_attached(arg2), true);
1270 assert_eq!(dfg.value_is_attached(arg3), true);
1271 assert_eq!(dfg.block_params(block), &[arg3, arg2]);
1272 dfg.swap_remove_block_param(arg2);
1273 assert_eq!(dfg.value_is_attached(arg2), false);
1274 assert_eq!(dfg.value_is_attached(arg3), true);
1275 assert_eq!(dfg.block_params(block), &[arg3]);
1276 dfg.swap_remove_block_param(arg3);
1277 assert_eq!(dfg.value_is_attached(arg3), false);
1278 assert_eq!(dfg.block_params(block), &[]);
1279 }
1280
1281 #[test]
aliases()1282 fn aliases() {
1283 use crate::ir::InstBuilder;
1284
1285 let mut func = Function::new();
1286 let block0 = func.dfg.make_block();
1287 let mut pos = FuncCursor::new(&mut func);
1288 pos.insert_block(block0);
1289
1290 // Build a little test program.
1291 let v1 = pos.ins().iconst(types::I32, 42);
1292
1293 // Make sure we can resolve value aliases even when values is empty.
1294 assert_eq!(pos.func.dfg.resolve_aliases(v1), v1);
1295
1296 let arg0 = pos.func.dfg.append_block_param(block0, types::I32);
1297 let (s, c) = pos.ins().iadd_ifcout(v1, arg0);
1298 let iadd = match pos.func.dfg.value_def(s) {
1299 ValueDef::Result(i, 0) => i,
1300 _ => panic!(),
1301 };
1302
1303 // Remove `c` from the result list.
1304 pos.func.dfg.clear_results(iadd);
1305 pos.func.dfg.attach_result(iadd, s);
1306
1307 // Replace `iadd_ifcout` with a normal `iadd` and an `ifcmp`.
1308 pos.func.dfg.replace(iadd).iadd(v1, arg0);
1309 let c2 = pos.ins().ifcmp(s, v1);
1310 pos.func.dfg.change_to_alias(c, c2);
1311
1312 assert_eq!(pos.func.dfg.resolve_aliases(c2), c2);
1313 assert_eq!(pos.func.dfg.resolve_aliases(c), c2);
1314
1315 // Make a copy of the alias.
1316 let c3 = pos.ins().copy(c);
1317 // This does not see through copies.
1318 assert_eq!(pos.func.dfg.resolve_aliases(c3), c3);
1319 }
1320 }
1321