src/librustc_target/abi/mod.rs

   1 pub use Integer::*;
   2 pub use Primitive::*;
   3
   4 use crate::spec::Target;
   5
   6 use std::ops::{Add, AddAssign, Deref, Mul, Range, RangeInclusive, Sub};
   7
   8 use rustc_index::vec::{Idx, IndexVec};
   9 use rustc_macros::HashStable_Generic;
  10 use rustc_span::Span;
  11
  12 pub mod call;
  13
  14 /// Parsed [Data layout](http://llvm.org/docs/LangRef.html#data-layout)
  15 /// for a target, which contains everything needed to compute layouts.
  16 pub struct TargetDataLayout {
  17     pub endian: Endian,
  18     pub i1_align: AbiAndPrefAlign,
  19     pub i8_align: AbiAndPrefAlign,
  20     pub i16_align: AbiAndPrefAlign,
  21     pub i32_align: AbiAndPrefAlign,
  22     pub i64_align: AbiAndPrefAlign,
  23     pub i128_align: AbiAndPrefAlign,
  24     pub f32_align: AbiAndPrefAlign,
  25     pub f64_align: AbiAndPrefAlign,
  26     pub pointer_size: Size,
  27     pub pointer_align: AbiAndPrefAlign,
  28     pub aggregate_align: AbiAndPrefAlign,
  29
  30     /// Alignments for vector types.
  31     pub vector_align: Vec<(Size, AbiAndPrefAlign)>,
  32
  33     pub instruction_address_space: u32,
  34 }
  35
  36 impl Default for TargetDataLayout {
  37     /// Creates an instance of `TargetDataLayout`.
  38     fn default() -> TargetDataLayout {
  39         let align = |bits| Align::from_bits(bits).unwrap();
  40         TargetDataLayout {
  41             endian: Endian::Big,
  42             i1_align: AbiAndPrefAlign::new(align(8)),
  43             i8_align: AbiAndPrefAlign::new(align(8)),
  44             i16_align: AbiAndPrefAlign::new(align(16)),
  45             i32_align: AbiAndPrefAlign::new(align(32)),
  46             i64_align: AbiAndPrefAlign { abi: align(32), pref: align(64) },
  47             i128_align: AbiAndPrefAlign { abi: align(32), pref: align(64) },
  48             f32_align: AbiAndPrefAlign::new(align(32)),
  49             f64_align: AbiAndPrefAlign::new(align(64)),
  50             pointer_size: Size::from_bits(64),
  51             pointer_align: AbiAndPrefAlign::new(align(64)),
  52             aggregate_align: AbiAndPrefAlign { abi: align(0), pref: align(64) },
  53             vector_align: vec![
  54                 (Size::from_bits(64), AbiAndPrefAlign::new(align(64))),
  55                 (Size::from_bits(128), AbiAndPrefAlign::new(align(128))),
  56             ],
  57             instruction_address_space: 0,
  58         }
  59     }
  60 }
  61
  62 impl TargetDataLayout {
  63     pub fn parse(target: &Target) -> Result<TargetDataLayout, String> {
  64         // Parse an address space index from a string.
  65         let parse_address_space = |s: &str, cause: &str| {
  66             s.parse::<u32>().map_err(|err| {
  67                 format!("invalid address space `{}` for `{}` in \"data-layout\": {}", s, cause, err)
  68             })
  69         };
  70
  71         // Parse a bit count from a string.
  72         let parse_bits = |s: &str, kind: &str, cause: &str| {
  73             s.parse::<u64>().map_err(|err| {
  74                 format!("invalid {} `{}` for `{}` in \"data-layout\": {}", kind, s, cause, err)
  75             })
  76         };
  77
  78         // Parse a size string.
  79         let size = |s: &str, cause: &str| parse_bits(s, "size", cause).map(Size::from_bits);
  80
  81         // Parse an alignment string.
  82         let align = |s: &[&str], cause: &str| {
  83             if s.is_empty() {
  84                 return Err(format!("missing alignment for `{}` in \"data-layout\"", cause));
  85             }
  86             let align_from_bits = |bits| {
  87                 Align::from_bits(bits).map_err(|err| {
  88                     format!("invalid alignment for `{}` in \"data-layout\": {}", cause, err)
  89                 })
  90             };
  91             let abi = parse_bits(s[0], "alignment", cause)?;
  92             let pref = s.get(1).map_or(Ok(abi), |pref| parse_bits(pref, "alignment", cause))?;
  93             Ok(AbiAndPrefAlign { abi: align_from_bits(abi)?, pref: align_from_bits(pref)? })
  94         };
  95
  96         let mut dl = TargetDataLayout::default();
  97         let mut i128_align_src = 64;
  98         for spec in target.data_layout.split('-') {
  99             let spec_parts = spec.split(':').collect::<Vec<_>>();
 100
 101             match &*spec_parts {
 102                 ["e"] => dl.endian = Endian::Little,
 103                 ["E"] => dl.endian = Endian::Big,
 104                 [p] if p.starts_with('P') => {
 105                     dl.instruction_address_space = parse_address_space(&p[1..], "P")?
 106                 }
 107                 ["a", ref a @ ..] => dl.aggregate_align = align(a, "a")?,
 108                 ["f32", ref a @ ..] => dl.f32_align = align(a, "f32")?,
 109                 ["f64", ref a @ ..] => dl.f64_align = align(a, "f64")?,
 110                 [p @ "p", s, ref a @ ..] | [p @ "p0", s, ref a @ ..] => {
 111                     dl.pointer_size = size(s, p)?;
 112                     dl.pointer_align = align(a, p)?;
 113                 }
 114                 [s, ref a @ ..] if s.starts_with('i') => {
 115                     let bits = match s[1..].parse::<u64>() {
 116                         Ok(bits) => bits,
 117                         Err(_) => {
 118                             size(&s[1..], "i")?; // For the user error.
 119                             continue;
 120                         }
 121                     };
 122                     let a = align(a, s)?;
 123                     match bits {
 124                         1 => dl.i1_align = a,
 125                         8 => dl.i8_align = a,
 126                         16 => dl.i16_align = a,
 127                         32 => dl.i32_align = a,
 128                         64 => dl.i64_align = a,
 129                         _ => {}
 130                     }
 131                     if bits >= i128_align_src && bits <= 128 {
 132                         // Default alignment for i128 is decided by taking the alignment of
 133                         // largest-sized i{64..=128}.
 134                         i128_align_src = bits;
 135                         dl.i128_align = a;
 136                     }
 137                 }
 138                 [s, ref a @ ..] if s.starts_with('v') => {
 139                     let v_size = size(&s[1..], "v")?;
 140                     let a = align(a, s)?;
 141                     if let Some(v) = dl.vector_align.iter_mut().find(|v| v.0 == v_size) {
 142                         v.1 = a;
 143                         continue;
 144                     }
 145                     // No existing entry, add a new one.
 146                     dl.vector_align.push((v_size, a));
 147                 }
 148                 _ => {} // Ignore everything else.
 149             }
 150         }
 151
 152         // Perform consistency checks against the Target information.
 153         let endian_str = match dl.endian {
 154             Endian::Little => "little",
 155             Endian::Big => "big",
 156         };
 157         if endian_str != target.target_endian {
 158             return Err(format!(
 159                 "inconsistent target specification: \"data-layout\" claims \
 160                                 architecture is {}-endian, while \"target-endian\" is `{}`",
 161                 endian_str, target.target_endian
 162             ));
 163         }
 164
 165         if dl.pointer_size.bits().to_string() != target.target_pointer_width {
 166             return Err(format!(
 167                 "inconsistent target specification: \"data-layout\" claims \
 168                                 pointers are {}-bit, while \"target-pointer-width\" is `{}`",
 169                 dl.pointer_size.bits(),
 170                 target.target_pointer_width
 171             ));
 172         }
 173
 174         Ok(dl)
 175     }
 176
 177     /// Returns exclusive upper bound on object size.
 178     ///
 179     /// The theoretical maximum object size is defined as the maximum positive `isize` value.
 180     /// This ensures that the `offset` semantics remain well-defined by allowing it to correctly
 181     /// index every address within an object along with one byte past the end, along with allowing
 182     /// `isize` to store the difference between any two pointers into an object.
 183     ///
 184     /// The upper bound on 64-bit currently needs to be lower because LLVM uses a 64-bit integer
 185     /// to represent object size in bits. It would need to be 1 << 61 to account for this, but is
 186     /// currently conservatively bounded to 1 << 47 as that is enough to cover the current usable
 187     /// address space on 64-bit ARMv8 and x86_64.
 188     pub fn obj_size_bound(&self) -> u64 {
 189         match self.pointer_size.bits() {
 190             16 => 1 << 15,
 191             32 => 1 << 31,
 192             64 => 1 << 47,
 193             bits => panic!("obj_size_bound: unknown pointer bit size {}", bits),
 194         }
 195     }
 196
 197     pub fn ptr_sized_integer(&self) -> Integer {
 198         match self.pointer_size.bits() {
 199             16 => I16,
 200             32 => I32,
 201             64 => I64,
 202             bits => panic!("ptr_sized_integer: unknown pointer bit size {}", bits),
 203         }
 204     }
 205
 206     pub fn vector_align(&self, vec_size: Size) -> AbiAndPrefAlign {
 207         for &(size, align) in &self.vector_align {
 208             if size == vec_size {
 209                 return align;
 210             }
 211         }
 212         // Default to natural alignment, which is what LLVM does.
 213         // That is, use the size, rounded up to a power of 2.
 214         AbiAndPrefAlign::new(Align::from_bytes(vec_size.bytes().next_power_of_two()).unwrap())
 215     }
 216 }
 217
 218 pub trait HasDataLayout {
 219     fn data_layout(&self) -> &TargetDataLayout;
 220 }
 221
 222 impl HasDataLayout for TargetDataLayout {
 223     fn data_layout(&self) -> &TargetDataLayout {
 224         self
 225     }
 226 }
 227
 228 /// Endianness of the target, which must match cfg(target-endian).
 229 #[derive(Copy, Clone, PartialEq)]
 230 pub enum Endian {
 231     Little,
 232     Big,
 233 }
 234
 235 /// Size of a type in bytes.
 236 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
 237 #[derive(HashStable_Generic)]
 238 pub struct Size {
 239     raw: u64,
 240 }
 241
 242 impl Size {
 243     pub const ZERO: Size = Self::from_bytes(0);
 244
 245     #[inline]
 246     pub fn from_bits(bits: u64) -> Size {
 247         // Avoid potential overflow from `bits + 7`.
 248         Size::from_bytes(bits / 8 + ((bits % 8) + 7) / 8)
 249     }
 250
 251     #[inline]
 252     pub const fn from_bytes(bytes: u64) -> Size {
 253         Size { raw: bytes }
 254     }
 255
 256     #[inline]
 257     pub fn bytes(self) -> u64 {
 258         self.raw
 259     }
 260
 261     #[inline]
 262     pub fn bits(self) -> u64 {
 263         self.bytes().checked_mul(8).unwrap_or_else(|| {
 264             panic!("Size::bits: {} bytes in bits doesn't fit in u64", self.bytes())
 265         })
 266     }
 267
 268     #[inline]
 269     pub fn align_to(self, align: Align) -> Size {
 270         let mask = align.bytes() - 1;
 271         Size::from_bytes((self.bytes() + mask) & !mask)
 272     }
 273
 274     #[inline]
 275     pub fn is_aligned(self, align: Align) -> bool {
 276         let mask = align.bytes() - 1;
 277         self.bytes() & mask == 0
 278     }
 279
 280     #[inline]
 281     pub fn checked_add<C: HasDataLayout>(self, offset: Size, cx: &C) -> Option<Size> {
 282         let dl = cx.data_layout();
 283
 284         let bytes = self.bytes().checked_add(offset.bytes())?;
 285
 286         if bytes < dl.obj_size_bound() { Some(Size::from_bytes(bytes)) } else { None }
 287     }
 288
 289     #[inline]
 290     pub fn checked_mul<C: HasDataLayout>(self, count: u64, cx: &C) -> Option<Size> {
 291         let dl = cx.data_layout();
 292
 293         let bytes = self.bytes().checked_mul(count)?;
 294         if bytes < dl.obj_size_bound() { Some(Size::from_bytes(bytes)) } else { None }
 295     }
 296 }
 297
 298 // Panicking addition, subtraction and multiplication for convenience.
 299 // Avoid during layout computation, return `LayoutError` instead.
 300
 301 impl Add for Size {
 302     type Output = Size;
 303     #[inline]
 304     fn add(self, other: Size) -> Size {
 305         Size::from_bytes(self.bytes().checked_add(other.bytes()).unwrap_or_else(|| {
 306             panic!("Size::add: {} + {} doesn't fit in u64", self.bytes(), other.bytes())
 307         }))
 308     }
 309 }
 310
 311 impl Sub for Size {
 312     type Output = Size;
 313     #[inline]
 314     fn sub(self, other: Size) -> Size {
 315         Size::from_bytes(self.bytes().checked_sub(other.bytes()).unwrap_or_else(|| {
 316             panic!("Size::sub: {} - {} would result in negative size", self.bytes(), other.bytes())
 317         }))
 318     }
 319 }
 320
 321 impl Mul<Size> for u64 {
 322     type Output = Size;
 323     #[inline]
 324     fn mul(self, size: Size) -> Size {
 325         size * self
 326     }
 327 }
 328
 329 impl Mul<u64> for Size {
 330     type Output = Size;
 331     #[inline]
 332     fn mul(self, count: u64) -> Size {
 333         match self.bytes().checked_mul(count) {
 334             Some(bytes) => Size::from_bytes(bytes),
 335             None => panic!("Size::mul: {} * {} doesn't fit in u64", self.bytes(), count),
 336         }
 337     }
 338 }
 339
 340 impl AddAssign for Size {
 341     #[inline]
 342     fn add_assign(&mut self, other: Size) {
 343         *self = *self + other;
 344     }
 345 }
 346
 347 /// Alignment of a type in bytes (always a power of two).
 348 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
 349 #[derive(HashStable_Generic)]
 350 pub struct Align {
 351     pow2: u8,
 352 }
 353
 354 impl Align {
 355     pub fn from_bits(bits: u64) -> Result<Align, String> {
 356         Align::from_bytes(Size::from_bits(bits).bytes())
 357     }
 358
 359     pub fn from_bytes(align: u64) -> Result<Align, String> {
 360         // Treat an alignment of 0 bytes like 1-byte alignment.
 361         if align == 0 {
 362             return Ok(Align { pow2: 0 });
 363         }
 364
 365         let mut bytes = align;
 366         let mut pow2: u8 = 0;
 367         while (bytes & 1) == 0 {
 368             pow2 += 1;
 369             bytes >>= 1;
 370         }
 371         if bytes != 1 {
 372             return Err(format!("`{}` is not a power of 2", align));
 373         }
 374         if pow2 > 29 {
 375             return Err(format!("`{}` is too large", align));
 376         }
 377
 378         Ok(Align { pow2 })
 379     }
 380
 381     pub fn bytes(self) -> u64 {
 382         1 << self.pow2
 383     }
 384
 385     pub fn bits(self) -> u64 {
 386         self.bytes() * 8
 387     }
 388
 389     /// Computes the best alignment possible for the given offset
 390     /// (the largest power of two that the offset is a multiple of).
 391     ///
 392     /// N.B., for an offset of `0`, this happens to return `2^64`.
 393     pub fn max_for_offset(offset: Size) -> Align {
 394         Align { pow2: offset.bytes().trailing_zeros() as u8 }
 395     }
 396
 397     /// Lower the alignment, if necessary, such that the given offset
 398     /// is aligned to it (the offset is a multiple of the alignment).
 399     pub fn restrict_for_offset(self, offset: Size) -> Align {
 400         self.min(Align::max_for_offset(offset))
 401     }
 402 }
 403
 404 /// A pair of aligments, ABI-mandated and preferred.
 405 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
 406 #[derive(HashStable_Generic)]
 407 pub struct AbiAndPrefAlign {
 408     pub abi: Align,
 409     pub pref: Align,
 410 }
 411
 412 impl AbiAndPrefAlign {
 413     pub fn new(align: Align) -> AbiAndPrefAlign {
 414         AbiAndPrefAlign { abi: align, pref: align }
 415     }
 416
 417     pub fn min(self, other: AbiAndPrefAlign) -> AbiAndPrefAlign {
 418         AbiAndPrefAlign { abi: self.abi.min(other.abi), pref: self.pref.min(other.pref) }
 419     }
 420
 421     pub fn max(self, other: AbiAndPrefAlign) -> AbiAndPrefAlign {
 422         AbiAndPrefAlign { abi: self.abi.max(other.abi), pref: self.pref.max(other.pref) }
 423     }
 424 }
 425
 426 /// Integers, also used for enum discriminants.
 427 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, HashStable_Generic)]
 428 pub enum Integer {
 429     I8,
 430     I16,
 431     I32,
 432     I64,
 433     I128,
 434 }
 435
 436 impl Integer {
 437     pub fn size(self) -> Size {
 438         match self {
 439             I8 => Size::from_bytes(1),
 440             I16 => Size::from_bytes(2),
 441             I32 => Size::from_bytes(4),
 442             I64 => Size::from_bytes(8),
 443             I128 => Size::from_bytes(16),
 444         }
 445     }
 446
 447     pub fn align<C: HasDataLayout>(self, cx: &C) -> AbiAndPrefAlign {
 448         let dl = cx.data_layout();
 449
 450         match self {
 451             I8 => dl.i8_align,
 452             I16 => dl.i16_align,
 453             I32 => dl.i32_align,
 454             I64 => dl.i64_align,
 455             I128 => dl.i128_align,
 456         }
 457     }
 458
 459     /// Finds the smallest Integer type which can represent the signed value.
 460     pub fn fit_signed(x: i128) -> Integer {
 461         match x {
 462             -0x0000_0000_0000_0080..=0x0000_0000_0000_007f => I8,
 463             -0x0000_0000_0000_8000..=0x0000_0000_0000_7fff => I16,
 464             -0x0000_0000_8000_0000..=0x0000_0000_7fff_ffff => I32,
 465             -0x8000_0000_0000_0000..=0x7fff_ffff_ffff_ffff => I64,
 466             _ => I128,
 467         }
 468     }
 469
 470     /// Finds the smallest Integer type which can represent the unsigned value.
 471     pub fn fit_unsigned(x: u128) -> Integer {
 472         match x {
 473             0..=0x0000_0000_0000_00ff => I8,
 474             0..=0x0000_0000_0000_ffff => I16,
 475             0..=0x0000_0000_ffff_ffff => I32,
 476             0..=0xffff_ffff_ffff_ffff => I64,
 477             _ => I128,
 478         }
 479     }
 480
 481     /// Finds the smallest integer with the given alignment.
 482     pub fn for_align<C: HasDataLayout>(cx: &C, wanted: Align) -> Option<Integer> {
 483         let dl = cx.data_layout();
 484
 485         for &candidate in &[I8, I16, I32, I64, I128] {
 486             if wanted == candidate.align(dl).abi && wanted.bytes() == candidate.size().bytes() {
 487                 return Some(candidate);
 488             }
 489         }
 490         None
 491     }
 492
 493     /// Find the largest integer with the given alignment or less.
 494     pub fn approximate_align<C: HasDataLayout>(cx: &C, wanted: Align) -> Integer {
 495         let dl = cx.data_layout();
 496
 497         // FIXME(eddyb) maybe include I128 in the future, when it works everywhere.
 498         for &candidate in &[I64, I32, I16] {
 499             if wanted >= candidate.align(dl).abi && wanted.bytes() >= candidate.size().bytes() {
 500                 return candidate;
 501             }
 502         }
 503         I8
 504     }
 505 }
 506
 507 /// Fundamental unit of memory access and layout.
 508 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 509 pub enum Primitive {
 510     /// The `bool` is the signedness of the `Integer` type.
 511     ///
 512     /// One would think we would not care about such details this low down,
 513     /// but some ABIs are described in terms of C types and ISAs where the
 514     /// integer arithmetic is done on {sign,zero}-extended registers, e.g.
 515     /// a negative integer passed by zero-extension will appear positive in
 516     /// the callee, and most operations on it will produce the wrong values.
 517     Int(Integer, bool),
 518     F32,
 519     F64,
 520     Pointer,
 521 }
 522
 523 impl Primitive {
 524     pub fn size<C: HasDataLayout>(self, cx: &C) -> Size {
 525         let dl = cx.data_layout();
 526
 527         match self {
 528             Int(i, _) => i.size(),
 529             F32 => Size::from_bits(32),
 530             F64 => Size::from_bits(64),
 531             Pointer => dl.pointer_size,
 532         }
 533     }
 534
 535     pub fn align<C: HasDataLayout>(self, cx: &C) -> AbiAndPrefAlign {
 536         let dl = cx.data_layout();
 537
 538         match self {
 539             Int(i, _) => i.align(dl),
 540             F32 => dl.f32_align,
 541             F64 => dl.f64_align,
 542             Pointer => dl.pointer_align,
 543         }
 544     }
 545
 546     pub fn is_float(self) -> bool {
 547         match self {
 548             F32 | F64 => true,
 549             _ => false,
 550         }
 551     }
 552
 553     pub fn is_int(self) -> bool {
 554         match self {
 555             Int(..) => true,
 556             _ => false,
 557         }
 558     }
 559 }
 560
 561 /// Information about one scalar component of a Rust type.
 562 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
 563 #[derive(HashStable_Generic)]
 564 pub struct Scalar {
 565     pub value: Primitive,
 566
 567     /// Inclusive wrap-around range of valid values, that is, if
 568     /// start > end, it represents `start..=max_value()`,
 569     /// followed by `0..=end`.
 570     ///
 571     /// That is, for an i8 primitive, a range of `254..=2` means following
 572     /// sequence:
 573     ///
 574     ///    254 (-2), 255 (-1), 0, 1, 2
 575     ///
 576     /// This is intended specifically to mirror LLVM’s `!range` metadata,
 577     /// semantics.
 578     // FIXME(eddyb) always use the shortest range, e.g., by finding
 579     // the largest space between two consecutive valid values and
 580     // taking everything else as the (shortest) valid range.
 581     pub valid_range: RangeInclusive<u128>,
 582 }
 583
 584 impl Scalar {
 585     pub fn is_bool(&self) -> bool {
 586         if let Int(I8, _) = self.value { self.valid_range == (0..=1) } else { false }
 587     }
 588
 589     /// Returns the valid range as a `x..y` range.
 590     ///
 591     /// If `x` and `y` are equal, the range is full, not empty.
 592     pub fn valid_range_exclusive<C: HasDataLayout>(&self, cx: &C) -> Range<u128> {
 593         // For a (max) value of -1, max will be `-1 as usize`, which overflows.
 594         // However, that is fine here (it would still represent the full range),
 595         // i.e., if the range is everything.
 596         let bits = self.value.size(cx).bits();
 597         assert!(bits <= 128);
 598         let mask = !0u128 >> (128 - bits);
 599         let start = *self.valid_range.start();
 600         let end = *self.valid_range.end();
 601         assert_eq!(start, start & mask);
 602         assert_eq!(end, end & mask);
 603         start..(end.wrapping_add(1) & mask)
 604     }
 605 }
 606
 607 /// Describes how the fields of a type are located in memory.
 608 #[derive(PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 609 pub enum FieldPlacement {
 610     /// All fields start at no offset. The `usize` is the field count.
 611     ///
 612     /// In the case of primitives the number of fields is `0`.
 613     Union(usize),
 614
 615     /// Array/vector-like placement, with all fields of identical types.
 616     Array { stride: Size, count: u64 },
 617
 618     /// Struct-like placement, with precomputed offsets.
 619     ///
 620     /// Fields are guaranteed to not overlap, but note that gaps
 621     /// before, between and after all the fields are NOT always
 622     /// padding, and as such their contents may not be discarded.
 623     /// For example, enum variants leave a gap at the start,
 624     /// where the discriminant field in the enum layout goes.
 625     Arbitrary {
 626         /// Offsets for the first byte of each field,
 627         /// ordered to match the source definition order.
 628         /// This vector does not go in increasing order.
 629         // FIXME(eddyb) use small vector optimization for the common case.
 630         offsets: Vec<Size>,
 631
 632         /// Maps source order field indices to memory order indices,
 633         /// depending on how the fields were reordered (if at all).
 634         /// This is a permutation, with both the source order and the
 635         /// memory order using the same (0..n) index ranges.
 636         ///
 637         /// Note that during computation of `memory_index`, sometimes
 638         /// it is easier to operate on the inverse mapping (that is,
 639         /// from memory order to source order), and that is usually
 640         /// named `inverse_memory_index`.
 641         ///
 642         // FIXME(eddyb) build a better abstraction for permutations, if possible.
 643         // FIXME(camlorn) also consider small vector  optimization here.
 644         memory_index: Vec<u32>,
 645     },
 646 }
 647
 648 impl FieldPlacement {
 649     pub fn count(&self) -> usize {
 650         match *self {
 651             FieldPlacement::Union(count) => count,
 652             FieldPlacement::Array { count, .. } => {
 653                 let usize_count = count as usize;
 654                 assert_eq!(usize_count as u64, count);
 655                 usize_count
 656             }
 657             FieldPlacement::Arbitrary { ref offsets, .. } => offsets.len(),
 658         }
 659     }
 660
 661     pub fn offset(&self, i: usize) -> Size {
 662         match *self {
 663             FieldPlacement::Union(_) => Size::ZERO,
 664             FieldPlacement::Array { stride, count } => {
 665                 let i = i as u64;
 666                 assert!(i < count);
 667                 stride * i
 668             }
 669             FieldPlacement::Arbitrary { ref offsets, .. } => offsets[i],
 670         }
 671     }
 672
 673     pub fn memory_index(&self, i: usize) -> usize {
 674         match *self {
 675             FieldPlacement::Union(_) | FieldPlacement::Array { .. } => i,
 676             FieldPlacement::Arbitrary { ref memory_index, .. } => {
 677                 let r = memory_index[i];
 678                 assert_eq!(r as usize as u32, r);
 679                 r as usize
 680             }
 681         }
 682     }
 683
 684     /// Gets source indices of the fields by increasing offsets.
 685     #[inline]
 686     pub fn index_by_increasing_offset<'a>(&'a self) -> impl Iterator<Item = usize> + 'a {
 687         let mut inverse_small = [0u8; 64];
 688         let mut inverse_big = vec![];
 689         let use_small = self.count() <= inverse_small.len();
 690
 691         // We have to write this logic twice in order to keep the array small.
 692         if let FieldPlacement::Arbitrary { ref memory_index, .. } = *self {
 693             if use_small {
 694                 for i in 0..self.count() {
 695                     inverse_small[memory_index[i] as usize] = i as u8;
 696                 }
 697             } else {
 698                 inverse_big = vec![0; self.count()];
 699                 for i in 0..self.count() {
 700                     inverse_big[memory_index[i] as usize] = i as u32;
 701                 }
 702             }
 703         }
 704
 705         (0..self.count()).map(move |i| match *self {
 706             FieldPlacement::Union(_) | FieldPlacement::Array { .. } => i,
 707             FieldPlacement::Arbitrary { .. } => {
 708                 if use_small {
 709                     inverse_small[i] as usize
 710                 } else {
 711                     inverse_big[i] as usize
 712                 }
 713             }
 714         })
 715     }
 716 }
 717
 718 /// Describes how values of the type are passed by target ABIs,
 719 /// in terms of categories of C types there are ABI rules for.
 720 #[derive(Clone, PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 721 pub enum Abi {
 722     Uninhabited,
 723     Scalar(Scalar),
 724     ScalarPair(Scalar, Scalar),
 725     Vector {
 726         element: Scalar,
 727         count: u64,
 728     },
 729     Aggregate {
 730         /// If true, the size is exact, otherwise it's only a lower bound.
 731         sized: bool,
 732     },
 733 }
 734
 735 impl Abi {
 736     /// Returns `true` if the layout corresponds to an unsized type.
 737     pub fn is_unsized(&self) -> bool {
 738         match *self {
 739             Abi::Uninhabited | Abi::Scalar(_) | Abi::ScalarPair(..) | Abi::Vector { .. } => false,
 740             Abi::Aggregate { sized } => !sized,
 741         }
 742     }
 743
 744     /// Returns `true` if this is a single signed integer scalar
 745     pub fn is_signed(&self) -> bool {
 746         match *self {
 747             Abi::Scalar(ref scal) => match scal.value {
 748                 Primitive::Int(_, signed) => signed,
 749                 _ => false,
 750             },
 751             _ => false,
 752         }
 753     }
 754
 755     /// Returns `true` if this is an uninhabited type
 756     pub fn is_uninhabited(&self) -> bool {
 757         match *self {
 758             Abi::Uninhabited => true,
 759             _ => false,
 760         }
 761     }
 762
 763     /// Returns `true` is this is a scalar type
 764     pub fn is_scalar(&self) -> bool {
 765         match *self {
 766             Abi::Scalar(_) => true,
 767             _ => false,
 768         }
 769     }
 770 }
 771
 772 rustc_index::newtype_index! {
 773     pub struct VariantIdx {
 774         derive [HashStable_Generic]
 775     }
 776 }
 777
 778 #[derive(PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 779 pub enum Variants {
 780     /// Single enum variants, structs/tuples, unions, and all non-ADTs.
 781     Single { index: VariantIdx },
 782
 783     /// Enum-likes with more than one inhabited variant: for each case there is
 784     /// a struct, and they all have space reserved for the discriminant.
 785     /// For enums this is the sole field of the layout.
 786     Multiple {
 787         discr: Scalar,
 788         discr_kind: DiscriminantKind,
 789         discr_index: usize,
 790         variants: IndexVec<VariantIdx, LayoutDetails>,
 791     },
 792 }
 793
 794 #[derive(PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 795 pub enum DiscriminantKind {
 796     /// Integer tag holding the discriminant value itself.
 797     Tag,
 798
 799     /// Niche (values invalid for a type) encoding the discriminant:
 800     /// the variant `dataful_variant` contains a niche at an arbitrary
 801     /// offset (field `discr_index` of the enum), which for a variant with
 802     /// discriminant `d` is set to
 803     /// `(d - niche_variants.start).wrapping_add(niche_start)`.
 804     ///
 805     /// For example, `Option<(usize, &T)>`  is represented such that
 806     /// `None` has a null pointer for the second tuple field, and
 807     /// `Some` is the identity function (with a non-null reference).
 808     Niche {
 809         dataful_variant: VariantIdx,
 810         niche_variants: RangeInclusive<VariantIdx>,
 811         niche_start: u128,
 812     },
 813 }
 814
 815 #[derive(Clone, PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 816 pub struct Niche {
 817     pub offset: Size,
 818     pub scalar: Scalar,
 819 }
 820
 821 impl Niche {
 822     pub fn from_scalar<C: HasDataLayout>(cx: &C, offset: Size, scalar: Scalar) -> Option<Self> {
 823         let niche = Niche { offset, scalar };
 824         if niche.available(cx) > 0 { Some(niche) } else { None }
 825     }
 826
 827     pub fn available<C: HasDataLayout>(&self, cx: &C) -> u128 {
 828         let Scalar { value, valid_range: ref v } = self.scalar;
 829         let bits = value.size(cx).bits();
 830         assert!(bits <= 128);
 831         let max_value = !0u128 >> (128 - bits);
 832
 833         // Find out how many values are outside the valid range.
 834         let niche = v.end().wrapping_add(1)..*v.start();
 835         niche.end.wrapping_sub(niche.start) & max_value
 836     }
 837
 838     pub fn reserve<C: HasDataLayout>(&self, cx: &C, count: u128) -> Option<(u128, Scalar)> {
 839         assert!(count > 0);
 840
 841         let Scalar { value, valid_range: ref v } = self.scalar;
 842         let bits = value.size(cx).bits();
 843         assert!(bits <= 128);
 844         let max_value = !0u128 >> (128 - bits);
 845
 846         if count > max_value {
 847             return None;
 848         }
 849
 850         // Compute the range of invalid values being reserved.
 851         let start = v.end().wrapping_add(1) & max_value;
 852         let end = v.end().wrapping_add(count) & max_value;
 853
 854         // If the `end` of our range is inside the valid range,
 855         // then we ran out of invalid values.
 856         // FIXME(eddyb) abstract this with a wraparound range type.
 857         let valid_range_contains = |x| {
 858             if v.start() <= v.end() {
 859                 *v.start() <= x && x <= *v.end()
 860             } else {
 861                 *v.start() <= x || x <= *v.end()
 862             }
 863         };
 864         if valid_range_contains(end) {
 865             return None;
 866         }
 867
 868         Some((start, Scalar { value, valid_range: *v.start()..=end }))
 869     }
 870 }
 871
 872 #[derive(PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 873 pub struct LayoutDetails {
 874     pub variants: Variants,
 875     pub fields: FieldPlacement,
 876     pub abi: Abi,
 877
 878     /// The leaf scalar with the largest number of invalid values
 879     /// (i.e. outside of its `valid_range`), if it exists.
 880     pub largest_niche: Option<Niche>,
 881
 882     pub align: AbiAndPrefAlign,
 883     pub size: Size,
 884 }
 885
 886 impl LayoutDetails {
 887     pub fn scalar<C: HasDataLayout>(cx: &C, scalar: Scalar) -> Self {
 888         let largest_niche = Niche::from_scalar(cx, Size::ZERO, scalar.clone());
 889         let size = scalar.value.size(cx);
 890         let align = scalar.value.align(cx);
 891         LayoutDetails {
 892             variants: Variants::Single { index: VariantIdx::new(0) },
 893             fields: FieldPlacement::Union(0),
 894             abi: Abi::Scalar(scalar),
 895             largest_niche,
 896             size,
 897             align,
 898         }
 899     }
 900 }
 901
 902 /// The details of the layout of a type, alongside the type itself.
 903 /// Provides various type traversal APIs (e.g., recursing into fields).
 904 ///
 905 /// Note that the details are NOT guaranteed to always be identical
 906 /// to those obtained from `layout_of(ty)`, as we need to produce
 907 /// layouts for which Rust types do not exist, such as enum variants
 908 /// or synthetic fields of enums (i.e., discriminants) and fat pointers.
 909 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
 910 pub struct TyLayout<'a, Ty> {
 911     pub ty: Ty,
 912     pub details: &'a LayoutDetails,
 913 }
 914
 915 impl<'a, Ty> Deref for TyLayout<'a, Ty> {
 916     type Target = &'a LayoutDetails;
 917     fn deref(&self) -> &&'a LayoutDetails {
 918         &self.details
 919     }
 920 }
 921
 922 pub trait LayoutOf {
 923     type Ty;
 924     type TyLayout;
 925
 926     fn layout_of(&self, ty: Self::Ty) -> Self::TyLayout;
 927     fn spanned_layout_of(&self, ty: Self::Ty, _span: Span) -> Self::TyLayout {
 928         self.layout_of(ty)
 929     }
 930 }
 931
 932 #[derive(Copy, Clone, PartialEq, Eq)]
 933 pub enum PointerKind {
 934     /// Most general case, we know no restrictions to tell LLVM.
 935     Shared,
 936
 937     /// `&T` where `T` contains no `UnsafeCell`, is `noalias` and `readonly`.
 938     Frozen,
 939
 940     /// `&mut T`, when we know `noalias` is safe for LLVM.
 941     UniqueBorrowed,
 942
 943     /// `Box<T>`, unlike `UniqueBorrowed`, it also has `noalias` on returns.
 944     UniqueOwned,
 945 }
 946
 947 #[derive(Copy, Clone)]
 948 pub struct PointeeInfo {
 949     pub size: Size,
 950     pub align: Align,
 951     pub safe: Option<PointerKind>,
 952 }
 953
 954 pub trait TyLayoutMethods<'a, C: LayoutOf<Ty = Self>>: Sized {
 955     fn for_variant(
 956         this: TyLayout<'a, Self>,
 957         cx: &C,
 958         variant_index: VariantIdx,
 959     ) -> TyLayout<'a, Self>;
 960     fn field(this: TyLayout<'a, Self>, cx: &C, i: usize) -> C::TyLayout;
 961     fn pointee_info_at(this: TyLayout<'a, Self>, cx: &C, offset: Size) -> Option<PointeeInfo>;
 962 }
 963
 964 impl<'a, Ty> TyLayout<'a, Ty> {
 965     pub fn for_variant<C>(self, cx: &C, variant_index: VariantIdx) -> Self
 966     where
 967         Ty: TyLayoutMethods<'a, C>,
 968         C: LayoutOf<Ty = Ty>,
 969     {
 970         Ty::for_variant(self, cx, variant_index)
 971     }
 972     pub fn field<C>(self, cx: &C, i: usize) -> C::TyLayout
 973     where
 974         Ty: TyLayoutMethods<'a, C>,
 975         C: LayoutOf<Ty = Ty>,
 976     {
 977         Ty::field(self, cx, i)
 978     }
 979     pub fn pointee_info_at<C>(self, cx: &C, offset: Size) -> Option<PointeeInfo>
 980     where
 981         Ty: TyLayoutMethods<'a, C>,
 982         C: LayoutOf<Ty = Ty>,
 983     {
 984         Ty::pointee_info_at(self, cx, offset)
 985     }
 986 }
 987
 988 impl<'a, Ty> TyLayout<'a, Ty> {
 989     /// Returns `true` if the layout corresponds to an unsized type.
 990     pub fn is_unsized(&self) -> bool {
 991         self.abi.is_unsized()
 992     }
 993
 994     /// Returns `true` if the type is a ZST and not unsized.
 995     pub fn is_zst(&self) -> bool {
 996         match self.abi {
 997             Abi::Scalar(_) | Abi::ScalarPair(..) | Abi::Vector { .. } => false,
 998             Abi::Uninhabited => self.size.bytes() == 0,
 999             Abi::Aggregate { sized } => sized && self.size.bytes() == 0,
1000         }
1001     }
1002 }