1 //! In-memory representation of compiled machine code, with labels and fixups to 2 //! refer to those labels. Handles constant-pool island insertion and also 3 //! veneer insertion for out-of-range jumps. 4 //! 5 //! This code exists to solve three problems: 6 //! 7 //! - Branch targets for forward branches are not known until later, when we 8 //! emit code in a single pass through the instruction structs. 9 //! 10 //! - On many architectures, address references or offsets have limited range. 11 //! For example, on AArch64, conditional branches can only target code +/- 1MB 12 //! from the branch itself. 13 //! 14 //! - The lowering of control flow from the CFG-with-edges produced by 15 //! [BlockLoweringOrder](super::BlockLoweringOrder), combined with many empty 16 //! edge blocks when the register allocator does not need to insert any 17 //! spills/reloads/moves in edge blocks, results in many suboptimal branch 18 //! patterns. The lowering also pays no attention to block order, and so 19 //! two-target conditional forms (cond-br followed by uncond-br) can often by 20 //! avoided because one of the targets is the fallthrough. There are several 21 //! cases here where we can simplify to use fewer branches. 22 //! 23 //! This "buffer" implements a single-pass code emission strategy (with a later 24 //! "fixup" pass, but only through recorded fixups, not all instructions). The 25 //! basic idea is: 26 //! 27 //! - Emit branches as they are, including two-target (cond/uncond) compound 28 //! forms, but with zero offsets and optimistically assuming the target will be 29 //! in range. Record the "fixup" for later. Targets are denoted instead by 30 //! symbolic "labels" that are then bound to certain offsets in the buffer as 31 //! we emit code. (Nominally, there is a label at the start of every basic 32 //! block.) 33 //! 34 //! - As we do this, track the offset in the buffer at which the first label 35 //! reference "goes out of range". We call this the "deadline". If we reach the 36 //! deadline and we still have not bound the label to which an unresolved branch 37 //! refers, we have a problem! 38 //! 39 //! - To solve this problem, we emit "islands" full of "veneers". An island is 40 //! simply a chunk of code inserted in the middle of the code actually produced 41 //! by the emitter (e.g., vcode iterating over instruction structs). The emitter 42 //! has some awareness of this: it either asks for an island between blocks, so 43 //! it is not accidentally executed, or else it emits a branch around the island 44 //! when all other options fail (see `Inst::EmitIsland` meta-instruction). 45 //! 46 //! - A "veneer" is an instruction (or sequence of instructions) in an "island" 47 //! that implements a longer-range reference to a label. The idea is that, for 48 //! example, a branch with a limited range can branch to a "veneer" instead, 49 //! which is simply a branch in a form that can use a longer-range reference. On 50 //! AArch64, for example, conditionals have a +/- 1 MB range, but a conditional 51 //! can branch to an unconditional branch which has a +/- 128 MB range. Hence, a 52 //! conditional branch's label reference can be fixed up with a "veneer" to 53 //! achieve a longer range. 54 //! 55 //! - To implement all of this, we require the backend to provide a `LabelUse` 56 //! type that implements a trait. This is nominally an enum that records one of 57 //! several kinds of references to an offset in code -- basically, a relocation 58 //! type -- and will usually correspond to different instruction formats. The 59 //! `LabelUse` implementation specifies the maximum range, how to patch in the 60 //! actual label location when known, and how to generate a veneer to extend the 61 //! range. 62 //! 63 //! That satisfies label references, but we still may have suboptimal branch 64 //! patterns. To clean up the branches, we do a simple "peephole"-style 65 //! optimization on the fly. To do so, the emitter (e.g., `Inst::emit()`) 66 //! informs the buffer of branches in the code and, in the case of conditionals, 67 //! the code that would have been emitted to invert this branch's condition. We 68 //! track the "latest branches": these are branches that are contiguous up to 69 //! the current offset. (If any code is emitted after a branch, that branch or 70 //! run of contiguous branches is no longer "latest".) The latest branches are 71 //! those that we can edit by simply truncating the buffer and doing something 72 //! else instead. 73 //! 74 //! To optimize branches, we implement several simple rules, and try to apply 75 //! them to the "latest branches" when possible: 76 //! 77 //! - A branch with a label target, when that label is bound to the ending 78 //! offset of the branch (the fallthrough location), can be removed altogether, 79 //! because the branch would have no effect). 80 //! 81 //! - An unconditional branch that starts at a label location, and branches to 82 //! another label, results in a "label alias": all references to the label bound 83 //! *to* this branch instruction are instead resolved to the *target* of the 84 //! branch instruction. This effectively removes empty blocks that just 85 //! unconditionally branch to the next block. We call this "branch threading". 86 //! 87 //! - A conditional followed by an unconditional, when the conditional branches 88 //! to the unconditional's fallthrough, results in (i) the truncation of the 89 //! unconditional, (ii) the inversion of the condition's condition, and (iii) 90 //! replacement of the conditional's target (using the original target of the 91 //! unconditional). This is a fancy way of saying "we can flip a two-target 92 //! conditional branch's taken/not-taken targets if it works better with our 93 //! fallthrough". To make this work, the emitter actually gives the buffer 94 //! *both* forms of every conditional branch: the true form is emitted into the 95 //! buffer, and the "inverted" machine-code bytes are provided as part of the 96 //! branch-fixup metadata. 97 //! 98 //! - An unconditional B preceded by another unconditional P, when B's label(s) have 99 //! been redirected to target(B), can be removed entirely. This is an extension 100 //! of the branch-threading optimization, and is valid because if we know there 101 //! will be no fallthrough into this branch instruction (the prior instruction 102 //! is an unconditional jump), and if we know we have successfully redirected 103 //! all labels, then this branch instruction is unreachable. Note that this 104 //! works because the redirection happens before the label is ever resolved 105 //! (fixups happen at island emission time, at which point latest-branches are 106 //! cleared, or at the end of emission), so we are sure to catch and redirect 107 //! all possible paths to this instruction. 108 //! 109 //! # Branch-optimization Correctness 110 //! 111 //! The branch-optimization mechanism depends on a few data structures with 112 //! invariants, which are always held outside the scope of top-level public 113 //! methods: 114 //! 115 //! - The latest-branches list. Each entry describes a span of the buffer 116 //! (start/end offsets), the label target, the corresponding fixup-list entry 117 //! index, and the bytes (must be the same length) for the inverted form, if 118 //! conditional. The list of labels that are bound to the start-offset of this 119 //! branch is *complete* (if any label has a resolved offset equal to `start` 120 //! and is not an alias, it must appear in this list) and *precise* (no label 121 //! in this list can be bound to another offset). No label in this list should 122 //! be an alias. No two branch ranges can overlap, and branches are in 123 //! ascending-offset order. 124 //! 125 //! - The labels-at-tail list. This contains all MachLabels that have been bound 126 //! to (whose resolved offsets are equal to) the tail offset of the buffer. 127 //! No label in this list should be an alias. 128 //! 129 //! - The label_offsets array, containing the bound offset of a label or 130 //! UNKNOWN. No label can be bound at an offset greater than the current 131 //! buffer tail. 132 //! 133 //! - The label_aliases array, containing another label to which a label is 134 //! bound or UNKNOWN. A label's resolved offset is the resolved offset 135 //! of the label it is aliased to, if this is set. 136 //! 137 //! We argue below, at each method, how the invariants in these data structures 138 //! are maintained (grep for "Post-invariant"). 139 //! 140 //! Given these invariants, we argue why each optimization preserves execution 141 //! semantics below (grep for "Preserves execution semantics"). 142 143 use crate::binemit::{Addend, CodeOffset, CodeSink, Reloc, StackMap}; 144 use crate::ir::{ExternalName, Opcode, SourceLoc, TrapCode}; 145 use crate::machinst::{BlockIndex, MachInstLabelUse, VCodeInst}; 146 use crate::timing; 147 148 use log::trace; 149 use smallvec::SmallVec; 150 use std::mem; 151 152 /// A buffer of output to be produced, fixed up, and then emitted to a CodeSink 153 /// in bulk. 154 /// 155 /// This struct uses `SmallVec`s to support small-ish function bodies without 156 /// any heap allocation. As such, it will be several kilobytes large. This is 157 /// likely fine as long as it is stack-allocated for function emission then 158 /// thrown away; but beware if many buffer objects are retained persistently. 159 pub struct MachBuffer<I: VCodeInst> { 160 /// The buffer contents, as raw bytes. 161 data: SmallVec<[u8; 1024]>, 162 /// Any relocations referring to this code. Note that only *external* 163 /// relocations are tracked here; references to labels within the buffer are 164 /// resolved before emission. 165 relocs: SmallVec<[MachReloc; 16]>, 166 /// Any trap records referring to this code. 167 traps: SmallVec<[MachTrap; 16]>, 168 /// Any call site records referring to this code. 169 call_sites: SmallVec<[MachCallSite; 16]>, 170 /// Any source location mappings referring to this code. 171 srclocs: SmallVec<[MachSrcLoc; 64]>, 172 /// Any stack maps referring to this code. 173 stack_maps: SmallVec<[MachStackMap; 8]>, 174 /// The current source location in progress (after `start_srcloc()` and 175 /// before `end_srcloc()`). This is a (start_offset, src_loc) tuple. 176 cur_srcloc: Option<(CodeOffset, SourceLoc)>, 177 /// Known label offsets; `UNKNOWN_LABEL_OFFSET` if unknown. 178 label_offsets: SmallVec<[CodeOffset; 16]>, 179 /// Label aliases: when one label points to an unconditional jump, and that 180 /// jump points to another label, we can redirect references to the first 181 /// label immediately to the second. 182 /// 183 /// Invariant: we don't have label-alias cycles. We ensure this by, 184 /// before setting label A to alias label B, resolving B's alias 185 /// target (iteratively until a non-aliased label); if B is already 186 /// aliased to A, then we cannot alias A back to B. 187 label_aliases: SmallVec<[MachLabel; 16]>, 188 /// Constants that must be emitted at some point. 189 pending_constants: SmallVec<[MachLabelConstant; 16]>, 190 /// Fixups that must be performed after all code is emitted. 191 fixup_records: SmallVec<[MachLabelFixup<I>; 16]>, 192 /// Current deadline at which all constants are flushed and all code labels 193 /// are extended by emitting long-range jumps in an island. This flush 194 /// should be rare (e.g., on AArch64, the shortest-range PC-rel references 195 /// are +/- 1MB for conditional jumps and load-literal instructions), so 196 /// it's acceptable to track a minimum and flush-all rather than doing more 197 /// detailed "current minimum" / sort-by-deadline trickery. 198 island_deadline: CodeOffset, 199 /// How many bytes are needed in the worst case for an island, given all 200 /// pending constants and fixups. 201 island_worst_case_size: CodeOffset, 202 /// Latest branches, to facilitate in-place editing for better fallthrough 203 /// behavior and empty-block removal. 204 latest_branches: SmallVec<[MachBranch; 4]>, 205 /// All labels at the current offset (emission tail). This is lazily 206 /// cleared: it is actually accurate as long as the current offset is 207 /// `labels_at_tail_off`, but if `cur_offset()` has grown larger, it should 208 /// be considered as empty. 209 /// 210 /// For correctness, this *must* be complete (i.e., the vector must contain 211 /// all labels whose offsets are resolved to the current tail), because we 212 /// rely on it to update labels when we truncate branches. 213 labels_at_tail: SmallVec<[MachLabel; 4]>, 214 /// The last offset at which `labels_at_tail` is valid. It is conceptually 215 /// always describing the tail of the buffer, but we do not clear 216 /// `labels_at_tail` eagerly when the tail grows, rather we lazily clear it 217 /// when the offset has grown past this (`labels_at_tail_off`) point. 218 /// Always <= `cur_offset()`. 219 labels_at_tail_off: CodeOffset, 220 } 221 222 /// A `MachBuffer` once emission is completed: holds generated code and records, 223 /// without fixups. This allows the type to be independent of the backend. 224 pub struct MachBufferFinalized { 225 /// The buffer contents, as raw bytes. 226 pub data: SmallVec<[u8; 1024]>, 227 /// Any relocations referring to this code. Note that only *external* 228 /// relocations are tracked here; references to labels within the buffer are 229 /// resolved before emission. 230 relocs: SmallVec<[MachReloc; 16]>, 231 /// Any trap records referring to this code. 232 traps: SmallVec<[MachTrap; 16]>, 233 /// Any call site records referring to this code. 234 call_sites: SmallVec<[MachCallSite; 16]>, 235 /// Any source location mappings referring to this code. 236 srclocs: SmallVec<[MachSrcLoc; 64]>, 237 /// Any stack maps referring to this code. 238 stack_maps: SmallVec<[MachStackMap; 8]>, 239 } 240 241 static UNKNOWN_LABEL_OFFSET: CodeOffset = 0xffff_ffff; 242 static UNKNOWN_LABEL: MachLabel = MachLabel(0xffff_ffff); 243 244 /// A label refers to some offset in a `MachBuffer`. It may not be resolved at 245 /// the point at which it is used by emitted code; the buffer records "fixups" 246 /// for references to the label, and will come back and patch the code 247 /// appropriately when the label's location is eventually known. 248 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] 249 pub struct MachLabel(u32); 250 251 impl MachLabel { 252 /// Get a label for a block. (The first N MachLabels are always reseved for 253 /// the N blocks in the vcode.) 254 pub fn from_block(bindex: BlockIndex) -> MachLabel { 255 MachLabel(bindex) 256 } 257 258 /// Get the numeric label index. 259 pub fn get(self) -> u32 { 260 self.0 261 } 262 } 263 264 /// A stack map extent, when creating a stack map. 265 pub enum StackMapExtent { 266 /// The stack map starts at this instruction, and ends after the number of upcoming bytes 267 /// (note: this is a code offset diff). 268 UpcomingBytes(CodeOffset), 269 270 /// The stack map started at the given offset and ends at the current one. This helps 271 /// architectures where the instruction size has not a fixed length. 272 StartedAtOffset(CodeOffset), 273 } 274 275 impl<I: VCodeInst> MachBuffer<I> { 276 /// Create a new section, known to start at `start_offset` and with a size limited to 277 /// `length_limit`. 278 pub fn new() -> MachBuffer<I> { 279 MachBuffer { 280 data: SmallVec::new(), 281 relocs: SmallVec::new(), 282 traps: SmallVec::new(), 283 call_sites: SmallVec::new(), 284 srclocs: SmallVec::new(), 285 stack_maps: SmallVec::new(), 286 cur_srcloc: None, 287 label_offsets: SmallVec::new(), 288 label_aliases: SmallVec::new(), 289 pending_constants: SmallVec::new(), 290 fixup_records: SmallVec::new(), 291 island_deadline: UNKNOWN_LABEL_OFFSET, 292 island_worst_case_size: 0, 293 latest_branches: SmallVec::new(), 294 labels_at_tail: SmallVec::new(), 295 labels_at_tail_off: 0, 296 } 297 } 298 299 /// Debug-only: check invariants of labels and branch-records described 300 /// under "Branch-optimization Correctness" above. 301 #[cfg(debug)] 302 fn check_label_branch_invariants(&self) { 303 let cur_off = self.cur_offset(); 304 // Check that every entry in latest_branches has *correct* 305 // labels_at_this_branch lists. We do not check completeness because 306 // that would require building a reverse index, which is too slow even 307 // for a debug invariant check. 308 let mut last_end = 0; 309 for b in &self.latest_branches { 310 debug_assert!(b.start < b.end); 311 debug_assert!(b.end <= cur_off); 312 debug_assert!(b.start >= last_end); 313 last_end = b.end; 314 for &l in &b.labels_at_this_branch { 315 debug_assert_eq!(self.resolve_label_offset(l), b.start); 316 debug_assert_eq!(self.label_aliases[l.0 as usize], UNKNOWN_LABEL); 317 } 318 } 319 320 // Check that every label is unresolved, or resolved at or before 321 // cur_offset. If at cur_offset, must be in `labels_at_tail`. 322 for (i, &off) in self.label_offsets.iter().enumerate() { 323 let label = MachLabel(i as u32); 324 debug_assert!(off == UNKNOWN_LABEL_OFFSET || off <= cur_off); 325 if off == cur_off { 326 debug_assert!( 327 self.labels_at_tail_off == cur_off && self.labels_at_tail.contains(&label) 328 ); 329 } 330 } 331 332 // Check that every label in `labels_at_tail_off` is precise, i.e., 333 // resolves to the cur offset. 334 debug_assert!(self.labels_at_tail_off <= cur_off); 335 if self.labels_at_tail_off == cur_off { 336 for &l in &self.labels_at_tail { 337 debug_assert_eq!(self.resolve_label_offset(l), cur_off); 338 debug_assert_eq!(self.label_aliases[l.0 as usize], UNKNOWN_LABEL); 339 } 340 } 341 } 342 343 #[cfg(not(debug))] 344 fn check_label_branch_invariants(&self) { 345 // Nothing. 346 } 347 348 /// Current offset from start of buffer. 349 pub fn cur_offset(&self) -> CodeOffset { 350 self.data.len() as CodeOffset 351 } 352 353 /// Add a byte. 354 pub fn put1(&mut self, value: u8) { 355 trace!("MachBuffer: put byte @ {}: {:x}", self.cur_offset(), value); 356 self.data.push(value); 357 358 // Post-invariant: conceptual-labels_at_tail contains a complete and 359 // precise list of labels bound at `cur_offset()`. We have advanced 360 // `cur_offset()`, hence if it had been equal to `labels_at_tail_off` 361 // before, it is not anymore (and it cannot become equal, because 362 // `labels_at_tail_off` is always <= `cur_offset()`). Thus the list is 363 // conceptually empty (even though it is only lazily cleared). No labels 364 // can be bound at this new offset (by invariant on `label_offsets`). 365 // Hence the invariant holds. 366 } 367 368 /// Add 2 bytes. 369 pub fn put2(&mut self, value: u16) { 370 trace!( 371 "MachBuffer: put 16-bit word @ {}: {:x}", 372 self.cur_offset(), 373 value 374 ); 375 let bytes = value.to_le_bytes(); 376 self.data.extend_from_slice(&bytes[..]); 377 378 // Post-invariant: as for `put1()`. 379 } 380 381 /// Add 4 bytes. 382 pub fn put4(&mut self, value: u32) { 383 trace!( 384 "MachBuffer: put 32-bit word @ {}: {:x}", 385 self.cur_offset(), 386 value 387 ); 388 let bytes = value.to_le_bytes(); 389 self.data.extend_from_slice(&bytes[..]); 390 391 // Post-invariant: as for `put1()`. 392 } 393 394 /// Add 8 bytes. 395 pub fn put8(&mut self, value: u64) { 396 trace!( 397 "MachBuffer: put 64-bit word @ {}: {:x}", 398 self.cur_offset(), 399 value 400 ); 401 let bytes = value.to_le_bytes(); 402 self.data.extend_from_slice(&bytes[..]); 403 404 // Post-invariant: as for `put1()`. 405 } 406 407 /// Add a slice of bytes. 408 pub fn put_data(&mut self, data: &[u8]) { 409 trace!( 410 "MachBuffer: put data @ {}: len {}", 411 self.cur_offset(), 412 data.len() 413 ); 414 self.data.extend_from_slice(data); 415 416 // Post-invariant: as for `put1()`. 417 } 418 419 /// Reserve appended space and return a mutable slice referring to it. 420 pub fn get_appended_space(&mut self, len: usize) -> &mut [u8] { 421 trace!("MachBuffer: put data @ {}: len {}", self.cur_offset(), len); 422 let off = self.data.len(); 423 let new_len = self.data.len() + len; 424 self.data.resize(new_len, 0); 425 &mut self.data[off..] 426 427 // Post-invariant: as for `put1()`. 428 } 429 430 /// Align up to the given alignment. 431 pub fn align_to(&mut self, align_to: CodeOffset) { 432 trace!("MachBuffer: align to {}", align_to); 433 assert!(align_to.is_power_of_two()); 434 while self.cur_offset() & (align_to - 1) != 0 { 435 self.put1(0); 436 } 437 438 // Post-invariant: as for `put1()`. 439 } 440 441 /// Allocate a `Label` to refer to some offset. May not be bound to a fixed 442 /// offset yet. 443 pub fn get_label(&mut self) -> MachLabel { 444 let l = self.label_offsets.len() as u32; 445 self.label_offsets.push(UNKNOWN_LABEL_OFFSET); 446 self.label_aliases.push(UNKNOWN_LABEL); 447 trace!("MachBuffer: new label -> {:?}", MachLabel(l)); 448 MachLabel(l) 449 450 // Post-invariant: the only mutation is to add a new label; it has no 451 // bound offset yet, so it trivially satisfies all invariants. 452 } 453 454 /// Reserve the first N MachLabels for blocks. 455 pub fn reserve_labels_for_blocks(&mut self, blocks: BlockIndex) { 456 trace!("MachBuffer: first {} labels are for blocks", blocks); 457 debug_assert!(self.label_offsets.is_empty()); 458 self.label_offsets 459 .resize(blocks as usize, UNKNOWN_LABEL_OFFSET); 460 self.label_aliases.resize(blocks as usize, UNKNOWN_LABEL); 461 462 // Post-invariant: as for `get_label()`. 463 } 464 465 /// Bind a label to the current offset. A label can only be bound once. 466 pub fn bind_label(&mut self, label: MachLabel) { 467 trace!( 468 "MachBuffer: bind label {:?} at offset {}", 469 label, 470 self.cur_offset() 471 ); 472 debug_assert_eq!(self.label_offsets[label.0 as usize], UNKNOWN_LABEL_OFFSET); 473 debug_assert_eq!(self.label_aliases[label.0 as usize], UNKNOWN_LABEL); 474 let offset = self.cur_offset(); 475 self.label_offsets[label.0 as usize] = offset; 476 self.lazily_clear_labels_at_tail(); 477 self.labels_at_tail.push(label); 478 479 // Invariants hold: bound offset of label is <= cur_offset (in fact it 480 // is equal). If the `labels_at_tail` list was complete and precise 481 // before, it is still, because we have bound this label to the current 482 // offset and added it to the list (which contains all labels at the 483 // current offset). 484 485 self.check_label_branch_invariants(); 486 self.optimize_branches(); 487 488 // Post-invariant: by `optimize_branches()` (see argument there). 489 self.check_label_branch_invariants(); 490 } 491 492 /// Lazily clear `labels_at_tail` if the tail offset has moved beyond the 493 /// offset that it applies to. 494 fn lazily_clear_labels_at_tail(&mut self) { 495 let offset = self.cur_offset(); 496 if offset > self.labels_at_tail_off { 497 self.labels_at_tail_off = offset; 498 self.labels_at_tail.clear(); 499 } 500 501 // Post-invariant: either labels_at_tail_off was at cur_offset, and 502 // state is untouched, or was less than cur_offset, in which case the 503 // labels_at_tail list was conceptually empty, and is now actually 504 // empty. 505 } 506 507 /// Resolve a label to an offset, if known. May return `UNKNOWN_LABEL_OFFSET`. 508 fn resolve_label_offset(&self, mut label: MachLabel) -> CodeOffset { 509 let mut iters = 0; 510 while self.label_aliases[label.0 as usize] != UNKNOWN_LABEL { 511 label = self.label_aliases[label.0 as usize]; 512 // To protect against an infinite loop (despite our assurances to 513 // ourselves that the invariants make this impossible), assert out 514 // after 1M iterations. The number of basic blocks is limited 515 // in most contexts anyway so this should be impossible to hit with 516 // a legitimate input. 517 iters += 1; 518 assert!(iters < 1_000_000, "Unexpected cycle in label aliases"); 519 } 520 self.label_offsets[label.0 as usize] 521 522 // Post-invariant: no mutations. 523 } 524 525 /// Emit a reference to the given label with the given reference type (i.e., 526 /// branch-instruction format) at the current offset. This is like a 527 /// relocation, but handled internally. 528 /// 529 /// This can be called before the branch is actually emitted; fixups will 530 /// not happen until an island is emitted or the buffer is finished. 531 pub fn use_label_at_offset(&mut self, offset: CodeOffset, label: MachLabel, kind: I::LabelUse) { 532 trace!( 533 "MachBuffer: use_label_at_offset: offset {} label {:?} kind {:?}", 534 offset, 535 label, 536 kind 537 ); 538 539 // Add the fixup, and update the worst-case island size based on a 540 // veneer for this label use. 541 self.fixup_records.push(MachLabelFixup { 542 label, 543 offset, 544 kind, 545 }); 546 if kind.supports_veneer() { 547 self.island_worst_case_size += kind.veneer_size(); 548 self.island_worst_case_size &= !(I::LabelUse::ALIGN - 1); 549 } 550 let deadline = offset + kind.max_pos_range(); 551 if deadline < self.island_deadline { 552 self.island_deadline = deadline; 553 } 554 555 // Post-invariant: no mutations to branches/labels data structures. 556 self.check_label_branch_invariants(); 557 } 558 559 /// Inform the buffer of an unconditional branch at the given offset, 560 /// targetting the given label. May be used to optimize branches. 561 /// The last added label-use must correspond to this branch. 562 /// This must be called when the current offset is equal to `start`; i.e., 563 /// before actually emitting the branch. This implies that for a branch that 564 /// uses a label and is eligible for optimizations by the MachBuffer, the 565 /// proper sequence is: 566 /// 567 /// - Call `use_label_at_offset()` to emit the fixup record. 568 /// - Call `add_uncond_branch()` to make note of the branch. 569 /// - Emit the bytes for the branch's machine code. 570 /// 571 /// Additional requirement: no labels may be bound between `start` and `end` 572 /// (exclusive on both ends). 573 pub fn add_uncond_branch(&mut self, start: CodeOffset, end: CodeOffset, target: MachLabel) { 574 assert!(self.cur_offset() == start); 575 debug_assert!(end > start); 576 assert!(!self.fixup_records.is_empty()); 577 let fixup = self.fixup_records.len() - 1; 578 self.lazily_clear_labels_at_tail(); 579 self.latest_branches.push(MachBranch { 580 start, 581 end, 582 target, 583 fixup, 584 inverted: None, 585 labels_at_this_branch: self.labels_at_tail.clone(), 586 }); 587 588 // Post-invariant: we asserted branch start is current tail; the list of 589 // labels at branch is cloned from list of labels at current tail. 590 self.check_label_branch_invariants(); 591 } 592 593 /// Inform the buffer of a conditional branch at the given offset, 594 /// targetting the given label. May be used to optimize branches. 595 /// The last added label-use must correspond to this branch. 596 /// 597 /// Additional requirement: no labels may be bound between `start` and `end` 598 /// (exclusive on both ends). 599 pub fn add_cond_branch( 600 &mut self, 601 start: CodeOffset, 602 end: CodeOffset, 603 target: MachLabel, 604 inverted: &[u8], 605 ) { 606 assert!(self.cur_offset() == start); 607 debug_assert!(end > start); 608 assert!(!self.fixup_records.is_empty()); 609 debug_assert!(inverted.len() == (end - start) as usize); 610 let fixup = self.fixup_records.len() - 1; 611 let inverted = Some(SmallVec::from(inverted)); 612 self.lazily_clear_labels_at_tail(); 613 self.latest_branches.push(MachBranch { 614 start, 615 end, 616 target, 617 fixup, 618 inverted, 619 labels_at_this_branch: self.labels_at_tail.clone(), 620 }); 621 622 // Post-invariant: we asserted branch start is current tail; labels at 623 // branch list is cloned from list of labels at current tail. 624 self.check_label_branch_invariants(); 625 } 626 627 fn truncate_last_branch(&mut self) { 628 self.lazily_clear_labels_at_tail(); 629 // Invariants hold at this point. 630 631 let b = self.latest_branches.pop().unwrap(); 632 assert!(b.end == self.cur_offset()); 633 634 // State: 635 // [PRE CODE] 636 // Offset b.start, b.labels_at_this_branch: 637 // [BRANCH CODE] 638 // cur_off, self.labels_at_tail --> 639 // (end of buffer) 640 self.data.truncate(b.start as usize); 641 self.fixup_records.truncate(b.fixup); 642 // State: 643 // [PRE CODE] 644 // cur_off, Offset b.start, b.labels_at_this_branch: 645 // (end of buffer) 646 // 647 // self.labels_at_tail --> (past end of buffer) 648 let cur_off = self.cur_offset(); 649 self.labels_at_tail_off = cur_off; 650 // State: 651 // [PRE CODE] 652 // cur_off, Offset b.start, b.labels_at_this_branch, 653 // self.labels_at_tail: 654 // (end of buffer) 655 // 656 // resolve_label_offset(l) for l in labels_at_tail: 657 // (past end of buffer) 658 659 trace!( 660 "truncate_last_branch: truncated {:?}; off now {}", 661 b, 662 cur_off 663 ); 664 665 // Fix up resolved label offsets for labels at tail. 666 for &l in &self.labels_at_tail { 667 self.label_offsets[l.0 as usize] = cur_off; 668 } 669 // Old labels_at_this_branch are now at cur_off. 670 self.labels_at_tail 671 .extend(b.labels_at_this_branch.into_iter()); 672 673 // Post-invariant: this operation is defined to truncate the buffer, 674 // which moves cur_off backward, and to move labels at the end of the 675 // buffer back to the start-of-branch offset. 676 // 677 // latest_branches satisfies all invariants: 678 // - it has no branches past the end of the buffer (branches are in 679 // order, we removed the last one, and we truncated the buffer to just 680 // before the start of that branch) 681 // - no labels were moved to lower offsets than the (new) cur_off, so 682 // the labels_at_this_branch list for any other branch need not change. 683 // 684 // labels_at_tail satisfies all invariants: 685 // - all labels that were at the tail after the truncated branch are 686 // moved backward to just before the branch, which becomes the new tail; 687 // thus every element in the list should remain (ensured by `.extend()` 688 // above). 689 // - all labels that refer to the new tail, which is the start-offset of 690 // the truncated branch, must be present. The `labels_at_this_branch` 691 // list in the truncated branch's record is a complete and precise list 692 // of exactly these labels; we append these to labels_at_tail. 693 // - labels_at_tail_off is at cur_off after truncation occurs, so the 694 // list is valid (not to be lazily cleared). 695 // 696 // The stated operation was performed: 697 // - For each label at the end of the buffer prior to this method, it 698 // now resolves to the new (truncated) end of the buffer: it must have 699 // been in `labels_at_tail` (this list is precise and complete, and 700 // the tail was at the end of the truncated branch on entry), and we 701 // iterate over this list and set `label_offsets` to the new tail. 702 // None of these labels could have been an alias (by invariant), so 703 // `label_offsets` is authoritative for each. 704 // - No other labels will be past the end of the buffer, because of the 705 // requirement that no labels be bound to the middle of branch ranges 706 // (see comments to `add_{cond,uncond}_branch()`). 707 // - The buffer is truncated to just before the last branch, and the 708 // fixup record referring to that last branch is removed. 709 self.check_label_branch_invariants(); 710 } 711 712 fn optimize_branches(&mut self) { 713 self.lazily_clear_labels_at_tail(); 714 // Invariants valid at this point. 715 716 trace!( 717 "enter optimize_branches:\n b = {:?}\n l = {:?}\n f = {:?}", 718 self.latest_branches, 719 self.labels_at_tail, 720 self.fixup_records 721 ); 722 723 // We continue to munch on branches at the tail of the buffer until no 724 // more rules apply. Note that the loop only continues if a branch is 725 // actually truncated (or if labels are redirected away from a branch), 726 // so this always makes progress. 727 while let Some(b) = self.latest_branches.last() { 728 let cur_off = self.cur_offset(); 729 trace!("optimize_branches: last branch {:?} at off {}", b, cur_off); 730 // If there has been any code emission since the end of the last branch or 731 // label definition, then there's nothing we can edit (because we 732 // don't move code once placed, only back up and overwrite), so 733 // clear the records and finish. 734 if b.end < cur_off { 735 break; 736 } 737 738 // Invariant: we are looking at a branch that ends at the tail of 739 // the buffer. 740 741 // For any branch, conditional or unconditional: 742 // - If the target is a label at the current offset, then remove 743 // the conditional branch, and reset all labels that targetted 744 // the current offset (end of branch) to the truncated 745 // end-of-code. 746 // 747 // Preserves execution semantics: a branch to its own fallthrough 748 // address is equivalent to a no-op; in both cases, nextPC is the 749 // fallthrough. 750 if self.resolve_label_offset(b.target) == cur_off { 751 trace!("branch with target == cur off; truncating"); 752 self.truncate_last_branch(); 753 continue; 754 } 755 756 // If latest is an unconditional branch: 757 // 758 // - If the branch's target is not its own start address, then for 759 // each label at the start of branch, make the label an alias of the 760 // branch target, and remove the label from the "labels at this 761 // branch" list. 762 // 763 // - Preserves execution semantics: an unconditional branch's 764 // only effect is to set PC to a new PC; this change simply 765 // collapses one step in the step-semantics. 766 // 767 // - Post-invariant: the labels that were bound to the start of 768 // this branch become aliases, so they must not be present in any 769 // labels-at-this-branch list or the labels-at-tail list. The 770 // labels are removed form the latest-branch record's 771 // labels-at-this-branch list, and are never placed in the 772 // labels-at-tail list. Furthermore, it is correct that they are 773 // not in either list, because they are now aliases, and labels 774 // that are aliases remain aliases forever. 775 // 776 // - If there is a prior unconditional branch that ends just before 777 // this one begins, and this branch has no labels bound to its 778 // start, then we can truncate this branch, because it is entirely 779 // unreachable (we have redirected all labels that make it 780 // reachable otherwise). Do so and continue around the loop. 781 // 782 // - Preserves execution semantics: the branch is unreachable, 783 // because execution can only flow into an instruction from the 784 // prior instruction's fallthrough or from a branch bound to that 785 // instruction's start offset. Unconditional branches have no 786 // fallthrough, so if the prior instruction is an unconditional 787 // branch, no fallthrough entry can happen. The 788 // labels-at-this-branch list is complete (by invariant), so if it 789 // is empty, then the instruction is entirely unreachable. Thus, 790 // it can be removed. 791 // 792 // - Post-invariant: ensured by truncate_last_branch(). 793 // 794 // - If there is a prior conditional branch whose target label 795 // resolves to the current offset (branches around the 796 // unconditional branch), then remove the unconditional branch, 797 // and make the target of the unconditional the target of the 798 // conditional instead. 799 // 800 // - Preserves execution semantics: previously we had: 801 // 802 // L1: 803 // cond_br L2 804 // br L3 805 // L2: 806 // (end of buffer) 807 // 808 // by removing the last branch, we have: 809 // 810 // L1: 811 // cond_br L2 812 // L2: 813 // (end of buffer) 814 // 815 // we then fix up the records for the conditional branch to 816 // have: 817 // 818 // L1: 819 // cond_br.inverted L3 820 // L2: 821 // 822 // In the original code, control flow reaches L2 when the 823 // conditional branch's predicate is true, and L3 otherwise. In 824 // the optimized code, the same is true. 825 // 826 // - Post-invariant: all edits to latest_branches and 827 // labels_at_tail are performed by `truncate_last_branch()`, 828 // which maintains the invariants at each step. 829 830 if b.is_uncond() { 831 // Set any label equal to current branch's start as an alias of 832 // the branch's target, if the target is not the branch itself 833 // (i.e., an infinite loop). 834 // 835 // We cannot perform this aliasing if the target of this branch 836 // ultimately aliases back here; if so, we need to keep this 837 // branch, so break out of this loop entirely (and clear the 838 // latest-branches list below). 839 // 840 // Note that this check is what prevents cycles from forming in 841 // `self.label_aliases`. To see why, consider an arbitrary start 842 // state: 843 // 844 // label_aliases[L1] = L2, label_aliases[L2] = L3, ..., up to 845 // Ln, which is not aliased. 846 // 847 // We would create a cycle if we assigned label_aliases[Ln] 848 // = L1. Note that the below assignment is the only write 849 // to label_aliases. 850 // 851 // By our other invariants, we have that Ln (`l` below) 852 // resolves to the offset `b.start`, because it is in the 853 // set `b.labels_at_this_branch`. 854 // 855 // If L1 were already aliased, through some arbitrarily deep 856 // chain, to Ln, then it must also resolve to this offset 857 // `b.start`. 858 // 859 // By checking the resolution of `L1` against this offset, 860 // and aborting this branch-simplification if they are 861 // equal, we prevent the below assignment from ever creating 862 // a cycle. 863 if self.resolve_label_offset(b.target) != b.start { 864 let redirected = b.labels_at_this_branch.len(); 865 for &l in &b.labels_at_this_branch { 866 trace!( 867 " -> label at start of branch {:?} redirected to target {:?}", 868 l, 869 b.target 870 ); 871 self.label_aliases[l.0 as usize] = b.target; 872 // NOTE: we continue to ensure the invariant that labels 873 // pointing to tail of buffer are in `labels_at_tail` 874 // because we already ensured above that the last branch 875 // cannot have a target of `cur_off`; so we never have 876 // to put the label into `labels_at_tail` when moving it 877 // here. 878 } 879 // Maintain invariant: all branches have been redirected 880 // and are no longer pointing at the start of this branch. 881 let mut_b = self.latest_branches.last_mut().unwrap(); 882 mut_b.labels_at_this_branch.clear(); 883 884 if redirected > 0 { 885 trace!(" -> after label redirects, restarting loop"); 886 continue; 887 } 888 } else { 889 break; 890 } 891 892 let b = self.latest_branches.last().unwrap(); 893 894 // Examine any immediately preceding branch. 895 if self.latest_branches.len() > 1 { 896 let prev_b = &self.latest_branches[self.latest_branches.len() - 2]; 897 trace!(" -> more than one branch; prev_b = {:?}", prev_b); 898 // This uncond is immediately after another uncond; we 899 // should have already redirected labels to this uncond away 900 // (but check to be sure); so we can truncate this uncond. 901 if prev_b.is_uncond() 902 && prev_b.end == b.start 903 && b.labels_at_this_branch.is_empty() 904 { 905 trace!(" -> uncond follows another uncond; truncating"); 906 self.truncate_last_branch(); 907 continue; 908 } 909 910 // This uncond is immediately after a conditional, and the 911 // conditional's target is the end of this uncond, and we've 912 // already redirected labels to this uncond away; so we can 913 // truncate this uncond, flip the sense of the conditional, and 914 // set the conditional's target (in `latest_branches` and in 915 // `fixup_records`) to the uncond's target. 916 if prev_b.is_cond() 917 && prev_b.end == b.start 918 && self.resolve_label_offset(prev_b.target) == cur_off 919 { 920 trace!(" -> uncond follows a conditional, and conditional's target resolves to current offset"); 921 // Save the target of the uncond (this becomes the 922 // target of the cond), and truncate the uncond. 923 let target = b.target; 924 let data = prev_b.inverted.clone().unwrap(); 925 self.truncate_last_branch(); 926 927 // Mutate the code and cond branch. 928 let off_before_edit = self.cur_offset(); 929 let prev_b = self.latest_branches.last_mut().unwrap(); 930 let not_inverted = SmallVec::from( 931 &self.data[(prev_b.start as usize)..(prev_b.end as usize)], 932 ); 933 934 // Low-level edit: replaces bytes of branch with 935 // inverted form. cur_off remains the same afterward, so 936 // we do not need to modify label data structures. 937 self.data.truncate(prev_b.start as usize); 938 self.data.extend_from_slice(&data[..]); 939 940 // Save the original code as the inversion of the 941 // inverted branch, in case we later edit this branch 942 // again. 943 prev_b.inverted = Some(not_inverted); 944 self.fixup_records[prev_b.fixup].label = target; 945 trace!(" -> reassigning target of condbr to {:?}", target); 946 prev_b.target = target; 947 debug_assert_eq!(off_before_edit, self.cur_offset()); 948 continue; 949 } 950 } 951 } 952 953 // If we couldn't do anything with the last branch, then break. 954 break; 955 } 956 957 self.purge_latest_branches(); 958 959 trace!( 960 "leave optimize_branches:\n b = {:?}\n l = {:?}\n f = {:?}", 961 self.latest_branches, 962 self.labels_at_tail, 963 self.fixup_records 964 ); 965 } 966 967 fn purge_latest_branches(&mut self) { 968 // All of our branch simplification rules work only if a branch ends at 969 // the tail of the buffer, with no following code; and branches are in 970 // order in latest_branches; so if the last entry ends prior to 971 // cur_offset, then clear all entries. 972 let cur_off = self.cur_offset(); 973 if let Some(l) = self.latest_branches.last() { 974 if l.end < cur_off { 975 trace!("purge_latest_branches: removing branch {:?}", l); 976 self.latest_branches.clear(); 977 } 978 } 979 980 // Post-invariant: no invariant requires any branch to appear in 981 // `latest_branches`; it is always optional. The list-clear above thus 982 // preserves all semantics. 983 } 984 985 /// Emit a constant at some point in the future, binding the given label to 986 /// its offset. The constant will be placed at most `max_distance` from the 987 /// current offset. 988 pub fn defer_constant( 989 &mut self, 990 label: MachLabel, 991 align: CodeOffset, 992 data: &[u8], 993 max_distance: CodeOffset, 994 ) { 995 let deadline = self.cur_offset() + max_distance; 996 self.island_worst_case_size += data.len() as CodeOffset; 997 self.island_worst_case_size &= !(I::LabelUse::ALIGN - 1); 998 self.pending_constants.push(MachLabelConstant { 999 label, 1000 align, 1001 data: SmallVec::from(data), 1002 }); 1003 if deadline < self.island_deadline { 1004 self.island_deadline = deadline; 1005 } 1006 } 1007 1008 /// Is an island needed within the next N bytes? 1009 pub fn island_needed(&self, distance: CodeOffset) -> bool { 1010 let worst_case_end_of_island = self.cur_offset() + distance + self.island_worst_case_size; 1011 worst_case_end_of_island > self.island_deadline 1012 } 1013 1014 /// Emit all pending constants and veneers. Should only be called if 1015 /// `island_needed()` returns true, i.e., if we actually reach a deadline: 1016 /// otherwise, unnecessary veneers may be inserted. 1017 pub fn emit_island(&mut self) { 1018 // We're going to purge fixups, so no latest-branch editing can happen 1019 // anymore. 1020 self.latest_branches.clear(); 1021 1022 let pending_constants = mem::replace(&mut self.pending_constants, SmallVec::new()); 1023 for MachLabelConstant { label, align, data } in pending_constants.into_iter() { 1024 self.align_to(align); 1025 self.bind_label(label); 1026 self.put_data(&data[..]); 1027 } 1028 1029 let fixup_records = mem::replace(&mut self.fixup_records, SmallVec::new()); 1030 let mut new_fixups = SmallVec::new(); 1031 for MachLabelFixup { 1032 label, 1033 offset, 1034 kind, 1035 } in fixup_records.into_iter() 1036 { 1037 trace!( 1038 "emit_island: fixup for label {:?} at offset {} kind {:?}", 1039 label, 1040 offset, 1041 kind 1042 ); 1043 // We eagerly perform fixups whose label targets are known, if not out 1044 // of range, to avoid unnecessary veneers. 1045 let label_offset = self.resolve_label_offset(label); 1046 let known = label_offset != UNKNOWN_LABEL_OFFSET; 1047 let in_range = if known { 1048 if label_offset >= offset { 1049 (label_offset - offset) <= kind.max_pos_range() 1050 } else { 1051 (offset - label_offset) <= kind.max_neg_range() 1052 } 1053 } else { 1054 false 1055 }; 1056 1057 trace!( 1058 " -> label_offset = {}, known = {}, in_range = {} (pos {} neg {})", 1059 label_offset, 1060 known, 1061 in_range, 1062 kind.max_pos_range(), 1063 kind.max_neg_range() 1064 ); 1065 1066 let start = offset as usize; 1067 let end = (offset + kind.patch_size()) as usize; 1068 if in_range { 1069 debug_assert!(known); // implied by in_range. 1070 let slice = &mut self.data[start..end]; 1071 trace!("patching in-range!"); 1072 kind.patch(slice, offset, label_offset); 1073 } else if !known && !kind.supports_veneer() { 1074 // Nothing for now. Keep it for next round. 1075 new_fixups.push(MachLabelFixup { 1076 label, 1077 offset, 1078 kind, 1079 }); 1080 } else if !in_range && kind.supports_veneer() { 1081 // Allocate space for a veneer in the island. 1082 self.align_to(I::LabelUse::ALIGN); 1083 let veneer_offset = self.cur_offset(); 1084 trace!("making a veneer at {}", veneer_offset); 1085 let slice = &mut self.data[start..end]; 1086 // Patch the original label use to refer to the veneer. 1087 trace!( 1088 "patching original at offset {} to veneer offset {}", 1089 offset, 1090 veneer_offset 1091 ); 1092 kind.patch(slice, offset, veneer_offset); 1093 // Generate the veneer. 1094 let veneer_slice = self.get_appended_space(kind.veneer_size() as usize); 1095 let (veneer_fixup_off, veneer_label_use) = 1096 kind.generate_veneer(veneer_slice, veneer_offset); 1097 trace!( 1098 "generated veneer; fixup offset {}, label_use {:?}", 1099 veneer_fixup_off, 1100 veneer_label_use 1101 ); 1102 // If the label is known (but was just out of range), do the 1103 // veneer label-use fixup now too; otherwise, save it for later. 1104 if known { 1105 let start = veneer_fixup_off as usize; 1106 let end = (veneer_fixup_off + veneer_label_use.patch_size()) as usize; 1107 let veneer_slice = &mut self.data[start..end]; 1108 trace!("doing veneer fixup right away too"); 1109 veneer_label_use.patch(veneer_slice, veneer_fixup_off, label_offset); 1110 } else { 1111 new_fixups.push(MachLabelFixup { 1112 label, 1113 offset: veneer_fixup_off, 1114 kind: veneer_label_use, 1115 }); 1116 } 1117 } else { 1118 panic!( 1119 "Cannot support label-use {:?} (known = {}, in-range = {})", 1120 kind, known, in_range 1121 ); 1122 } 1123 } 1124 1125 self.fixup_records = new_fixups; 1126 self.island_deadline = UNKNOWN_LABEL_OFFSET; 1127 } 1128 1129 /// Finish any deferred emissions and/or fixups. 1130 pub fn finish(mut self) -> MachBufferFinalized { 1131 let _tt = timing::vcode_emit_finish(); 1132 1133 // Ensure that all labels are defined. This is a full (release-mode) 1134 // assert because we must avoid looping indefinitely below; an 1135 // unresolved label will prevent the fixup_records vec from emptying. 1136 assert!(self 1137 .label_offsets 1138 .iter() 1139 .all(|&off| off != UNKNOWN_LABEL_OFFSET)); 1140 1141 while !self.pending_constants.is_empty() || !self.fixup_records.is_empty() { 1142 // `emit_island()` will emit any pending veneers and constants, and 1143 // as a side-effect, will also take care of any fixups with resolved 1144 // labels eagerly. 1145 self.emit_island(); 1146 } 1147 1148 MachBufferFinalized { 1149 data: self.data, 1150 relocs: self.relocs, 1151 traps: self.traps, 1152 call_sites: self.call_sites, 1153 srclocs: self.srclocs, 1154 stack_maps: self.stack_maps, 1155 } 1156 } 1157 1158 /// Add an external relocation at the current offset. 1159 pub fn add_reloc( 1160 &mut self, 1161 srcloc: SourceLoc, 1162 kind: Reloc, 1163 name: &ExternalName, 1164 addend: Addend, 1165 ) { 1166 let name = name.clone(); 1167 self.relocs.push(MachReloc { 1168 offset: self.data.len() as CodeOffset, 1169 srcloc, 1170 kind, 1171 name, 1172 addend, 1173 }); 1174 } 1175 1176 /// Add a trap record at the current offset. 1177 pub fn add_trap(&mut self, srcloc: SourceLoc, code: TrapCode) { 1178 self.traps.push(MachTrap { 1179 offset: self.data.len() as CodeOffset, 1180 srcloc, 1181 code, 1182 }); 1183 } 1184 1185 /// Add a call-site record at the current offset. 1186 pub fn add_call_site(&mut self, srcloc: SourceLoc, opcode: Opcode) { 1187 self.call_sites.push(MachCallSite { 1188 ret_addr: self.data.len() as CodeOffset, 1189 srcloc, 1190 opcode, 1191 }); 1192 } 1193 1194 /// Set the `SourceLoc` for code from this offset until the offset at the 1195 /// next call to `end_srcloc()`. 1196 pub fn start_srcloc(&mut self, loc: SourceLoc) { 1197 self.cur_srcloc = Some((self.cur_offset(), loc)); 1198 } 1199 1200 /// Mark the end of the `SourceLoc` segment started at the last 1201 /// `start_srcloc()` call. 1202 pub fn end_srcloc(&mut self) { 1203 let (start, loc) = self 1204 .cur_srcloc 1205 .take() 1206 .expect("end_srcloc() called without start_srcloc()"); 1207 let end = self.cur_offset(); 1208 // Skip zero-length extends. 1209 debug_assert!(end >= start); 1210 if end > start { 1211 self.srclocs.push(MachSrcLoc { start, end, loc }); 1212 } 1213 } 1214 1215 /// Add stack map metadata for this program point: a set of stack offsets 1216 /// (from SP upward) that contain live references. 1217 /// 1218 /// The `offset_to_fp` value is the offset from the nominal SP (at which the `stack_offsets` 1219 /// are based) and the FP value. By subtracting `offset_to_fp` from each `stack_offsets` 1220 /// element, one can obtain live-reference offsets from FP instead. 1221 pub fn add_stack_map(&mut self, extent: StackMapExtent, stack_map: StackMap) { 1222 let (start, end) = match extent { 1223 StackMapExtent::UpcomingBytes(insn_len) => { 1224 let start_offset = self.cur_offset(); 1225 (start_offset, start_offset + insn_len) 1226 } 1227 StackMapExtent::StartedAtOffset(start_offset) => { 1228 let end_offset = self.cur_offset(); 1229 debug_assert!(end_offset >= start_offset); 1230 (start_offset, end_offset) 1231 } 1232 }; 1233 self.stack_maps.push(MachStackMap { 1234 offset: start, 1235 offset_end: end, 1236 stack_map, 1237 }); 1238 } 1239 } 1240 1241 impl MachBufferFinalized { 1242 /// Get a list of source location mapping tuples in sorted-by-start-offset order. 1243 pub fn get_srclocs_sorted(&self) -> &[MachSrcLoc] { 1244 &self.srclocs[..] 1245 } 1246 1247 /// Get the total required size for the code. 1248 pub fn total_size(&self) -> CodeOffset { 1249 self.data.len() as CodeOffset 1250 } 1251 1252 /// Emit this buffer to the given CodeSink. 1253 pub fn emit<CS: CodeSink>(&self, sink: &mut CS) { 1254 // N.B.: we emit every section into the .text section as far as 1255 // the `CodeSink` is concerned; we do not bother to segregate 1256 // the contents into the actual program text, the jumptable and the 1257 // rodata (constant pool). This allows us to generate code assuming 1258 // that these will not be relocated relative to each other, and avoids 1259 // having to designate each section as belonging in one of the three 1260 // fixed categories defined by `CodeSink`. If this becomes a problem 1261 // later (e.g. because of memory permissions or similar), we can 1262 // add this designation and segregate the output; take care, however, 1263 // to add the appropriate relocations in this case. 1264 1265 let mut next_reloc = 0; 1266 let mut next_trap = 0; 1267 let mut next_call_site = 0; 1268 for (idx, byte) in self.data.iter().enumerate() { 1269 if next_reloc < self.relocs.len() { 1270 let reloc = &self.relocs[next_reloc]; 1271 if reloc.offset == idx as CodeOffset { 1272 sink.reloc_external(reloc.srcloc, reloc.kind, &reloc.name, reloc.addend); 1273 next_reloc += 1; 1274 } 1275 } 1276 if next_trap < self.traps.len() { 1277 let trap = &self.traps[next_trap]; 1278 if trap.offset == idx as CodeOffset { 1279 sink.trap(trap.code, trap.srcloc); 1280 next_trap += 1; 1281 } 1282 } 1283 if next_call_site < self.call_sites.len() { 1284 let call_site = &self.call_sites[next_call_site]; 1285 if call_site.ret_addr == idx as CodeOffset { 1286 sink.add_call_site(call_site.opcode, call_site.srcloc); 1287 next_call_site += 1; 1288 } 1289 } 1290 sink.put1(*byte); 1291 } 1292 1293 sink.begin_jumptables(); 1294 sink.begin_rodata(); 1295 sink.end_codegen(); 1296 } 1297 1298 /// Get the stack map metadata for this code. 1299 pub fn stack_maps(&self) -> &[MachStackMap] { 1300 &self.stack_maps[..] 1301 } 1302 } 1303 1304 /// A constant that is deferred to the next constant-pool opportunity. 1305 struct MachLabelConstant { 1306 /// This label will refer to the constant's offset. 1307 label: MachLabel, 1308 /// Required alignment. 1309 align: CodeOffset, 1310 /// This data will be emitted when able. 1311 data: SmallVec<[u8; 16]>, 1312 } 1313 1314 /// A fixup to perform on the buffer once code is emitted. Fixups always refer 1315 /// to labels and patch the code based on label offsets. Hence, they are like 1316 /// relocations, but internal to one buffer. 1317 #[derive(Debug)] 1318 struct MachLabelFixup<I: VCodeInst> { 1319 /// The label whose offset controls this fixup. 1320 label: MachLabel, 1321 /// The offset to fix up / patch to refer to this label. 1322 offset: CodeOffset, 1323 /// The kind of fixup. This is architecture-specific; each architecture may have, 1324 /// e.g., several types of branch instructions, each with differently-sized 1325 /// offset fields and different places within the instruction to place the 1326 /// bits. 1327 kind: I::LabelUse, 1328 } 1329 1330 /// A relocation resulting from a compilation. 1331 struct MachReloc { 1332 /// The offset at which the relocation applies, *relative to the 1333 /// containing section*. 1334 offset: CodeOffset, 1335 /// The original source location. 1336 srcloc: SourceLoc, 1337 /// The kind of relocation. 1338 kind: Reloc, 1339 /// The external symbol / name to which this relocation refers. 1340 name: ExternalName, 1341 /// The addend to add to the symbol value. 1342 addend: i64, 1343 } 1344 1345 /// A trap record resulting from a compilation. 1346 struct MachTrap { 1347 /// The offset at which the trap instruction occurs, *relative to the 1348 /// containing section*. 1349 offset: CodeOffset, 1350 /// The original source location. 1351 srcloc: SourceLoc, 1352 /// The trap code. 1353 code: TrapCode, 1354 } 1355 1356 /// A call site record resulting from a compilation. 1357 struct MachCallSite { 1358 /// The offset of the call's return address, *relative to the containing section*. 1359 ret_addr: CodeOffset, 1360 /// The original source location. 1361 srcloc: SourceLoc, 1362 /// The call's opcode. 1363 opcode: Opcode, 1364 } 1365 1366 /// A source-location mapping resulting from a compilation. 1367 #[derive(Clone, Debug)] 1368 pub struct MachSrcLoc { 1369 /// The start of the region of code corresponding to a source location. 1370 /// This is relative to the start of the function, not to the start of the 1371 /// section. 1372 pub start: CodeOffset, 1373 /// The end of the region of code corresponding to a source location. 1374 /// This is relative to the start of the section, not to the start of the 1375 /// section. 1376 pub end: CodeOffset, 1377 /// The source location. 1378 pub loc: SourceLoc, 1379 } 1380 1381 /// Record of stack map metadata: stack offsets containing references. 1382 #[derive(Clone, Debug)] 1383 pub struct MachStackMap { 1384 /// The code offset at which this stack map applies. 1385 pub offset: CodeOffset, 1386 /// The code offset just past the "end" of the instruction: that is, the 1387 /// offset of the first byte of the following instruction, or equivalently, 1388 /// the start offset plus the instruction length. 1389 pub offset_end: CodeOffset, 1390 /// The stack map itself. 1391 pub stack_map: StackMap, 1392 } 1393 1394 /// Record of branch instruction in the buffer, to facilitate editing. 1395 #[derive(Clone, Debug)] 1396 struct MachBranch { 1397 start: CodeOffset, 1398 end: CodeOffset, 1399 target: MachLabel, 1400 fixup: usize, 1401 inverted: Option<SmallVec<[u8; 8]>>, 1402 /// All labels pointing to the start of this branch. For correctness, this 1403 /// *must* be complete (i.e., must contain all labels whose resolved offsets 1404 /// are at the start of this branch): we rely on being able to redirect all 1405 /// labels that could jump to this branch before removing it, if it is 1406 /// otherwise unreachable. 1407 labels_at_this_branch: SmallVec<[MachLabel; 4]>, 1408 } 1409 1410 impl MachBranch { 1411 fn is_cond(&self) -> bool { 1412 self.inverted.is_some() 1413 } 1414 fn is_uncond(&self) -> bool { 1415 self.inverted.is_none() 1416 } 1417 } 1418 1419 // We use an actual instruction definition to do tests, so we depend on the `arm64` feature here. 1420 #[cfg(all(test, feature = "arm64"))] 1421 mod test { 1422 use super::*; 1423 use crate::isa::aarch64::inst::xreg; 1424 use crate::isa::aarch64::inst::{BranchTarget, CondBrKind, Inst}; 1425 use crate::machinst::MachInstEmit; 1426 use crate::settings; 1427 use std::default::Default; 1428 1429 fn label(n: u32) -> MachLabel { 1430 MachLabel::from_block(n) 1431 } 1432 fn target(n: u32) -> BranchTarget { 1433 BranchTarget::Label(label(n)) 1434 } 1435 1436 #[test] 1437 fn test_elide_jump_to_next() { 1438 let flags = settings::Flags::new(settings::builder()); 1439 let mut buf = MachBuffer::new(); 1440 let mut state = Default::default(); 1441 1442 buf.reserve_labels_for_blocks(2); 1443 buf.bind_label(label(0)); 1444 let inst = Inst::Jump { dest: target(1) }; 1445 inst.emit(&mut buf, &flags, &mut state); 1446 buf.bind_label(label(1)); 1447 let buf = buf.finish(); 1448 assert_eq!(0, buf.total_size()); 1449 } 1450 1451 #[test] 1452 fn test_elide_trivial_jump_blocks() { 1453 let flags = settings::Flags::new(settings::builder()); 1454 let mut buf = MachBuffer::new(); 1455 let mut state = Default::default(); 1456 1457 buf.reserve_labels_for_blocks(4); 1458 1459 buf.bind_label(label(0)); 1460 let inst = Inst::CondBr { 1461 kind: CondBrKind::NotZero(xreg(0)), 1462 taken: target(1), 1463 not_taken: target(2), 1464 }; 1465 inst.emit(&mut buf, &flags, &mut state); 1466 1467 buf.bind_label(label(1)); 1468 let inst = Inst::Jump { dest: target(3) }; 1469 inst.emit(&mut buf, &flags, &mut state); 1470 1471 buf.bind_label(label(2)); 1472 let inst = Inst::Jump { dest: target(3) }; 1473 inst.emit(&mut buf, &flags, &mut state); 1474 1475 buf.bind_label(label(3)); 1476 1477 let buf = buf.finish(); 1478 assert_eq!(0, buf.total_size()); 1479 } 1480 1481 #[test] 1482 fn test_flip_cond() { 1483 let flags = settings::Flags::new(settings::builder()); 1484 let mut buf = MachBuffer::new(); 1485 let mut state = Default::default(); 1486 1487 buf.reserve_labels_for_blocks(4); 1488 1489 buf.bind_label(label(0)); 1490 let inst = Inst::CondBr { 1491 kind: CondBrKind::NotZero(xreg(0)), 1492 taken: target(1), 1493 not_taken: target(2), 1494 }; 1495 inst.emit(&mut buf, &flags, &mut state); 1496 1497 buf.bind_label(label(1)); 1498 let inst = Inst::Udf { 1499 trap_info: (SourceLoc::default(), TrapCode::Interrupt), 1500 }; 1501 inst.emit(&mut buf, &flags, &mut state); 1502 1503 buf.bind_label(label(2)); 1504 let inst = Inst::Nop4; 1505 inst.emit(&mut buf, &flags, &mut state); 1506 1507 buf.bind_label(label(3)); 1508 1509 let buf = buf.finish(); 1510 1511 let mut buf2 = MachBuffer::new(); 1512 let mut state = Default::default(); 1513 let inst = Inst::TrapIf { 1514 kind: CondBrKind::NotZero(xreg(0)), 1515 trap_info: (SourceLoc::default(), TrapCode::Interrupt), 1516 }; 1517 inst.emit(&mut buf2, &flags, &mut state); 1518 let inst = Inst::Nop4; 1519 inst.emit(&mut buf2, &flags, &mut state); 1520 1521 let buf2 = buf2.finish(); 1522 1523 assert_eq!(buf.data, buf2.data); 1524 } 1525 1526 #[test] 1527 fn test_island() { 1528 let flags = settings::Flags::new(settings::builder()); 1529 let mut buf = MachBuffer::new(); 1530 let mut state = Default::default(); 1531 1532 buf.reserve_labels_for_blocks(4); 1533 1534 buf.bind_label(label(0)); 1535 let inst = Inst::CondBr { 1536 kind: CondBrKind::NotZero(xreg(0)), 1537 taken: target(2), 1538 not_taken: target(3), 1539 }; 1540 inst.emit(&mut buf, &flags, &mut state); 1541 1542 buf.bind_label(label(1)); 1543 while buf.cur_offset() < 2000000 { 1544 if buf.island_needed(0) { 1545 buf.emit_island(); 1546 } 1547 let inst = Inst::Nop4; 1548 inst.emit(&mut buf, &flags, &mut state); 1549 } 1550 1551 buf.bind_label(label(2)); 1552 let inst = Inst::Nop4; 1553 inst.emit(&mut buf, &flags, &mut state); 1554 1555 buf.bind_label(label(3)); 1556 let inst = Inst::Nop4; 1557 inst.emit(&mut buf, &flags, &mut state); 1558 1559 let buf = buf.finish(); 1560 1561 assert_eq!(2000000 + 8, buf.total_size()); 1562 1563 let mut buf2 = MachBuffer::new(); 1564 let mut state = Default::default(); 1565 let inst = Inst::CondBr { 1566 kind: CondBrKind::NotZero(xreg(0)), 1567 taken: BranchTarget::ResolvedOffset(1048576 - 4), 1568 not_taken: BranchTarget::ResolvedOffset(2000000 + 4 - 4), 1569 }; 1570 inst.emit(&mut buf2, &flags, &mut state); 1571 1572 let buf2 = buf2.finish(); 1573 1574 assert_eq!(&buf.data[0..8], &buf2.data[..]); 1575 } 1576 1577 #[test] 1578 fn test_island_backward() { 1579 let flags = settings::Flags::new(settings::builder()); 1580 let mut buf = MachBuffer::new(); 1581 let mut state = Default::default(); 1582 1583 buf.reserve_labels_for_blocks(4); 1584 1585 buf.bind_label(label(0)); 1586 let inst = Inst::Nop4; 1587 inst.emit(&mut buf, &flags, &mut state); 1588 1589 buf.bind_label(label(1)); 1590 let inst = Inst::Nop4; 1591 inst.emit(&mut buf, &flags, &mut state); 1592 1593 buf.bind_label(label(2)); 1594 while buf.cur_offset() < 2000000 { 1595 let inst = Inst::Nop4; 1596 inst.emit(&mut buf, &flags, &mut state); 1597 } 1598 1599 buf.bind_label(label(3)); 1600 let inst = Inst::CondBr { 1601 kind: CondBrKind::NotZero(xreg(0)), 1602 taken: target(0), 1603 not_taken: target(1), 1604 }; 1605 inst.emit(&mut buf, &flags, &mut state); 1606 1607 let buf = buf.finish(); 1608 1609 assert_eq!(2000000 + 12, buf.total_size()); 1610 1611 let mut buf2 = MachBuffer::new(); 1612 let mut state = Default::default(); 1613 let inst = Inst::CondBr { 1614 kind: CondBrKind::NotZero(xreg(0)), 1615 taken: BranchTarget::ResolvedOffset(8), 1616 not_taken: BranchTarget::ResolvedOffset(4 - (2000000 + 4)), 1617 }; 1618 inst.emit(&mut buf2, &flags, &mut state); 1619 let inst = Inst::Jump { 1620 dest: BranchTarget::ResolvedOffset(-(2000000 + 8)), 1621 }; 1622 inst.emit(&mut buf2, &flags, &mut state); 1623 1624 let buf2 = buf2.finish(); 1625 1626 assert_eq!(&buf.data[2000000..], &buf2.data[..]); 1627 } 1628 1629 #[test] 1630 fn test_multiple_redirect() { 1631 // label0: 1632 // cbz x0, label1 1633 // b label2 1634 // label1: 1635 // b label3 1636 // label2: 1637 // nop 1638 // nop 1639 // b label0 1640 // label3: 1641 // b label4 1642 // label4: 1643 // b label5 1644 // label5: 1645 // b label7 1646 // label6: 1647 // nop 1648 // label7: 1649 // ret 1650 // 1651 // -- should become: 1652 // 1653 // label0: 1654 // cbz x0, label7 1655 // label2: 1656 // nop 1657 // nop 1658 // b label0 1659 // label6: 1660 // nop 1661 // label7: 1662 // ret 1663 1664 let flags = settings::Flags::new(settings::builder()); 1665 let mut buf = MachBuffer::new(); 1666 let mut state = Default::default(); 1667 1668 buf.reserve_labels_for_blocks(8); 1669 1670 buf.bind_label(label(0)); 1671 let inst = Inst::CondBr { 1672 kind: CondBrKind::Zero(xreg(0)), 1673 taken: target(1), 1674 not_taken: target(2), 1675 }; 1676 inst.emit(&mut buf, &flags, &mut state); 1677 1678 buf.bind_label(label(1)); 1679 let inst = Inst::Jump { dest: target(3) }; 1680 inst.emit(&mut buf, &flags, &mut state); 1681 1682 buf.bind_label(label(2)); 1683 let inst = Inst::Nop4; 1684 inst.emit(&mut buf, &flags, &mut state); 1685 inst.emit(&mut buf, &flags, &mut state); 1686 let inst = Inst::Jump { dest: target(0) }; 1687 inst.emit(&mut buf, &flags, &mut state); 1688 1689 buf.bind_label(label(3)); 1690 let inst = Inst::Jump { dest: target(4) }; 1691 inst.emit(&mut buf, &flags, &mut state); 1692 1693 buf.bind_label(label(4)); 1694 let inst = Inst::Jump { dest: target(5) }; 1695 inst.emit(&mut buf, &flags, &mut state); 1696 1697 buf.bind_label(label(5)); 1698 let inst = Inst::Jump { dest: target(7) }; 1699 inst.emit(&mut buf, &flags, &mut state); 1700 1701 buf.bind_label(label(6)); 1702 let inst = Inst::Nop4; 1703 inst.emit(&mut buf, &flags, &mut state); 1704 1705 buf.bind_label(label(7)); 1706 let inst = Inst::Ret; 1707 inst.emit(&mut buf, &flags, &mut state); 1708 1709 let buf = buf.finish(); 1710 1711 let golden_data = vec![ 1712 0xa0, 0x00, 0x00, 0xb4, // cbz x0, 0x14 1713 0x1f, 0x20, 0x03, 0xd5, // nop 1714 0x1f, 0x20, 0x03, 0xd5, // nop 1715 0xfd, 0xff, 0xff, 0x17, // b 0 1716 0x1f, 0x20, 0x03, 0xd5, // nop 1717 0xc0, 0x03, 0x5f, 0xd6, // ret 1718 ]; 1719 1720 assert_eq!(&golden_data[..], &buf.data[..]); 1721 } 1722 1723 #[test] 1724 fn test_handle_branch_cycle() { 1725 // label0: 1726 // b label1 1727 // label1: 1728 // b label2 1729 // label2: 1730 // b label3 1731 // label3: 1732 // b label4 1733 // label4: 1734 // b label1 // note: not label0 (to make it interesting). 1735 // 1736 // -- should become: 1737 // 1738 // label0, label1, ..., label4: 1739 // b label0 1740 let flags = settings::Flags::new(settings::builder()); 1741 let mut buf = MachBuffer::new(); 1742 let mut state = Default::default(); 1743 1744 buf.reserve_labels_for_blocks(5); 1745 1746 buf.bind_label(label(0)); 1747 let inst = Inst::Jump { dest: target(1) }; 1748 inst.emit(&mut buf, &flags, &mut state); 1749 1750 buf.bind_label(label(1)); 1751 let inst = Inst::Jump { dest: target(2) }; 1752 inst.emit(&mut buf, &flags, &mut state); 1753 1754 buf.bind_label(label(2)); 1755 let inst = Inst::Jump { dest: target(3) }; 1756 inst.emit(&mut buf, &flags, &mut state); 1757 1758 buf.bind_label(label(3)); 1759 let inst = Inst::Jump { dest: target(4) }; 1760 inst.emit(&mut buf, &flags, &mut state); 1761 1762 buf.bind_label(label(4)); 1763 let inst = Inst::Jump { dest: target(1) }; 1764 inst.emit(&mut buf, &flags, &mut state); 1765 1766 let buf = buf.finish(); 1767 1768 let golden_data = vec![ 1769 0x00, 0x00, 0x00, 0x14, // b 0 1770 ]; 1771 1772 assert_eq!(&golden_data[..], &buf.data[..]); 1773 } 1774 } 1775