src/librustc_target/abi/mod.rs

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