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::dynamic_type::{DynamicTypeData, DynamicTypes}; 7 use crate::ir::instructions::{CallInfo, InstructionData}; 8 use crate::ir::pcc::Fact; 9 use crate::ir::user_stack_maps::{UserStackMapEntry, UserStackMapEntryVec}; 10 use crate::ir::{ 11 Block, BlockArg, BlockCall, ConstantData, ConstantPool, DynamicType, ExceptionTables, 12 ExtFuncData, FuncRef, Immediate, Inst, JumpTables, RelSourceLoc, SigRef, Signature, Type, 13 Value, ValueLabelAssignments, ValueList, ValueListPool, types, 14 }; 15 use crate::packed_option::ReservedValue; 16 use crate::write::write_operands; 17 use core::fmt; 18 use core::iter; 19 use core::mem; 20 use core::ops::{Index, IndexMut}; 21 use core::u16; 22 23 use alloc::collections::BTreeMap; 24 #[cfg(feature = "enable-serde")] 25 use serde_derive::{Deserialize, Serialize}; 26 use smallvec::SmallVec; 27 28 /// Storage for instructions within the DFG. 29 #[derive(Clone, PartialEq, Hash)] 30 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))] 31 pub struct Insts(PrimaryMap<Inst, InstructionData>); 32 33 /// Allow immutable access to instructions via indexing. 34 impl Index<Inst> for Insts { 35 type Output = InstructionData; 36 37 fn index(&self, inst: Inst) -> &InstructionData { 38 self.0.index(inst) 39 } 40 } 41 42 /// Allow mutable access to instructions via indexing. 43 impl IndexMut<Inst> for Insts { 44 fn index_mut(&mut self, inst: Inst) -> &mut InstructionData { 45 self.0.index_mut(inst) 46 } 47 } 48 49 /// Storage for basic blocks within the DFG. 50 #[derive(Clone, PartialEq, Hash)] 51 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))] 52 pub struct Blocks(PrimaryMap<Block, BlockData>); 53 54 impl Blocks { 55 /// Create a new basic block. 56 pub fn add(&mut self) -> Block { 57 self.0.push(BlockData::new()) 58 } 59 60 /// Get the total number of basic blocks created in this function, whether they are 61 /// currently inserted in the layout or not. 62 /// 63 /// This is intended for use with `SecondaryMap::with_capacity`. 64 pub fn len(&self) -> usize { 65 self.0.len() 66 } 67 68 /// Returns `true` if the given block reference is valid. 69 pub fn is_valid(&self, block: Block) -> bool { 70 self.0.is_valid(block) 71 } 72 } 73 74 impl Index<Block> for Blocks { 75 type Output = BlockData; 76 77 fn index(&self, block: Block) -> &BlockData { 78 &self.0[block] 79 } 80 } 81 82 impl IndexMut<Block> for Blocks { 83 fn index_mut(&mut self, block: Block) -> &mut BlockData { 84 &mut self.0[block] 85 } 86 } 87 88 /// A data flow graph defines all instructions and basic blocks in a function as well as 89 /// the data flow dependencies between them. The DFG also tracks values which can be either 90 /// instruction results or block parameters. 91 /// 92 /// The layout of blocks in the function and of instructions in each block is recorded by the 93 /// `Layout` data structure which forms the other half of the function representation. 94 /// 95 #[derive(Clone, PartialEq, Hash)] 96 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))] 97 pub struct DataFlowGraph { 98 /// Data about all of the instructions in the function, including opcodes and operands. 99 /// The instructions in this map are not in program order. That is tracked by `Layout`, along 100 /// with the block containing each instruction. 101 pub insts: Insts, 102 103 /// List of result values for each instruction. 104 /// 105 /// This map gets resized automatically by `make_inst()` so it is always in sync with the 106 /// primary `insts` map. 107 results: SecondaryMap<Inst, ValueList>, 108 109 /// User-defined stack maps. 110 /// 111 /// Not to be confused with the stack maps that `regalloc2` produces. These 112 /// are defined by the user in `cranelift-frontend`. These will eventually 113 /// replace the stack maps support in `regalloc2`, but in the name of 114 /// incrementalism and avoiding gigantic PRs that completely overhaul 115 /// Cranelift and Wasmtime at the same time, we are allowing them to live in 116 /// parallel for the time being. 117 user_stack_maps: alloc::collections::BTreeMap<Inst, UserStackMapEntryVec>, 118 119 /// basic blocks in the function and their parameters. 120 /// 121 /// This map is not in program order. That is handled by `Layout`, and so is the sequence of 122 /// instructions contained in each block. 123 pub blocks: Blocks, 124 125 /// Dynamic types created. 126 pub dynamic_types: DynamicTypes, 127 128 /// Memory pool of value lists. 129 /// 130 /// The `ValueList` references into this pool appear in many places: 131 /// 132 /// - Instructions in `insts` that don't have room for their entire argument list inline. 133 /// - Instruction result values in `results`. 134 /// - block parameters in `blocks`. 135 pub value_lists: ValueListPool, 136 137 /// Primary value table with entries for all values. 138 values: PrimaryMap<Value, ValueDataPacked>, 139 140 /// Facts: proof-carrying-code assertions about values. 141 pub facts: SecondaryMap<Value, Option<Fact>>, 142 143 /// Function signature table. These signatures are referenced by indirect call instructions as 144 /// well as the external function references. 145 pub signatures: PrimaryMap<SigRef, Signature>, 146 147 /// External function references. These are functions that can be called directly. 148 pub ext_funcs: PrimaryMap<FuncRef, ExtFuncData>, 149 150 /// Saves Value labels. 151 pub values_labels: Option<BTreeMap<Value, ValueLabelAssignments>>, 152 153 /// Constants used within the function. 154 pub constants: ConstantPool, 155 156 /// Stores large immediates that otherwise will not fit on InstructionData. 157 pub immediates: PrimaryMap<Immediate, ConstantData>, 158 159 /// Jump tables used in this function. 160 pub jump_tables: JumpTables, 161 162 /// Exception tables used in this function. 163 pub exception_tables: ExceptionTables, 164 } 165 166 impl DataFlowGraph { 167 /// Create a new empty `DataFlowGraph`. 168 pub fn new() -> Self { 169 Self { 170 insts: Insts(PrimaryMap::new()), 171 results: SecondaryMap::new(), 172 user_stack_maps: alloc::collections::BTreeMap::new(), 173 blocks: Blocks(PrimaryMap::new()), 174 dynamic_types: DynamicTypes::new(), 175 value_lists: ValueListPool::new(), 176 values: PrimaryMap::new(), 177 facts: SecondaryMap::new(), 178 signatures: PrimaryMap::new(), 179 ext_funcs: PrimaryMap::new(), 180 values_labels: None, 181 constants: ConstantPool::new(), 182 immediates: PrimaryMap::new(), 183 jump_tables: JumpTables::new(), 184 exception_tables: ExceptionTables::new(), 185 } 186 } 187 188 /// Clear everything. 189 pub fn clear(&mut self) { 190 self.insts.0.clear(); 191 self.results.clear(); 192 self.user_stack_maps.clear(); 193 self.blocks.0.clear(); 194 self.dynamic_types.clear(); 195 self.value_lists.clear(); 196 self.values.clear(); 197 self.signatures.clear(); 198 self.ext_funcs.clear(); 199 self.values_labels = None; 200 self.constants.clear(); 201 self.immediates.clear(); 202 self.jump_tables.clear(); 203 self.facts.clear(); 204 } 205 206 /// Get the total number of instructions created in this function, whether they are currently 207 /// inserted in the layout or not. 208 /// 209 /// This is intended for use with `SecondaryMap::with_capacity`. 210 pub fn num_insts(&self) -> usize { 211 self.insts.0.len() 212 } 213 214 /// Returns `true` if the given instruction reference is valid. 215 pub fn inst_is_valid(&self, inst: Inst) -> bool { 216 self.insts.0.is_valid(inst) 217 } 218 219 /// Get the total number of basic blocks created in this function, whether they are 220 /// currently inserted in the layout or not. 221 /// 222 /// This is intended for use with `SecondaryMap::with_capacity`. 223 pub fn num_blocks(&self) -> usize { 224 self.blocks.len() 225 } 226 227 /// Returns `true` if the given block reference is valid. 228 pub fn block_is_valid(&self, block: Block) -> bool { 229 self.blocks.is_valid(block) 230 } 231 232 /// Make a BlockCall, bundling together the block and its arguments. 233 pub fn block_call<'a>( 234 &mut self, 235 block: Block, 236 args: impl IntoIterator<Item = &'a BlockArg>, 237 ) -> BlockCall { 238 BlockCall::new(block, args.into_iter().copied(), &mut self.value_lists) 239 } 240 241 /// Get the total number of values. 242 pub fn num_values(&self) -> usize { 243 self.values.len() 244 } 245 246 /// Get an iterator over all values and their definitions. 247 pub fn values_and_defs(&self) -> impl Iterator<Item = (Value, ValueDef)> + '_ { 248 self.values().map(|value| (value, self.value_def(value))) 249 } 250 251 /// Starts collection of debug information. 252 pub fn collect_debug_info(&mut self) { 253 if self.values_labels.is_none() { 254 self.values_labels = Some(Default::default()); 255 } 256 } 257 258 /// Inserts a `ValueLabelAssignments::Alias` for `to_alias` if debug info 259 /// collection is enabled. 260 pub fn add_value_label_alias(&mut self, to_alias: Value, from: RelSourceLoc, value: Value) { 261 if let Some(values_labels) = self.values_labels.as_mut() { 262 values_labels.insert(to_alias, ir::ValueLabelAssignments::Alias { from, value }); 263 } 264 } 265 } 266 267 /// Resolve value aliases. 268 /// 269 /// Find the original SSA value that `value` aliases, or None if an 270 /// alias cycle is detected. 271 fn maybe_resolve_aliases( 272 values: &PrimaryMap<Value, ValueDataPacked>, 273 value: Value, 274 ) -> Option<Value> { 275 let mut v = value; 276 277 // Note that values may be empty here. 278 for _ in 0..=values.len() { 279 if let ValueData::Alias { original, .. } = ValueData::from(values[v]) { 280 v = original; 281 } else { 282 return Some(v); 283 } 284 } 285 286 None 287 } 288 289 /// Resolve value aliases. 290 /// 291 /// Find the original SSA value that `value` aliases. 292 fn resolve_aliases(values: &PrimaryMap<Value, ValueDataPacked>, value: Value) -> Value { 293 if let Some(v) = maybe_resolve_aliases(values, value) { 294 v 295 } else { 296 panic!("Value alias loop detected for {value}"); 297 } 298 } 299 300 /// Iterator over all Values in a DFG. 301 pub struct Values<'a> { 302 inner: entity::Iter<'a, Value, ValueDataPacked>, 303 } 304 305 /// Check for non-values. 306 fn valid_valuedata(data: ValueDataPacked) -> bool { 307 let data = ValueData::from(data); 308 if let ValueData::Alias { 309 ty: types::INVALID, 310 original, 311 } = data 312 { 313 if original == Value::reserved_value() { 314 return false; 315 } 316 } 317 true 318 } 319 320 impl<'a> Iterator for Values<'a> { 321 type Item = Value; 322 323 fn next(&mut self) -> Option<Self::Item> { 324 self.inner 325 .by_ref() 326 .find(|kv| valid_valuedata(*kv.1)) 327 .map(|kv| kv.0) 328 } 329 } 330 331 /// Handling values. 332 /// 333 /// Values are either block parameters or instruction results. 334 impl DataFlowGraph { 335 /// Allocate an extended value entry. 336 fn make_value(&mut self, data: ValueData) -> Value { 337 self.values.push(data.into()) 338 } 339 340 /// Get an iterator over all values. 341 pub fn values<'a>(&'a self) -> Values<'a> { 342 Values { 343 inner: self.values.iter(), 344 } 345 } 346 347 /// Check if a value reference is valid. 348 pub fn value_is_valid(&self, v: Value) -> bool { 349 self.values.is_valid(v) 350 } 351 352 /// Check whether a value is valid and not an alias. 353 pub fn value_is_real(&self, value: Value) -> bool { 354 // Deleted or unused values are also stored as aliases so this excludes 355 // those as well. 356 self.value_is_valid(value) && !matches!(self.values[value].into(), ValueData::Alias { .. }) 357 } 358 359 /// Get the type of a value. 360 pub fn value_type(&self, v: Value) -> Type { 361 self.values[v].ty() 362 } 363 364 /// Get the definition of a value. 365 /// 366 /// This is either the instruction that defined it or the Block that has the value as an 367 /// parameter. 368 pub fn value_def(&self, v: Value) -> ValueDef { 369 match ValueData::from(self.values[v]) { 370 ValueData::Inst { inst, num, .. } => ValueDef::Result(inst, num as usize), 371 ValueData::Param { block, num, .. } => ValueDef::Param(block, num as usize), 372 ValueData::Alias { original, .. } => { 373 // Make sure we only recurse one level. `resolve_aliases` has safeguards to 374 // detect alias loops without overrunning the stack. 375 self.value_def(self.resolve_aliases(original)) 376 } 377 ValueData::Union { x, y, .. } => ValueDef::Union(x, y), 378 } 379 } 380 381 /// Determine if `v` is an attached instruction result / block parameter. 382 /// 383 /// An attached value can't be attached to something else without first being detached. 384 /// 385 /// Value aliases are not considered to be attached to anything. Use `resolve_aliases()` to 386 /// determine if the original aliased value is attached. 387 pub fn value_is_attached(&self, v: Value) -> bool { 388 use self::ValueData::*; 389 match ValueData::from(self.values[v]) { 390 Inst { inst, num, .. } => Some(&v) == self.inst_results(inst).get(num as usize), 391 Param { block, num, .. } => Some(&v) == self.block_params(block).get(num as usize), 392 Alias { .. } => false, 393 Union { .. } => false, 394 } 395 } 396 397 /// Resolve value aliases. 398 /// 399 /// Find the original SSA value that `value` aliases. 400 pub fn resolve_aliases(&self, value: Value) -> Value { 401 resolve_aliases(&self.values, value) 402 } 403 404 /// Replace all uses of value aliases with their resolved values, and delete 405 /// the aliases. 406 pub fn resolve_all_aliases(&mut self) { 407 let invalid_value = ValueDataPacked::from(ValueData::Alias { 408 ty: types::INVALID, 409 original: Value::reserved_value(), 410 }); 411 412 // Rewrite each chain of aliases. Update every alias along the chain 413 // into an alias directly to the final value. Due to updating every 414 // alias that it looks at, this loop runs in time linear in the number 415 // of values. 416 for mut src in self.values.keys() { 417 let value_data = self.values[src]; 418 if value_data == invalid_value { 419 continue; 420 } 421 if let ValueData::Alias { mut original, .. } = value_data.into() { 422 // We don't use the type after this, we just need some place to 423 // store the resolved aliases temporarily. 424 let resolved = ValueDataPacked::from(ValueData::Alias { 425 ty: types::INVALID, 426 original: resolve_aliases(&self.values, original), 427 }); 428 // Walk the chain again, splatting the new alias everywhere. 429 // resolve_aliases panics if there's an alias cycle, so we don't 430 // need to guard against cycles here. 431 loop { 432 self.values[src] = resolved; 433 src = original; 434 if let ValueData::Alias { original: next, .. } = self.values[src].into() { 435 original = next; 436 } else { 437 break; 438 } 439 } 440 } 441 } 442 443 // Now aliases don't point to other aliases, so we can replace any use 444 // of an alias with the final value in constant time. 445 446 // Rewrite InstructionData in `self.insts`. 447 for inst in self.insts.0.values_mut() { 448 inst.map_values( 449 &mut self.value_lists, 450 &mut self.jump_tables, 451 &mut self.exception_tables, 452 |arg| { 453 if let ValueData::Alias { original, .. } = self.values[arg].into() { 454 original 455 } else { 456 arg 457 } 458 }, 459 ); 460 } 461 462 // - `results` and block-params in `blocks` are not aliases, by 463 // definition. 464 // - `dynamic_types` has no values. 465 // - `value_lists` can only be accessed via references from elsewhere. 466 // - `values` only has value references in aliases (which we've 467 // removed), and unions (but the egraph pass ensures there are no 468 // aliases before creating unions). 469 470 // Merge `facts` from any alias onto the aliased value. Note that if 471 // there was a chain of aliases, at this point every alias that was in 472 // the chain points to the same final value, so their facts will all be 473 // merged together. 474 for value in self.facts.keys() { 475 if let ValueData::Alias { original, .. } = self.values[value].into() { 476 if let Some(new_fact) = self.facts[value].take() { 477 match &mut self.facts[original] { 478 Some(old_fact) => *old_fact = Fact::intersect(old_fact, &new_fact), 479 old_fact => *old_fact = Some(new_fact), 480 } 481 } 482 } 483 } 484 485 // - `signatures` and `ext_funcs` have no values. 486 487 if let Some(values_labels) = &mut self.values_labels { 488 // Debug info is best-effort. If any is attached to value aliases, 489 // just discard it. 490 values_labels.retain(|&k, _| !matches!(self.values[k].into(), ValueData::Alias { .. })); 491 492 // If debug-info says a value should have the same labels as another 493 // value, then make sure that target is not a value alias. 494 for value_label in values_labels.values_mut() { 495 if let ValueLabelAssignments::Alias { value, .. } = value_label { 496 if let ValueData::Alias { original, .. } = self.values[*value].into() { 497 *value = original; 498 } 499 } 500 } 501 } 502 503 // - `constants` and `immediates` have no values. 504 // - `jump_tables` is updated together with instruction-data above. 505 506 // Delete all aliases now that there are no uses left. 507 for value in self.values.values_mut() { 508 if let ValueData::Alias { .. } = ValueData::from(*value) { 509 *value = invalid_value; 510 } 511 } 512 } 513 514 /// Turn a value into an alias of another. 515 /// 516 /// Change the `dest` value to behave as an alias of `src`. This means that all uses of `dest` 517 /// will behave as if they used that value `src`. 518 /// 519 /// The `dest` value can't be attached to an instruction or block. 520 pub fn change_to_alias(&mut self, dest: Value, src: Value) { 521 debug_assert!(!self.value_is_attached(dest)); 522 // Try to create short alias chains by finding the original source value. 523 // This also avoids the creation of loops. 524 let original = self.resolve_aliases(src); 525 debug_assert_ne!( 526 dest, original, 527 "Aliasing {dest} to {src} would create a loop" 528 ); 529 let ty = self.value_type(original); 530 debug_assert_eq!( 531 self.value_type(dest), 532 ty, 533 "Aliasing {} to {} would change its type {} to {}", 534 dest, 535 src, 536 self.value_type(dest), 537 ty 538 ); 539 debug_assert_ne!(ty, types::INVALID); 540 541 self.values[dest] = ValueData::Alias { ty, original }.into(); 542 } 543 544 /// Replace the results of one instruction with aliases to the results of another. 545 /// 546 /// Change all the results of `dest_inst` to behave as aliases of 547 /// corresponding results of `src_inst`, as if calling change_to_alias for 548 /// each. 549 /// 550 /// After calling this instruction, `dest_inst` will have had its results 551 /// cleared, so it likely needs to be removed from the graph. 552 /// 553 pub fn replace_with_aliases(&mut self, dest_inst: Inst, original_inst: Inst) { 554 debug_assert_ne!( 555 dest_inst, original_inst, 556 "Replacing {dest_inst} with itself would create a loop" 557 ); 558 559 let dest_results = self.results[dest_inst].as_slice(&self.value_lists); 560 let original_results = self.results[original_inst].as_slice(&self.value_lists); 561 562 debug_assert_eq!( 563 dest_results.len(), 564 original_results.len(), 565 "Replacing {dest_inst} with {original_inst} would produce a different number of results." 566 ); 567 568 for (&dest, &original) in dest_results.iter().zip(original_results) { 569 let ty = self.value_type(original); 570 debug_assert_eq!( 571 self.value_type(dest), 572 ty, 573 "Aliasing {} to {} would change its type {} to {}", 574 dest, 575 original, 576 self.value_type(dest), 577 ty 578 ); 579 debug_assert_ne!(ty, types::INVALID); 580 581 self.values[dest] = ValueData::Alias { ty, original }.into(); 582 } 583 584 self.clear_results(dest_inst); 585 } 586 587 /// Get the stack map entries associated with the given instruction. 588 pub fn user_stack_map_entries(&self, inst: Inst) -> Option<&[UserStackMapEntry]> { 589 self.user_stack_maps.get(&inst).map(|es| &**es) 590 } 591 592 /// Append a new stack map entry for the given call instruction. 593 /// 594 /// # Panics 595 /// 596 /// Panics if the given instruction is not a (non-tail) call instruction. 597 pub fn append_user_stack_map_entry(&mut self, inst: Inst, entry: UserStackMapEntry) { 598 let opcode = self.insts[inst].opcode(); 599 assert!(opcode.is_safepoint()); 600 self.user_stack_maps.entry(inst).or_default().push(entry); 601 } 602 } 603 604 /// Where did a value come from? 605 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 606 pub enum ValueDef { 607 /// Value is the n'th result of an instruction. 608 Result(Inst, usize), 609 /// Value is the n'th parameter to a block. 610 Param(Block, usize), 611 /// Value is a union of two other values. 612 Union(Value, Value), 613 } 614 615 impl ValueDef { 616 /// Unwrap the instruction where the value was defined, or panic. 617 pub fn unwrap_inst(&self) -> Inst { 618 self.inst().expect("Value is not an instruction result") 619 } 620 621 /// Get the instruction where the value was defined, if any. 622 pub fn inst(&self) -> Option<Inst> { 623 match *self { 624 Self::Result(inst, _) => Some(inst), 625 _ => None, 626 } 627 } 628 629 /// Unwrap the block there the parameter is defined, or panic. 630 pub fn unwrap_block(&self) -> Block { 631 match *self { 632 Self::Param(block, _) => block, 633 _ => panic!("Value is not a block parameter"), 634 } 635 } 636 637 /// Get the number component of this definition. 638 /// 639 /// When multiple values are defined at the same program point, this indicates the index of 640 /// this value. 641 pub fn num(self) -> usize { 642 match self { 643 Self::Result(_, n) | Self::Param(_, n) => n, 644 Self::Union(_, _) => 0, 645 } 646 } 647 } 648 649 /// Internal table storage for extended values. 650 #[derive(Clone, Debug, PartialEq, Hash)] 651 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))] 652 enum ValueData { 653 /// Value is defined by an instruction. 654 Inst { ty: Type, num: u16, inst: Inst }, 655 656 /// Value is a block parameter. 657 Param { ty: Type, num: u16, block: Block }, 658 659 /// Value is an alias of another value. 660 /// An alias value can't be linked as an instruction result or block parameter. It is used as a 661 /// placeholder when the original instruction or block has been rewritten or modified. 662 Alias { ty: Type, original: Value }, 663 664 /// Union is a "fork" in representation: the value can be 665 /// represented as either of the values named here. This is used 666 /// for aegraph (acyclic egraph) representation in the DFG. 667 Union { ty: Type, x: Value, y: Value }, 668 } 669 670 /// Bit-packed version of ValueData, for efficiency. 671 /// 672 /// Layout: 673 /// 674 /// ```plain 675 /// | tag:2 | type:14 | x:24 | y:24 | 676 /// 677 /// Inst 00 ty inst output inst index 678 /// Param 01 ty blockparam num block index 679 /// Alias 10 ty 0 value index 680 /// Union 11 ty first value second value 681 /// ``` 682 #[derive(Clone, Copy, Debug, PartialEq, Hash)] 683 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))] 684 struct ValueDataPacked(u64); 685 686 /// Encodes a value in 0..2^32 into 0..2^n, where n is less than 32 687 /// (and is implied by `mask`), by translating 2^32-1 (0xffffffff) 688 /// into 2^n-1 and panic'ing on 2^n..2^32-1. 689 fn encode_narrow_field(x: u32, bits: u8) -> u32 { 690 let max = (1 << bits) - 1; 691 if x == 0xffff_ffff { 692 max 693 } else { 694 debug_assert!( 695 x < max, 696 "{x} does not fit into {bits} bits (must be less than {max} to \ 697 allow for a 0xffffffff sentinel)" 698 ); 699 x 700 } 701 } 702 703 /// The inverse of the above `encode_narrow_field`: unpacks 2^n-1 into 704 /// 2^32-1. 705 fn decode_narrow_field(x: u32, bits: u8) -> u32 { 706 if x == (1 << bits) - 1 { 0xffff_ffff } else { x } 707 } 708 709 impl ValueDataPacked { 710 const Y_SHIFT: u8 = 0; 711 const Y_BITS: u8 = 24; 712 const X_SHIFT: u8 = Self::Y_SHIFT + Self::Y_BITS; 713 const X_BITS: u8 = 24; 714 const TYPE_SHIFT: u8 = Self::X_SHIFT + Self::X_BITS; 715 const TYPE_BITS: u8 = 14; 716 const TAG_SHIFT: u8 = Self::TYPE_SHIFT + Self::TYPE_BITS; 717 const TAG_BITS: u8 = 2; 718 719 const TAG_INST: u64 = 0; 720 const TAG_PARAM: u64 = 1; 721 const TAG_ALIAS: u64 = 2; 722 const TAG_UNION: u64 = 3; 723 724 fn make(tag: u64, ty: Type, x: u32, y: u32) -> ValueDataPacked { 725 debug_assert!(tag < (1 << Self::TAG_BITS)); 726 debug_assert!(ty.repr() < (1 << Self::TYPE_BITS)); 727 728 let x = encode_narrow_field(x, Self::X_BITS); 729 let y = encode_narrow_field(y, Self::Y_BITS); 730 731 ValueDataPacked( 732 (tag << Self::TAG_SHIFT) 733 | ((ty.repr() as u64) << Self::TYPE_SHIFT) 734 | ((x as u64) << Self::X_SHIFT) 735 | ((y as u64) << Self::Y_SHIFT), 736 ) 737 } 738 739 #[inline(always)] 740 fn field(self, shift: u8, bits: u8) -> u64 { 741 (self.0 >> shift) & ((1 << bits) - 1) 742 } 743 744 #[inline(always)] 745 fn ty(self) -> Type { 746 let ty = self.field(ValueDataPacked::TYPE_SHIFT, ValueDataPacked::TYPE_BITS) as u16; 747 Type::from_repr(ty) 748 } 749 750 #[inline(always)] 751 fn set_type(&mut self, ty: Type) { 752 self.0 &= !(((1 << Self::TYPE_BITS) - 1) << Self::TYPE_SHIFT); 753 self.0 |= (ty.repr() as u64) << Self::TYPE_SHIFT; 754 } 755 } 756 757 impl From<ValueData> for ValueDataPacked { 758 fn from(data: ValueData) -> Self { 759 match data { 760 ValueData::Inst { ty, num, inst } => { 761 Self::make(Self::TAG_INST, ty, num.into(), inst.as_bits()) 762 } 763 ValueData::Param { ty, num, block } => { 764 Self::make(Self::TAG_PARAM, ty, num.into(), block.as_bits()) 765 } 766 ValueData::Alias { ty, original } => { 767 Self::make(Self::TAG_ALIAS, ty, 0, original.as_bits()) 768 } 769 ValueData::Union { ty, x, y } => { 770 Self::make(Self::TAG_UNION, ty, x.as_bits(), y.as_bits()) 771 } 772 } 773 } 774 } 775 776 impl From<ValueDataPacked> for ValueData { 777 fn from(data: ValueDataPacked) -> Self { 778 let tag = data.field(ValueDataPacked::TAG_SHIFT, ValueDataPacked::TAG_BITS); 779 let ty = u16::try_from(data.field(ValueDataPacked::TYPE_SHIFT, ValueDataPacked::TYPE_BITS)) 780 .expect("Mask should ensure result fits in a u16"); 781 let x = u32::try_from(data.field(ValueDataPacked::X_SHIFT, ValueDataPacked::X_BITS)) 782 .expect("Mask should ensure result fits in a u32"); 783 let y = u32::try_from(data.field(ValueDataPacked::Y_SHIFT, ValueDataPacked::Y_BITS)) 784 .expect("Mask should ensure result fits in a u32"); 785 786 let ty = Type::from_repr(ty); 787 match tag { 788 ValueDataPacked::TAG_INST => ValueData::Inst { 789 ty, 790 num: u16::try_from(x).expect("Inst result num should fit in u16"), 791 inst: Inst::from_bits(decode_narrow_field(y, ValueDataPacked::Y_BITS)), 792 }, 793 ValueDataPacked::TAG_PARAM => ValueData::Param { 794 ty, 795 num: u16::try_from(x).expect("Blockparam index should fit in u16"), 796 block: Block::from_bits(decode_narrow_field(y, ValueDataPacked::Y_BITS)), 797 }, 798 ValueDataPacked::TAG_ALIAS => ValueData::Alias { 799 ty, 800 original: Value::from_bits(decode_narrow_field(y, ValueDataPacked::Y_BITS)), 801 }, 802 ValueDataPacked::TAG_UNION => ValueData::Union { 803 ty, 804 x: Value::from_bits(decode_narrow_field(x, ValueDataPacked::X_BITS)), 805 y: Value::from_bits(decode_narrow_field(y, ValueDataPacked::Y_BITS)), 806 }, 807 _ => panic!("Invalid tag {} in ValueDataPacked 0x{:x}", tag, data.0), 808 } 809 } 810 } 811 812 /// Instructions. 813 /// 814 impl DataFlowGraph { 815 /// Create a new instruction. 816 /// 817 /// The type of the first result is indicated by `data.ty`. If the 818 /// instruction produces multiple results, also call 819 /// `make_inst_results` to allocate value table entries. (It is 820 /// always safe to call `make_inst_results`, regardless of how 821 /// many results the instruction has.) 822 pub fn make_inst(&mut self, data: InstructionData) -> Inst { 823 let n = self.num_insts() + 1; 824 self.results.resize(n); 825 self.insts.0.push(data) 826 } 827 828 /// Declares a dynamic vector type 829 pub fn make_dynamic_ty(&mut self, data: DynamicTypeData) -> DynamicType { 830 self.dynamic_types.push(data) 831 } 832 833 /// Returns an object that displays `inst`. 834 pub fn display_inst<'a>(&'a self, inst: Inst) -> DisplayInst<'a> { 835 DisplayInst(self, inst) 836 } 837 838 /// Returns an object that displays the given `value`'s defining instruction. 839 /// 840 /// Panics if the value is not defined by an instruction (i.e. it is a basic 841 /// block argument). 842 pub fn display_value_inst(&self, value: Value) -> DisplayInst<'_> { 843 match self.value_def(value) { 844 ir::ValueDef::Result(inst, _) => self.display_inst(inst), 845 ir::ValueDef::Param(_, _) => panic!("value is not defined by an instruction"), 846 ir::ValueDef::Union(_, _) => panic!("value is a union of two other values"), 847 } 848 } 849 850 /// Construct a read-only visitor context for the values of this instruction. 851 pub fn inst_values<'dfg>( 852 &'dfg self, 853 inst: Inst, 854 ) -> impl DoubleEndedIterator<Item = Value> + 'dfg { 855 self.inst_args(inst).iter().copied().chain( 856 self.insts[inst] 857 .branch_destination(&self.jump_tables, &self.exception_tables) 858 .into_iter() 859 .flat_map(|branch| { 860 branch 861 .args(&self.value_lists) 862 .filter_map(|arg| arg.as_value()) 863 }), 864 ) 865 } 866 867 /// Map a function over the values of the instruction. 868 pub fn map_inst_values<F>(&mut self, inst: Inst, body: F) 869 where 870 F: FnMut(Value) -> Value, 871 { 872 self.insts[inst].map_values( 873 &mut self.value_lists, 874 &mut self.jump_tables, 875 &mut self.exception_tables, 876 body, 877 ); 878 } 879 880 /// Overwrite the instruction's value references with values from the iterator. 881 /// NOTE: the iterator provided is expected to yield at least as many values as the instruction 882 /// currently has. 883 pub fn overwrite_inst_values<I>(&mut self, inst: Inst, mut values: I) 884 where 885 I: Iterator<Item = Value>, 886 { 887 self.insts[inst].map_values( 888 &mut self.value_lists, 889 &mut self.jump_tables, 890 &mut self.exception_tables, 891 |_| values.next().unwrap(), 892 ); 893 } 894 895 /// Get all value arguments on `inst` as a slice. 896 pub fn inst_args(&self, inst: Inst) -> &[Value] { 897 self.insts[inst].arguments(&self.value_lists) 898 } 899 900 /// Get all value arguments on `inst` as a mutable slice. 901 pub fn inst_args_mut(&mut self, inst: Inst) -> &mut [Value] { 902 self.insts[inst].arguments_mut(&mut self.value_lists) 903 } 904 905 /// Get the fixed value arguments on `inst` as a slice. 906 pub fn inst_fixed_args(&self, inst: Inst) -> &[Value] { 907 let num_fixed_args = self.insts[inst] 908 .opcode() 909 .constraints() 910 .num_fixed_value_arguments(); 911 &self.inst_args(inst)[..num_fixed_args] 912 } 913 914 /// Get the fixed value arguments on `inst` as a mutable slice. 915 pub fn inst_fixed_args_mut(&mut self, inst: Inst) -> &mut [Value] { 916 let num_fixed_args = self.insts[inst] 917 .opcode() 918 .constraints() 919 .num_fixed_value_arguments(); 920 &mut self.inst_args_mut(inst)[..num_fixed_args] 921 } 922 923 /// Get the variable value arguments on `inst` as a slice. 924 pub fn inst_variable_args(&self, inst: Inst) -> &[Value] { 925 let num_fixed_args = self.insts[inst] 926 .opcode() 927 .constraints() 928 .num_fixed_value_arguments(); 929 &self.inst_args(inst)[num_fixed_args..] 930 } 931 932 /// Get the variable value arguments on `inst` as a mutable slice. 933 pub fn inst_variable_args_mut(&mut self, inst: Inst) -> &mut [Value] { 934 let num_fixed_args = self.insts[inst] 935 .opcode() 936 .constraints() 937 .num_fixed_value_arguments(); 938 &mut self.inst_args_mut(inst)[num_fixed_args..] 939 } 940 941 /// Create result values for an instruction that produces multiple results. 942 /// 943 /// Instructions that produce no result values only need to be created with `make_inst`, 944 /// otherwise call `make_inst_results` to allocate value table entries for the results. 945 /// 946 /// The result value types are determined from the instruction's value type constraints and the 947 /// provided `ctrl_typevar` type for polymorphic instructions. For non-polymorphic 948 /// instructions, `ctrl_typevar` is ignored, and `INVALID` can be used. 949 /// 950 /// The type of the first result value is also set, even if it was already set in the 951 /// `InstructionData` passed to `make_inst`. If this function is called with a single-result 952 /// instruction, that is the only effect. 953 pub fn make_inst_results(&mut self, inst: Inst, ctrl_typevar: Type) -> usize { 954 self.make_inst_results_reusing(inst, ctrl_typevar, iter::empty()) 955 } 956 957 /// Create result values for `inst`, reusing the provided detached values. 958 /// 959 /// Create a new set of result values for `inst` using `ctrl_typevar` to determine the result 960 /// types. Any values provided by `reuse` will be reused. When `reuse` is exhausted or when it 961 /// produces `None`, a new value is created. 962 pub fn make_inst_results_reusing<I>( 963 &mut self, 964 inst: Inst, 965 ctrl_typevar: Type, 966 reuse: I, 967 ) -> usize 968 where 969 I: Iterator<Item = Option<Value>>, 970 { 971 self.clear_results(inst); 972 973 let mut reuse = reuse.fuse(); 974 let result_tys: SmallVec<[_; 16]> = self.inst_result_types(inst, ctrl_typevar).collect(); 975 976 for (expected, &ty) in result_tys.iter().enumerate() { 977 let num = u16::try_from(expected).expect("Result value index should fit in u16"); 978 let value_data = ValueData::Inst { ty, num, inst }; 979 let v = if let Some(Some(v)) = reuse.next() { 980 debug_assert_eq!(self.value_type(v), ty, "Reused {ty} is wrong type"); 981 debug_assert!(!self.value_is_attached(v)); 982 self.values[v] = value_data.into(); 983 v 984 } else { 985 self.make_value(value_data) 986 }; 987 let actual = self.results[inst].push(v, &mut self.value_lists); 988 debug_assert_eq!(expected, actual); 989 } 990 991 result_tys.len() 992 } 993 994 /// Create a `ReplaceBuilder` that will replace `inst` with a new instruction in place. 995 pub fn replace(&mut self, inst: Inst) -> ReplaceBuilder<'_> { 996 ReplaceBuilder::new(self, inst) 997 } 998 999 /// Clear the list of result values from `inst`. 1000 /// 1001 /// This leaves `inst` without any result values. New result values can be created by calling 1002 /// `make_inst_results` or by using a `replace(inst)` builder. 1003 pub fn clear_results(&mut self, inst: Inst) { 1004 self.results[inst].clear(&mut self.value_lists) 1005 } 1006 1007 /// Replace an instruction result with a new value of type `new_type`. 1008 /// 1009 /// The `old_value` must be an attached instruction result. 1010 /// 1011 /// The old value is left detached, so it should probably be changed into something else. 1012 /// 1013 /// Returns the new value. 1014 pub fn replace_result(&mut self, old_value: Value, new_type: Type) -> Value { 1015 let (num, inst) = match ValueData::from(self.values[old_value]) { 1016 ValueData::Inst { num, inst, .. } => (num, inst), 1017 _ => panic!("{old_value} is not an instruction result value"), 1018 }; 1019 let new_value = self.make_value(ValueData::Inst { 1020 ty: new_type, 1021 num, 1022 inst, 1023 }); 1024 let num = num as usize; 1025 let attached = mem::replace( 1026 self.results[inst] 1027 .get_mut(num, &mut self.value_lists) 1028 .expect("Replacing detached result"), 1029 new_value, 1030 ); 1031 debug_assert_eq!( 1032 attached, 1033 old_value, 1034 "{} wasn't detached from {}", 1035 old_value, 1036 self.display_inst(inst) 1037 ); 1038 new_value 1039 } 1040 1041 /// Clone an instruction, attaching new result `Value`s and 1042 /// returning them. 1043 pub fn clone_inst(&mut self, inst: Inst) -> Inst { 1044 // First, add a clone of the InstructionData. 1045 let inst_data = self.insts[inst]; 1046 // If the `inst_data` has a reference to a ValueList, clone it 1047 // as well, because we can't share these (otherwise mutating 1048 // one would affect the other). 1049 let inst_data = inst_data.deep_clone(&mut self.value_lists); 1050 let new_inst = self.make_inst(inst_data); 1051 // Get the controlling type variable. 1052 let ctrl_typevar = self.ctrl_typevar(inst); 1053 // Create new result values. 1054 let num_results = self.make_inst_results(new_inst, ctrl_typevar); 1055 // Copy over PCC facts, if any. 1056 for i in 0..num_results { 1057 let old_result = self.inst_results(inst)[i]; 1058 let new_result = self.inst_results(new_inst)[i]; 1059 self.facts[new_result] = self.facts[old_result].clone(); 1060 } 1061 new_inst 1062 } 1063 1064 /// Get the first result of an instruction. 1065 /// 1066 /// This function panics if the instruction doesn't have any result. 1067 pub fn first_result(&self, inst: Inst) -> Value { 1068 self.results[inst] 1069 .first(&self.value_lists) 1070 .unwrap_or_else(|| panic!("{inst} has no results")) 1071 } 1072 1073 /// Test if `inst` has any result values currently. 1074 pub fn has_results(&self, inst: Inst) -> bool { 1075 !self.results[inst].is_empty() 1076 } 1077 1078 /// Return all the results of an instruction. 1079 pub fn inst_results(&self, inst: Inst) -> &[Value] { 1080 self.results[inst].as_slice(&self.value_lists) 1081 } 1082 1083 /// Return all the results of an instruction as ValueList. 1084 pub fn inst_results_list(&self, inst: Inst) -> ValueList { 1085 self.results[inst] 1086 } 1087 1088 /// Create a union of two values. 1089 pub fn union(&mut self, x: Value, y: Value) -> Value { 1090 // Get the type. 1091 let ty = self.value_type(x); 1092 debug_assert_eq!(ty, self.value_type(y)); 1093 self.make_value(ValueData::Union { ty, x, y }) 1094 } 1095 1096 /// Get the call signature of a direct or indirect call instruction. 1097 /// Returns `None` if `inst` is not a call instruction. 1098 pub fn call_signature(&self, inst: Inst) -> Option<SigRef> { 1099 match self.insts[inst].analyze_call(&self.value_lists, &self.exception_tables) { 1100 CallInfo::NotACall => None, 1101 CallInfo::Direct(f, _) => Some(self.ext_funcs[f].signature), 1102 CallInfo::DirectWithSig(_, s, _) => Some(s), 1103 CallInfo::Indirect(s, _) => Some(s), 1104 } 1105 } 1106 1107 /// Like `call_signature` but returns none for tail call 1108 /// instructions and try-call (exception-handling invoke) 1109 /// instructions. 1110 fn non_tail_call_or_try_call_signature(&self, inst: Inst) -> Option<SigRef> { 1111 let sig = self.call_signature(inst)?; 1112 match self.insts[inst].opcode() { 1113 ir::Opcode::ReturnCall | ir::Opcode::ReturnCallIndirect => None, 1114 ir::Opcode::TryCall | ir::Opcode::TryCallIndirect => None, 1115 _ => Some(sig), 1116 } 1117 } 1118 1119 // Only for use by the verifier. Everyone else should just use 1120 // `dfg.inst_results(inst).len()`. 1121 pub(crate) fn num_expected_results_for_verifier(&self, inst: Inst) -> usize { 1122 match self.non_tail_call_or_try_call_signature(inst) { 1123 Some(sig) => self.signatures[sig].returns.len(), 1124 None => { 1125 let constraints = self.insts[inst].opcode().constraints(); 1126 constraints.num_fixed_results() 1127 } 1128 } 1129 } 1130 1131 /// Get the result types of the given instruction. 1132 pub fn inst_result_types<'a>( 1133 &'a self, 1134 inst: Inst, 1135 ctrl_typevar: Type, 1136 ) -> impl iter::ExactSizeIterator<Item = Type> + 'a { 1137 return match self.non_tail_call_or_try_call_signature(inst) { 1138 Some(sig) => InstResultTypes::Signature(self, sig, 0), 1139 None => { 1140 let constraints = self.insts[inst].opcode().constraints(); 1141 InstResultTypes::Constraints(constraints, ctrl_typevar, 0) 1142 } 1143 }; 1144 1145 enum InstResultTypes<'a> { 1146 Signature(&'a DataFlowGraph, SigRef, usize), 1147 Constraints(ir::instructions::OpcodeConstraints, Type, usize), 1148 } 1149 1150 impl Iterator for InstResultTypes<'_> { 1151 type Item = Type; 1152 1153 fn next(&mut self) -> Option<Type> { 1154 match self { 1155 InstResultTypes::Signature(dfg, sig, i) => { 1156 let param = dfg.signatures[*sig].returns.get(*i)?; 1157 *i += 1; 1158 Some(param.value_type) 1159 } 1160 InstResultTypes::Constraints(constraints, ctrl_ty, i) => { 1161 if *i < constraints.num_fixed_results() { 1162 let ty = constraints.result_type(*i, *ctrl_ty); 1163 *i += 1; 1164 Some(ty) 1165 } else { 1166 None 1167 } 1168 } 1169 } 1170 } 1171 1172 fn size_hint(&self) -> (usize, Option<usize>) { 1173 let len = match self { 1174 InstResultTypes::Signature(dfg, sig, i) => { 1175 dfg.signatures[*sig].returns.len() - *i 1176 } 1177 InstResultTypes::Constraints(constraints, _, i) => { 1178 constraints.num_fixed_results() - *i 1179 } 1180 }; 1181 (len, Some(len)) 1182 } 1183 } 1184 1185 impl ExactSizeIterator for InstResultTypes<'_> {} 1186 } 1187 1188 /// Compute the type of an instruction result from opcode constraints and call signatures. 1189 /// 1190 /// This computes the same sequence of result types that `make_inst_results()` above would 1191 /// assign to the created result values, but it does not depend on `make_inst_results()` being 1192 /// called first. 1193 /// 1194 /// Returns `None` if asked about a result index that is too large. 1195 pub fn compute_result_type( 1196 &self, 1197 inst: Inst, 1198 result_idx: usize, 1199 ctrl_typevar: Type, 1200 ) -> Option<Type> { 1201 self.inst_result_types(inst, ctrl_typevar).nth(result_idx) 1202 } 1203 1204 /// Get the controlling type variable, or `INVALID` if `inst` isn't polymorphic. 1205 pub fn ctrl_typevar(&self, inst: Inst) -> Type { 1206 let constraints = self.insts[inst].opcode().constraints(); 1207 1208 if !constraints.is_polymorphic() { 1209 types::INVALID 1210 } else if constraints.requires_typevar_operand() { 1211 // Not all instruction formats have a designated operand, but in that case 1212 // `requires_typevar_operand()` should never be true. 1213 self.value_type( 1214 self.insts[inst] 1215 .typevar_operand(&self.value_lists) 1216 .unwrap_or_else(|| { 1217 panic!( 1218 "Instruction format for {:?} doesn't have a designated operand", 1219 self.insts[inst] 1220 ) 1221 }), 1222 ) 1223 } else { 1224 self.value_type(self.first_result(inst)) 1225 } 1226 } 1227 } 1228 1229 /// basic blocks. 1230 impl DataFlowGraph { 1231 /// Create a new basic block. 1232 pub fn make_block(&mut self) -> Block { 1233 self.blocks.add() 1234 } 1235 1236 /// Get the number of parameters on `block`. 1237 pub fn num_block_params(&self, block: Block) -> usize { 1238 self.blocks[block].params(&self.value_lists).len() 1239 } 1240 1241 /// Get the parameters on `block`. 1242 pub fn block_params(&self, block: Block) -> &[Value] { 1243 self.blocks[block].params(&self.value_lists) 1244 } 1245 1246 /// Get the types of the parameters on `block`. 1247 pub fn block_param_types(&self, block: Block) -> impl Iterator<Item = Type> + '_ { 1248 self.block_params(block).iter().map(|&v| self.value_type(v)) 1249 } 1250 1251 /// Append a parameter with type `ty` to `block`. 1252 pub fn append_block_param(&mut self, block: Block, ty: Type) -> Value { 1253 let param = self.values.next_key(); 1254 let num = self.blocks[block].params.push(param, &mut self.value_lists); 1255 debug_assert!(num <= u16::MAX as usize, "Too many parameters on block"); 1256 self.make_value(ValueData::Param { 1257 ty, 1258 num: num as u16, 1259 block, 1260 }) 1261 } 1262 1263 /// Removes `val` from `block`'s parameters by swapping it with the last parameter on `block`. 1264 /// Returns the position of `val` before removal. 1265 /// 1266 /// *Important*: to ensure O(1) deletion, this method swaps the removed parameter with the 1267 /// last `block` parameter. This can disrupt all the branch instructions jumping to this 1268 /// `block` for which you have to change the branch argument order if necessary. 1269 /// 1270 /// Panics if `val` is not a block parameter. 1271 pub fn swap_remove_block_param(&mut self, val: Value) -> usize { 1272 let (block, num) = 1273 if let ValueData::Param { num, block, .. } = ValueData::from(self.values[val]) { 1274 (block, num) 1275 } else { 1276 panic!("{val} must be a block parameter"); 1277 }; 1278 self.blocks[block] 1279 .params 1280 .swap_remove(num as usize, &mut self.value_lists); 1281 if let Some(last_arg_val) = self.blocks[block] 1282 .params 1283 .get(num as usize, &self.value_lists) 1284 { 1285 // We update the position of the old last arg. 1286 let mut last_arg_data = ValueData::from(self.values[last_arg_val]); 1287 if let ValueData::Param { num: old_num, .. } = &mut last_arg_data { 1288 *old_num = num; 1289 self.values[last_arg_val] = last_arg_data.into(); 1290 } else { 1291 panic!("{last_arg_val} should be a Block parameter"); 1292 } 1293 } 1294 num as usize 1295 } 1296 1297 /// Removes `val` from `block`'s parameters by a standard linear time list removal which 1298 /// preserves ordering. Also updates the values' data. 1299 pub fn remove_block_param(&mut self, val: Value) { 1300 let (block, num) = 1301 if let ValueData::Param { num, block, .. } = ValueData::from(self.values[val]) { 1302 (block, num) 1303 } else { 1304 panic!("{val} must be a block parameter"); 1305 }; 1306 self.blocks[block] 1307 .params 1308 .remove(num as usize, &mut self.value_lists); 1309 for index in num..(self.num_block_params(block) as u16) { 1310 let packed = &mut self.values[self.blocks[block] 1311 .params 1312 .get(index as usize, &self.value_lists) 1313 .unwrap()]; 1314 let mut data = ValueData::from(*packed); 1315 match &mut data { 1316 ValueData::Param { num, .. } => { 1317 *num -= 1; 1318 *packed = data.into(); 1319 } 1320 _ => panic!( 1321 "{} must be a block parameter", 1322 self.blocks[block] 1323 .params 1324 .get(index as usize, &self.value_lists) 1325 .unwrap() 1326 ), 1327 } 1328 } 1329 } 1330 1331 /// Append an existing value to `block`'s parameters. 1332 /// 1333 /// The appended value can't already be attached to something else. 1334 /// 1335 /// In almost all cases, you should be using `append_block_param()` instead of this method. 1336 pub fn attach_block_param(&mut self, block: Block, param: Value) { 1337 debug_assert!(!self.value_is_attached(param)); 1338 let num = self.blocks[block].params.push(param, &mut self.value_lists); 1339 debug_assert!(num <= u16::MAX as usize, "Too many parameters on block"); 1340 let ty = self.value_type(param); 1341 self.values[param] = ValueData::Param { 1342 ty, 1343 num: num as u16, 1344 block, 1345 } 1346 .into(); 1347 } 1348 1349 /// Replace a block parameter with a new value of type `ty`. 1350 /// 1351 /// The `old_value` must be an attached block parameter. It is removed from its place in the list 1352 /// of parameters and replaced by a new value of type `new_type`. The new value gets the same 1353 /// position in the list, and other parameters are not disturbed. 1354 /// 1355 /// The old value is left detached, so it should probably be changed into something else. 1356 /// 1357 /// Returns the new value. 1358 pub fn replace_block_param(&mut self, old_value: Value, new_type: Type) -> Value { 1359 // Create new value identical to the old one except for the type. 1360 let (block, num) = 1361 if let ValueData::Param { num, block, .. } = ValueData::from(self.values[old_value]) { 1362 (block, num) 1363 } else { 1364 panic!("{old_value} must be a block parameter"); 1365 }; 1366 let new_arg = self.make_value(ValueData::Param { 1367 ty: new_type, 1368 num, 1369 block, 1370 }); 1371 1372 self.blocks[block] 1373 .params 1374 .as_mut_slice(&mut self.value_lists)[num as usize] = new_arg; 1375 new_arg 1376 } 1377 1378 /// Detach all the parameters from `block` and return them as a `ValueList`. 1379 /// 1380 /// This is a quite low-level operation. Sensible things to do with the detached block parameters 1381 /// is to put them back on the same block with `attach_block_param()` or change them into aliases 1382 /// with `change_to_alias()`. 1383 pub fn detach_block_params(&mut self, block: Block) -> ValueList { 1384 self.blocks[block].params.take() 1385 } 1386 1387 /// Detach all of an instruction's result values. 1388 /// 1389 /// This is a quite low-level operation. A sensible thing to do with the 1390 /// detached results is to change them into aliases with 1391 /// `change_to_alias()`. 1392 pub fn detach_inst_results(&mut self, inst: Inst) { 1393 self.results[inst].clear(&mut self.value_lists); 1394 } 1395 1396 /// Merge the facts for two values. If both values have facts and 1397 /// they differ, both values get a special "conflict" fact that is 1398 /// never satisfied. 1399 pub fn merge_facts(&mut self, a: Value, b: Value) { 1400 let a = self.resolve_aliases(a); 1401 let b = self.resolve_aliases(b); 1402 match (&self.facts[a], &self.facts[b]) { 1403 (Some(a), Some(b)) if a == b => { /* nothing */ } 1404 (None, None) => { /* nothing */ } 1405 (Some(a), None) => { 1406 self.facts[b] = Some(a.clone()); 1407 } 1408 (None, Some(b)) => { 1409 self.facts[a] = Some(b.clone()); 1410 } 1411 (Some(a_fact), Some(b_fact)) => { 1412 assert_eq!(self.value_type(a), self.value_type(b)); 1413 let merged = Fact::intersect(a_fact, b_fact); 1414 crate::trace!( 1415 "facts merge on {} and {}: {:?}, {:?} -> {:?}", 1416 a, 1417 b, 1418 a_fact, 1419 b_fact, 1420 merged, 1421 ); 1422 self.facts[a] = Some(merged.clone()); 1423 self.facts[b] = Some(merged); 1424 } 1425 } 1426 } 1427 } 1428 1429 /// Contents of a basic block. 1430 /// 1431 /// Parameters on a basic block are values that dominate everything in the block. All 1432 /// branches to this block must provide matching arguments, and the arguments to the entry block must 1433 /// match the function arguments. 1434 #[derive(Clone, PartialEq, Hash)] 1435 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))] 1436 pub struct BlockData { 1437 /// List of parameters to this block. 1438 params: ValueList, 1439 } 1440 1441 impl BlockData { 1442 fn new() -> Self { 1443 Self { 1444 params: ValueList::new(), 1445 } 1446 } 1447 1448 /// Get the parameters on `block`. 1449 pub fn params<'a>(&self, pool: &'a ValueListPool) -> &'a [Value] { 1450 self.params.as_slice(pool) 1451 } 1452 } 1453 1454 /// Object that can display an instruction. 1455 pub struct DisplayInst<'a>(&'a DataFlowGraph, Inst); 1456 1457 impl<'a> fmt::Display for DisplayInst<'a> { 1458 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 1459 let dfg = self.0; 1460 let inst = self.1; 1461 1462 if let Some((first, rest)) = dfg.inst_results(inst).split_first() { 1463 write!(f, "{first}")?; 1464 for v in rest { 1465 write!(f, ", {v}")?; 1466 } 1467 write!(f, " = ")?; 1468 } 1469 1470 let typevar = dfg.ctrl_typevar(inst); 1471 if typevar.is_invalid() { 1472 write!(f, "{}", dfg.insts[inst].opcode())?; 1473 } else { 1474 write!(f, "{}.{}", dfg.insts[inst].opcode(), typevar)?; 1475 } 1476 write_operands(f, dfg, inst) 1477 } 1478 } 1479 1480 /// Parser routines. These routines should not be used outside the parser. 1481 impl DataFlowGraph { 1482 /// Set the type of a value. This is only for use in the parser, which needs 1483 /// to create invalid values for index padding which may be reassigned later. 1484 #[cold] 1485 fn set_value_type_for_parser(&mut self, v: Value, t: Type) { 1486 assert_eq!( 1487 self.value_type(v), 1488 types::INVALID, 1489 "this function is only for assigning types to previously invalid values" 1490 ); 1491 self.values[v].set_type(t); 1492 } 1493 1494 /// Check that the given concrete `Type` has been defined in the function. 1495 pub fn check_dynamic_type(&mut self, ty: Type) -> Option<Type> { 1496 debug_assert!(ty.is_dynamic_vector()); 1497 if self 1498 .dynamic_types 1499 .values() 1500 .any(|dyn_ty_data| dyn_ty_data.concrete().unwrap() == ty) 1501 { 1502 Some(ty) 1503 } else { 1504 None 1505 } 1506 } 1507 1508 /// Create result values for `inst`, reusing the provided detached values. 1509 /// This is similar to `make_inst_results_reusing` except it's only for use 1510 /// in the parser, which needs to reuse previously invalid values. 1511 #[cold] 1512 pub fn make_inst_results_for_parser( 1513 &mut self, 1514 inst: Inst, 1515 ctrl_typevar: Type, 1516 reuse: &[Value], 1517 ) -> usize { 1518 let mut reuse_iter = reuse.iter().copied(); 1519 let result_tys: SmallVec<[_; 16]> = self.inst_result_types(inst, ctrl_typevar).collect(); 1520 for ty in result_tys { 1521 if ty.is_dynamic_vector() { 1522 self.check_dynamic_type(ty) 1523 .unwrap_or_else(|| panic!("Use of undeclared dynamic type: {ty}")); 1524 } 1525 if let Some(v) = reuse_iter.next() { 1526 self.set_value_type_for_parser(v, ty); 1527 } 1528 } 1529 1530 self.make_inst_results_reusing(inst, ctrl_typevar, reuse.iter().map(|x| Some(*x))) 1531 } 1532 1533 /// Similar to `append_block_param`, append a parameter with type `ty` to 1534 /// `block`, but using value `val`. This is only for use by the parser to 1535 /// create parameters with specific values. 1536 #[cold] 1537 pub fn append_block_param_for_parser(&mut self, block: Block, ty: Type, val: Value) { 1538 let num = self.blocks[block].params.push(val, &mut self.value_lists); 1539 assert!(num <= u16::MAX as usize, "Too many parameters on block"); 1540 self.values[val] = ValueData::Param { 1541 ty, 1542 num: num as u16, 1543 block, 1544 } 1545 .into(); 1546 } 1547 1548 /// Create a new value alias. This is only for use by the parser to create 1549 /// aliases with specific values, and the printer for testing. 1550 #[cold] 1551 pub fn make_value_alias_for_serialization(&mut self, src: Value, dest: Value) { 1552 assert_ne!(src, Value::reserved_value()); 1553 assert_ne!(dest, Value::reserved_value()); 1554 1555 let ty = if self.values.is_valid(src) { 1556 self.value_type(src) 1557 } else { 1558 // As a special case, if we can't resolve the aliasee yet, use INVALID 1559 // temporarily. It will be resolved later in parsing. 1560 types::INVALID 1561 }; 1562 let data = ValueData::Alias { ty, original: src }; 1563 self.values[dest] = data.into(); 1564 } 1565 1566 /// If `v` is already defined as an alias, return its destination value. 1567 /// Otherwise return None. This allows the parser to coalesce identical 1568 /// alias definitions, and the printer to identify an alias's immediate target. 1569 #[cold] 1570 pub fn value_alias_dest_for_serialization(&self, v: Value) -> Option<Value> { 1571 if let ValueData::Alias { original, .. } = ValueData::from(self.values[v]) { 1572 Some(original) 1573 } else { 1574 None 1575 } 1576 } 1577 1578 /// Compute the type of an alias. This is only for use in the parser. 1579 /// Returns false if an alias cycle was encountered. 1580 #[cold] 1581 pub fn set_alias_type_for_parser(&mut self, v: Value) -> bool { 1582 if let Some(resolved) = maybe_resolve_aliases(&self.values, v) { 1583 let old_ty = self.value_type(v); 1584 let new_ty = self.value_type(resolved); 1585 if old_ty == types::INVALID { 1586 self.set_value_type_for_parser(v, new_ty); 1587 } else { 1588 assert_eq!(old_ty, new_ty); 1589 } 1590 true 1591 } else { 1592 false 1593 } 1594 } 1595 1596 /// Create an invalid value, to pad the index space. This is only for use by 1597 /// the parser to pad out the value index space. 1598 #[cold] 1599 pub fn make_invalid_value_for_parser(&mut self) { 1600 let data = ValueData::Alias { 1601 ty: types::INVALID, 1602 original: Value::reserved_value(), 1603 }; 1604 self.make_value(data); 1605 } 1606 1607 /// Check if a value reference is valid, while being aware of aliases which 1608 /// may be unresolved while parsing. 1609 #[cold] 1610 pub fn value_is_valid_for_parser(&self, v: Value) -> bool { 1611 if !self.value_is_valid(v) { 1612 return false; 1613 } 1614 if let ValueData::Alias { ty, .. } = ValueData::from(self.values[v]) { 1615 ty != types::INVALID 1616 } else { 1617 true 1618 } 1619 } 1620 } 1621 1622 #[cfg(test)] 1623 mod tests { 1624 use super::*; 1625 use crate::cursor::{Cursor, FuncCursor}; 1626 use crate::ir::{Function, Opcode, TrapCode}; 1627 use alloc::string::ToString; 1628 1629 #[test] 1630 fn make_inst() { 1631 let mut dfg = DataFlowGraph::new(); 1632 1633 let idata = InstructionData::UnaryImm { 1634 opcode: Opcode::Iconst, 1635 imm: 0.into(), 1636 }; 1637 let inst = dfg.make_inst(idata); 1638 1639 dfg.make_inst_results(inst, types::I32); 1640 assert_eq!(inst.to_string(), "inst0"); 1641 assert_eq!(dfg.display_inst(inst).to_string(), "v0 = iconst.i32 0"); 1642 1643 // Immutable reference resolution. 1644 { 1645 let immdfg = &dfg; 1646 let ins = &immdfg.insts[inst]; 1647 assert_eq!(ins.opcode(), Opcode::Iconst); 1648 } 1649 1650 // Results. 1651 let val = dfg.first_result(inst); 1652 assert_eq!(dfg.inst_results(inst), &[val]); 1653 1654 assert_eq!(dfg.value_def(val), ValueDef::Result(inst, 0)); 1655 assert_eq!(dfg.value_type(val), types::I32); 1656 1657 // Replacing results. 1658 assert!(dfg.value_is_attached(val)); 1659 let v2 = dfg.replace_result(val, types::F64); 1660 assert!(!dfg.value_is_attached(val)); 1661 assert!(dfg.value_is_attached(v2)); 1662 assert_eq!(dfg.inst_results(inst), &[v2]); 1663 assert_eq!(dfg.value_def(v2), ValueDef::Result(inst, 0)); 1664 assert_eq!(dfg.value_type(v2), types::F64); 1665 } 1666 1667 #[test] 1668 fn no_results() { 1669 let mut dfg = DataFlowGraph::new(); 1670 1671 let idata = InstructionData::Trap { 1672 opcode: Opcode::Trap, 1673 code: TrapCode::unwrap_user(1), 1674 }; 1675 let inst = dfg.make_inst(idata); 1676 assert_eq!(dfg.display_inst(inst).to_string(), "trap user1"); 1677 1678 // Result slice should be empty. 1679 assert_eq!(dfg.inst_results(inst), &[]); 1680 } 1681 1682 #[test] 1683 fn block() { 1684 let mut dfg = DataFlowGraph::new(); 1685 1686 let block = dfg.make_block(); 1687 assert_eq!(block.to_string(), "block0"); 1688 assert_eq!(dfg.num_block_params(block), 0); 1689 assert_eq!(dfg.block_params(block), &[]); 1690 assert!(dfg.detach_block_params(block).is_empty()); 1691 assert_eq!(dfg.num_block_params(block), 0); 1692 assert_eq!(dfg.block_params(block), &[]); 1693 1694 let arg1 = dfg.append_block_param(block, types::F32); 1695 assert_eq!(arg1.to_string(), "v0"); 1696 assert_eq!(dfg.num_block_params(block), 1); 1697 assert_eq!(dfg.block_params(block), &[arg1]); 1698 1699 let arg2 = dfg.append_block_param(block, types::I16); 1700 assert_eq!(arg2.to_string(), "v1"); 1701 assert_eq!(dfg.num_block_params(block), 2); 1702 assert_eq!(dfg.block_params(block), &[arg1, arg2]); 1703 1704 assert_eq!(dfg.value_def(arg1), ValueDef::Param(block, 0)); 1705 assert_eq!(dfg.value_def(arg2), ValueDef::Param(block, 1)); 1706 assert_eq!(dfg.value_type(arg1), types::F32); 1707 assert_eq!(dfg.value_type(arg2), types::I16); 1708 1709 // Swap the two block parameters. 1710 let vlist = dfg.detach_block_params(block); 1711 assert_eq!(dfg.num_block_params(block), 0); 1712 assert_eq!(dfg.block_params(block), &[]); 1713 assert_eq!(vlist.as_slice(&dfg.value_lists), &[arg1, arg2]); 1714 dfg.attach_block_param(block, arg2); 1715 let arg3 = dfg.append_block_param(block, types::I32); 1716 dfg.attach_block_param(block, arg1); 1717 assert_eq!(dfg.block_params(block), &[arg2, arg3, arg1]); 1718 } 1719 1720 #[test] 1721 fn replace_block_params() { 1722 let mut dfg = DataFlowGraph::new(); 1723 1724 let block = dfg.make_block(); 1725 let arg1 = dfg.append_block_param(block, types::F32); 1726 1727 let new1 = dfg.replace_block_param(arg1, types::I64); 1728 assert_eq!(dfg.value_type(arg1), types::F32); 1729 assert_eq!(dfg.value_type(new1), types::I64); 1730 assert_eq!(dfg.block_params(block), &[new1]); 1731 1732 dfg.attach_block_param(block, arg1); 1733 assert_eq!(dfg.block_params(block), &[new1, arg1]); 1734 1735 let new2 = dfg.replace_block_param(arg1, types::I8); 1736 assert_eq!(dfg.value_type(arg1), types::F32); 1737 assert_eq!(dfg.value_type(new2), types::I8); 1738 assert_eq!(dfg.block_params(block), &[new1, new2]); 1739 1740 dfg.attach_block_param(block, arg1); 1741 assert_eq!(dfg.block_params(block), &[new1, new2, arg1]); 1742 1743 let new3 = dfg.replace_block_param(new2, types::I16); 1744 assert_eq!(dfg.value_type(new1), types::I64); 1745 assert_eq!(dfg.value_type(new2), types::I8); 1746 assert_eq!(dfg.value_type(new3), types::I16); 1747 assert_eq!(dfg.block_params(block), &[new1, new3, arg1]); 1748 } 1749 1750 #[test] 1751 fn swap_remove_block_params() { 1752 let mut dfg = DataFlowGraph::new(); 1753 1754 let block = dfg.make_block(); 1755 let arg1 = dfg.append_block_param(block, types::F32); 1756 let arg2 = dfg.append_block_param(block, types::F32); 1757 let arg3 = dfg.append_block_param(block, types::F32); 1758 assert_eq!(dfg.block_params(block), &[arg1, arg2, arg3]); 1759 1760 dfg.swap_remove_block_param(arg1); 1761 assert_eq!(dfg.value_is_attached(arg1), false); 1762 assert_eq!(dfg.value_is_attached(arg2), true); 1763 assert_eq!(dfg.value_is_attached(arg3), true); 1764 assert_eq!(dfg.block_params(block), &[arg3, arg2]); 1765 dfg.swap_remove_block_param(arg2); 1766 assert_eq!(dfg.value_is_attached(arg2), false); 1767 assert_eq!(dfg.value_is_attached(arg3), true); 1768 assert_eq!(dfg.block_params(block), &[arg3]); 1769 dfg.swap_remove_block_param(arg3); 1770 assert_eq!(dfg.value_is_attached(arg3), false); 1771 assert_eq!(dfg.block_params(block), &[]); 1772 } 1773 1774 #[test] 1775 fn aliases() { 1776 use crate::ir::InstBuilder; 1777 use crate::ir::condcodes::IntCC; 1778 1779 let mut func = Function::new(); 1780 let block0 = func.dfg.make_block(); 1781 let mut pos = FuncCursor::new(&mut func); 1782 pos.insert_block(block0); 1783 1784 // Build a little test program. 1785 let v1 = pos.ins().iconst(types::I32, 42); 1786 1787 // Make sure we can resolve value aliases even when values is empty. 1788 assert_eq!(pos.func.dfg.resolve_aliases(v1), v1); 1789 1790 let arg0 = pos.func.dfg.append_block_param(block0, types::I32); 1791 let (s, c) = pos.ins().uadd_overflow(v1, arg0); 1792 let iadd = match pos.func.dfg.value_def(s) { 1793 ValueDef::Result(i, 0) => i, 1794 _ => panic!(), 1795 }; 1796 1797 // Remove `c` from the result list. 1798 pos.func.stencil.dfg.results[iadd].remove(1, &mut pos.func.stencil.dfg.value_lists); 1799 1800 // Replace `uadd_overflow` with a normal `iadd` and an `icmp`. 1801 pos.func.dfg.replace(iadd).iadd(v1, arg0); 1802 let c2 = pos.ins().icmp(IntCC::Equal, s, v1); 1803 pos.func.dfg.change_to_alias(c, c2); 1804 1805 assert_eq!(pos.func.dfg.resolve_aliases(c2), c2); 1806 assert_eq!(pos.func.dfg.resolve_aliases(c), c2); 1807 } 1808 1809 #[test] 1810 fn cloning() { 1811 use crate::ir::InstBuilder; 1812 1813 let mut func = Function::new(); 1814 let mut sig = Signature::new(crate::isa::CallConv::SystemV); 1815 sig.params.push(ir::AbiParam::new(types::I32)); 1816 let sig = func.import_signature(sig); 1817 let block0 = func.dfg.make_block(); 1818 let mut pos = FuncCursor::new(&mut func); 1819 pos.insert_block(block0); 1820 let v1 = pos.ins().iconst(types::I32, 0); 1821 let v2 = pos.ins().iconst(types::I32, 1); 1822 let call_inst = pos.ins().call_indirect(sig, v1, &[v1]); 1823 let func = pos.func; 1824 1825 let call_inst_dup = func.dfg.clone_inst(call_inst); 1826 func.dfg.inst_args_mut(call_inst)[0] = v2; 1827 assert_eq!(v1, func.dfg.inst_args(call_inst_dup)[0]); 1828 } 1829 } 1830