Use checked arithmetic by default

[brson]

There's a lot of concern that having +, -, and * overflow by default is incorrect - it's a source of many security vulnerabilities. Let's try changing the default to being checked and measure the impact on performance and code size.

There are some open questions:

• what happens on overflow? Probably fail!. It could also raise a condition, but having codegen raise conditions is a big step to take, and we're not sure we like conditions.
• how do you turn it off? Either with unchecked blocks, explicit methods, or additional types.

Nominating well defined.

[thestinger]

You can try using it via the checked arithmetic traits I implemented, and there's a huge overhead in terms of both performance and code size. LLVM is almost never capable of removing the checks, just like it rarely actually removes array bounds checks. It makes whole passes like loop and scalar vectorization useless.

Failing on overflow doesn't make the incorrect code any more correct, since a failure is still going to be a bug in 99% of programs. I feel strongly that the correct solution is to make integer literals not default to a signed fixed-size integer, and making generic literals work for big integers.

The most common integer type for application logic could be the one proposed in #8635.

[thestinger]

Here's an optimized IR comparison, to give an idea of the code generation when it can't eliminate the check. In these examples, it can't eliminate it because there are inputs to a function (it must inline deep enough to see the values or range of values, to have a hope of eliminating them):

fn foo(x: u32, y: u32) -> u32 {
    x + y
}

; Function Attrs: nounwind readnone uwtable
define i32 @_ZN3foo17h73f0a05a6ca431af4v0.0E({ i64, %tydesc*, i8*, i8*, i8 }* nocapture readnone, i32, i32) #2 {
"function top level":
  %3 = add i32 %2, %1
  ret i32 %3
}

Checked operation, calling fail on overflow:

fn bar(x: u32, y: u32) -> u32 {
    x.checked_add(&y).unwrap()
}

; Function Attrs: uwtable
define i32 @_ZN3bar17h73f0a05a6ca431av4v0.0E({ i64, %tydesc*, i8*, i8*, i8 }* nocapture readnone, i32, i32) #3 {
"function top level":
  %3 = alloca %str_slice, align 8
  %4 = alloca %str_slice, align 8
  %5 = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %1, i32 %2) #1
  %6 = extractvalue { i32, i1 } %5, 1
  br i1 %6, label %match_else.i, label %_ZN6option6Option6unwrap21h1283b974be2d27c1lBau4v0.0E.exit

match_else.i:                                     ; preds = %"function top level"
  %7 = bitcast %str_slice* %3 to i8*
  call void @llvm.lifetime.start(i64 16, i8* %7)
  %8 = bitcast %str_slice* %4 to i8*
  call void @llvm.lifetime.start(i64 16, i8* %8)
  %9 = getelementptr inbounds %str_slice* %3, i64 0, i32 0
  store i8* getelementptr inbounds ([44 x i8]* @str1262, i64 0, i64 0), i8** %9, align 8
  %10 = getelementptr inbounds %str_slice* %3, i64 0, i32 1
  store i64 43, i64* %10, align 8
  %11 = getelementptr inbounds %str_slice* %4, i64 0, i32 0
  store i8* getelementptr inbounds ([46 x i8]* @str1263, i64 0, i64 0), i8** %11, align 8
  %12 = getelementptr inbounds %str_slice* %4, i64 0, i32 1
  store i64 45, i64* %12, align 8
  call void @"_ZN3sys28FailWithCause$__extensions__9fail_with20hdb4c44d01ce41167qaF4v0.8E"({}* sret undef, { i64, %tydesc*, i8*, i8*, i8 }* undef, %str_slice* %3, %str_slice* %4, i64 323)
  unreachable

_ZN6option6Option6unwrap21h1283b974be2d27c1lBau4v0.0E.exit: ; preds = %"function top level"
  %13 = extractvalue { i32, i1 } %5, 0
  %14 = bitcast %str_slice* %3 to i8*
  call void @llvm.lifetime.start(i64 16, i8* %14)
  %15 = bitcast %str_slice* %4 to i8*
  call void @llvm.lifetime.start(i64 16, i8* %15)
  call void @llvm.lifetime.end(i64 16, i8* %14)
  call void @llvm.lifetime.end(i64 16, i8* %15)
  ret i32 %13
}

