rustc: implement arithmetic overflow checking

Adds overflow checking to integer addition, multiplication, and subtraction
when `-Z force-overflow-checks` is true, or if `--cfg ndebug` is not passed to
the compiler. On overflow, it panics with `arithmetic operation overflowed`.
Also adds `overflowing_add`, `overflowing_sub`, and `overflowing_mul`
intrinsics for doing unchecked arithmetic.

[breaking-change]

10 files changed, 203 insertions, 7 deletions

diff --git a/src/libcore/intrinsics.rs b/src/libcore/intrinsics.rs
index 1ca243134cc..ed129136091 100644
--- a/src/libcore/intrinsics.rs
+++ b/src/libcore/intrinsics.rs
@@ -546,3 +546,14 @@ extern "rust-intrinsic" {
     /// Performs checked `u64` multiplication.
     pub fn u64_mul_with_overflow(x: u64, y: u64) -> (u64, bool);
 }
+
+// SNAP 880fb89
+#[cfg(not(stage0))]
+extern "rust-intrinsic" {
+    /// Returns (a + b) mod 2^N, where N is the width of N in bits.
+    pub fn overflowing_add<T>(a: T, b: T) -> T;
+    /// Returns (a - b) mod 2^N, where N is the width of N in bits.
+    pub fn overflowing_sub<T>(a: T, b: T) -> T;
+    /// Returns (a * b) mod 2^N, where N is the width of N in bits.
+    pub fn overflowing_mul<T>(a: T, b: T) -> T;
+}
diff --git a/src/librustc/session/config.rs b/src/librustc/session/config.rs
index efcde8b2fa1..53c1f4e4a40 100644
--- a/src/librustc/session/config.rs
+++ b/src/librustc/session/config.rs
@@ -259,7 +259,6 @@ pub enum CrateType {
     CrateTypeStaticlib,
 }
 
-
 #[derive(Clone)]
 pub enum Passes {
     SomePasses(Vec<String>),
@@ -585,6 +584,8 @@ options! {DebuggingOptions, DebuggingSetter, basic_debugging_options,
           "Adds unstable command line options to rustc interface"),
     print_enum_sizes: bool = (false, parse_bool,
           "Print the size of enums and their variants"),
+    force_overflow_checks: Option<bool> = (None, parse_opt_bool,
+          "Force overflow checks on or off"),
 }
 
 pub fn default_lib_output() -> CrateType {
diff --git a/src/librustc_trans/trans/base.rs b/src/librustc_trans/trans/base.rs
index 7a6960d3790..149dad47654 100644
--- a/src/librustc_trans/trans/base.rs
+++ b/src/librustc_trans/trans/base.rs
@@ -3102,6 +3102,12 @@ pub fn trans_crate<'tcx>(analysis: ty::CrateAnalysis<'tcx>)
     let ty::CrateAnalysis { ty_cx: tcx, export_map, reachable, name, .. } = analysis;
     let krate = tcx.map.krate();
 
+    let check_overflow = if let Some(v) = tcx.sess.opts.debugging_opts.force_overflow_checks {
+        v
+    } else {
+        !attr::contains_name(&krate.config, "ndebug")
+    };
+
     // Before we touch LLVM, make sure that multithreading is enabled.
     unsafe {
         use std::sync::{Once, ONCE_INIT};
@@ -3129,7 +3135,8 @@ pub fn trans_crate<'tcx>(analysis: ty::CrateAnalysis<'tcx>)
                                              export_map,
                                              Sha256::new(),
                                              link_meta.clone(),
