1 //! Intermediate representation of a function. 2 //! 3 //! The `Function` struct defined in this module owns all of its basic blocks and 4 //! instructions. 5 6 use crate::binemit::CodeOffset; 7 use crate::entity::{PrimaryMap, SecondaryMap}; 8 use crate::ir; 9 use crate::ir::{ 10 instructions::BranchInfo, Block, ExtFuncData, FuncRef, GlobalValue, GlobalValueData, Heap, 11 HeapData, Inst, InstructionData, JumpTable, JumpTableData, Opcode, SigRef, StackSlot, 12 StackSlotData, Table, TableData, 13 }; 14 use crate::ir::{BlockOffsets, InstEncodings, SourceLocs, StackSlots, ValueLocations}; 15 use crate::ir::{DataFlowGraph, ExternalName, Layout, Signature}; 16 use crate::ir::{JumpTableOffsets, JumpTables}; 17 use crate::isa::{CallConv, EncInfo, Encoding, Legalize, TargetIsa}; 18 use crate::regalloc::{EntryRegDiversions, RegDiversions}; 19 use crate::value_label::ValueLabelsRanges; 20 use crate::write::write_function; 21 #[cfg(feature = "enable-serde")] 22 use alloc::string::String; 23 use alloc::vec::Vec; 24 use core::fmt; 25 26 #[cfg(feature = "enable-serde")] 27 use serde::de::{Deserializer, Error}; 28 #[cfg(feature = "enable-serde")] 29 use serde::ser::Serializer; 30 #[cfg(feature = "enable-serde")] 31 use serde::{Deserialize, Serialize}; 32 33 /// A version marker used to ensure that serialized clif ir is never deserialized with a 34 /// different version of Cranelift. 35 #[derive(Copy, Clone, Debug)] 36 pub struct VersionMarker; 37 38 #[cfg(feature = "enable-serde")] 39 impl Serialize for VersionMarker { serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer,40 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> 41 where 42 S: Serializer, 43 { 44 crate::VERSION.serialize(serializer) 45 } 46 } 47 48 #[cfg(feature = "enable-serde")] 49 impl<'de> Deserialize<'de> for VersionMarker { deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>,50 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> 51 where 52 D: Deserializer<'de>, 53 { 54 let version = String::deserialize(deserializer)?; 55 if version != crate::VERSION { 56 return Err(D::Error::custom(&format!( 57 "Expected a clif ir function for version {}, found one for version {}", 58 crate::VERSION, 59 version, 60 ))); 61 } 62 Ok(VersionMarker) 63 } 64 } 65 66 /// 67 /// Functions can be cloned, but it is not a very fast operation. 68 /// The clone will have all the same entity numbers as the original. 69 #[derive(Clone)] 70 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))] 71 pub struct Function { 72 /// A version marker used to ensure that serialized clif ir is never deserialized with a 73 /// different version of Cranelift. 74 // Note: This must be the first field to ensure that Serde will deserialize it before 75 // attempting to deserialize other fields that are potentially changed between versions. 76 pub version_marker: VersionMarker, 77 78 /// Name of this function. Mostly used by `.clif` files. 79 pub name: ExternalName, 80 81 /// Signature of this function. 82 pub signature: Signature, 83 84 /// The old signature of this function, before the most recent legalization, 85 /// if any. 86 pub old_signature: Option<Signature>, 87 88 /// Stack slots allocated in this function. 89 pub stack_slots: StackSlots, 90 91 /// Global values referenced. 92 pub global_values: PrimaryMap<ir::GlobalValue, ir::GlobalValueData>, 93 94 /// Heaps referenced. 95 pub heaps: PrimaryMap<ir::Heap, ir::HeapData>, 96 97 /// Tables referenced. 98 pub tables: PrimaryMap<ir::Table, ir::TableData>, 99 100 /// Jump tables used in this function. 101 pub jump_tables: JumpTables, 102 103 /// Data flow graph containing the primary definition of all instructions, blocks and values. 104 pub dfg: DataFlowGraph, 105 106 /// Layout of blocks and instructions in the function body. 107 pub layout: Layout, 108 109 /// Encoding recipe and bits for the legal instructions. 110 /// Illegal instructions have the `Encoding::default()` value. 111 pub encodings: InstEncodings, 112 113 /// Location assigned to every value. 114 pub locations: ValueLocations, 115 116 /// Non-default locations assigned to value at the entry of basic blocks. 117 /// 118 /// At the entry of each basic block, we might have values which are not in their default 119 /// ValueLocation. This field records these register-to-register moves as Diversions. 120 pub entry_diversions: EntryRegDiversions, 121 122 /// Code offsets of the block headers. 123 /// 124 /// This information is only transiently available after the `binemit::relax_branches` function 125 /// computes it, and it can easily be recomputed by calling that function. It is not included 126 /// in the textual IR format. 127 pub offsets: BlockOffsets, 128 129 /// Code offsets of Jump Table headers. 130 pub jt_offsets: JumpTableOffsets, 131 132 /// Source locations. 133 /// 134 /// Track the original source location for each instruction. The source locations are not 135 /// interpreted by Cranelift, only preserved. 136 pub srclocs: SourceLocs, 137 138 /// Instruction that marks the end (inclusive) of the function's prologue. 139 /// 140 /// This is used for some ABIs to generate unwind information. 141 pub prologue_end: Option<Inst>, 142 143 /// The instructions that mark the start (inclusive) of an epilogue in the function. 144 /// 145 /// This is used for some ABIs to generate unwind information. 146 pub epilogues_start: Vec<(Inst, Block)>, 147 148 /// An optional global value which represents an expression evaluating to 149 /// the stack limit for this function. This `GlobalValue` will be 150 /// interpreted in the prologue, if necessary, to insert a stack check to 151 /// ensure that a trap happens if the stack pointer goes below the 152 /// threshold specified here. 153 pub stack_limit: Option<ir::GlobalValue>, 154 } 155 156 impl Function { 157 /// Create a function with the given name and signature. with_name_signature(name: ExternalName, sig: Signature) -> Self158 pub fn with_name_signature(name: ExternalName, sig: Signature) -> Self { 159 Self { 160 version_marker: VersionMarker, 161 name, 162 signature: sig, 163 old_signature: None, 164 stack_slots: StackSlots::new(), 165 global_values: PrimaryMap::new(), 166 heaps: PrimaryMap::new(), 167 tables: PrimaryMap::new(), 168 jump_tables: PrimaryMap::new(), 169 dfg: DataFlowGraph::new(), 170 layout: Layout::new(), 171 encodings: SecondaryMap::new(), 172 locations: SecondaryMap::new(), 173 entry_diversions: EntryRegDiversions::new(), 174 offsets: SecondaryMap::new(), 175 jt_offsets: SecondaryMap::new(), 176 srclocs: SecondaryMap::new(), 177 prologue_end: None, 178 epilogues_start: Vec::new(), 179 stack_limit: None, 180 } 181 } 182 183 /// Clear all data structures in this function. clear(&mut self)184 pub fn clear(&mut self) { 185 self.signature.clear(CallConv::Fast); 186 self.stack_slots.clear(); 187 self.global_values.clear(); 188 self.heaps.clear(); 189 self.tables.clear(); 190 self.jump_tables.clear(); 191 self.dfg.clear(); 192 self.layout.clear(); 193 self.encodings.clear(); 194 self.locations.clear(); 195 self.entry_diversions.clear(); 196 self.offsets.clear(); 197 self.jt_offsets.clear(); 198 self.srclocs.clear(); 199 self.prologue_end = None; 200 self.epilogues_start.clear(); 201 self.stack_limit = None; 202 } 203 204 /// Create a new empty, anonymous function with a Fast calling convention. new() -> Self205 pub fn new() -> Self { 206 Self::with_name_signature(ExternalName::default(), Signature::new(CallConv::Fast)) 207 } 208 209 /// Creates a jump table in the function, to be used by `br_table` instructions. create_jump_table(&mut self, data: JumpTableData) -> JumpTable210 pub fn create_jump_table(&mut self, data: JumpTableData) -> JumpTable { 211 self.jump_tables.push(data) 212 } 213 214 /// Creates a stack slot in the function, to be used by `stack_load`, `stack_store` and 215 /// `stack_addr` instructions. create_stack_slot(&mut self, data: StackSlotData) -> StackSlot216 pub fn create_stack_slot(&mut self, data: StackSlotData) -> StackSlot { 217 self.stack_slots.push(data) 218 } 219 220 /// Adds a signature which can later be used to declare an external function import. import_signature(&mut self, signature: Signature) -> SigRef221 pub fn import_signature(&mut self, signature: Signature) -> SigRef { 222 self.dfg.signatures.push(signature) 223 } 224 225 /// Declare an external function import. import_function(&mut self, data: ExtFuncData) -> FuncRef226 pub fn import_function(&mut self, data: ExtFuncData) -> FuncRef { 227 self.dfg.ext_funcs.push(data) 228 } 229 230 /// Declares a global value accessible to the function. create_global_value(&mut self, data: GlobalValueData) -> GlobalValue231 pub fn create_global_value(&mut self, data: GlobalValueData) -> GlobalValue { 232 self.global_values.push(data) 233 } 234 235 /// Declares a heap accessible to the function. create_heap(&mut self, data: HeapData) -> Heap236 pub fn create_heap(&mut self, data: HeapData) -> Heap { 237 self.heaps.push(data) 238 } 239 240 /// Declares a table accessible to the function. create_table(&mut self, data: TableData) -> Table241 pub fn create_table(&mut self, data: TableData) -> Table { 242 self.tables.push(data) 243 } 244 245 /// Return an object that can display this function with correct ISA-specific annotations. display<'a, I: Into<Option<&'a dyn TargetIsa>>>( &'a self, isa: I, ) -> DisplayFunction<'a>246 pub fn display<'a, I: Into<Option<&'a dyn TargetIsa>>>( 247 &'a self, 248 isa: I, 249 ) -> DisplayFunction<'a> { 250 DisplayFunction(self, isa.into().into()) 251 } 252 253 /// Return an object that can display this function with correct ISA-specific annotations. display_with<'a>( &'a self, annotations: DisplayFunctionAnnotations<'a>, ) -> DisplayFunction<'a>254 pub fn display_with<'a>( 255 &'a self, 256 annotations: DisplayFunctionAnnotations<'a>, 257 ) -> DisplayFunction<'a> { 258 DisplayFunction(self, annotations) 259 } 260 261 /// Find a presumed unique special-purpose function parameter value. 262 /// 263 /// Returns the value of the last `purpose` parameter, or `None` if no such parameter exists. special_param(&self, purpose: ir::ArgumentPurpose) -> Option<ir::Value>264 pub fn special_param(&self, purpose: ir::ArgumentPurpose) -> Option<ir::Value> { 265 let entry = self.layout.entry_block().expect("Function is empty"); 266 self.signature 267 .special_param_index(purpose) 268 .map(|i| self.dfg.block_params(entry)[i]) 269 } 270 271 /// Get an iterator over the instructions in `block`, including offsets and encoded instruction 272 /// sizes. 273 /// 274 /// The iterator returns `(offset, inst, size)` tuples, where `offset` if the offset in bytes 275 /// from the beginning of the function to the instruction, and `size` is the size of the 276 /// instruction in bytes, or 0 for unencoded instructions. 277 /// 278 /// This function can only be used after the code layout has been computed by the 279 /// `binemit::relax_branches()` function. inst_offsets<'a>(&'a self, block: Block, encinfo: &EncInfo) -> InstOffsetIter<'a>280 pub fn inst_offsets<'a>(&'a self, block: Block, encinfo: &EncInfo) -> InstOffsetIter<'a> { 281 assert!( 282 !self.offsets.is_empty(), 283 "Code layout must be computed first" 284 ); 285 let mut divert = RegDiversions::new(); 286 divert.at_block(&self.entry_diversions, block); 287 InstOffsetIter { 288 encinfo: encinfo.clone(), 289 func: self, 290 divert, 291 encodings: &self.encodings, 292 offset: self.offsets[block], 293 iter: self.layout.block_insts(block), 294 } 295 } 296 297 /// Wrapper around `encode` which assigns `inst` the resulting encoding. update_encoding(&mut self, inst: ir::Inst, isa: &dyn TargetIsa) -> Result<(), Legalize>298 pub fn update_encoding(&mut self, inst: ir::Inst, isa: &dyn TargetIsa) -> Result<(), Legalize> { 299 if isa.get_mach_backend().is_some() { 300 Ok(()) 301 } else { 302 self.encode(inst, isa).map(|e| self.encodings[inst] = e) 303 } 304 } 305 306 /// Wrapper around `TargetIsa::encode` for encoding an existing instruction 307 /// in the `Function`. encode(&self, inst: ir::Inst, isa: &dyn TargetIsa) -> Result<Encoding, Legalize>308 pub fn encode(&self, inst: ir::Inst, isa: &dyn TargetIsa) -> Result<Encoding, Legalize> { 309 if isa.get_mach_backend().is_some() { 310 Ok(Encoding::new(0, 0)) 311 } else { 312 isa.encode(&self, &self.dfg[inst], self.dfg.ctrl_typevar(inst)) 313 } 314 } 315 316 /// Starts collection of debug information. collect_debug_info(&mut self)317 pub fn collect_debug_info(&mut self) { 318 self.dfg.collect_debug_info(); 319 } 320 321 /// Changes the destination of a jump or branch instruction. 322 /// Does nothing if called with a non-jump or non-branch instruction. 323 /// 324 /// Note that this method ignores multi-destination branches like `br_table`. change_branch_destination(&mut self, inst: Inst, new_dest: Block)325 pub fn change_branch_destination(&mut self, inst: Inst, new_dest: Block) { 326 match self.dfg[inst].branch_destination_mut() { 327 None => (), 328 Some(inst_dest) => *inst_dest = new_dest, 329 } 330 } 331 332 /// Rewrite the branch destination to `new_dest` if the destination matches `old_dest`. 333 /// Does nothing if called with a non-jump or non-branch instruction. 334 /// 335 /// Unlike [change_branch_destination](Function::change_branch_destination), this method rewrite the destinations of 336 /// multi-destination branches like `br_table`. rewrite_branch_destination(&mut self, inst: Inst, old_dest: Block, new_dest: Block)337 pub fn rewrite_branch_destination(&mut self, inst: Inst, old_dest: Block, new_dest: Block) { 338 match self.dfg.analyze_branch(inst) { 339 BranchInfo::SingleDest(dest, ..) => { 340 if dest == old_dest { 341 self.change_branch_destination(inst, new_dest); 342 } 343 } 344 345 BranchInfo::Table(table, default_dest) => { 346 self.jump_tables[table].iter_mut().for_each(|entry| { 347 if *entry == old_dest { 348 *entry = new_dest; 349 } 350 }); 351 352 if default_dest == Some(old_dest) { 353 match &mut self.dfg[inst] { 354 InstructionData::BranchTable { destination, .. } => { 355 *destination = new_dest; 356 } 357 _ => panic!( 358 "Unexpected instruction {} having default destination", 359 self.dfg.display_inst(inst, None) 360 ), 361 } 362 } 363 } 364 365 BranchInfo::NotABranch => {} 366 } 367 } 368 369 /// Checks that the specified block can be encoded as a basic block. 370 /// 371 /// On error, returns the first invalid instruction and an error message. is_block_basic(&self, block: Block) -> Result<(), (Inst, &'static str)>372 pub fn is_block_basic(&self, block: Block) -> Result<(), (Inst, &'static str)> { 373 let dfg = &self.dfg; 374 let inst_iter = self.layout.block_insts(block); 375 376 // Ignore all instructions prior to the first branch. 377 let mut inst_iter = inst_iter.skip_while(|&inst| !dfg[inst].opcode().is_branch()); 378 379 // A conditional branch is permitted in a basic block only when followed 380 // by a terminal jump or fallthrough instruction. 381 if let Some(_branch) = inst_iter.next() { 382 if let Some(next) = inst_iter.next() { 383 match dfg[next].opcode() { 384 Opcode::Fallthrough | Opcode::Jump => (), 385 _ => return Err((next, "post-branch instruction not fallthrough or jump")), 386 } 387 } 388 } 389 390 Ok(()) 391 } 392 393 /// Returns true if the function is function that doesn't call any other functions. This is not 394 /// to be confused with a "leaf function" in Windows terminology. is_leaf(&self) -> bool395 pub fn is_leaf(&self) -> bool { 396 // Conservative result: if there's at least one function signature referenced in this 397 // function, assume it is not a leaf. 398 self.dfg.signatures.is_empty() 399 } 400 401 /// Replace the `dst` instruction's data with the `src` instruction's data 402 /// and then remove `src`. 403 /// 404 /// `src` and its result values should not be used at all, as any uses would 405 /// be left dangling after calling this method. 406 /// 407 /// `src` and `dst` must have the same number of resulting values, and 408 /// `src`'s i^th value must have the same type as `dst`'s i^th value. transplant_inst(&mut self, dst: Inst, src: Inst)409 pub fn transplant_inst(&mut self, dst: Inst, src: Inst) { 410 debug_assert_eq!( 411 self.dfg.inst_results(dst).len(), 412 self.dfg.inst_results(src).len() 413 ); 414 debug_assert!(self 415 .dfg 416 .inst_results(dst) 417 .iter() 418 .zip(self.dfg.inst_results(src)) 419 .all(|(a, b)| self.dfg.value_type(*a) == self.dfg.value_type(*b))); 420 421 self.dfg[dst] = self.dfg[src].clone(); 422 self.layout.remove_inst(src); 423 } 424 } 425 426 /// Additional annotations for function display. 427 #[derive(Default)] 428 pub struct DisplayFunctionAnnotations<'a> { 429 /// Enable ISA annotations. 430 pub isa: Option<&'a dyn TargetIsa>, 431 432 /// Enable value labels annotations. 433 pub value_ranges: Option<&'a ValueLabelsRanges>, 434 } 435 436 impl<'a> From<Option<&'a dyn TargetIsa>> for DisplayFunctionAnnotations<'a> { from(isa: Option<&'a dyn TargetIsa>) -> DisplayFunctionAnnotations437 fn from(isa: Option<&'a dyn TargetIsa>) -> DisplayFunctionAnnotations { 438 DisplayFunctionAnnotations { 439 isa, 440 value_ranges: None, 441 } 442 } 443 } 444 445 /// Wrapper type capable of displaying a `Function` with correct ISA annotations. 446 pub struct DisplayFunction<'a>(&'a Function, DisplayFunctionAnnotations<'a>); 447 448 impl<'a> fmt::Display for DisplayFunction<'a> { fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result449 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { 450 write_function(fmt, self.0, &self.1) 451 } 452 } 453 454 impl fmt::Display for Function { fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result455 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { 456 write_function(fmt, self, &DisplayFunctionAnnotations::default()) 457 } 458 } 459 460 impl fmt::Debug for Function { fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result461 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { 462 write_function(fmt, self, &DisplayFunctionAnnotations::default()) 463 } 464 } 465 466 /// Iterator returning instruction offsets and sizes: `(offset, inst, size)`. 467 pub struct InstOffsetIter<'a> { 468 encinfo: EncInfo, 469 divert: RegDiversions, 470 func: &'a Function, 471 encodings: &'a InstEncodings, 472 offset: CodeOffset, 473 iter: ir::layout::Insts<'a>, 474 } 475 476 impl<'a> Iterator for InstOffsetIter<'a> { 477 type Item = (CodeOffset, ir::Inst, CodeOffset); 478 next(&mut self) -> Option<Self::Item>479 fn next(&mut self) -> Option<Self::Item> { 480 self.iter.next().map(|inst| { 481 self.divert.apply(&self.func.dfg[inst]); 482 let byte_size = 483 self.encinfo 484 .byte_size(self.encodings[inst], inst, &self.divert, self.func); 485 let offset = self.offset; 486 self.offset += byte_size; 487 (offset, inst, byte_size) 488 }) 489 } 490 } 491