argotorg / argotorg/solidity

Signed int256 addition optimization

Open
#15,283 2 comments 2 reactions 0 assignees View on GitHub
feature low effort medium impact optimizer selected for development
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.