Where is the implementation of `dividedReportingOverflow`?

I was just looking at SR–3535 / SR–5964 / SR–11865, about how both dividedReportingOverflow and remainderReportingOverflow will fail to compile if the division is statically known to overflow (eg. the divisor is 0, or both the divisor is -1 and the dividend is .min).

So I wanted to take a look at the implementation of those methods (which I presume boils down to directly calling a built-in intrinsic operation), however I am unable to locate them.

When I search the Swift repo for dividedReportingOverflow, there are results in 6 files: 4 are tests, then Integers.swift which only declares the protocol requirements, and IntegerTypes.swift.gyb which produces the documentation comments but does not seem to contain the implementations.

So…where I can I find the implementations of dividedReportingOverflow and remainderReportingOverflow?

It does not call an intrinsic that reports overflow: as the comment states, there are no LLVM primitives for checking overflow of division operations, so we check manually, and only if there's no division by zero does it call the ordinary intrinsics for division operations.

IntegerTypes.swift.gyb does contain the concrete implementation of all standard library fixed-width integer types: you have to scroll past the documentation. Just search "ReportingOverflow" in that file.

Unless I'm mistaken, there is nothing about the implementation in that file which can solve SR-5964. The correct constant folding of the existing implementation should give (0, true) (or whatever the appropriate value is) instead of attempting to divide, so it's a constant folding bug.

3 Likes

In case it helps, here's the de-gybbed implementation from an unsigned and a signed type:

extension UInt8 {
  @_transparent
  public func dividedReportingOverflow(
    by other: UInt8
  ) -> (partialValue: UInt8, overflow: Bool) {
    // No LLVM primitives for checking overflow of division operations, so we
    // check manually.
    if _slowPath(other == (0 as UInt8)) {
      return (partialValue: self, overflow: true)
    }

    let (newStorage, overflow) = (
      Builtin.udiv_Int8(self._value, other._value),
      false._value)
    return (
      partialValue: UInt8(newStorage),
      overflow: Bool(overflow))
  }
}

extension Int8 {
  @_transparent
  public func dividedReportingOverflow(
    by other: Int8
  ) -> (partialValue: Int8, overflow: Bool) {
    // No LLVM primitives for checking overflow of division operations, so we
    // check manually.
    if _slowPath(other == (0 as Int8)) {
      return (partialValue: self, overflow: true)
    }
    if _slowPath(self == Int8.min && other == (-1 as Int8)) {
      return (partialValue: self, overflow: true)
    }

    let (newStorage, overflow) = (
      Builtin.sdiv_Int8(self._value, other._value),
      false._value)
    return (
      partialValue: Int8(newStorage),
      overflow: Bool(overflow))
  }
}
2 Likes

Ah, thanks, I made the classic mistake of searching for the name of the method I wanted to find. How silly of me.

Hmm, I don’t understand this. The very first thing the implementation does is check:

if _slowPath(other == (0 as ${Self})) {
  return (partialValue: self, overflow: true)
}

How on earth does the compiler not simply inline this result when it sees a known-constant 0 as the argument?

1 Like

Yup.

2 Likes

All right, having considered this further, I think that arithmetic overflow should never be a compile-time error. The documentation is clear that operations like + and / will trap on overflow, and trapping is a runtime behavior.

Moreover, Swift has consistently upheld the principle that trapping is *safe*, which is why trapping arithmetic is used by default in the first place. Therefore, if the compiler finds an arithmetic overflow while constant-folding, it may substitute an unconditional trap instruction, but there should be no compilation error.

• • •

According to the changelog, this behavior (raising a compile-time error for arithmetic overflow) was added on 2013-10-16.

I think that was a mistake.

Looking at the list of arithmetic diagnostics, I’m pretty sure most of them should be removed entirely. Maybe a few should stay as warnings, but the point is that code which traps at runtime is totally fine and ordinary and expected.

If a programmer writes something that will trap at runtime, then that’s the behavior they should get: it ought to compile and run and trap, as expected.

Essentially, you're saying that 42 / 0 should be explicitly permitted as an esoteric spelling of fatalError: I really don't see what use case could be served by not informing the user of an unconditional trap when it's not explicitly spelled in code as such. What's the harm and what's the use case?

I'm also not sure I see much distinction between this and arguing, say, that notional copies of value type instances must always actually occur at runtime. The Swift compiler elides such behaviors pervasively; a different language may not, but the overall direction of Swift has been making things compiler evaluable as much as possible.