[thestinger]

Note that the function is also no longer marked readnone/nounwind so this bubbles up into the rest of the code and results in many more invoke instructions and landing pads being generated along with the call being viewed as impure.

[jfager]

I agree that if safety is the motivation using bigints by default makes more sense. Failing on overflow doesn't seem that much better than wrapping in day-to-day development. But it seems like using something like GMP is a better option than a rust impl - why fight that battle again?

I'd be disappointed if unchecked arithmetic required anything more than just specifying a fixed-width int type. I like Rust because it balances safety and control. Making unchecked arithmetic hard feels like it goes too far over to the safety side of the fence.

Fwiw this is the approach Haskell takes.

[thestinger]

I don't there should should be a default at all, just generic literals and the choice to use what's appropriate by not falling back to int. There are cases when you want a big integer, and others where you want a flexible type expanding to one only as necessary.

[pnkfelix]

cc me

[catamorphism]

Accepted for well-defined

[UtherII]

About how to turning checked arithmetic off, would it be possible to use unsafe block but allowing to make them more specific about unsafe operations.

For example something like:

    unsafe "int_overflow" {
        // integer overflows don't fail, others unsafe operations are still forbidden
    }
    unsafe "ffi", "raw_ptr"{
        // ffi and dereferencing raw pointers allowed, others unsafe operations are still forbidden
    }

[Thiez]

Overflow is not unsafe when you explicitly want it to occur, so I don't think it makes sense to wrap it in an 'unsafe' block.

Perhaps some new types that implement the arithmetic traits but perform checked arithmetic? Or a Checked<T> wrapper? We already have the Checked_<Op> traits defined on int.

[thestinger]

I think a type-based solution is best. Signed/unsigned integer types using the checked operations and expanding to a big integer on overflow would make sense. I don't think there's much benefit to a type throwing a failure on an overflow, because that's still going to be a bug in the application.

Something to note is that the checked operations aren't implemented in hardware on every architecture. We need to start using compiler-rt to provide cross-platform support. A notable example is the lack of 64-bit checked multiplication on i686.

[pnkfelix]

I am surprised by the statements that a fail-on-overflow is not much different from the semantic errors you get from modular-arithmetic wrapping; I think that a proper fail! on overflow is a very different development experience than an under- or overflowed value then propagating somewhere else in the application.

(But do not interpret the above as a vote against bigints; I do agree they make the most sense in a number of contexts, though I'm not yet sure how best to incorporate them.)

@thestinger what are your thoughts about how to handle underflow for an unsigned integer type? I assume you would want at least that to fail! ?

[thestinger]

@pnkfelix: Underflow would still expand to a big integer, I was thinking it might make sense performance-wise to have coverage over different ranges before expanding to a big integer. It's probably enough to just have a single type based on int using an enum.

I don't really see much point in having an unsigned big integer type like we have in extra and I can't find precedence for it in other languages/libraries.

[pnkfelix]

@thestinger Ah, I see. I had thought you had meant that an unsigned fixed-width uint would overflow to an unsigned big uint. But now I interpret your suggestion as saying that uint should over- and underflow to signed integer.

[thestinger]

@pnkfelix: I don't want to change the semantics of the built-in integers from what they are now, but rather introduce a new type expanding to a big integer when necessary. There isn't a need to have an unsigned version, it was a silly thought.

[jfager]

@pnkfelix It is a different developer experience (fail-fast vs. fail-mysteriously-at-some-point) and if those were the only two options with no other tradeoffs fail-fast would definitely be the preferable one. But they're both still runtime failures. For either approach, your code has to be aware of and prevent overflow conditions in order to not blow up.

@thestinger's suggestion seems to make way more sense. You write code blissfully ignoring overflow issues, and overflow issues never bite you. And if you want overflow or to not pay the cost of overflow checking, then you can just go back to using standard fixed-width integer types and accept the tradeoff.