-                                             reachable);
+                                             reachable,
+                                             check_overflow);
 
     {
         let ccx = shared_ccx.get_ccx(0);
diff --git a/src/librustc_trans/trans/context.rs b/src/librustc_trans/trans/context.rs
index 3586a9dda20..9777398bddc 100644
--- a/src/librustc_trans/trans/context.rs
+++ b/src/librustc_trans/trans/context.rs
@@ -69,6 +69,7 @@ pub struct SharedCrateContext<'tcx> {
     symbol_hasher: RefCell<Sha256>,
     tcx: ty::ctxt<'tcx>,
     stats: Stats,
+    check_overflow: bool,
 
     available_monomorphizations: RefCell<FnvHashSet<String>>,
     available_drop_glues: RefCell<FnvHashMap<Ty<'tcx>, String>>,
@@ -245,7 +246,8 @@ impl<'tcx> SharedCrateContext<'tcx> {
                export_map: ExportMap,
                symbol_hasher: Sha256,
                link_meta: LinkMeta,
-               reachable: NodeSet)
+               reachable: NodeSet,
+               check_overflow: bool)
                -> SharedCrateContext<'tcx> {
         let (metadata_llcx, metadata_llmod) = unsafe {
             create_context_and_module(&tcx.sess, "metadata")
@@ -274,6 +276,7 @@ impl<'tcx> SharedCrateContext<'tcx> {
                 llvm_insns: RefCell::new(FnvHashMap()),
                 fn_stats: RefCell::new(Vec::new()),
             },
+            check_overflow: check_overflow,
             available_monomorphizations: RefCell::new(FnvHashSet()),
             available_drop_glues: RefCell::new(FnvHashMap()),
         };
@@ -743,6 +746,10 @@ impl<'b, 'tcx> CrateContext<'b, 'tcx> {
             &format!("the type `{}` is too big for the current architecture",
                     obj.repr(self.tcx())))
     }
+
+    pub fn check_overflow(&self) -> bool {
+        self.shared.check_overflow
+    }
 }
 
 fn declare_intrinsic(ccx: &CrateContext, key: & &'static str) -> Option<ValueRef> {
diff --git a/src/librustc_trans/trans/expr.rs b/src/librustc_trans/trans/expr.rs
index 27f9b9506a5..60455119d58 100644
--- a/src/librustc_trans/trans/expr.rs
+++ b/src/librustc_trans/trans/expr.rs
@@ -82,6 +82,7 @@ use trans::machine::{llsize_of, llsize_of_alloc};
 use trans::type_::Type;
 
 use syntax::{ast, ast_util, codemap};
+use syntax::parse::token::InternedString;
 use syntax::ptr::P;
 use syntax::parse::token;
 use std::iter::repeat;
@@ -1709,8 +1710,8 @@ fn trans_eager_binop<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
     };
     let is_float = ty::type_is_fp(intype);
     let is_signed = ty::type_is_signed(intype);
-
     let rhs = base::cast_shift_expr_rhs(bcx, op, lhs, rhs);
+    let info = expr_info(binop_expr);
 
     let binop_debug_loc = binop_expr.debug_loc();
 
@@ -1720,21 +1721,30 @@ fn trans_eager_binop<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
         if is_float {
             FAdd(bcx, lhs, rhs, binop_debug_loc)
         } else {
-            Add(bcx, lhs, rhs, binop_debug_loc)
+            let (newbcx, res) = with_overflow_check(
+                bcx, OverflowOp::Add, info, lhs_t, lhs, rhs, binop_debug_loc);
+            bcx = newbcx;
+            res
         }
       }
       ast::BiSub => {
         if is_float {
             FSub(bcx, lhs, rhs, binop_debug_loc)
         } else {
-            Sub(bcx, lhs, rhs, binop_debug_loc)
+            let (newbcx, res) = with_overflow_check(
+                bcx, OverflowOp::Sub, info, lhs_t, lhs, rhs, binop_debug_loc);
+            bcx = newbcx;
+            res
         }
       }
       ast::BiMul => {
         if is_float {
             FMul(bcx, lhs, rhs, binop_debug_loc)
         } else {
-            Mul(bcx, lhs, rhs, binop_debug_loc)
+            let (newbcx, res) = with_overflow_check(
+                bcx, OverflowOp::Mul, info, lhs_t, lhs, rhs, binop_debug_loc);
+            bcx = newbcx;
+            res
         }
       }
       ast::BiDiv => {
@@ -2314,3 +2324,110 @@ fn deref_once<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
         DatumBlock { bcx: bcx, datum: datum }
     }
 }
