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], combined with many empty edge blocks when the register 16 //! allocator does not need to insert any spills/reloads/moves in edge blocks, 17 //! results in many suboptimal branch patterns. The lowering also pays no 18 //! attention to block order, and so two-target conditional forms (cond-br 19 //! followed by uncond-br) can often by avoided because one of the targets is 20 //! the fallthrough. There are several cases here where we can simplify to use 21 //! 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}; 144 use crate::ir::{ExternalName, Opcode, SourceLoc, TrapCode}; 145 use crate::machinst::{BlockIndex, MachInstLabelUse, VCodeInst}; 146 147 use log::trace; 148 use smallvec::SmallVec; 149 use std::mem; 150 151 /// A buffer of output to be produced, fixed up, and then emitted to a CodeSink 152 /// in bulk. 153 /// 154 /// This struct uses `SmallVec`s to support small-ish function bodies without 155 /// any heap allocation. As such, it will be several kilobytes large. This is 156 /// likely fine as long as it is stack-allocated for function emission then 157 /// thrown away; but beware if many buffer objects are retained persistently. 158 pub struct MachBuffer<I: VCodeInst> { 159 /// The buffer contents, as raw bytes. 160 data: SmallVec<[u8; 1024]>, 161 /// Any relocations referring to this code. Note that only *external* 162 /// relocations are tracked here; references to labels within the buffer are 163 /// resolved before emission. 164 relocs: SmallVec<[MachReloc; 16]>, 165 /// Any trap records referring to this code. 166 traps: SmallVec<[MachTrap; 16]>, 167 /// Any call site records referring to this code. 168 call_sites: SmallVec<[MachCallSite; 16]>, 169 /// Any source location mappings referring to this code. 170 srclocs: SmallVec<[MachSrcLoc; 64]>, 171 /// The current source location in progress (after `start_srcloc()` and 172 /// before `end_srcloc()`). This is a (start_offset, src_loc) tuple. 173 cur_srcloc: Option<(CodeOffset, SourceLoc)>, 174 /// Known label offsets; `UNKNOWN_LABEL_OFFSET` if unknown. 175 label_offsets: SmallVec<[CodeOffset; 16]>, 176 /// Label aliases: when one label points to an unconditional jump, and that 177 /// jump points to another label, we can redirect references to the first 178 /// label immediately to the second. (We don't chase arbitrarily deep to 179 /// avoid problems with cycles, but rather only one level, i.e. through one 180 /// jump.) 181 label_aliases: SmallVec<[MachLabel; 16]>, 182 /// Constants that must be emitted at some point. 183 pending_constants: SmallVec<[MachLabelConstant; 16]>, 184 /// Fixups that must be performed after all code is emitted. 185 fixup_records: SmallVec<[MachLabelFixup<I>; 16]>, 186 /// Current deadline at which all constants are flushed and all code labels 187 /// are extended by emitting long-range jumps in an island. This flush 188 /// should be rare (e.g., on AArch64, the shortest-range PC-rel references 189 /// are +/- 1MB for conditional jumps and load-literal instructions), so 190 /// it's acceptable to track a minimum and flush-all rather than doing more 191 /// detailed "current minimum" / sort-by-deadline trickery. 192 island_deadline: CodeOffset, 193 /// How many bytes are needed in the worst case for an island, given all 194 /// pending constants and fixups. 195 island_worst_case_size: CodeOffset, 196 /// Latest branches, to facilitate in-place editing for better fallthrough 197 /// behavior and empty-block removal. 198 latest_branches: SmallVec<[MachBranch; 4]>, 199 /// All labels at the current offset (emission tail). This is lazily 200 /// cleared: it is actually accurate as long as the current offset is 201 /// `labels_at_tail_off`, but if `cur_offset()` has grown larger, it should 202 /// be considered as empty. 203 /// 204 /// For correctness, this *must* be complete (i.e., the vector must contain 205 /// all labels whose offsets are resolved to the current tail), because we 206 /// rely on it to update labels when we truncate branches. 207 labels_at_tail: SmallVec<[MachLabel; 4]>, 208 /// The last offset at which `labels_at_tail` is valid. It is conceptually 209 /// always describing the tail of the buffer, but we do not clear 210 /// `labels_at_tail` eagerly when the tail grows, rather we lazily clear it 211 /// when the offset has grown past this (`labels_at_tail_off`) point. 212 /// Always <= `cur_offset()`. 213 labels_at_tail_off: CodeOffset, 214 } 215 216 /// A `MachBuffer` once emission is completed: holds generated code and records, 217 /// without fixups. This allows the type to be independent of the backend. 218 pub struct MachBufferFinalized { 219 /// The buffer contents, as raw bytes. 220 pub data: SmallVec<[u8; 1024]>, 221 /// Any relocations referring to this code. Note that only *external* 222 /// relocations are tracked here; references to labels within the buffer are 223 /// resolved before emission. 224 relocs: SmallVec<[MachReloc; 16]>, 225 /// Any trap records referring to this code. 226 traps: SmallVec<[MachTrap; 16]>, 227 /// Any call site records referring to this code. 228 call_sites: SmallVec<[MachCallSite; 16]>, 229 /// Any source location mappings referring to this code. 230 srclocs: SmallVec<[MachSrcLoc; 64]>, 231 } 232 233 static UNKNOWN_LABEL_OFFSET: CodeOffset = 0xffff_ffff; 234 static UNKNOWN_LABEL: MachLabel = MachLabel(0xffff_ffff); 235 236 /// A label refers to some offset in a `MachBuffer`. It may not be resolved at 237 /// the point at which it is used by emitted code; the buffer records "fixups" 238 /// for references to the label, and will come back and patch the code 239 /// appropriately when the label's location is eventually known. 240 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] 241 pub struct MachLabel(u32); 242 243 impl MachLabel { 244 /// Get a label for a block. (The first N MachLabels are always reseved for 245 /// the N blocks in the vcode.) 246 pub fn from_block(bindex: BlockIndex) -> MachLabel { 247 MachLabel(bindex) 248 } 249 250 /// Get the numeric label index. 251 pub fn get(self) -> u32 { 252 self.0 253 } 254 } 255 256 impl<I: VCodeInst> MachBuffer<I> { 257 /// Create a new section, known to start at `start_offset` and with a size limited to `length_limit`. 258 pub fn new() -> MachBuffer<I> { 259 MachBuffer { 260 data: SmallVec::new(), 261 relocs: SmallVec::new(), 262 traps: SmallVec::new(), 263 call_sites: SmallVec::new(), 264 srclocs: SmallVec::new(), 265 cur_srcloc: None, 266 label_offsets: SmallVec::new(), 267 label_aliases: SmallVec::new(), 268 pending_constants: SmallVec::new(), 269 fixup_records: SmallVec::new(), 270 island_deadline: UNKNOWN_LABEL_OFFSET, 271 island_worst_case_size: 0, 272 latest_branches: SmallVec::new(), 273 labels_at_tail: SmallVec::new(), 274 labels_at_tail_off: 0, 275 } 276 } 277 278 /// Debug-only: check invariants of labels and branch-records described 279 /// under "Branch-optimization Correctness" above. 280 #[cfg(debug)] 281 fn check_label_branch_invariants(&self) { 282 let cur_off = self.cur_offset(); 283 // Check that every entry in latest_branches has *correct* 284 // labels_at_this_branch lists. We do not check completeness because 285 // that would require building a reverse index, which is too slow even 286 // for a debug invariant check. 287 let mut last_end = 0; 288 for b in &self.latest_branches { 289 debug_assert!(b.start < b.end); 290 debug_assert!(b.end <= cur_off); 291 debug_assert!(b.start >= last_end); 292 last_end = b.end; 293 for &l in &b.labels_at_this_branch { 294 debug_assert_eq!(self.resolve_label_offset(l), b.start); 295 debug_assert_eq!(self.label_aliases[l.0 as usize], UNKNOWN_LABEL); 296 } 297 } 298 299 // Check that every label is unresolved, or resolved at or before 300 // cur_offset. If at cur_offset, must be in `labels_at_tail`. 301 for (i, &off) in self.label_offsets.iter().enumerate() { 302 let label = MachLabel(i as u32); 303 debug_assert!(off == UNKNOWN_LABEL_OFFSET || off <= cur_off); 304 if off == cur_off { 305 debug_assert!( 306 self.labels_at_tail_off == cur_off && self.labels_at_tail.contains(&label) 307 ); 308 } 309 } 310 311 // Check that every label in `labels_at_tail_off` is precise, i.e., 312 // resolves to the cur offset. 313 debug_assert!(self.labels_at_tail_off <= cur_off); 314 if self.labels_at_tail_off == cur_off { 315 for &l in &self.labels_at_tail { 316 debug_assert_eq!(self.resolve_label_offset(l), cur_off); 317 debug_assert_eq!(self.label_aliases[l.0 as usize], UNKNOWN_LABEL); 318 } 319 } 320 } 321 322 #[cfg(not(debug))] 323 fn check_label_branch_invariants(&self) { 324 // Nothing. 325 } 326 327 /// Current offset from start of buffer. 328 pub fn cur_offset(&self) -> CodeOffset { 329 self.data.len() as CodeOffset 330 } 331 332 /// Add a byte. 333 pub fn put1(&mut self, value: u8) { 334 trace!("MachBuffer: put byte @ {}: {:x}", self.cur_offset(), value); 335 self.data.push(value); 336 337 // Post-invariant: conceptual-labels_at_tail contains a complete and 338 // precise list of labels bound at `cur_offset()`. We have advanced 339 // `cur_offset()`, hence if it had been equal to `labels_at_tail_off` 340 // before, it is not anymore (and it cannot become equal, because 341 // `labels_at_tail_off` is always <= `cur_offset()`). Thus the list is 342 // conceptually empty (even though it is only lazily cleared). No labels 343 // can be bound at this new offset (by invariant on `label_offsets`). 344 // Hence the invariant holds. 345 } 346 347 /// Add 2 bytes. 348 pub fn put2(&mut self, value: u16) { 349 trace!( 350 "MachBuffer: put 16-bit word @ {}: {:x}", 351 self.cur_offset(), 352 value 353 ); 354 let bytes = value.to_le_bytes(); 355 self.data.extend_from_slice(&bytes[..]); 356 357 // Post-invariant: as for `put1()`. 358 } 359 360 /// Add 4 bytes. 361 pub fn put4(&mut self, value: u32) { 362 trace!( 363 "MachBuffer: put 32-bit word @ {}: {:x}", 364 self.cur_offset(), 365 value 366 ); 367 let bytes = value.to_le_bytes(); 368 self.data.extend_from_slice(&bytes[..]); 369 370 // Post-invariant: as for `put1()`. 371 } 372 373 /// Add 8 bytes. 374 pub fn put8(&mut self, value: u64) { 375 trace!( 376 "MachBuffer: put 64-bit word @ {}: {:x}", 377 self.cur_offset(), 378 value 379 ); 380 let bytes = value.to_le_bytes(); 381 self.data.extend_from_slice(&bytes[..]); 382 383 // Post-invariant: as for `put1()`. 384 } 385 386 /// Add a slice of bytes. 387 pub fn put_data(&mut self, data: &[u8]) { 388 trace!( 389 "MachBuffer: put data @ {}: len {}", 390 self.cur_offset(), 391 data.len() 392 ); 393 self.data.extend_from_slice(data); 394 395 // Post-invariant: as for `put1()`. 396 } 397 398 /// Reserve appended space and return a mutable slice referring to it. 399 pub fn get_appended_space(&mut self, len: usize) -> &mut [u8] { 400 trace!("MachBuffer: put data @ {}: len {}", self.cur_offset(), len); 401 let off = self.data.len(); 402 let new_len = self.data.len() + len; 403 self.data.resize(new_len, 0); 404 &mut self.data[off..] 405 406 // Post-invariant: as for `put1()`. 407 } 408 409 /// Align up to the given alignment. 410 pub fn align_to(&mut self, align_to: CodeOffset) { 411 trace!("MachBuffer: align to {}", align_to); 412 assert!(align_to.is_power_of_two()); 413 while self.cur_offset() & (align_to - 1) != 0 { 414 self.put1(0); 415 } 416 417 // Post-invariant: as for `put1()`. 418 } 419 420 /// Allocate a `Label` to refer to some offset. May not be bound to a fixed 421 /// offset yet. 422 pub fn get_label(&mut self) -> MachLabel { 423 let l = self.label_offsets.len() as u32; 424 self.label_offsets.push(UNKNOWN_LABEL_OFFSET); 425 self.label_aliases.push(UNKNOWN_LABEL); 426 trace!("MachBuffer: new label -> {:?}", MachLabel(l)); 427 MachLabel(l) 428 429 // Post-invariant: the only mutation is to add a new label; it has no 430 // bound offset yet, so it trivially satisfies all invariants. 431 } 432 433 /// Reserve the first N MachLabels for blocks. 434 pub fn reserve_labels_for_blocks(&mut self, blocks: BlockIndex) { 435 trace!("MachBuffer: first {} labels are for blocks", blocks); 436 debug_assert!(self.label_offsets.is_empty()); 437 self.label_offsets 438 .resize(blocks as usize, UNKNOWN_LABEL_OFFSET); 439 self.label_aliases.resize(blocks as usize, UNKNOWN_LABEL); 440 441 // Post-invariant: as for `get_label()`. 442 } 443 444 /// Bind a label to the current offset. A label can only be bound once. 445 pub fn bind_label(&mut self, label: MachLabel) { 446 trace!( 447 "MachBuffer: bind label {:?} at offset {}", 448 label, 449 self.cur_offset() 450 ); 451 debug_assert_eq!(self.label_offsets[label.0 as usize], UNKNOWN_LABEL_OFFSET); 452 debug_assert_eq!(self.label_aliases[label.0 as usize], UNKNOWN_LABEL); 453 let offset = self.cur_offset(); 454 self.label_offsets[label.0 as usize] = offset; 455 self.lazily_clear_labels_at_tail(); 456 self.labels_at_tail.push(label); 457 458 // Invariants hold: bound offset of label is <= cur_offset (in fact it 459 // is equal). If the `labels_at_tail` list was complete and precise 460 // before, it is still, because we have bound this label to the current 461 // offset and added it to the list (which contains all labels at the 462 // current offset). 463 464 self.check_label_branch_invariants(); 465 self.optimize_branches(); 466 467 // Post-invariant: by `optimize_branches()` (see argument there). 468 self.check_label_branch_invariants(); 469 } 470 471 /// Lazily clear `labels_at_tail` if the tail offset has moved beyond the 472 /// offset that it applies to. 473 fn lazily_clear_labels_at_tail(&mut self) { 474 let offset = self.cur_offset(); 475 if offset > self.labels_at_tail_off { 476 self.labels_at_tail_off = offset; 477 self.labels_at_tail.clear(); 478 } 479 480 // Post-invariant: either labels_at_tail_off was at cur_offset, and 481 // state is untouched, or was less than cur_offset, in which case the 482 // labels_at_tail list was conceptually empty, and is now actually 483 // empty. 484 } 485 486 /// Resolve a label to an offset, if known. May return `UNKNOWN_LABEL_OFFSET`. 487 fn resolve_label_offset(&self, label: MachLabel) -> CodeOffset { 488 let alias = self.label_aliases[label.0 as usize]; 489 if alias != UNKNOWN_LABEL { 490 self.label_offsets[alias.0 as usize] 491 } else { 492 self.label_offsets[label.0 as usize] 493 } 494 495 // Post-invariant: no mutations. 496 } 497 498 /// Emit a reference to the given label with the given reference type (i.e., 499 /// branch-instruction format) at the current offset. This is like a 500 /// relocation, but handled internally. 501 /// 502 /// This can be called before the branch is actually emitted; fixups will 503 /// not happen until an island is emitted or the buffer is finished. 504 pub fn use_label_at_offset(&mut self, offset: CodeOffset, label: MachLabel, kind: I::LabelUse) { 505 trace!( 506 "MachBuffer: use_label_at_offset: offset {} label {:?} kind {:?}", 507 offset, 508 label, 509 kind 510 ); 511 512 // Add the fixup, and update the worst-case island size based on a 513 // veneer for this label use. 514 self.fixup_records.push(MachLabelFixup { 515 label, 516 offset, 517 kind, 518 }); 519 if kind.supports_veneer() { 520 self.island_worst_case_size += kind.veneer_size(); 521 self.island_worst_case_size &= !(I::LabelUse::ALIGN - 1); 522 } 523 let deadline = offset + kind.max_pos_range(); 524 if deadline < self.island_deadline { 525 self.island_deadline = deadline; 526 } 527 528 // Post-invariant: no mutations to branches/labels data structures. 529 self.check_label_branch_invariants(); 530 } 531 532 /// Inform the buffer of an unconditional branch at the given offset, 533 /// targetting the given label. May be used to optimize branches. 534 /// The last added label-use must correspond to this branch. 535 /// This must be called when the current offset is equal to `start`; i.e., 536 /// before actually emitting the branch. This implies that for a branch that 537 /// uses a label and is eligible for optimizations by the MachBuffer, the 538 /// proper sequence is: 539 /// 540 /// - Call `use_label_at_offset()` to emit the fixup record. 541 /// - Call `add_uncond_branch()` to make note of the branch. 542 /// - Emit the bytes for the branch's machine code. 543 /// 544 /// Additional requirement: no labels may be bound between `start` and `end` 545 /// (exclusive on both ends). 546 pub fn add_uncond_branch(&mut self, start: CodeOffset, end: CodeOffset, target: MachLabel) { 547 assert!(self.cur_offset() == start); 548 debug_assert!(end > start); 549 assert!(!self.fixup_records.is_empty()); 550 let fixup = self.fixup_records.len() - 1; 551 self.lazily_clear_labels_at_tail(); 552 self.latest_branches.push(MachBranch { 553 start, 554 end, 555 target, 556 fixup, 557 inverted: None, 558 labels_at_this_branch: self.labels_at_tail.clone(), 559 }); 560 561 // Post-invariant: we asserted branch start is current tail; the list of 562 // labels at branch is cloned from list of labels at current tail. 563 self.check_label_branch_invariants(); 564 } 565 566 /// Inform the buffer of a conditional branch at the given offset, 567 /// targetting the given label. May be used to optimize branches. 568 /// The last added label-use must correspond to this branch. 569 /// 570 /// Additional requirement: no labels may be bound between `start` and `end` 571 /// (exclusive on both ends). 572 pub fn add_cond_branch( 573 &mut self, 574 start: CodeOffset, 575 end: CodeOffset, 576 target: MachLabel, 577 inverted: &[u8], 578 ) { 579 assert!(self.cur_offset() == start); 580 debug_assert!(end > start); 581 assert!(!self.fixup_records.is_empty()); 582 debug_assert!(inverted.len() == (end - start) as usize); 583 let fixup = self.fixup_records.len() - 1; 584 let inverted = Some(SmallVec::from(inverted)); 585 self.lazily_clear_labels_at_tail(); 586 self.latest_branches.push(MachBranch { 587 start, 588 end, 589 target, 590 fixup, 591 inverted, 592 labels_at_this_branch: self.labels_at_tail.clone(), 593 }); 594 595 // Post-invariant: we asserted branch start is current tail; labels at 596 // branch list is cloned from list of labels at current tail. 597 self.check_label_branch_invariants(); 598 } 599 600 fn truncate_last_branch(&mut self) { 601 self.lazily_clear_labels_at_tail(); 602 // Invariants hold at this point. 603 604 let b = self.latest_branches.pop().unwrap(); 605 assert!(b.end == self.cur_offset()); 606 607 // State: 608 // [PRE CODE] 609 // Offset b.start, b.labels_at_this_branch: 610 // [BRANCH CODE] 611 // cur_off, self.labels_at_tail --> 612 // (end of buffer) 613 self.data.truncate(b.start as usize); 614 self.fixup_records.truncate(b.fixup); 615 // State: 616 // [PRE CODE] 617 // cur_off, Offset b.start, b.labels_at_this_branch: 618 // (end of buffer) 619 // 620 // self.labels_at_tail --> (past end of buffer) 621 let cur_off = self.cur_offset(); 622 self.labels_at_tail_off = cur_off; 623 // State: 624 // [PRE CODE] 625 // cur_off, Offset b.start, b.labels_at_this_branch, 626 // self.labels_at_tail: 627 // (end of buffer) 628 // 629 // resolve_label_offset(l) for l in labels_at_tail: 630 // (past end of buffer) 631 632 trace!( 633 "truncate_last_branch: truncated {:?}; off now {}", 634 b, 635 cur_off 636 ); 637 638 // Fix up resolved label offsets for labels at tail. 639 for &l in &self.labels_at_tail { 640 self.label_offsets[l.0 as usize] = cur_off; 641 } 642 // Old labels_at_this_branch are now at cur_off. 643 self.labels_at_tail 644 .extend(b.labels_at_this_branch.into_iter()); 645 646 // Post-invariant: this operation is defined to truncate the buffer, 647 // which moves cur_off backward, and to move labels at the end of the 648 // buffer back to the start-of-branch offset. 649 // 650 // latest_branches satisfies all invariants: 651 // - it has no branches past the end of the buffer (branches are in 652 // order, we removed the last one, and we truncated the buffer to just 653 // before the start of that branch) 654 // - no labels were moved to lower offsets than the (new) cur_off, so 655 // the labels_at_this_branch list for any other branch need not change. 656 // 657 // labels_at_tail satisfies all invariants: 658 // - all labels that were at the tail after the truncated branch are 659 // moved backward to just before the branch, which becomes the new tail; 660 // thus every element in the list should remain (ensured by `.extend()` 661 // above). 662 // - all labels that refer to the new tail, which is the start-offset of 663 // the truncated branch, must be present. The `labels_at_this_branch` 664 // list in the truncated branch's record is a complete and precise list 665 // of exactly these labels; we append these to labels_at_tail. 666 // - labels_at_tail_off is at cur_off after truncation occurs, so the 667 // list is valid (not to be lazily cleared). 668 // 669 // The stated operation was performed: 670 // - For each label at the end of the buffer prior to this method, it 671 // now resolves to the new (truncated) end of the buffer: it must have 672 // been in `labels_at_tail` (this list is precise and complete, and 673 // the tail was at the end of the truncated branch on entry), and we 674 // iterate over this list and set `label_offsets` to the new tail. 675 // None of these labels could have been an alias (by invariant), so 676 // `label_offsets` is authoritative for each. 677 // - No other labels will be past the end of the buffer, because of the 678 // requirement that no labels be bound to the middle of branch ranges 679 // (see comments to `add_{cond,uncond}_branch()`). 680 // - The buffer is truncated to just before the last branch, and the 681 // fixup record referring to that last branch is removed. 682 self.check_label_branch_invariants(); 683 } 684 685 fn optimize_branches(&mut self) { 686 self.lazily_clear_labels_at_tail(); 687 // Invariants valid at this point. 688 689 trace!( 690 "enter optimize_branches:\n b = {:?}\n l = {:?}\n f = {:?}", 691 self.latest_branches, 692 self.labels_at_tail, 693 self.fixup_records 694 ); 695 696 // We continue to munch on branches at the tail of the buffer until no 697 // more rules apply. Note that the loop only continues if a branch is 698 // actually truncated (or if labels are redirected away from a branch), 699 // so this always makes progress. 700 while let Some(b) = self.latest_branches.last() { 701 let cur_off = self.cur_offset(); 702 trace!("optimize_branches: last branch {:?} at off {}", b, cur_off); 703 // If there has been any code emission since the end of the last branch or 704 // label definition, then there's nothing we can edit (because we 705 // don't move code once placed, only back up and overwrite), so 706 // clear the records and finish. 707 if b.end < cur_off { 708 break; 709 } 710 711 // Invariant: we are looking at a branch that ends at the tail of 712 // the buffer. 713 714 // For any branch, conditional or unconditional: 715 // - If the target is a label at the current offset, then remove 716 // the conditional branch, and reset all labels that targetted 717 // the current offset (end of branch) to the truncated 718 // end-of-code. 719 // 720 // Preserves execution semantics: a branch to its own fallthrough 721 // address is equivalent to a no-op; in both cases, nextPC is the 722 // fallthrough. 723 if self.resolve_label_offset(b.target) == cur_off { 724 trace!("branch with target == cur off; truncating"); 725 self.truncate_last_branch(); 726 continue; 727 } 728 729 // If latest is an unconditional branch: 730 // 731 // - If the branch's target is not its own start address, then for 732 // each label at the start of branch, make the label an alias of the 733 // branch target, and remove the label from the "labels at this 734 // branch" list. 735 // 736 // - Preserves execution semantics: an unconditional branch's 737 // only effect is to set PC to a new PC; this change simply 738 // collapses one step in the step-semantics. 739 // 740 // - Post-invariant: the labels that were bound to the start of 741 // this branch become aliases, so they must not be present in any 742 // labels-at-this-branch list or the labels-at-tail list. The 743 // labels are removed form the latest-branch record's 744 // labels-at-this-branch list, and are never placed in the 745 // labels-at-tail list. Furthermore, it is correct that they are 746 // not in either list, because they are now aliases, and labels 747 // that are aliases remain aliases forever. 748 // 749 // - If there is a prior unconditional branch that ends just before 750 // this one begins, and this branch has no labels bound to its 751 // start, then we can truncate this branch, because it is entirely 752 // unreachable (we have redirected all labels that make it 753 // reachable otherwise). Do so and continue around the loop. 754 // 755 // - Preserves execution semantics: the branch is unreachable, 756 // because execution can only flow into an instruction from the 757 // prior instruction's fallthrough or from a branch bound to that 758 // instruction's start offset. Unconditional branches have no 759 // fallthrough, so if the prior instruction is an unconditional 760 // branch, no fallthrough entry can happen. The 761 // labels-at-this-branch list is complete (by invariant), so if it 762 // is empty, then the instruction is entirely unreachable. Thus, 763 // it can be removed. 764 // 765 // - Post-invariant: ensured by truncate_last_branch(). 766 // 767 // - If there is a prior conditional branch whose target label 768 // resolves to the current offset (branches around the 769 // unconditional branch), then remove the unconditional branch, 770 // and make the target of the unconditional the target of the 771 // conditional instead. 772 // 773 // - Preserves execution semantics: previously we had: 774 // 775 // L1: 776 // cond_br L2 777 // br L3 778 // L2: 779 // (end of buffer) 780 // 781 // by removing the last branch, we have: 782 // 783 // L1: 784 // cond_br L2 785 // L2: 786 // (end of buffer) 787 // 788 // we then fix up the records for the conditional branch to 789 // have: 790 // 791 // L1: 792 // cond_br.inverted L3 793 // L2: 794 // 795 // In the original code, control flow reaches L2 when the 796 // conditional branch's predicate is true, and L3 otherwise. In 797 // the optimized code, the same is true. 798 // 799 // - Post-invariant: all edits to latest_branches and 800 // labels_at_tail are performed by `truncate_last_branch()`, 801 // which maintains the invariants at each step. 802 803 if b.is_uncond() { 804 // Set any label equal to current branch's start as an alias of 805 // the branch's target, if the target is not the branch itself 806 // (i.e., an infinite loop). 807 if self.resolve_label_offset(b.target) != b.start { 808 let redirected = b.labels_at_this_branch.len(); 809 for &l in &b.labels_at_this_branch { 810 trace!( 811 " -> label at start of branch {:?} redirected to target {:?}", 812 l, 813 b.target 814 ); 815 self.label_aliases[l.0 as usize] = b.target; 816 // NOTE: we continue to ensure the invariant that labels 817 // pointing to tail of buffer are in `labels_at_tail` 818 // because we already ensured above that the last branch 819 // cannot have a target of `cur_off`; so we never have 820 // to put the label into `labels_at_tail` when moving it 821 // here. 822 } 823 // Maintain invariant: all branches have been redirected 824 // and are no longer pointing at the start of this branch. 825 let mut_b = self.latest_branches.last_mut().unwrap(); 826 mut_b.labels_at_this_branch.clear(); 827 828 if redirected > 0 { 829 trace!(" -> after label redirects, restarting loop"); 830 continue; 831 } 832 } 833 let b = self.latest_branches.last().unwrap(); 834 835 // Examine any immediately preceding branch. 836 if self.latest_branches.len() > 1 { 837 let prev_b = &self.latest_branches[self.latest_branches.len() - 2]; 838 trace!(" -> more than one branch; prev_b = {:?}", prev_b); 839 // This uncond is immediately after another uncond; we 840 // should have already redirected labels to this uncond away 841 // (but check to be sure); so we can truncate this uncond. 842 if prev_b.is_uncond() 843 && prev_b.end == b.start 844 && b.labels_at_this_branch.is_empty() 845 { 846 trace!(" -> uncond follows another uncond; truncating"); 847 self.truncate_last_branch(); 848 continue; 849 } 850 851 // This uncond is immediately after a conditional, and the 852 // conditional's target is the end of this uncond, and we've 853 // already redirected labels to this uncond away; so we can 854 // truncate this uncond, flip the sense of the conditional, and 855 // set the conditional's target (in `latest_branches` and in 856 // `fixup_records`) to the uncond's target. 857 if prev_b.is_cond() 858 && prev_b.end == b.start 859 && self.resolve_label_offset(prev_b.target) == cur_off 860 { 861 trace!(" -> uncond follows a conditional, and conditional's target resolves to current offset"); 862 // Save the target of the uncond (this becomes the 863 // target of the cond), and truncate the uncond. 864 let target = b.target; 865 let data = prev_b.inverted.clone().unwrap(); 866 self.truncate_last_branch(); 867 868 // Mutate the code and cond branch. 869 let off_before_edit = self.cur_offset(); 870 let prev_b = self.latest_branches.last_mut().unwrap(); 871 let not_inverted = SmallVec::from( 872 &self.data[(prev_b.start as usize)..(prev_b.end as usize)], 873 ); 874 875 // Low-level edit: replaces bytes of branch with 876 // inverted form. cur_off remains the same afterward, so 877 // we do not need to modify label data structures. 878 self.data.truncate(prev_b.start as usize); 879 self.data.extend_from_slice(&data[..]); 880 881 // Save the original code as the inversion of the 882 // inverted branch, in case we later edit this branch 883 // again. 884 prev_b.inverted = Some(not_inverted); 885 self.fixup_records[prev_b.fixup].label = target; 886 trace!(" -> reassigning target of condbr to {:?}", target); 887 prev_b.target = target; 888 debug_assert_eq!(off_before_edit, self.cur_offset()); 889 continue; 890 } 891 } 892 } 893 894 // If we couldn't do anything with the last branch, then break. 895 break; 896 } 897 898 self.purge_latest_branches(); 899 900 trace!( 901 "leave optimize_branches:\n b = {:?}\n l = {:?}\n f = {:?}", 902 self.latest_branches, 903 self.labels_at_tail, 904 self.fixup_records 905 ); 906 } 907 908 fn purge_latest_branches(&mut self) { 909 // All of our branch simplification rules work only if a branch ends at 910 // the tail of the buffer, with no following code; and branches are in 911 // order in latest_branches; so if the last entry ends prior to 912 // cur_offset, then clear all entries. 913 let cur_off = self.cur_offset(); 914 if let Some(l) = self.latest_branches.last() { 915 if l.end < cur_off { 916 trace!("purge_latest_branches: removing branch {:?}", l); 917 self.latest_branches.clear(); 918 } 919 } 920 921 // Post-invariant: no invariant requires any branch to appear in 922 // `latest_branches`; it is always optional. The list-clear above thus 923 // preserves all semantics. 924 } 925 926 /// Emit a constant at some point in the future, binding the given label to 927 /// its offset. The constant will be placed at most `max_distance` from the 928 /// current offset. 929 pub fn defer_constant( 930 &mut self, 931 label: MachLabel, 932 align: CodeOffset, 933 data: &[u8], 934 max_distance: CodeOffset, 935 ) { 936 let deadline = self.cur_offset() + max_distance; 937 self.island_worst_case_size += data.len() as CodeOffset; 938 self.island_worst_case_size &= !(I::LabelUse::ALIGN - 1); 939 self.pending_constants.push(MachLabelConstant { 940 label, 941 align, 942 data: SmallVec::from(data), 943 }); 944 if deadline < self.island_deadline { 945 self.island_deadline = deadline; 946 } 947 } 948 949 /// Is an island needed within the next N bytes? 950 pub fn island_needed(&self, distance: CodeOffset) -> bool { 951 let worst_case_end_of_island = self.cur_offset() + distance + self.island_worst_case_size; 952 worst_case_end_of_island > self.island_deadline 953 } 954 955 /// Emit all pending constants and veneers. Should only be called if 956 /// `island_needed()` returns true, i.e., if we actually reach a deadline: 957 /// otherwise, unnecessary veneers may be inserted. 958 pub fn emit_island(&mut self) { 959 // We're going to purge fixups, so no latest-branch editing can happen 960 // anymore. 961 self.latest_branches.clear(); 962 963 let pending_constants = mem::replace(&mut self.pending_constants, SmallVec::new()); 964 for MachLabelConstant { label, align, data } in pending_constants.into_iter() { 965 self.align_to(align); 966 self.bind_label(label); 967 self.put_data(&data[..]); 968 } 969 970 let fixup_records = mem::replace(&mut self.fixup_records, SmallVec::new()); 971 let mut new_fixups = SmallVec::new(); 972 for MachLabelFixup { 973 label, 974 offset, 975 kind, 976 } in fixup_records.into_iter() 977 { 978 trace!( 979 "emit_island: fixup for label {:?} at offset {} kind {:?}", 980 label, 981 offset, 982 kind 983 ); 984 // We eagerly perform fixups whose label targets are known, if not out 985 // of range, to avoid unnecessary veneers. 986 let label_offset = self.resolve_label_offset(label); 987 let known = label_offset != UNKNOWN_LABEL_OFFSET; 988 let in_range = if known { 989 if label_offset >= offset { 990 (label_offset - offset) <= kind.max_pos_range() 991 } else { 992 (offset - label_offset) <= kind.max_neg_range() 993 } 994 } else { 995 false 996 }; 997 998 trace!( 999 " -> label_offset = {}, known = {}, in_range = {} (pos {} neg {})", 1000 label_offset, 1001 known, 1002 in_range, 1003 kind.max_pos_range(), 1004 kind.max_neg_range() 1005 ); 1006 1007 let start = offset as usize; 1008 let end = (offset + kind.patch_size()) as usize; 1009 if in_range { 1010 debug_assert!(known); // implied by in_range. 1011 let slice = &mut self.data[start..end]; 1012 trace!("patching in-range!"); 1013 kind.patch(slice, offset, label_offset); 1014 } else if !known && !kind.supports_veneer() { 1015 // Nothing for now. Keep it for next round. 1016 new_fixups.push(MachLabelFixup { 1017 label, 1018 offset, 1019 kind, 1020 }); 1021 } else if !in_range && kind.supports_veneer() { 1022 // Allocate space for a veneer in the island. 1023 self.align_to(I::LabelUse::ALIGN); 1024 let veneer_offset = self.cur_offset(); 1025 trace!("making a veneer at {}", veneer_offset); 1026 let slice = &mut self.data[start..end]; 1027 // Patch the original label use to refer to teh veneer. 1028 trace!( 1029 "patching original at offset {} to veneer offset {}", 1030 offset, 1031 veneer_offset 1032 ); 1033 kind.patch(slice, offset, veneer_offset); 1034 // Generate the veneer. 1035 let veneer_slice = self.get_appended_space(kind.veneer_size() as usize); 1036 let (veneer_fixup_off, veneer_label_use) = 1037 kind.generate_veneer(veneer_slice, veneer_offset); 1038 trace!( 1039 "generated veneer; fixup offset {}, label_use {:?}", 1040 veneer_fixup_off, 1041 veneer_label_use 1042 ); 1043 // If the label is known (but was just out of range), do the 1044 // veneer label-use fixup now too; otherwise, save it for later. 1045 if known { 1046 let start = veneer_fixup_off as usize; 1047 let end = (veneer_fixup_off + veneer_label_use.patch_size()) as usize; 1048 let veneer_slice = &mut self.data[start..end]; 1049 trace!("doing veneer fixup right away too"); 1050 veneer_label_use.patch(veneer_slice, veneer_fixup_off, label_offset); 1051 } else { 1052 new_fixups.push(MachLabelFixup { 1053 label, 1054 offset: veneer_fixup_off, 1055 kind: veneer_label_use, 1056 }); 1057 } 1058 } else { 1059 panic!( 1060 "Cannot support label-use {:?} (known = {}, in-range = {})", 1061 kind, known, in_range 1062 ); 1063 } 1064 } 1065 1066 self.fixup_records = new_fixups; 1067 self.island_deadline = UNKNOWN_LABEL_OFFSET; 1068 } 1069 1070 /// Finish any deferred emissions and/or fixups. 1071 pub fn finish(mut self) -> MachBufferFinalized { 1072 // Ensure that all labels are defined. This is a full (release-mode) 1073 // assert because we must avoid looping indefinitely below; an 1074 // unresolved label will prevent the fixup_records vec from emptying. 1075 assert!(self 1076 .label_offsets 1077 .iter() 1078 .all(|&off| off != UNKNOWN_LABEL_OFFSET)); 1079 1080 while !self.pending_constants.is_empty() || !self.fixup_records.is_empty() { 1081 // `emit_island()` will emit any pending veneers and constants, and 1082 // as a side-effect, will also take care of any fixups with resolved 1083 // labels eagerly. 1084 self.emit_island(); 1085 } 1086 1087 MachBufferFinalized { 1088 data: self.data, 1089 relocs: self.relocs, 1090 traps: self.traps, 1091 call_sites: self.call_sites, 1092 srclocs: self.srclocs, 1093 } 1094 } 1095 1096 /// Add an external relocation at the current offset. 1097 pub fn add_reloc( 1098 &mut self, 1099 srcloc: SourceLoc, 1100 kind: Reloc, 1101 name: &ExternalName, 1102 addend: Addend, 1103 ) { 1104 let name = name.clone(); 1105 self.relocs.push(MachReloc { 1106 offset: self.data.len() as CodeOffset, 1107 srcloc, 1108 kind, 1109 name, 1110 addend, 1111 }); 1112 } 1113 1114 /// Add a trap record at the current offset. 1115 pub fn add_trap(&mut self, srcloc: SourceLoc, code: TrapCode) { 1116 self.traps.push(MachTrap { 1117 offset: self.data.len() as CodeOffset, 1118 srcloc, 1119 code, 1120 }); 1121 } 1122 1123 /// Add a call-site record at the current offset. 1124 pub fn add_call_site(&mut self, srcloc: SourceLoc, opcode: Opcode) { 1125 self.call_sites.push(MachCallSite { 1126 ret_addr: self.data.len() as CodeOffset, 1127 srcloc, 1128 opcode, 1129 }); 1130 } 1131 1132 /// Set the `SourceLoc` for code from this offset until the offset at the 1133 /// next call to `end_srcloc()`. 1134 pub fn start_srcloc(&mut self, loc: SourceLoc) { 1135 self.cur_srcloc = Some((self.cur_offset(), loc)); 1136 } 1137 1138 /// Mark the end of the `SourceLoc` segment started at the last 1139 /// `start_srcloc()` call. 1140 pub fn end_srcloc(&mut self) { 1141 let (start, loc) = self 1142 .cur_srcloc 1143 .take() 1144 .expect("end_srcloc() called without start_srcloc()"); 1145 let end = self.cur_offset(); 1146 // Skip zero-length extends. 1147 debug_assert!(end >= start); 1148 if end > start { 1149 self.srclocs.push(MachSrcLoc { start, end, loc }); 1150 } 1151 } 1152 } 1153 1154 impl MachBufferFinalized { 1155 /// Get a list of source location mapping tuples in sorted-by-start-offset order. 1156 pub fn get_srclocs_sorted(&self) -> &[MachSrcLoc] { 1157 &self.srclocs[..] 1158 } 1159 1160 /// Get the total required size for the code. 1161 pub fn total_size(&self) -> CodeOffset { 1162 self.data.len() as CodeOffset 1163 } 1164 1165 /// Emit this buffer to the given CodeSink. 1166 pub fn emit<CS: CodeSink>(&self, sink: &mut CS) { 1167 // N.B.: we emit every section into the .text section as far as 1168 // the `CodeSink` is concerned; we do not bother to segregate 1169 // the contents into the actual program text, the jumptable and the 1170 // rodata (constant pool). This allows us to generate code assuming 1171 // that these will not be relocated relative to each other, and avoids 1172 // having to designate each section as belonging in one of the three 1173 // fixed categories defined by `CodeSink`. If this becomes a problem 1174 // later (e.g. because of memory permissions or similar), we can 1175 // add this designation and segregate the output; take care, however, 1176 // to add the appropriate relocations in this case. 1177 1178 let mut next_reloc = 0; 1179 let mut next_trap = 0; 1180 let mut next_call_site = 0; 1181 for (idx, byte) in self.data.iter().enumerate() { 1182 if next_reloc < self.relocs.len() { 1183 let reloc = &self.relocs[next_reloc]; 1184 if reloc.offset == idx as CodeOffset { 1185 sink.reloc_external(reloc.srcloc, reloc.kind, &reloc.name, reloc.addend); 1186 next_reloc += 1; 1187 } 1188 } 1189 if next_trap < self.traps.len() { 1190 let trap = &self.traps[next_trap]; 1191 if trap.offset == idx as CodeOffset { 1192 sink.trap(trap.code, trap.srcloc); 1193 next_trap += 1; 1194 } 1195 } 1196 if next_call_site < self.call_sites.len() { 1197 let call_site = &self.call_sites[next_call_site]; 1198 if call_site.ret_addr == idx as CodeOffset { 1199 sink.add_call_site(call_site.opcode, call_site.srcloc); 1200 next_call_site += 1; 1201 } 1202 } 1203 sink.put1(*byte); 1204 } 1205 1206 sink.begin_jumptables(); 1207 sink.begin_rodata(); 1208 sink.end_codegen(); 1209 } 1210 } 1211 1212 /// A constant that is deferred to the next constant-pool opportunity. 1213 struct MachLabelConstant { 1214 /// This label will refer to the constant's offset. 1215 label: MachLabel, 1216 /// Required alignment. 1217 align: CodeOffset, 1218 /// This data will be emitted when able. 1219 data: SmallVec<[u8; 16]>, 1220 } 1221 1222 /// A fixup to perform on the buffer once code is emitted. Fixups always refer 1223 /// to labels and patch the code based on label offsets. Hence, they are like 1224 /// relocations, but internal to one buffer. 1225 #[derive(Debug)] 1226 struct MachLabelFixup<I: VCodeInst> { 1227 /// The label whose offset controls this fixup. 1228 label: MachLabel, 1229 /// The offset to fix up / patch to refer to this label. 1230 offset: CodeOffset, 1231 /// The kind of fixup. This is architecture-specific; each architecture may have, 1232 /// e.g., several types of branch instructions, each with differently-sized 1233 /// offset fields and different places within the instruction to place the 1234 /// bits. 1235 kind: I::LabelUse, 1236 } 1237 1238 /// A relocation resulting from a compilation. 1239 struct MachReloc { 1240 /// The offset at which the relocation applies, *relative to the 1241 /// containing section*. 1242 offset: CodeOffset, 1243 /// The original source location. 1244 srcloc: SourceLoc, 1245 /// The kind of relocation. 1246 kind: Reloc, 1247 /// The external symbol / name to which this relocation refers. 1248 name: ExternalName, 1249 /// The addend to add to the symbol value. 1250 addend: i64, 1251 } 1252 1253 /// A trap record resulting from a compilation. 1254 struct MachTrap { 1255 /// The offset at which the trap instruction occurs, *relative to the 1256 /// containing section*. 1257 offset: CodeOffset, 1258 /// The original source location. 1259 srcloc: SourceLoc, 1260 /// The trap code. 1261 code: TrapCode, 1262 } 1263 1264 /// A call site record resulting from a compilation. 1265 struct MachCallSite { 1266 /// The offset of the call's return address, *relative to the containing section*. 1267 ret_addr: CodeOffset, 1268 /// The original source location. 1269 srcloc: SourceLoc, 1270 /// The call's opcode. 1271 opcode: Opcode, 1272 } 1273 1274 /// A source-location mapping resulting from a compilation. 1275 #[derive(Clone, Debug)] 1276 pub struct MachSrcLoc { 1277 /// The start of the region of code corresponding to a source location. 1278 /// This is relative to the start of the function, not to the start of the 1279 /// section. 1280 pub start: CodeOffset, 1281 /// The end of the region of code corresponding to a source location. 1282 /// This is relative to the start of the section, not to the start of the 1283 /// section. 1284 pub end: CodeOffset, 1285 /// The source location. 1286 pub loc: SourceLoc, 1287 } 1288 1289 /// Record of branch instruction in the buffer, to facilitate editing. 1290 #[derive(Clone, Debug)] 1291 struct MachBranch { 1292 start: CodeOffset, 1293 end: CodeOffset, 1294 target: MachLabel, 1295 fixup: usize, 1296 inverted: Option<SmallVec<[u8; 8]>>, 1297 /// All labels pointing to the start of this branch. For correctness, this 1298 /// *must* be complete (i.e., must contain all labels whose resolved offsets 1299 /// are at the start of this branch): we rely on being able to redirect all 1300 /// labels that could jump to this branch before removing it, if it is 1301 /// otherwise unreachable. 1302 labels_at_this_branch: SmallVec<[MachLabel; 4]>, 1303 } 1304 1305 impl MachBranch { 1306 fn is_cond(&self) -> bool { 1307 self.inverted.is_some() 1308 } 1309 fn is_uncond(&self) -> bool { 1310 self.inverted.is_none() 1311 } 1312 } 1313 1314 // We use an actual instruction definition to do tests, so we depend on the `arm64` feature here. 1315 #[cfg(all(test, feature = "arm64"))] 1316 mod test { 1317 use super::*; 1318 use crate::isa::aarch64::inst::xreg; 1319 use crate::isa::aarch64::inst::{BranchTarget, CondBrKind, Inst}; 1320 use crate::machinst::MachInstEmit; 1321 use crate::settings; 1322 use std::default::Default; 1323 1324 fn label(n: u32) -> MachLabel { 1325 MachLabel::from_block(n) 1326 } 1327 fn target(n: u32) -> BranchTarget { 1328 BranchTarget::Label(label(n)) 1329 } 1330 1331 #[test] 1332 fn test_elide_jump_to_next() { 1333 let flags = settings::Flags::new(settings::builder()); 1334 let mut buf = MachBuffer::new(); 1335 let mut state = Default::default(); 1336 1337 buf.reserve_labels_for_blocks(2); 1338 buf.bind_label(label(0)); 1339 let inst = Inst::Jump { dest: target(1) }; 1340 inst.emit(&mut buf, &flags, &mut state); 1341 buf.bind_label(label(1)); 1342 let buf = buf.finish(); 1343 assert_eq!(0, buf.total_size()); 1344 } 1345 1346 #[test] 1347 fn test_elide_trivial_jump_blocks() { 1348 let flags = settings::Flags::new(settings::builder()); 1349 let mut buf = MachBuffer::new(); 1350 let mut state = Default::default(); 1351 1352 buf.reserve_labels_for_blocks(4); 1353 1354 buf.bind_label(label(0)); 1355 let inst = Inst::CondBr { 1356 kind: CondBrKind::NotZero(xreg(0)), 1357 taken: target(1), 1358 not_taken: target(2), 1359 }; 1360 inst.emit(&mut buf, &flags, &mut state); 1361 1362 buf.bind_label(label(1)); 1363 let inst = Inst::Jump { dest: target(3) }; 1364 inst.emit(&mut buf, &flags, &mut state); 1365 1366 buf.bind_label(label(2)); 1367 let inst = Inst::Jump { dest: target(3) }; 1368 inst.emit(&mut buf, &flags, &mut state); 1369 1370 buf.bind_label(label(3)); 1371 1372 let buf = buf.finish(); 1373 assert_eq!(0, buf.total_size()); 1374 } 1375 1376 #[test] 1377 fn test_flip_cond() { 1378 let flags = settings::Flags::new(settings::builder()); 1379 let mut buf = MachBuffer::new(); 1380 let mut state = Default::default(); 1381 1382 buf.reserve_labels_for_blocks(4); 1383 1384 buf.bind_label(label(0)); 1385 let inst = Inst::CondBr { 1386 kind: CondBrKind::NotZero(xreg(0)), 1387 taken: target(1), 1388 not_taken: target(2), 1389 }; 1390 inst.emit(&mut buf, &flags, &mut state); 1391 1392 buf.bind_label(label(1)); 1393 let inst = Inst::Nop4; 1394 inst.emit(&mut buf, &flags, &mut state); 1395 1396 buf.bind_label(label(2)); 1397 let inst = Inst::Nop4; 1398 inst.emit(&mut buf, &flags, &mut state); 1399 1400 buf.bind_label(label(3)); 1401 1402 let buf = buf.finish(); 1403 1404 let mut buf2 = MachBuffer::new(); 1405 let mut state = Default::default(); 1406 let inst = Inst::OneWayCondBr { 1407 kind: CondBrKind::Zero(xreg(0)), 1408 target: BranchTarget::ResolvedOffset(8), 1409 }; 1410 inst.emit(&mut buf2, &flags, &mut state); 1411 let inst = Inst::Nop4; 1412 inst.emit(&mut buf2, &flags, &mut state); 1413 inst.emit(&mut buf2, &flags, &mut state); 1414 1415 let buf2 = buf2.finish(); 1416 1417 assert_eq!(buf.data, buf2.data); 1418 } 1419 1420 #[test] 1421 fn test_island() { 1422 let flags = settings::Flags::new(settings::builder()); 1423 let mut buf = MachBuffer::new(); 1424 let mut state = Default::default(); 1425 1426 buf.reserve_labels_for_blocks(4); 1427 1428 buf.bind_label(label(0)); 1429 let inst = Inst::CondBr { 1430 kind: CondBrKind::NotZero(xreg(0)), 1431 taken: target(2), 1432 not_taken: target(3), 1433 }; 1434 inst.emit(&mut buf, &flags, &mut state); 1435 1436 buf.bind_label(label(1)); 1437 while buf.cur_offset() < 2000000 { 1438 if buf.island_needed(0) { 1439 buf.emit_island(); 1440 } 1441 let inst = Inst::Nop4; 1442 inst.emit(&mut buf, &flags, &mut state); 1443 } 1444 1445 buf.bind_label(label(2)); 1446 let inst = Inst::Nop4; 1447 inst.emit(&mut buf, &flags, &mut state); 1448 1449 buf.bind_label(label(3)); 1450 let inst = Inst::Nop4; 1451 inst.emit(&mut buf, &flags, &mut state); 1452 1453 let buf = buf.finish(); 1454 1455 assert_eq!(2000000 + 8, buf.total_size()); 1456 1457 let mut buf2 = MachBuffer::new(); 1458 let mut state = Default::default(); 1459 let inst = Inst::CondBr { 1460 kind: CondBrKind::NotZero(xreg(0)), 1461 taken: BranchTarget::ResolvedOffset(1048576 - 4), 1462 not_taken: BranchTarget::ResolvedOffset(2000000 + 4 - 4), 1463 }; 1464 inst.emit(&mut buf2, &flags, &mut state); 1465 1466 let buf2 = buf2.finish(); 1467 1468 assert_eq!(&buf.data[0..8], &buf2.data[..]); 1469 } 1470 1471 #[test] 1472 fn test_island_backward() { 1473 let flags = settings::Flags::new(settings::builder()); 1474 let mut buf = MachBuffer::new(); 1475 let mut state = Default::default(); 1476 1477 buf.reserve_labels_for_blocks(4); 1478 1479 buf.bind_label(label(0)); 1480 let inst = Inst::Nop4; 1481 inst.emit(&mut buf, &flags, &mut state); 1482 1483 buf.bind_label(label(1)); 1484 let inst = Inst::Nop4; 1485 inst.emit(&mut buf, &flags, &mut state); 1486 1487 buf.bind_label(label(2)); 1488 while buf.cur_offset() < 2000000 { 1489 let inst = Inst::Nop4; 1490 inst.emit(&mut buf, &flags, &mut state); 1491 } 1492 1493 buf.bind_label(label(3)); 1494 let inst = Inst::CondBr { 1495 kind: CondBrKind::NotZero(xreg(0)), 1496 taken: target(0), 1497 not_taken: target(1), 1498 }; 1499 inst.emit(&mut buf, &flags, &mut state); 1500 1501 let buf = buf.finish(); 1502 1503 assert_eq!(2000000 + 12, buf.total_size()); 1504 1505 let mut buf2 = MachBuffer::new(); 1506 let mut state = Default::default(); 1507 let inst = Inst::CondBr { 1508 kind: CondBrKind::NotZero(xreg(0)), 1509 taken: BranchTarget::ResolvedOffset(8), 1510 not_taken: BranchTarget::ResolvedOffset(4 - (2000000 + 4)), 1511 }; 1512 inst.emit(&mut buf2, &flags, &mut state); 1513 let inst = Inst::Jump { 1514 dest: BranchTarget::ResolvedOffset(-(2000000 + 8)), 1515 }; 1516 inst.emit(&mut buf2, &flags, &mut state); 1517 1518 let buf2 = buf2.finish(); 1519 1520 assert_eq!(&buf.data[2000000..], &buf2.data[..]); 1521 } 1522 } 1523