Following the discussions in this PR and this previous thread, we wanted to raise this RFC to agree on the overflow semantics of Arith operations.
Background
The integers in Arith are represented (previously implicitly, but now the documentation mentions this too) by a two’s complement representation. In this representation overflows by design behave as a wraparound. In the existing transformations, this overflow semantics seems to be assumed implicitly (i.e. if overflows are to be something else, such as poison, then transformations would branch on these cases)
Observations
LLVM have optional poison semantics for overflows controlled by flags, and is another potential possibility for Arith’s overflow semantics.
However, existing lowering of Arith → LLVM lowers arith.addi to the wraparound version - implying the semantics for overflows is a wraparound in this pass.
Likewise, the other main lowering pass from Arith to SPIR-V also implies overflow semantics.
Discussion & Proposal
Wondering if there are any current use cases which adopt something other than wraparound semantics? If not, this RFC would propose to add the wraparound overflow semantics of addi, muli etc operations into the documentation.
Note that this RFC is limited to the arith dialect, in case this is not obvious based on the title of this thread.
I shared my analysis of the state of the arith dialect in the codebase in the comment linked above. In summary, it seems to me that wraparound is the current implicit semantics for arith ops arith.addi and arith.muli, because both lowering paths preserve it, we already have transforms that rely on it, and I’m not aware of code that actively tries to avoid creating ops that may overflow. If folks agree, the next step would be to document this behavior, no changes to the code necessary.
In my view the default semantics for integers should absolutely be the same as the default semantics in LLVM (which mirrors all modern processors, and also languages like Java): two’s complement wraparound.
In some situations, making signed or unsigned overflow undefined allows interesting optimizations, which is fine – but this must be opt-in, not the default.
+1 to defining overflow semantics and working on corresponding lowering paths.
Regarding lowering, I cannot find any mentions of nsw/nuw in current llvm dialect definition, not sure if they are actually supported in dialect.
For SPIR-V I’ve recently added NoSignedWrap/NoUnsignedWrap decorations [mlir][spirv] Add some op decorations by Hardcode84 · Pull Request #72809 · llvm/llvm-project · GitHub. but they are not being used anywhere upstream. Internally we have a pass which adds those on all relevant SPIR-V ops based on global flag.
It’d be nice to have nsw/nuw attributes as part of arith dialect, but I don’t have any concrete design proposal yet.
We’ve been fuzzing arith programs (with @regehr group) with the semantics you are currently proposing, and at least for canonicalization and lowerings to LLVM, using poison seems consistent with the implementation. The only “bug” I found was that if we keep the same semantics in arith.select as llvm.select, there is currently a canonicalization pattern that’s incorrect (it does this optimization Compiler Explorer).
I would recommend that following LLVM’s convention might be a good start, by adding just “no-wrap”, and add some docs/code to produce poison when overflow with “no-wrap” .
Because I guess most people are like me, just treating arith as a fancy proxy to LLVM, and it seems there is no explicit “wrap” in LLVM.
As for me, I tried to use some Saturation arithmetic overflow semantics in a toy project, so I guess it might be better to add something like an “ArithErrorInterface” to handle these things.
At the IR level, the question is slightly different. For example when you say that “overflow behavior is implementation defined”, you’re not making the HW more difficult to build. The question is somewhere about what guarantee you provide on the behavior vs how much freedom the optimizer gets (the usual question of “undefined behavior” as well).
(I’m not advocating against the proposal here)
I’d still really would like a path towards merging the two
More and more arith won’t justify itself.
To clarify, this is not implementation-defined or undefined in LLVM in the absence of nsw/nuw. LLVM’s lang ref is explicit about wrapping on overflow being the behavior add/sub/mul: LLVM Language Reference Manual — LLVM 18.0.0git documentation. I think what you are pointing out could be that there’s no ‘wrap’ keyword to indicate wrapping in LLVM, but this seems like more of a syntactic property to me since the semantics for these instructions very explicitly define wrapping.
This proposal would result in the same default being documented at the level of arith. And in the future, nothing stops from adding attributes or new ops for different behaviors like nsw/nuw or saturation. I’d like to avoid an all-or-nothing approach and document what the current semantics are before we branch out and start exploring possible future implementations.
To generalize this line of thinking, I think that we could say that the lowering chain has to result in refinement at each step, up until the hardware/runtime. It’s generally fine to make things more defined as we lower, but making the behavior less defined is not. Because the source language may leave overflow undefined/implementation defined, it may be useful to preserve it through the lowering chain, hoping some layers can exploit it and simplify the code.
This justifies having mechanisms like nsw/nuw in llvm, but I don’t see how leaving things implementation-defined in the middle of the lowering chain helps. For example, I wouldn’t want an ‘implementation-defined’ addition overflow that returns a non-deterministic result (even for the same pair of inputs). I’d rather have something with tighter semantics like poison that I can reason about. That’s why I see making overflow ‘implementation-defined’ a strictly worse option that any other set of semantics described.
You’re saying “non-deterministic”, I assume you mean “changing when upgrading the compiler or changing the HW”? (the definition of “implementation-defined” basically).
Other I don’t quite grasp on the source of non-determinism?