+
+enum OverflowOp {
+    Add,
+    Sub,
+    Mul,
+}
+
+impl OverflowOp {
+    fn to_intrinsic_name(&self, tcx: &ty::ctxt, ty: Ty) -> &'static str {
+        use syntax::ast::IntTy::*;
+        use syntax::ast::UintTy::*;
+        use middle::ty::{ty_int, ty_uint};
+
+        let new_sty = match ty.sty {
+            ty_int(TyIs(_)) => match &tcx.sess.target.target.target_pointer_width[..] {
+                "32" => ty_int(TyI32),
+                "64" => ty_int(TyI64),
+                _ => panic!("unsupported target word size")
+            },
+            ty_uint(TyUs(_)) => match &tcx.sess.target.target.target_pointer_width[..] {
+                "32" => ty_uint(TyU32),
+                "64" => ty_uint(TyU64),
+                _ => panic!("unsupported target word size")
+            },
+            ref t @ ty_uint(_) | ref t @ ty_int(_) => t.clone(),
+            _ => panic!("tried to get overflow intrinsic for non-int type")
+        };
+
+        match *self {
+            OverflowOp::Add => match new_sty {
+                ty_int(TyI8) => "llvm.sadd.with.overflow.i8",
+                ty_int(TyI16) => "llvm.sadd.with.overflow.i16",
+                ty_int(TyI32) => "llvm.sadd.with.overflow.i32",
+                ty_int(TyI64) => "llvm.sadd.with.overflow.i64",
+
+                ty_uint(TyU8) => "llvm.uadd.with.overflow.i8",
+                ty_uint(TyU16) => "llvm.uadd.with.overflow.i16",
+                ty_uint(TyU32) => "llvm.uadd.with.overflow.i32",
+                ty_uint(TyU64) => "llvm.uadd.with.overflow.i64",
+
+                _ => unreachable!(),
+            },
+            OverflowOp::Sub => match new_sty {
+                ty_int(TyI8) => "llvm.ssub.with.overflow.i8",
+                ty_int(TyI16) => "llvm.ssub.with.overflow.i16",
+                ty_int(TyI32) => "llvm.ssub.with.overflow.i32",
+                ty_int(TyI64) => "llvm.ssub.with.overflow.i64",
+
+                ty_uint(TyU8) => "llvm.usub.with.overflow.i8",
+                ty_uint(TyU16) => "llvm.usub.with.overflow.i16",
+                ty_uint(TyU32) => "llvm.usub.with.overflow.i32",
+                ty_uint(TyU64) => "llvm.usub.with.overflow.i64",
+
+                _ => unreachable!(),
+            },
+            OverflowOp::Mul => match new_sty {
+                ty_int(TyI8) => "llvm.smul.with.overflow.i8",
+                ty_int(TyI16) => "llvm.smul.with.overflow.i16",
+                ty_int(TyI32) => "llvm.smul.with.overflow.i32",
+                ty_int(TyI64) => "llvm.smul.with.overflow.i64",
+
+                ty_uint(TyU8) => "llvm.umul.with.overflow.i8",
+                ty_uint(TyU16) => "llvm.umul.with.overflow.i16",
+                ty_uint(TyU32) => "llvm.umul.with.overflow.i32",
+                ty_uint(TyU64) => "llvm.umul.with.overflow.i64",
+
+                _ => unreachable!(),
+            },
+        }
+    }
+}
+
+
+fn with_overflow_check<'a, 'b>(bcx: Block<'a, 'b>, oop: OverflowOp, info: NodeIdAndSpan,
+                               lhs_t: Ty, lhs: ValueRef, rhs: ValueRef, binop_debug_loc: DebugLoc)
+                               -> (Block<'a, 'b>, ValueRef) {
+    if bcx.unreachable.get() { return (bcx, _Undef(lhs)); }
+    if bcx.ccx().check_overflow() {
+        let name = oop.to_intrinsic_name(bcx.tcx(), lhs_t);
+        let llfn = bcx.ccx().get_intrinsic(&name);
+
+        let val = Call(bcx, llfn, &[lhs, rhs], None, binop_debug_loc);
+        let result = ExtractValue(bcx, val, 0); // iN operation result
+        let overflow = ExtractValue(bcx, val, 1); // i1 "did it overflow?"
+
+        let cond = ICmp(bcx, llvm::IntEQ, overflow, C_integral(Type::i1(bcx.ccx()), 1, false),
+                        binop_debug_loc);
+
+        let expect = bcx.ccx().get_intrinsic(&"llvm.expect.i1");
+        Call(bcx, expect, &[cond, C_integral(Type::i1(bcx.ccx()), 0, false)],
+             None, binop_debug_loc);
+
+        let bcx =
+            base::with_cond(bcx, cond, |bcx|
+                controlflow::trans_fail(bcx, info,
+                    InternedString::new("arithmetic operation overflowed")));
+
+        (bcx, result)
+    } else {
+        let res = match oop {
+            OverflowOp::Add => Add(bcx, lhs, rhs, binop_debug_loc),
+            OverflowOp::Sub => Sub(bcx, lhs, rhs, binop_debug_loc),
+            OverflowOp::Mul => Mul(bcx, lhs, rhs, binop_debug_loc),
+        };
+        (bcx, res)
+    }
+}
diff --git a/src/librustc_trans/trans/intrinsic.rs b/src/librustc_trans/trans/intrinsic.rs
index 54644c92869..916492195c2 100644
--- a/src/librustc_trans/trans/intrinsic.rs
+++ b/src/librustc_trans/trans/intrinsic.rs
@@ -660,6 +660,11 @@ pub fn trans_intrinsic_call<'a, 'blk, 'tcx>(mut bcx: Block<'blk, 'tcx>,
                                     llargs[0],
                                     llargs[1],
                                     call_debug_location),
