From b3a317c368d424929cdd2e6c3be661d7d8553cc0 Mon Sep 17 00:00:00 2001 From: Daniel Micay Date: Mon, 5 Aug 2013 19:23:29 -0400 Subject: iterator: simplify the `take` implementation --- src/libstd/iterator.rs | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/libstd') diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs index 56a0dca5667..4803e2e004e 100644 --- a/src/libstd/iterator.rs +++ b/src/libstd/iterator.rs @@ -1316,10 +1316,9 @@ pub struct Take { impl> Iterator for Take { #[inline] fn next(&mut self) -> Option { - let next = self.iter.next(); if self.n != 0 { self.n -= 1; - next + self.iter.next() } else { None } -- cgit 1.4.1-3-g733a5 From c13f4f398a0c27af573fac8d426a6cda68a168fe Mon Sep 17 00:00:00 2001 From: Daniel Micay Date: Mon, 5 Aug 2013 19:58:56 -0400 Subject: add Extendable to the prelude --- src/libstd/prelude.rs | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/libstd') diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs index 517bc4a441a..65db55297b3 100644 --- a/src/libstd/prelude.rs +++ b/src/libstd/prelude.rs @@ -49,6 +49,7 @@ pub use char::Char; pub use container::{Container, Mutable, Map, MutableMap, Set, MutableSet}; pub use hash::Hash; pub use iter::Times; +pub use iterator::Extendable; pub use iterator::{Iterator, IteratorUtil, DoubleEndedIterator, DoubleEndedIteratorUtil}; pub use iterator::{ClonableIterator, OrdIterator}; pub use num::{Num, NumCast}; @@ -64,7 +65,7 @@ pub use path::WindowsPath; pub use ptr::RawPtr; pub use ascii::{Ascii, AsciiCast, OwnedAsciiCast, AsciiStr, ToBytesConsume}; pub use str::{Str, StrVector, StrSlice, OwnedStr, NullTerminatedStr}; -pub use from_str::{FromStr}; +pub use from_str::FromStr; pub use to_bytes::IterBytes; pub use to_str::{ToStr, ToStrConsume}; pub use tuple::{CopyableTuple, ImmutableTuple, ExtendedTupleOps}; -- cgit 1.4.1-3-g733a5 From 40d11a546178ca32523e7424a0bf61fe25f7e3d1 Mon Sep 17 00:00:00 2001 From: Daniel Micay Date: Mon, 5 Aug 2013 20:02:26 -0400 Subject: iterator: rename `Counter::new` to `count` to match the convention used by `range`, since `iterator::count` is already namespaced enough and won't be ambiguous --- src/libextra/ringbuf.rs | 2 +- src/libstd/iterator.rs | 32 +++++++++++++++----------------- 2 files changed, 16 insertions(+), 18 deletions(-) (limited to 'src/libstd') diff --git a/src/libextra/ringbuf.rs b/src/libextra/ringbuf.rs index 9833bd5d1cb..da8089250b3 100644 --- a/src/libextra/ringbuf.rs +++ b/src/libextra/ringbuf.rs @@ -696,7 +696,7 @@ mod tests { let u: ~[int] = deq.iter().transform(|&x| x).collect(); assert_eq!(u, v); - let mut seq = iterator::Counter::new(0u, 2).take_(256); + let mut seq = iterator::count(0u, 2).take_(256); let deq: RingBuf = seq.collect(); for (i, &x) in deq.iter().enumerate() { assert_eq!(2*i, x); diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs index 4803e2e004e..65cb7e7a8a9 100644 --- a/src/libstd/iterator.rs +++ b/src/libstd/iterator.rs @@ -313,7 +313,7 @@ pub trait IteratorUtil { /// ~~~ {.rust} /// let xs = [2u, 3]; /// let ys = [0u, 1, 0, 1, 2]; - /// let mut it = xs.iter().flat_map_(|&x| Counter::new(0u, 1).take_(x)); + /// let mut it = xs.iter().flat_map_(|&x| count(0u, 1).take_(x)); /// // Check that `it` has the same elements as `ys` /// let mut i = 0; /// for x: uint in it { @@ -351,7 +351,7 @@ pub trait IteratorUtil { /// ~~~ {.rust} /// use std::iterator::Counter; /// - /// for i in Counter::new(0, 10) { + /// for i in count(0, 10) { /// printfln!("%d", i); /// } /// ~~~ @@ -723,7 +723,7 @@ pub trait MultiplicativeIterator { /// use std::iterator::Counter; /// /// fn factorial(n: uint) -> uint { - /// Counter::new(1u, 1).take_while(|&i| i <= n).product() + /// count(1u, 1).take_while(|&i| i <= n).product() /// } /// assert!(factorial(0) == 1); /// assert!(factorial(1) == 1); @@ -790,7 +790,7 @@ pub trait ClonableIterator { /// # Example /// /// ~~~ {.rust} - /// let a = Counter::new(1,1).take_(1); + /// let a = count(1,1).take_(1); /// let mut cy = a.cycle(); /// assert_eq!(cy.next(), Some(1)); /// assert_eq!(cy.next(), Some(1)); @@ -1526,12 +1526,10 @@ pub struct Counter { step: A } -impl Counter { - /// Creates a new counter with the specified start/step - #[inline] - pub fn new(start: A, step: A) -> Counter { - Counter{state: start, step: step} - } +/// Creates a new counter with the specified start/step +#[inline] +pub fn count(start: A, step: A) -> Counter { + Counter{state: start, step: step} } /// A range of numbers from [0, N) @@ -1618,7 +1616,7 @@ mod tests { #[test] fn test_counter_from_iter() { - let mut it = Counter::new(0, 5).take_(10); + let mut it = count(0, 5).take_(10); let xs: ~[int] = FromIterator::from_iterator(&mut it); assert_eq!(xs, ~[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]); } @@ -1636,7 +1634,7 @@ mod tests { } assert_eq!(i, expected.len()); - let ys = Counter::new(30u, 10).take_(4); + let ys = count(30u, 10).take_(4); let mut it = xs.iter().transform(|&x| x).chain_(ys); let mut i = 0; for x in it { @@ -1648,7 +1646,7 @@ mod tests { #[test] fn test_filter_map() { - let mut it = Counter::new(0u, 1u).take_(10) + let mut it = count(0u, 1u).take_(10) .filter_map(|x| if x.is_even() { Some(x*x) } else { None }); assert_eq!(it.collect::<~[uint]>(), ~[0*0, 2*2, 4*4, 6*6, 8*8]); } @@ -1737,7 +1735,7 @@ mod tests { fn test_iterator_flat_map() { let xs = [0u, 3, 6]; let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8]; - let mut it = xs.iter().flat_map_(|&x| Counter::new(x, 1).take_(3)); + let mut it = xs.iter().flat_map_(|&x| count(x, 1).take_(3)); let mut i = 0; for x in it { assert_eq!(x, ys[i]); @@ -1784,13 +1782,13 @@ mod tests { #[test] fn test_cycle() { let cycle_len = 3; - let it = Counter::new(0u, 1).take_(cycle_len).cycle(); + let it = count(0u, 1).take_(cycle_len).cycle(); assert_eq!(it.size_hint(), (uint::max_value, None)); for (i, x) in it.take_(100).enumerate() { assert_eq!(i % cycle_len, x); } - let mut it = Counter::new(0u, 1).take_(0).cycle(); + let mut it = count(0u, 1).take_(0).cycle(); assert_eq!(it.size_hint(), (0, Some(0))); assert_eq!(it.next(), None); } @@ -1852,7 +1850,7 @@ mod tests { #[test] fn test_iterator_size_hint() { - let c = Counter::new(0, 1); + let c = count(0, 1); let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; let v2 = &[10, 11, 12]; let vi = v.iter(); -- cgit 1.4.1-3-g733a5 From f23fb19ee508515912e136c948a0242cc88a2d4e Mon Sep 17 00:00:00 2001 From: Daniel Micay Date: Tue, 6 Aug 2013 17:15:43 -0400 Subject: vec: avoid `ptrtoint`/`inttoptr` in the iterators This results in throwing away alias analysis information, because LLVM does *not* implement reasoning about these conversions yet. We specialize zero-size types since a `getelementptr` offset will return us the same pointer, making it broken as a simple counter. --- src/libstd/vec.rs | 26 ++++++++++++++++++-------- 1 file changed, 18 insertions(+), 8 deletions(-) (limited to 'src/libstd') diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs index 0259b547ab3..8dbfb3ec543 100644 --- a/src/libstd/vec.rs +++ b/src/libstd/vec.rs @@ -849,10 +849,15 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] { fn iter(self) -> VecIterator<'self, T> { unsafe { let p = vec::raw::to_ptr(self); - VecIterator{ptr: p, - end: (p as uint + self.len() * - sys::nonzero_size_of::()) as *T, - lifetime: cast::transmute(p)} + if sys::size_of::() == 0 { + VecIterator{ptr: p, + end: (p as uint + self.len()) as *T, + lifetime: cast::transmute(p)} + } else { + VecIterator{ptr: p, + end: p.offset(self.len() as int), + lifetime: cast::transmute(p)} + } } } @@ -1826,10 +1831,15 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] { fn mut_iter(self) -> VecMutIterator<'self, T> { unsafe { let p = vec::raw::to_mut_ptr(self); - VecMutIterator{ptr: p, - end: (p as uint + self.len() * - sys::nonzero_size_of::()) as *mut T, - lifetime: cast::transmute(p)} + if sys::size_of::() == 0 { + VecMutIterator{ptr: p, + end: (p as uint + self.len()) as *mut T, + lifetime: cast::transmute(p)} + } else { + VecMutIterator{ptr: p, + end: p.offset(self.len() as int), + lifetime: cast::transmute(p)} + } } } -- cgit 1.4.1-3-g733a5 From 7d115c94205dd4b937d29c77d1704aa3f801869e Mon Sep 17 00:00:00 2001 From: Daniel Micay Date: Tue, 6 Aug 2013 17:44:40 -0400 Subject: add an intrinsic for inbounds GEP --- src/librustc/middle/trans/foreign.rs | 5 +++++ src/librustc/middle/trans/type_use.rs | 3 ++- src/librustc/middle/typeck/check/mod.rs | 14 ++++++++++++++ src/libstd/ptr.rs | 22 ++++++++++++++++++++++ src/libstd/unstable/intrinsics.rs | 11 ++++++++++- 5 files changed, 53 insertions(+), 2 deletions(-) (limited to 'src/libstd') diff --git a/src/librustc/middle/trans/foreign.rs b/src/librustc/middle/trans/foreign.rs index 5153296337d..b1e600b9d73 100644 --- a/src/librustc/middle/trans/foreign.rs +++ b/src/librustc/middle/trans/foreign.rs @@ -888,6 +888,11 @@ pub fn trans_intrinsic(ccx: @mut CrateContext, let offset = get_param(decl, first_real_arg + 1); Ret(bcx, GEP(bcx, ptr, [offset])); } + "offset_inbounds" => { + let ptr = get_param(decl, first_real_arg); + let offset = get_param(decl, first_real_arg + 1); + Ret(bcx, InBoundsGEP(bcx, ptr, [offset])); + } "memcpy32" => memcpy_intrinsic(bcx, "llvm.memcpy.p0i8.p0i8.i32", substs.tys[0], 32), "memcpy64" => memcpy_intrinsic(bcx, "llvm.memcpy.p0i8.p0i8.i64", substs.tys[0], 64), "memmove32" => memcpy_intrinsic(bcx, "llvm.memmove.p0i8.p0i8.i32", substs.tys[0], 32), diff --git a/src/librustc/middle/trans/type_use.rs b/src/librustc/middle/trans/type_use.rs index 42d5527ee43..ad83286c8c1 100644 --- a/src/librustc/middle/trans/type_use.rs +++ b/src/librustc/middle/trans/type_use.rs @@ -148,7 +148,8 @@ pub fn type_uses_for(ccx: @mut CrateContext, fn_id: def_id, n_tps: uint) "visit_tydesc" | "forget" | "frame_address" | "morestack_addr" => 0, - "offset" | "memcpy32" | "memcpy64" | "memmove32" | "memmove64" | + "offset" | "offset_inbounds" | + "memcpy32" | "memcpy64" | "memmove32" | "memmove64" | "memset32" | "memset64" => use_repr, "sqrtf32" | "sqrtf64" | "powif32" | "powif64" | diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs index ea8a11fc7b3..8623ee546d6 100644 --- a/src/librustc/middle/typeck/check/mod.rs +++ b/src/librustc/middle/typeck/check/mod.rs @@ -3481,6 +3481,20 @@ pub fn check_intrinsic_type(ccx: @mut CrateCtxt, it: @ast::foreign_item) { mutbl: ast::m_imm })) } + "offset_inbounds" => { + (1, + ~[ + ty::mk_ptr(tcx, ty::mt { + ty: param(ccx, 0), + mutbl: ast::m_imm + }), + ty::mk_int() + ], + ty::mk_ptr(tcx, ty::mt { + ty: param(ccx, 0), + mutbl: ast::m_imm + })) + } "memcpy32" => { (1, ~[ diff --git a/src/libstd/ptr.rs b/src/libstd/ptr.rs index dfd11f9227d..98fb132672c 100644 --- a/src/libstd/ptr.rs +++ b/src/libstd/ptr.rs @@ -272,6 +272,8 @@ pub trait RawPtr { fn is_not_null(&self) -> bool; unsafe fn to_option(&self) -> Option<&T>; fn offset(&self, count: int) -> Self; + #[cfg(not(stage0))] + unsafe fn offset_inbounds(self, count: int) -> Self; } /// Extension methods for immutable pointers @@ -304,6 +306,14 @@ impl RawPtr for *T { /// Calculates the offset from a pointer. #[inline] fn offset(&self, count: int) -> *T { offset(*self, count) } + + /// Calculates the offset from a pointer. The offset *must* be in-bounds of + /// the object, or one-byte-past-the-end. + #[inline] + #[cfg(not(stage0))] + unsafe fn offset_inbounds(self, count: int) -> *T { + intrinsics::offset_inbounds(self, count) + } } /// Extension methods for mutable pointers @@ -336,6 +346,18 @@ impl RawPtr for *mut T { /// Calculates the offset from a mutable pointer. #[inline] fn offset(&self, count: int) -> *mut T { mut_offset(*self, count) } + + /// Calculates the offset from a pointer. The offset *must* be in-bounds of + /// the object, or one-byte-past-the-end. An arithmetic overflow is also + /// undefined behaviour. + /// + /// This method should be preferred over `offset` when the guarantee can be + /// satisfied, to enable better optimization. + #[inline] + #[cfg(not(stage0))] + unsafe fn offset_inbounds(self, count: int) -> *mut T { + intrinsics::offset_inbounds(self as *T, count) as *mut T + } } // Equality for pointers diff --git a/src/libstd/unstable/intrinsics.rs b/src/libstd/unstable/intrinsics.rs index 1270a80c354..c60edad3dbd 100644 --- a/src/libstd/unstable/intrinsics.rs +++ b/src/libstd/unstable/intrinsics.rs @@ -317,12 +317,21 @@ extern "rust-intrinsic" { /// Get the address of the `__morestack` stack growth function. pub fn morestack_addr() -> *(); - /// Adjust a pointer by an offset. + /// Calculates the offset from a pointer. /// /// This is implemented as an intrinsic to avoid converting to and from an /// integer, since the conversion would throw away aliasing information. pub fn offset(dst: *T, offset: int) -> *T; + /// Calculates the offset from a pointer. The offset *must* be in-bounds of + /// the object, or one-byte-past-the-end. An arithmetic overflow is also + /// undefined behaviour. + /// + /// This intrinsic should be preferred over `offset` when the guarantee can + /// be satisfied, to enable better optimization. + #[cfg(not(stage0))] + pub fn offset_inbounds(dst: *T, offset: int) -> *T; + /// Equivalent to the `llvm.memcpy.p0i8.0i8.i32` intrinsic, with a size of /// `count` * `size_of::()` and an alignment of `min_align_of::()` pub fn memcpy32(dst: *mut T, src: *T, count: u32); -- cgit 1.4.1-3-g733a5 From 55f3d04101c214a13f7d47fbdb140c5c1126c41b Mon Sep 17 00:00:00 2001 From: Daniel Micay Date: Tue, 6 Aug 2013 18:05:43 -0400 Subject: vec: use `offset_inbounds` for iterators This allows LLVM to optimize vector iterators to an `getelementptr` and `icmp` pair, instead of `getelementptr` and *two* comparisons. Code snippet: ~~~ fn foo(xs: &mut [f64]) { for x in xs.mut_iter() { *x += 10.0; } } ~~~ LLVM IR at stage0: ~~~ ; Function Attrs: noinline uwtable define void @"_ZN3foo17_68e1b25bca131dba7_0$x2e0E"({ i64, %tydesc*, i8*, i8*, i8 }* nocapture, { double*, i64 }* nocapture) #1 { "function top level": %2 = getelementptr inbounds { double*, i64 }* %1, i64 0, i32 0 %3 = load double** %2, align 8 %4 = getelementptr inbounds { double*, i64 }* %1, i64 0, i32 1 %5 = load i64* %4, align 8 %6 = ptrtoint double* %3 to i64 %7 = and i64 %5, -8 %8 = add i64 %7, %6 %9 = inttoptr i64 %8 to double* %10 = icmp eq double* %3, %9 %11 = icmp eq double* %3, null %or.cond6 = or i1 %10, %11 br i1 %or.cond6, label %match_case, label %match_else match_else: ; preds = %"function top level", %match_else %12 = phi double* [ %13, %match_else ], [ %3, %"function top level" ] %13 = getelementptr double* %12, i64 1 %14 = load double* %12, align 8 %15 = fadd double %14, 1.000000e+01 store double %15, double* %12, align 8 %16 = icmp eq double* %13, %9 %17 = icmp eq double* %13, null %or.cond = or i1 %16, %17 br i1 %or.cond, label %match_case, label %match_else match_case: ; preds = %match_else, %"function top level" ret void } ~~~ Optimized LLVM IR at stage1/stage2: ~~~ ; Function Attrs: noinline uwtable define void @"_ZN3foo17_68e1b25bca131dba7_0$x2e0E"({ i64, %tydesc*, i8*, i8*, i8 }* nocapture, { double*, i64 }* nocapture) #1 { "function top level": %2 = getelementptr inbounds { double*, i64 }* %1, i64 0, i32 0 %3 = load double** %2, align 8 %4 = getelementptr inbounds { double*, i64 }* %1, i64 0, i32 1 %5 = load i64* %4, align 8 %6 = lshr i64 %5, 3 %7 = getelementptr inbounds double* %3, i64 %6 %8 = icmp eq i64 %6, 0 %9 = icmp eq double* %3, null %or.cond6 = or i1 %8, %9 br i1 %or.cond6, label %match_case, label %match_else match_else: ; preds = %"function top level", %match_else %.sroa.0.0.in7 = phi double* [ %10, %match_else ], [ %3, %"function top level" ] %10 = getelementptr inbounds double* %.sroa.0.0.in7, i64 1 %11 = load double* %.sroa.0.0.in7, align 8 %12 = fadd double %11, 1.000000e+01 store double %12, double* %.sroa.0.0.in7, align 8 %13 = icmp eq double* %10, %7 br i1 %13, label %match_case, label %match_else match_case: ; preds = %match_else, %"function top level" ret void } ~~~ --- src/libstd/ptr.rs | 21 ++++++++++++++++++++- src/libstd/vec.rs | 8 ++++---- 2 files changed, 24 insertions(+), 5 deletions(-) (limited to 'src/libstd') diff --git a/src/libstd/ptr.rs b/src/libstd/ptr.rs index 98fb132672c..5a2bd0c4de9 100644 --- a/src/libstd/ptr.rs +++ b/src/libstd/ptr.rs @@ -272,7 +272,6 @@ pub trait RawPtr { fn is_not_null(&self) -> bool; unsafe fn to_option(&self) -> Option<&T>; fn offset(&self, count: int) -> Self; - #[cfg(not(stage0))] unsafe fn offset_inbounds(self, count: int) -> Self; } @@ -307,6 +306,14 @@ impl RawPtr for *T { #[inline] fn offset(&self, count: int) -> *T { offset(*self, count) } + /// Calculates the offset from a pointer. The offset *must* be in-bounds of + /// the object, or one-byte-past-the-end. + #[inline] + #[cfg(stage0)] + unsafe fn offset_inbounds(self, count: int) -> *T { + intrinsics::offset(self, count) + } + /// Calculates the offset from a pointer. The offset *must* be in-bounds of /// the object, or one-byte-past-the-end. #[inline] @@ -347,6 +354,18 @@ impl RawPtr for *mut T { #[inline] fn offset(&self, count: int) -> *mut T { mut_offset(*self, count) } + /// Calculates the offset from a pointer. The offset *must* be in-bounds of + /// the object, or one-byte-past-the-end. An arithmetic overflow is also + /// undefined behaviour. + /// + /// This method should be preferred over `offset` when the guarantee can be + /// satisfied, to enable better optimization. + #[inline] + #[cfg(stage0)] + unsafe fn offset_inbounds(self, count: int) -> *mut T { + intrinsics::offset(self as *T, count) as *mut T + } + /// Calculates the offset from a pointer. The offset *must* be in-bounds of /// the object, or one-byte-past-the-end. An arithmetic overflow is also /// undefined behaviour. diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs index 8dbfb3ec543..36201dc5e82 100644 --- a/src/libstd/vec.rs +++ b/src/libstd/vec.rs @@ -855,7 +855,7 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] { lifetime: cast::transmute(p)} } else { VecIterator{ptr: p, - end: p.offset(self.len() as int), + end: p.offset_inbounds(self.len() as int), lifetime: cast::transmute(p)} } } @@ -1837,7 +1837,7 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] { lifetime: cast::transmute(p)} } else { VecMutIterator{ptr: p, - end: p.offset(self.len() as int), + end: p.offset_inbounds(self.len() as int), lifetime: cast::transmute(p)} } } @@ -2193,7 +2193,7 @@ macro_rules! iterator { // same pointer. cast::transmute(self.ptr as uint + 1) } else { - self.ptr.offset(1) + self.ptr.offset_inbounds(1) }; Some(cast::transmute(old)) @@ -2225,7 +2225,7 @@ macro_rules! double_ended_iterator { // See above for why 'ptr.offset' isn't used cast::transmute(self.end as uint - 1) } else { - self.end.offset(-1) + self.end.offset_inbounds(-1) }; Some(cast::transmute(self.end)) } -- cgit 1.4.1-3-g733a5