From 6c2d875261e10105dcfcbd9be84d05a730edd235 Mon Sep 17 00:00:00 2001 From: =?utf8?q?John=20K=C3=A5re=20Alsaker?= Date: Wed, 2 May 2018 08:02:57 +0200 Subject: [PATCH] Make &Slice a thin pointer --- src/libarena/lib.rs | 59 ++++++++++-------- src/librustc/lib.rs | 1 + src/librustc/ty/context.rs | 27 ++++---- src/librustc/ty/mod.rs | 93 +++++++++++++++++++++++++--- src/test/mir-opt/basic_assignment.rs | 2 +- 5 files changed, 134 insertions(+), 48 deletions(-) diff --git a/src/libarena/lib.rs b/src/libarena/lib.rs index f7143a4f981..b6a81596d06 100644 --- a/src/libarena/lib.rs +++ b/src/libarena/lib.rs @@ -314,8 +314,7 @@ pub fn in_arena(&self, ptr: *const T) -> bool { false } - fn align_for(&self) { - let align = mem::align_of::(); + fn align(&self, align: usize) { let final_address = ((self.ptr.get() as usize) + align - 1) & !(align - 1); self.ptr.set(final_address as *mut u8); assert!(self.ptr <= self.end); @@ -323,8 +322,7 @@ fn align_for(&self) { #[inline(never)] #[cold] - fn grow(&self, n: usize) { - let needed_bytes = n * mem::size_of::(); + fn grow(&self, needed_bytes: usize) { unsafe { let mut chunks = self.chunks.borrow_mut(); let (chunk, mut new_capacity); @@ -356,25 +354,38 @@ fn grow(&self, n: usize) { } #[inline] - pub fn alloc(&self, object: T) -> &mut T { + pub fn alloc_raw(&self, bytes: usize, align: usize) -> &mut [u8] { unsafe { - assert!(!mem::needs_drop::()); - assert!(mem::size_of::() != 0); + assert!(bytes != 0); + + self.align(align); - self.align_for::(); - let future_end = intrinsics::arith_offset(self.ptr.get(), mem::size_of::() as isize); + let future_end = intrinsics::arith_offset(self.ptr.get(), bytes as isize); if (future_end as *mut u8) >= self.end.get() { - self.grow::(1) + self.grow(bytes); } let ptr = self.ptr.get(); // Set the pointer past ourselves self.ptr.set( - intrinsics::arith_offset(self.ptr.get(), mem::size_of::() as isize) as *mut u8, + intrinsics::arith_offset(self.ptr.get(), bytes as isize) as *mut u8, ); + slice::from_raw_parts_mut(ptr, bytes) + } + } + + #[inline] + pub fn alloc(&self, object: T) -> &mut T { + assert!(!mem::needs_drop::()); + + let mem = self.alloc_raw( + mem::size_of::(), + mem::align_of::()) as *mut _ as *mut T; + + unsafe { // Write into uninitialized memory. - ptr::write(ptr as *mut T, object); - &mut *(ptr as *mut T) + ptr::write(mem, object); + &mut *mem } } @@ -393,21 +404,13 @@ pub fn alloc_slice(&self, slice: &[T]) -> &mut [T] assert!(!mem::needs_drop::()); assert!(mem::size_of::() != 0); assert!(slice.len() != 0); - self.align_for::(); - let future_end = unsafe { - intrinsics::arith_offset(self.ptr.get(), (slice.len() * mem::size_of::()) as isize) - }; - if (future_end as *mut u8) >= self.end.get() { - self.grow::(slice.len()); - } + let mem = self.alloc_raw( + slice.len() * mem::size_of::(), + mem::align_of::()) as *mut _ as *mut T; unsafe { - let arena_slice = slice::from_raw_parts_mut(self.ptr.get() as *mut T, slice.len()); - self.ptr.set(intrinsics::arith_offset( - self.ptr.get(), - (slice.len() * mem::size_of::()) as isize, - ) as *mut u8); + let arena_slice = slice::from_raw_parts_mut(mem, slice.len()); arena_slice.copy_from_slice(slice); arena_slice } @@ -464,6 +467,12 @@ pub fn in_arena(&self, ptr: *const T) -> bool { self.lock.lock().in_arena(ptr) } + #[inline(always)] + pub fn alloc_raw(&self, bytes: usize, align: usize) -> &mut [u8] { + // Extend the lifetime of the result since it's limited to the lock guard + unsafe { &mut *(self.lock.lock().alloc_raw(bytes, align) as *mut [u8]) } + } + #[inline(always)] pub fn alloc(&self, object: T) -> &mut T { // Extend the lifetime of the result since it's limited to the lock guard diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs index 486ea93588c..e8402487c7d 100644 --- a/src/librustc/lib.rs +++ b/src/librustc/lib.rs @@ -54,6 +54,7 @@ #![feature(macro_vis_matcher)] #![feature(never_type)] #![feature(exhaustive_patterns)] +#![feature(extern_types)] #![feature(non_exhaustive)] #![feature(proc_macro_internals)] #![feature(quote)] diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs index 8a73219cf70..3580926d8ad 100644 --- a/src/librustc/ty/context.rs +++ b/src/librustc/ty/context.rs @@ -2056,9 +2056,8 @@ fn borrow<'a>(&'a self) -> &'a [Goal<'lcx>] { macro_rules! intern_method { ($lt_tcx:tt, $name:ident: $method:ident($alloc:ty, - $alloc_method:ident, + $alloc_method:expr, $alloc_to_key:expr, - $alloc_to_ret:expr, $keep_in_local_tcx:expr) -> $ty:ty) => { impl<'a, 'gcx, $lt_tcx> TyCtxt<'a, 'gcx, $lt_tcx> { pub fn $method(self, v: $alloc) -> &$lt_tcx $ty { @@ -2081,7 +2080,7 @@ pub fn $method(self, v: $alloc) -> &$lt_tcx $ty { v); } - let i = ($alloc_to_ret)(self.interners.arena.$alloc_method(v)); + let i = $alloc_method(&self.interners.arena, v); interner.insert(Interned(i)); i } else { @@ -2094,7 +2093,9 @@ pub fn $method(self, v: $alloc) -> &$lt_tcx $ty { let v = unsafe { mem::transmute(v) }; - let i = ($alloc_to_ret)(self.global_interners.arena.$alloc_method(v)); + let i: &$lt_tcx $ty = $alloc_method(&self.global_interners.arena, v); + // Cast to 'gcx + let i = unsafe { mem::transmute(i) }; interner.insert(Interned(i)); i } @@ -2121,8 +2122,10 @@ fn hash(&self, s: &mut H) { intern_method!( $lt_tcx, - $name: $method($ty, alloc, |x| x, |x| x, $keep_in_local_tcx) -> $ty - );)+ + $name: $method($ty, + |a: &$lt_tcx SyncDroplessArena, v| -> &$lt_tcx $ty { a.alloc(v) }, + |x| x, + $keep_in_local_tcx) -> $ty);)+ } } @@ -2137,10 +2140,11 @@ pub fn keep_local<'tcx, T: ty::TypeFoldable<'tcx>>(x: &T) -> bool { macro_rules! slice_interners { ($($field:ident: $method:ident($ty:ident)),+) => ( - $(intern_method!('tcx, $field: $method(&[$ty<'tcx>], alloc_slice, Deref::deref, - |xs: &[$ty]| -> &Slice<$ty> { - unsafe { mem::transmute(xs) } - }, |xs: &[$ty]| xs.iter().any(keep_local)) -> Slice<$ty<'tcx>>);)+ + $(intern_method!( 'tcx, $field: $method( + &[$ty<'tcx>], + |a, v| Slice::from_arena(a, v), + Deref::deref, + |xs: &[$ty]| xs.iter().any(keep_local)) -> Slice<$ty<'tcx>>);)+ ) } @@ -2162,9 +2166,8 @@ macro_rules! slice_interners { 'tcx, canonical_var_infos: _intern_canonical_var_infos( &[CanonicalVarInfo], - alloc_slice, + |a, v| Slice::from_arena(a, v), Deref::deref, - |xs: &[CanonicalVarInfo]| -> &Slice { unsafe { mem::transmute(xs) } }, |_xs: &[CanonicalVarInfo]| -> bool { false } ) -> Slice } diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs index 115c6442db5..a4ca0c41701 100644 --- a/src/librustc/ty/mod.rs +++ b/src/librustc/ty/mod.rs @@ -36,12 +36,14 @@ use ty::walk::TypeWalker; use util::captures::Captures; use util::nodemap::{NodeSet, DefIdMap, FxHashMap}; +use arena::SyncDroplessArena; use serialize::{self, Encodable, Encoder}; use std::cell::RefCell; use std::cmp::{self, Ordering}; use std::fmt; use std::hash::{Hash, Hasher}; +use std::marker::PhantomData; use std::ops::Deref; use rustc_data_structures::sync::Lrc; use std::slice; @@ -582,18 +584,76 @@ fn intern(_gcx: TyCtxt<'_, 'gcx, 'gcx>, } } +extern { + /// A dummy type used to force Slice to by unsized without requiring fat pointers + type OpaqueSliceContents; +} + /// A wrapper for slices with the additional invariant /// that the slice is interned and no other slice with /// the same contents can exist in the same context. /// This means we can use pointer + length for both /// equality comparisons and hashing. -#[derive(Debug, RustcEncodable)] -pub struct Slice([T]); +pub struct Slice(PhantomData, OpaqueSliceContents); + +impl Slice { + /// Returns the offset of the array + #[inline(always)] + fn offset() -> usize { + // Align up the size of the len (usize) field + let align = mem::align_of::(); + let align_mask = align - 1; + let offset = mem::size_of::(); + (offset + align_mask) & !align_mask + } +} + +impl Slice { + #[inline] + fn from_arena<'tcx>(arena: &'tcx SyncDroplessArena, slice: &[T]) -> &'tcx Slice { + assert!(!mem::needs_drop::()); + assert!(mem::size_of::() != 0); + assert!(slice.len() != 0); + + let offset = Slice::::offset(); + let size = offset + slice.len() * mem::size_of::(); + + let mem: *mut u8 = arena.alloc_raw( + size, + cmp::max(mem::align_of::(), mem::align_of::())).as_mut_ptr(); + + unsafe { + // Write the length + *(mem as *mut usize) = slice.len(); + + // Write the elements + let arena_slice = slice::from_raw_parts_mut( + mem.offset(offset as isize) as *mut T, + slice.len()); + arena_slice.copy_from_slice(slice); + + &*(mem as *const Slice) + } + } +} + +impl fmt::Debug for Slice { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + (**self).fmt(f) + } +} + +impl Encodable for Slice { + #[inline] + fn encode(&self, s: &mut S) -> Result<(), S::Error> { + (**self).encode(s) + } +} impl Ord for Slice where T: Ord { fn cmp(&self, other: &Slice) -> Ordering { if self == other { Ordering::Equal } else { - <[T] as Ord>::cmp(&self.0, &other.0) + <[T] as Ord>::cmp(&**self, &**other) } } } @@ -601,35 +661,43 @@ fn cmp(&self, other: &Slice) -> Ordering { impl PartialOrd for Slice where T: PartialOrd { fn partial_cmp(&self, other: &Slice) -> Option { if self == other { Some(Ordering::Equal) } else { - <[T] as PartialOrd>::partial_cmp(&self.0, &other.0) + <[T] as PartialOrd>::partial_cmp(&**self, &**other) } } } -impl PartialEq for Slice { +impl PartialEq for Slice { #[inline] fn eq(&self, other: &Slice) -> bool { - (&self.0 as *const [T]) == (&other.0 as *const [T]) + (self as *const _) == (other as *const _) } } -impl Eq for Slice {} +impl Eq for Slice {} impl Hash for Slice { + #[inline] fn hash(&self, s: &mut H) { - (self.as_ptr(), self.len()).hash(s) + (self as *const Slice).hash(s) } } impl Deref for Slice { type Target = [T]; + #[inline(always)] fn deref(&self) -> &[T] { - &self.0 + unsafe { + let raw = self as *const _ as *const u8; + let len = *(raw as *const usize); + let slice = raw.offset(Slice::::offset() as isize); + slice::from_raw_parts(slice as *const T, len) + } } } impl<'a, T> IntoIterator for &'a Slice { type Item = &'a T; type IntoIter = <&'a [T] as IntoIterator>::IntoIter; + #[inline(always)] fn into_iter(self) -> Self::IntoIter { self[..].iter() } @@ -638,9 +706,14 @@ fn into_iter(self) -> Self::IntoIter { impl<'tcx> serialize::UseSpecializedDecodable for &'tcx Slice> {} impl Slice { + #[inline(always)] pub fn empty<'a>() -> &'a Slice { + #[repr(align(64), C)] + struct EmptySlice([u8; 64]); + static EMPTY_SLICE: EmptySlice = EmptySlice([0; 64]); + assert!(mem::align_of::() <= 64); unsafe { - mem::transmute(slice::from_raw_parts(0x1 as *const T, 0)) + &*(&EMPTY_SLICE as *const _ as *const Slice) } } } diff --git a/src/test/mir-opt/basic_assignment.rs b/src/test/mir-opt/basic_assignment.rs index 3c236ddcf04..54b7a3821ca 100644 --- a/src/test/mir-opt/basic_assignment.rs +++ b/src/test/mir-opt/basic_assignment.rs @@ -48,7 +48,7 @@ fn main() { // _2 = move _3; // StorageDead(_3); // StorageLive(_4); -// UserAssertTy(Canonical { variables: Slice([]), value: std::option::Option> }, _4); +// UserAssertTy(Canonical { variables: [], value: std::option::Option> }, _4); // _4 = std::option::Option>::None; // StorageLive(_5); // StorageLive(_6); -- 2.44.0