+
+        (_, "overflowing_add") => Add(bcx, llargs[0], llargs[1], call_debug_location),
+        (_, "overflowing_sub") => Sub(bcx, llargs[0], llargs[1], call_debug_location),
+        (_, "overflowing_mul") => Mul(bcx, llargs[0], llargs[1], call_debug_location),
+
         (_, "return_address") => {
             if !fcx.caller_expects_out_pointer {
                 tcx.sess.span_err(call_info.span,
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index cd72fd85cb7..273aadc383c 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -5491,6 +5491,9 @@ pub fn check_intrinsic_type(ccx: &CrateCtxt, it: &ast::ForeignItem) {
                 (0, vec!(tcx.types.u64, tcx.types.u64),
                 ty::mk_tup(tcx, vec!(tcx.types.u64, tcx.types.bool))),
 
+            "overflowing_add" | "overflowing_sub" | "overflowing_mul" =>
+                (1, vec![param(ccx, 0), param(ccx, 0)], param(ccx, 0)),
+
             "return_address" => (0, vec![], ty::mk_imm_ptr(tcx, tcx.types.u8)),
 
             "assume" => (0, vec![tcx.types.bool], ty::mk_nil(tcx)),
diff --git a/src/test/run-fail/overflowing-add.rs b/src/test/run-fail/overflowing-add.rs
new file mode 100644
index 00000000000..c3e41110d20
--- /dev/null
+++ b/src/test/run-fail/overflowing-add.rs
@@ -0,0 +1,15 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// error-pattern:thread '<main>' panicked at 'arithmatic operation overflowed'
+
+fn main() {
+    let x = 200u8 + 200u8 + 200u8;
+}
diff --git a/src/test/run-fail/overflowing-mul.rs b/src/test/run-fail/overflowing-mul.rs
new file mode 100644
index 00000000000..bf7a9d07586
--- /dev/null
+++ b/src/test/run-fail/overflowing-mul.rs
@@ -0,0 +1,15 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// error-pattern:thread '<main>' panicked at 'arithmatic operation overflowed'
+
+fn main() {
+    let x = 200u8 + 4u8;
+}
diff --git a/src/test/run-fail/overflowing-sub.rs b/src/test/run-fail/overflowing-sub.rs
new file mode 100644
index 00000000000..961b36d322c
--- /dev/null
+++ b/src/test/run-fail/overflowing-sub.rs
@@ -0,0 +1,15 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// error-pattern:thread '<main>' panicked at 'arithmatic operation overflowed'
+
+fn main() {
+    let x = 42u8 - 43u8;
+}