Allow for better optimizations of iterators for zero-sized types

Using regular pointer arithmetic to iterate collections of zero-sized types
doesn't work, because we'd get the same pointer all the time. Our
current solution is to convert the pointer to an integer, add an offset
and then convert back, but this inhibits certain optimizations.

What we should do instead is to convert the pointer to one that points
to an i8*, and then use a LLVM GEP instructions without the inbounds
flag to perform the pointer arithmetic. This allows to generate pointers
that point outside allocated objects without causing UB (as long as you
don't dereference them), and it wraps around using two's complement,
i.e. it behaves exactly like the wrapping_* operations we're currently
using, with the added benefit of LLVM being able to better optimize the
resulting IR.

6 files changed, 219 insertions, 46 deletions

diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs
index bca0e1427e4..4f3c3b08263 100644
--- a/src/libcollections/btree/node.rs
+++ b/src/libcollections/btree/node.rs
@@ -19,6 +19,8 @@ pub use self::TraversalItem::*;
 use core::prelude::*;
 
 use core::cmp::Ordering::{Greater, Less, Equal};
+#[cfg(not(stage0))]
+use core::intrinsics::arith_offset;
 use core::iter::Zip;
 use core::marker::PhantomData;
 use core::ops::{Deref, DerefMut, Index, IndexMut};
@@ -205,6 +207,7 @@ impl<T> RawItems<T> {
         RawItems::from_parts(slice.as_ptr(), slice.len())
     }
 
+    #[cfg(stage0)]
     unsafe fn from_parts(ptr: *const T, len: usize) -> RawItems<T> {
         if mem::size_of::<T>() == 0 {
             RawItems {
@@ -219,6 +222,22 @@ impl<T> RawItems<T> {
         }
     }
 
+    #[cfg(not(stage0))]
+    unsafe fn from_parts(ptr: *const T, len: usize) -> RawItems<T> {
+        if mem::size_of::<T>() == 0 {
+            RawItems {
+                head: ptr,
+                tail: arith_offset(ptr as *const i8, len as isize) as *const T,
+            }
+        } else {
+            RawItems {
+                head: ptr,
+                tail: ptr.offset(len as isize),
+            }
+        }
+    }
+
+    #[cfg(stage0)]
     unsafe fn push(&mut self, val: T) {
         ptr::write(self.tail as *mut T, val);
 
@@ -228,11 +247,23 @@ impl<T> RawItems<T> {
             self.tail = self.tail.offset(1);
         }
     }
+
+    #[cfg(not(stage0))]
+    unsafe fn push(&mut self, val: T) {
+        ptr::write(self.tail as *mut T, val);
+
+        if mem::size_of::<T>() == 0 {
+            self.tail = arith_offset(self.tail as *const i8, 1) as *const T;
+        } else {
+            self.tail = self.tail.offset(1);
+        }
+    }
 }
 
 impl<T> Iterator for RawItems<T> {
     type Item = T;
 
+    #[cfg(stage0)]
     fn next(&mut self) -> Option<T> {
         if self.head == self.tail {
             None
@@ -250,9 +281,29 @@ impl<T> Iterator for RawItems<T> {
             }
         }
     }
+
+    #[cfg(not(stage0))]
+    fn next(&mut self) -> Option<T> {
+        if self.head == self.tail {
+            None
+        } else {
+            unsafe {
+                let ret = Some(ptr::read(self.head));
+
+                if mem::size_of::<T>() == 0 {
+                    self.head = arith_offset(self.head as *const i8, 1) as *const T;
+                } else {
+                    self.head = self.head.offset(1);
+                }
+
+                ret
+            }
+        }
+    }
 }
 
 impl<T> DoubleEndedIterator for RawItems<T> {
+    #[cfg(stage0)]
     fn next_back(&mut self) -> Option<T> {
         if self.head == self.tail {
             None
@@ -268,6 +319,23 @@ impl<T> DoubleEndedIterator for RawItems<T> {
             }
         }
     }
+
+    #[cfg(not(stage0))]
+    fn next_back(&mut self) -> Option<T> {
+        if self.head == self.tail {
+            None
+        } else {
+            unsafe {
+                if mem::size_of::<T>() == 0 {
+                    self.tail = arith_offset(self.tail as *const i8, -1) as *const T;
+                } else {
+                    self.tail = self.tail.offset(-1);
+                }
+
+                Some(ptr::read(self.tail))
+            }
+        }
+    }
 }
 
 impl<T> Drop for RawItems<T> {
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index e35d81d3996..d3315758df0 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -66,6 +66,8 @@ use core::cmp::Ordering;
 use core::fmt;
 use core::hash::{self, Hash};
 use core::intrinsics::assume;
+#[cfg(not(stage0))]
+use core::intrinsics::arith_offset;
 use core::iter::{repeat, FromIterator};
 use core::marker::PhantomData;
 use core::mem;
@@ -1527,6 +1529,7 @@ impl<T> IntoIterator for Vec<T> {
     /// }
     /// ```
     #[inline]
+    #[cfg(stage0)]
     fn into_iter(self) -> IntoIter<T> {
         unsafe {
             let ptr = *self.ptr;
@@ -1542,6 +1545,24 @@ impl<T> IntoIterator for Vec<T> {
             IntoIter { allocation: ptr, cap: cap, ptr: begin, end: end }
         }
     }
+
+    #[inline]
+    #[cfg(not(stage0))]
+    fn into_iter(self) -> IntoIter<T> {
+        unsafe {
+            let ptr = *self.ptr;
+            assume(!ptr.is_null());
+            let cap = self.cap;
+            let begin = ptr as *const T;
+            let end = if mem::size_of::<T>() == 0 {
+                arith_offset(ptr as *const i8, self.len() as isize) as *const T
+            } else {
+                ptr.offset(self.len() as isize) as *const T
+            };
+            mem::forget(self);
+            IntoIter { allocation: ptr, cap: cap, ptr: begin, end: end }
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1746,6 +1767,7 @@ impl<T> Iterator for IntoIter<T> {
     type Item = T;
 
     #[inline]
+    #[cfg(stage0)]
     fn next(&mut self) -> Option<T> {
         unsafe {
             if self.ptr == self.end {
@@ -1770,6 +1792,31 @@ impl<T> Iterator for IntoIter<T> {
     }
 
     #[inline]
+    #[cfg(not(stage0))]
+    fn next(&mut self) -> Option<T> {
+        unsafe {
+            if self.ptr == self.end {
+                None
+            } else {
+                if mem::size_of::<T>() == 0 {
+                    // purposefully don't use 'ptr.offset' because for
+                    // vectors with 0-size elements this would return the
+                    // same pointer.
+                    self.ptr = arith_offset(self.ptr as *const i8, 1) as *const T;
+
+                    // Use a non-null pointer value
+                    Some(ptr::read(EMPTY as *mut T))
+                } else {
+                    let old = self.ptr;
+                    self.ptr = self.ptr.offset(1);
+
+                    Some(ptr::read(old))
+                }
+            }
+        }
+    }
+
+    #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         let diff = (self.end as usize) - (self.ptr as usize);
         let size = mem::size_of::<T>();
@@ -1786,6 +1833,7 @@ impl<T> Iterator for IntoIter<T> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> DoubleEndedIterator for IntoIter<T> {
     #[inline]
+    #[cfg(stage0)]
     fn next_back(&mut self) -> Option<T> {
         unsafe {
             if self.end == self.ptr {
@@ -1805,6 +1853,28 @@ impl<T> DoubleEndedIterator for IntoIter<T> {
             }
         }
     }
+
+    #[inline]
+    #[cfg(not(stage0))]
+    fn next_back(&mut self) -> Option<T> {
+        unsafe {
+            if self.end == self.ptr {
+                None
+            } else {
+                if mem::size_of::<T>() == 0 {
+                    // See above for why 'ptr.offset' isn't used
+                    self.end = arith_offset(self.end as *const i8, -1) as *const T;
+
+                    // Use a non-null pointer value
+                    Some(ptr::read(EMPTY as *mut T))
+                } else {
+                    self.end = self.end.offset(-1);
+
+                    Some(ptr::read(mem::transmute(self.end)))
+                }
+            }
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libcore/intrinsics.rs b/src/libcore/intrinsics.rs
index d94b8884112..fa432e311eb 100644
--- a/src/libcore/intrinsics.rs
+++ b/src/libcore/intrinsics.rs
@@ -283,6 +283,20 @@ extern "rust-intrinsic" {
     /// returned value will result in undefined behavior.
     pub fn offset<T>(dst: *const T, offset: isize) -> *const T;
 
+    /// Calculates the offset from a pointer, potentially wrapping.
+    ///
+    /// This is implemented as an intrinsic to avoid converting to and from an
+    /// integer, since the conversion inhibits certain optimizations.
+    ///
+    /// # Safety
+    ///
+    /// Unlike the `offset` intrinsic, this intrinsic does not restrict the
+    /// resulting pointer to point into or one byte past the end of an allocated
+    /// object, and it wraps with two's complement arithmetic. The resulting
+    /// value is not necessarily valid to be used to actually access memory.
+    #[cfg(not(stage0))]
+    pub fn arith_offset<T>(dst: *const T, offset: isize) -> *const T;
+
     /// Copies `count * size_of<T>` bytes from `src` to `dst`. The source
     /// and destination may *not* overlap.
     ///
diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index 9db1ceddf0d..346afdc963d 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -124,6 +124,43 @@ pub trait SliceExt {
     fn clone_from_slice(&mut self, &[Self::Item]) -> usize where Self::Item: Clone;
 }
 
+// Use macros to be generic over const/mut
+#[cfg(stage0)]
+macro_rules! slice_offset {
+    ($ptr:expr, $by:expr) => {{
+        let ptr = $ptr;
+        if size_from_ptr(ptr) == 0 {
+            transmute((ptr as isize).wrapping_add($by))
+        } else {
+            ptr.offset($by)
+        }
+    }};
+}
+
+#[cfg(not(stage0))]
+macro_rules! slice_offset {
+    ($ptr:expr, $by:expr) => {{
+        let ptr = $ptr;
+        if size_from_ptr(ptr) == 0 {
+            ::intrinsics::arith_offset(ptr as *mut i8, $by) as *mut _
+        } else {
+            ptr.offset($by)
+        }
+    }};
+}
+
+macro_rules! slice_ref {
+    ($ptr:expr) => {{
+        let ptr = $ptr;
+        if size_from_ptr(ptr) == 0 {
+            // Use a non-null pointer value
+            &mut *(1 as *mut _)
+        } else {
+            transmute(ptr)
+        }
+    }};
+}
+
 #[unstable(feature = "core")]
 impl<T> SliceExt for [T] {
     type Item = T;
@@ -136,16 +173,18 @@ impl<T> SliceExt for [T] {
     #[inline]
     fn iter<'a>(&'a self) -> Iter<'a, T> {
         unsafe {
-            let p = self.as_ptr();
-            assume(!p.is_null());
-            if mem::size_of::<T>() == 0 {
-                Iter {ptr: p,
-                      end: ((p as usize).wrapping_add(self.len())) as *const T,
-                      _marker: marker::PhantomData}
+            let p = if mem::size_of::<T>() == 0 {
+                1 as *const _
             } else {
-                Iter {ptr: p,
-                      end: p.offset(self.len() as isize),
-                      _marker: marker::PhantomData}
+                let p = self.as_ptr();
+                assume(!p.is_null());
+                p
+            };
+
+            Iter {
+                ptr: p,
+                end: slice_offset!(p, self.len() as isize),
+                _marker: marker::PhantomData
             }
         }
     }
@@ -273,16 +312,18 @@ impl<T> SliceExt for [T] {
     #[inline]
     fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
         unsafe {
-            let p = self.as_mut_ptr();
-            assume(!p.is_null());
-            if mem::size_of::<T>() == 0 {
-                IterMut {ptr: p,
-                         end: ((p as usize).wrapping_add(self.len())) as *mut T,
-                         _marker: marker::PhantomData}
+            let p = if mem::size_of::<T>() == 0 {
+                1 as *mut _
             } else {
-                IterMut {ptr: p,
-                         end: p.offset(self.len() as isize),
-                         _marker: marker::PhantomData}
+                let p = self.as_mut_ptr();
+                assume(!p.is_null());
+                p
+            };
+
+            IterMut {
+                ptr: p,
+                end: slice_offset!(p, self.len() as isize),
+                _marker: marker::PhantomData
             }
         }
     }
@@ -630,31 +671,6 @@ fn size_from_ptr<T>(_: *const T) -> usize {
     mem::size_of::<T>()
 }
 
-
-// Use macros to be generic over const/mut
-macro_rules! slice_offset {
-    ($ptr:expr, $by:expr) => {{
-        let ptr = $ptr;
-        if size_from_ptr(ptr) == 0 {
-            transmute((ptr as isize).wrapping_add($by))
-        } else {
-            ptr.offset($by)
-        }
-    }};
-}
-
-macro_rules! slice_ref {
-    ($ptr:expr) => {{
-        let ptr = $ptr;
-        if size_from_ptr(ptr) == 0 {
-            // Use a non-null pointer value
-            &mut *(1 as *mut _)
-        } else {
-            transmute(ptr)
-        }
-    }};
-}
-
 // The shared definition of the `Iter` and `IterMut` iterators
 macro_rules! iterator {
     (struct $name:ident -> $ptr:ty, $elem:ty) => {
@@ -781,7 +797,7 @@ impl<'a, T> Iter<'a, T> {
         match self.as_slice().get(n) {
             Some(elem_ref) => unsafe {
                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
-                Some(slice_ref!(elem_ref))
+                Some(elem_ref)
             },
             None => {
                 self.ptr = self.end;
@@ -849,7 +865,7 @@ impl<'a, T> IterMut<'a, T> {
         match make_mut_slice!(self.ptr, self.end).get_mut(n) {
             Some(elem_ref) => unsafe {
                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
-                Some(slice_ref!(elem_ref))
+                Some(elem_ref)
             },
             None => {
                 self.ptr = self.end;
diff --git a/src/librustc_trans/trans/intrinsic.rs b/src/librustc_trans/trans/intrinsic.rs
index 951d30c4fb8..4608918ec59 100644
--- a/src/librustc_trans/trans/intrinsic.rs
+++ b/src/librustc_trans/trans/intrinsic.rs
@@ -418,6 +418,11 @@ pub fn trans_intrinsic_call<'a, 'blk, 'tcx>(mut bcx: Block<'blk, 'tcx>,
             let offset = llargs[1];
             InBoundsGEP(bcx, ptr, &[offset])
         }
+        (_, "arith_offset") => {
+            let ptr = llargs[0];
+            let offset = llargs[1];
+            GEP(bcx, ptr, &[offset])
+        }
 
         (_, "copy_nonoverlapping") => {
             copy_intrinsic(bcx,
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 3cdbaec1528..f13305bba34 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -5009,7 +5009,7 @@ pub fn check_intrinsic_type(ccx: &CrateCtxt, it: &ast::ForeignItem) {
             "type_name" => (1, Vec::new(), ty::mk_str_slice(tcx, tcx.mk_region(ty::ReStatic),
                                                              ast::MutImmutable)),
             "type_id" => (1, Vec::new(), ccx.tcx.types.u64),
-            "offset" => {
+            "offset" | "arith_offset" => {
               (1,
                vec!(
                   ty::mk_ptr(tcx, ty::mt {