This is all still not addressing the real underlying issue of the bugs you're pointing out, which is that constant folding isn't producing the expected constant-folded result.

3 Likes

The use-case is three-fold:

First, pedagogically, 42 / 0 has a defined behavior, so a programmer should be able to observe that behavior by running it.

Second, a programmer may write code which simplifies to 42 / 0, but only when that code is unreachable.

For example:

func foo(_ n: Int) -> Int {
  if n < 10 {
    return 5
  } else {
    return 42 / n
  }
}

foo(0)

Third, as a principle, trapping is safe. The compiler should not prevent code from compiling simply because it will trap.

Of note, the code may do other things prior to trapping, and the language contract requires that the program must actually do those things before it crashes.

That is a good point. Does Swift actually produce an error in such a scenario as you illustrate above with foo(0)?

1 Like

I just rewrote the dividedReportingOverflow logic a little bit.

You'll need to actually flip the < to a > to make your example actually lead to a division by zero. I just tried this in Playgrounds and encounter a runtime error, not a compile-time error, so this is not an issue even with a reachable divide-by-zero in user code afaict. I certainly agree that, if it becomes an issue, then it needs to be addressed.

[Edit: I just re-read your post and see your point about unreachability: yes, that's basically a reformulated version of the constant folding bug involving dividedReportingOverflow, and it needs to be fixed, but the same issue does not seem to impact user code modeled after that function: in Playgrounds, I correctly get no error at all with your example as written.]

Again, the dividedReportingOverflow bug you mention is a problem with constant-folding that needs to be solved. But I don't evidence of how that translates into demonstrating a design problem here: in the general case, Swift doesn't seem to prohibit users from calling a function with a constant which causes an unconditional runtime trap but after performing other work that can't be elided. Again, I agree that if it did so, it should not.


As to your other points:

I don't buy this argument for the same reason, as I said, that it's not distinguishable from notional copies: Pedagogically, let x = y is a copy, so a programmer should be able to observe that behavior by running it: but no, Swift can elide such copies and does so pervasively.

See above, that is the point about the constant folding bug that needs to be solved for *ReportingOverflow that doesn't seem to apply to user-written code.

No, it should not, and it does not--when the trap is spelled fatalError. But I do think it's fine (even desirable) that the compiler should require all unconditional traps to be spelled obviously as such, not as a mathematical operation or some other function call.

See above, yes agree vigorously that Swift should not stop the user from writing such things.

1 Like

The constant-folding is correct. The code really does include a line equivalent to 42 / 0. The problem is that this produces a compile-time error, instead of simply substituting a trap instruction.

No, the constant-folding is incorrect. In dividedReportingOverflow, the actual division should never be reached with a denominator of 0, so how can it be correct to fold that into a compiler error?

1 Like

It is correct to fold it into a division by zero.

It is incorrect to turn division by zero into a compiler error.

I do not understand. When given a zero denominator, no division by anything should take place. Why would it be correct to fold it into a division by anything?

2 Likes

This line of argument is not productive. It doesn't matter what optimisation pass triggers the diagnostic, and the fact that an optimisation pass triggers the diagnostic is not the problem.

What is clear is that the compile error is wrong, and the reason it is wrong is that this is not an unconditional trap but a conditional one. The compiler should only emit a diagnostic for a statement that is provably going to trap at compile time if it can exhaustively prove that the statement will trap. The compiler cannot prove that here, and so it should remain silent.

2 Likes

Division by zero has a defined behavior in Swift: it is guaranteed to trap at runtime.

Specifically, my argument is this:

func foo(n: Int) -> Int {
    return n / 0  // Should fail to compile, will always trap.
}

func bar(n: Int) -> Int {
    if n % 2 == 0 {
        return n / 0 // Should fail to compile, will trap for all n that can enter this branch
    } else {
        return n / 2
    }
}

func baz(n: Int) -> Int {
    if n % 2 == 0 {
        return n + 1 / n // Must compile, will only trap for some inputs that enter this branch
    } else {
        return n / 2
    }
}

func boz(n: Int) -> Int {
    if n != 0 {
        return 5 / n  // Must compile, will never trap for any n that can enter this branch
    } else {
        return 5
    }
}

baz(0) // Iff baz's definition is available, should fail to compile as this will unconditionally trap.
boz(0) // Must compile, an example of the bug being discussed here

Agree; I thought that was what I expressed in my line of argumentation? If not, that is what I mean :)

2 Likes

Those examples should at most warn.

They should all compile, since they exercise defined behavior.

Terms of Service

Privacy Policy

Cookie Policy