Signed int256 addition optimization
- Dominant language
- C++
- Stars
- 25.7k
- Forks
- 6.2k
- Avg merge
- 2d 19h
- Merged PRs (30d)
- 29
Description
## Abstract
I think the current implementation of int256 addition overflow check is quite suboptimal. The optimizer seems not to be able to catch this possible optimization, probably because it's unaware of the bounds of the inputs.
## Motivation
The compiler seems to be outputting the following Yul equivalent when intending to add two signed integers `a` and `b` (thanks to [Dedaub](https://app.dedaub.com/decompile) for the decompiler):
```js
let res := add(b, a)
let check0 := slt(res, a)
let check1 := slt(b, 0x0)
let overflow := or(and(iszero(check1), check0), and(check1, iszero(check0)))
if overflow {
mstore(0x0, 0x4e487b7100000000000000000000000000000000000000000000000000000000)
mstore(0x4, 0x11)
revert(0x0, 0x24)
}
```
This is quite inefficient. Since `slt` returns 0 or 1, we can use `xor` instead of an `or`, two `and`s and two `iszero`s:
```js
let overflow := xor(check0, check1)
```
## Specification
Consider altering the following code in [`YulUtilFunctions.cpp#734-737`](https://github.com/ethereum/solidity/blob/81a05f37531766bc1fd325e96f6a97e41d95b65f/libsolidity/codegen/YulUtilFunctions.cpp#L734-L737):
```
if or(
and(iszero(slt(x, 0)), slt(sum, y)),
and(slt(x, 0), iszero(slt(sum, y)))
) { () }
```
into the following:
```
if xor(slt(x, 0), slt(sum, y)) { () }
```
## Backwards Compatibility
This is just a bytecode generation improvement. Should be fully backward compatible.
PS. I don't know the structure of the codebase very well, so I'm not comfortable writing a PR for this – this is why I'm raising this as an issue. Sorry for any additional effort needed due to this.
Contributor guide
Research direction
Start in libsolidity/codegen/YulUtilFunctions.cpp around lines 734-737 and inspect the signed addition overflow check shown in the issue. Verify that the proposed xor expression preserves the overflow behavior, then confirm the generated Yul or bytecode uses the simpler check without changing backward-compatible behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, solidity
- Domain
- blockchain, compilers
- Issue type
- Refactor
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 48/100