Auto merge of #25434 - dotdash:gep, r=alexcrichton

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.

2 files changed, 138 insertions, 0 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")]