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