solidity icon indicating copy to clipboard operation
solidity copied to clipboard

Check overflow after multiplication operation is executed.

Open matheusaaguiar opened this issue 2 years ago • 27 comments

Changes overflow/underflow checks to be performed after multiplication operation is executed as discussed in #12814 .

matheusaaguiar avatar Jun 20 '22 22:06 matheusaaguiar

Gas benchmarks for external tests ** OUTDATED **

IR-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.03% 0% 0%
brink 0%
chainlink -0.05% -0.05% -0%
colony -0.01%
elementfi +0%
ens 0% -0% 0%
euler -0.04% -0.03% -0.33%
gnosis -0.06% +0% +0%
gp2 +0% +0% +0%
perpetual-pools -0.01% -0.01% -0.03%
pool-together -0% -0.01% -0%
prb-math 0% 0% 0%
trident -0.04% -0.16% +0.07%
uniswap -0.36% -0.33% -0.22%
yield_liquidator +0% +0% -0.01%
zeppelin +0% +0% +0%
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.01%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

LEGACY-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0%
colony -0%
elementfi 0%
ens 0%
euler -0.02% -0.02% -0.21%
gnosis 0% -0% 0%
gp2 0%
perpetual-pools 0% -0% +0%
pool-together -0% -0% -0%
prb-math 0% 0% 0%
trident -0% -0% -0%
uniswap -0.16% -0.16% -0.13%
yield_liquidator -0% -0% -0%
zeppelin 0% +0% +0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.02% 0% 0%
brink 0%
chainlink -0.02% -0.01% +0.01%
colony -0.01%
elementfi -0.01%
ens 0% +0% 0%
euler -0.08% -0.05% -0.36%
gnosis -0.01% -0.01% +0.01%
gp2 -0.02% -0.02% +0%
perpetual-pools -0% -0% -0%
pool-together -0% -0% +0%
prb-math 0% -0% 0%
trident -0.01% -0.01% +0.07%
uniswap -0.43% -0.4% -0.23%
yield_liquidator -0.03% -0.04% -0%
zeppelin -0.02% -0.02% +0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.02% -0.02% +0%
colony -0.01%
elementfi -0.01%
ens 0% 0% 0%
euler -0.09% -0.06% -0.41%
gnosis -0.02% -0.01% +0%
gp2 -0.02% -0.02% +0%
perpetual-pools -0.01% -0.01% +0.02%
pool-together -0.05% -0.06% -0%
prb-math 0% -0% 0%
trident -0.03% -0.03% +0.06%
uniswap -0.42% -0.38% -0.2%
yield_liquidator -0.04% -0.05% -0%
zeppelin -0.01% -0.01% +0%
------------------ --------------- ---------------- ------------

matheusaaguiar avatar Jun 21 '22 12:06 matheusaaguiar

I'm a bit worried that this does not improve gas costs. It is understandable since we do not really change much for types larger than 128 bits. The SafeMath library uses division to check on uint256 - maybe we could try that?

https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/math/SafeMath.sol#L47

chriseth avatar Jul 01 '22 12:07 chriseth

Benchmarks for commit f71e542 (different checks for less than or equal int128)

IR-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.04% 0% 0%
brink 0%
chainlink -0.1% -0.1% -0%
colony -0.01%
elementfi -0.01%
ens 0% 0% 0%
euler -0.13% -0.1% -0.58%
gnosis -0.08% 0% +0%
gp2 +0% +0% +0%
perpetual-pools 0% +0% -0.01%
pool-together -0% -0.01% -0%
prb-math 0% -0% 0%
trident +0.03% +0.01% +0.08%
uniswap -1.26% -1.64% -0.82%
yield_liquidator +0% +0% -0%
zeppelin 0% 0% -0%
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.01%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

LEGACY-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0%
colony -0%
elementfi 0%
ens 0%
euler -0.08% -0.04% -0.66%
gnosis 0% 0% +0%
gp2 0%
perpetual-pools 0% +0% +0.01%
pool-together -0% -0% -0%
prb-math 0% -0% 0%
trident -0% -0% +0%
uniswap -0.54% -0.5% -0.34%
yield_liquidator -0% -0% -0%
zeppelin 0% +0% +0.05%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.03% 0% 0%
brink 0%
chainlink -0.03% -0.03% +0%
colony -0.01%
elementfi -0.02%
ens 0% +0% 0%
euler -0.13% -0.08% -0.64%
gnosis -0.01% -0.01% +0.01%
gp2 -0.02% -0.02% +0%
perpetual-pools -0.01% -0.01% -0%
pool-together -0.02% -0.02% +0%
prb-math 0% -0% 0%
trident -0.03% -0.03% +0.07%
uniswap -0.78% -0.76% -0.42%
yield_liquidator -0.04% -0.05% -0%
zeppelin -0.01% -0.01% +0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.02% -0.02% +0%
colony -0.01%
elementfi -0.01%
ens 0% -0% 0%
euler -0.12% -0.08% -0.62%
gnosis -0.02% -0.01% +0.01%
gp2 -0.02% -0.02% +0%
perpetual-pools -0.01% -0.01% +0.01%
pool-together -0.05% -0.06% -0%
prb-math 0% -0% 0%
trident -0.03% -0.03% +0.06%
uniswap -0.65% -0.59% -0.35%
yield_liquidator -0.04% -0.05% -0%
zeppelin -0.01% -0.01% +0%
------------------ --------------- ---------------- ------------

matheusaaguiar avatar Jul 04 '22 20:07 matheusaaguiar

I'm a bit worried that this does not improve gas costs. It is understandable since we do not really change much for types larger than 128 bits. The SafeMath library uses division to check on uint256 - maybe we could try that?

https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/math/SafeMath.sol#L47

@matheusaaguiar Don't you want to try this?

wechman avatar Jul 08 '22 06:07 wechman

@wechman I tried that, but it only works for uint256bit. I was testing this approach yesterday to get benchmarks, but the proof is not passing and I am not sure if it has to do with the actual logic. I am going to look closer at it and try to fix.

matheusaaguiar avatar Jul 08 '22 12:07 matheusaaguiar

Benchmarks for commit (Added special case for uint256)

IR-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.06%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.13% 0% 0%
brink 0%
chainlink -0.26% -0.29% -0.01%
colony -0.02%
elementfi -0.1%
ens 0% -0% 0%
euler -0.25% -0.22% -0.58%
gnosis -0.11% -0.03% +0%
gp2 -0.03% -0.03% -0%
perpetual-pools -0.02% -0.02% -0.01%
pool-together +0.03% +0.02% -0%
prb-math 0% 0% 0%
trident -0.07% -0.04% -0.13%
uniswap -1.2% -1.57% -0.73%
yield_liquidator -0% +0% -0%
zeppelin -0.01% -0% +0%
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.02%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

LEGACY-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.13%
colony -0.06%
elementfi -0.09%
ens 0%
euler -0.24% -0.18% -0.66%
gnosis -0.09% -0.1% +0%
gp2 -0.13%
perpetual-pools -0.06% -0.07% +0.01%
pool-together -0.06% -0.06% -0%
prb-math 0% 0% 0%
trident -0.14% -0.1% -0.1%
uniswap -0.64% -0.56% -0.4%
yield_liquidator -0.15% -0.17% -0%
zeppelin -0.06% -0.06% +0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.04% 0% 0%
brink 0%
chainlink -0.04% -0.04% -0%
colony -0.02%
elementfi -0.03%
ens 0% +0% 0%
euler -0.15% -0.1% -0.64%
gnosis -0.03% -0.03% +0%
gp2 -0.04% -0.04% +0%
perpetual-pools -0.02% -0.02% -0.01%
pool-together -0.03% -0.03% +0%
prb-math 0% 0% 0%
trident -0.04% -0.04% +0.03%
uniswap -0.79% -0.76% -0.44%
yield_liquidator -0.06% -0.07% -0%
zeppelin -0.02% -0.02% +0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.04% -0.04% -0%
colony -0.02%
elementfi -0.02%
ens 0% 0% 0%
euler -0.14% -0.09% -0.63%
gnosis -0.03% -0.02% +0.01%
gp2 -0.03% -0.03% +0%
perpetual-pools -0.02% -0.02% +0%
pool-together -0.06% -0.07% -0%
prb-math 0% -0% 0%
trident -0.04% -0.03% +0.03%
uniswap -0.66% -0.59% -0.37%
yield_liquidator -0.06% -0.07% -0.01%
zeppelin -0.01% -0.02% +0%
------------------ --------------- ---------------- ------------

matheusaaguiar avatar Jul 08 '22 13:07 matheusaaguiar

Looking at the failed test I guess that z3 solver is having trouble proving the rules for 16 bit.

matheusaaguiar avatar Jul 08 '22 18:07 matheusaaguiar

@wechman I tried that, but it only works for uint256bit. I was testing this approach yesterday to get benchmarks, but the proof is not passing and I am not sure if it has to do with the actual logic. I am going to look closer at it and try to fix.

@matheusaaguiar I think you need to use a bitmask on a multiplication product to get the algorithm working. E.g. for uint8: uint256 c = (a * b) & 0xff;

wechman avatar Jul 11 '22 05:07 wechman

Updated Benchmarks

IR-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony +0.01%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.12% 0% 0%
brink 0%
chainlink -0.27% -0.31% -0.01%
colony -0.02%
elementfi -0.1%
ens 0% -0% 0%
euler -0.25% -0.22% -0.58%
gnosis -0.11% -0.03% +0%
gp2 -0.03% -0.03% -0%
perpetual-pools +0.01% +0.01% +0%
pool-together +0.02% +0.01% +0%
prb-math 0% 0% 0%
trident -0.48% -0.2% -0.13%
uniswap -1.19% -1.56% -0.73%
yield_liquidator -0.15% -0.19% +0%
zeppelin -0.01% -0% +0%
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.02%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

LEGACY-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink +0.01%
colony +0.01%
elementfi +0.01%
ens 0%
euler -0.06% -0.03% -0.65%
gnosis +0.01% +0.01% +0%
gp2 +0.01%
perpetual-pools +0.01% +0.01% +0%
pool-together +0.01% +0.01% +0%
prb-math 0% 0% 0%
trident +0.01% +0.01% +0.06%
uniswap -0.53% -0.5% -0.31%
yield_liquidator +0.02% +0.02% +0%
zeppelin +0.01% +0.01% +0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.02% 0% 0%
brink 0%
chainlink -0.03% -0.02% -0%
colony -0.02%
elementfi -0.03%
ens 0% -0% 0%
euler -0.15% -0.1% -0.64%
gnosis -0.03% -0.03% +0%
gp2 -0.04% -0.04% +0%
perpetual-pools -0.02% -0.02% +0%
pool-together +0% +0% +0.01%
prb-math 0% 0% 0%
trident -0.03% -0.02% +0.03%
uniswap -0.79% -0.76% -0.44%
yield_liquidator -0.04% -0.04% +0.01%
zeppelin -0.02% -0.02% +0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.03% -0.03% -0%
colony -0.02%
elementfi -0.02%
ens 0% 0% 0%
euler -0.14% -0.09% -0.63%
gnosis -0.03% -0.02% +0%
gp2 -0.03% -0.03% +0%
perpetual-pools -0.02% -0.02% -0%
pool-together -0.04% -0.05% -0%
prb-math 0% 0% 0%
trident -0.04% -0.03% +0.03%
uniswap -0.66% -0.59% -0.37%
yield_liquidator -0.05% -0.06% +0%
zeppelin -0.01% -0.01% +0%
------------------ --------------- ---------------- ------------

matheusaaguiar avatar Jul 12 '22 12:07 matheusaaguiar

@wechman I tried that, but it only works for uint256bit. I was testing this approach yesterday to get benchmarks, but the proof is not passing and I am not sure if it has to do with the actual logic. I am going to look closer at it and try to fix.

@matheusaaguiar I think you need to use a bitmask on a multiplication product to get the algorithm working. E.g. for uint8: uint256 c = (a * b) & 0xff;

Thanks @wechman! This was the missing part indeed.

matheusaaguiar avatar Jul 12 '22 19:07 matheusaaguiar

I wonder whether we want to update signed numbers section too. Seems, newly suggested approach to check overflow works properly with them (at least all isol tests pass):

<?signed>
	<?gt128bit>
		if and(iszero(iszero(x)), iszero(eq(y, sdiv(and(product, <bitMask>), x)))) { <panic>() }
	<!gt128bit>
		if or(sgt(product, <maxValue>), slt(product, <minValue>)) { <panic>() }
	</gt128bit>
<!signed>
	// overflow, if x != 0 and y != product/x
	if and(iszero(iszero(x)), iszero(eq(y, div(and(product, <bitMask>), x)))) { <panic>() }
</signed>

Also, I guess it is still possible to get rid of differentiation between numbers greater and smaller than 128 bits.

wechman avatar Jul 13 '22 12:07 wechman

Yes. I am testing this approach with signed int too. I am checking if numbers between 128bit and 256bit are going to be properly covered, but I think it should be fine.

matheusaaguiar avatar Jul 13 '22 12:07 matheusaaguiar

I think the problem is that, for signed int, when we do product = (x*y) & bitmask, the MSB (sign bit) gets turned off. This is a problem for negative numbers and I guess positive too. For example, if type has 4 bits and 8 bits is maximum size:

0000 0010	(X = 2)
1111 1111	(Y = -1)
1111 1110	(P = -2)
0000 1111	(M)
0000 1110	(P & M = 14)  Overflow detected  incorrectly 

Also, p = -1 * minValue = minValue (overflow), so when we test minValue == minValue / -1, there's another overflow in the division which produces minValue == minValue.

More examples:

0000 0101	(X = 5)
1111 1110	(Y = -2)
1111 0110	(P = -10)
0000 1111	(M)
0000 0110	(P & M = 6) Overflow detected correctly

0000 0011	(X = 3)
0000 0100	(Y = 4)
0000 1100	(P = 12)
0000 1111	(M)
0000 1110	(P & M = 12) Overflow NOT detected

1111 1101	(X = -3)
1111 1101	(Y = -3)
0000 1001	(P = 9)
0000 1111	(M)
0000 1001	(P & M = 9) Overflow NOT detected

1111 1110	(X = -2)
1111 1000	(Y = -8)
0001 0000	(P = 16)
0000 1111	(M)
0000 0000	(P & M = 0) Overflow detected correctly 

matheusaaguiar avatar Jul 14 '22 15:07 matheusaaguiar

The solution I came up with detects what is the value of the MSB (inside the type range) and then apply the bitMask accordingly. If the sign bit is 0, then we have an and(product, <bitMask>) operation to turn off the out of range bits. If the sign bit is 1, then we have an or(product, not(<bitMask>) operation to turn on the out of range bits. Example: (type = 4 bits, 8 bits max)

0000 0010	(X = 2)
1111 1111	(Y = -1)
1111 1110	(P = -2)
1111 0000	(M)	--> sign bit was on 
1111 1110	(P | M = -2) Overflow not detected

0000 0011	(X = 3)
0000 0100	(Y = 4)
0000 1100	(P = 12)
1111 0000	(M)	--> sign bit was on 
1111 1100	(P | M = -4) Overflow detected as it should

matheusaaguiar avatar Jul 14 '22 22:07 matheusaaguiar

Sounds good! I'm curious about the gas improvement with this solution.

wechman avatar Jul 15 '22 09:07 wechman

Click for Gas Benchmark

IR-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.01%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.12% 0% 0%
brink 0%
chainlink -0.29% -0.33% -0.01%
colony -0.06%
elementfi -1.36%
ens 0% 0% 0%
euler -0.19% -0.19% -0.23%
gnosis -0.11% -0.03% +0%
gp2 -0.03% -0.03% -0%
perpetual-pools -0.03% -0.03% -0%
pool-together +0.02% +0.01% +0%
prb-math 0% -0% 0%
trident -0.48% -0.2% -0.13%
uniswap -1.23% -1.63% -0.83%
yield_liquidator -0.15% -0.19% +0%
zeppelin !V !V !V
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.05%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

LEGACY-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink +0%
colony -0.01%
elementfi -0.09%
ens 0%
euler -0.04% -0.02% -0.49%
gnosis +0.01% +0.01% +0.01%
gp2 +0.01%
perpetual-pools -0.01% -0.01% -0.02%
pool-together +0.01% +0.01% +0%
prb-math 0% +0% 0%
trident +0.01% +0.01% +0.06%
uniswap -0.55% -0.52% -0.34%
yield_liquidator +0.02% +0.02% +0%
zeppelin !V !V !V
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.02% 0% 0%
brink 0%
chainlink -0.05% -0.05% -0%
colony -0.06%
elementfi -0.28%
ens 0% 0% 0%
euler -0.09% -0.06% -0.26%
gnosis -0.03% -0.03% +0%
gp2 -0.04% -0.04% +0%
perpetual-pools -0.05% -0.06% -0.01%
pool-together +0% +0% +0.01%
prb-math 0% 0% 0%
trident -0.03% -0.02% +0.03%
uniswap -0.63% -0.58% -0.46%
yield_liquidator -0.04% -0.04% +0.01%
zeppelin !V !V !V
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.06% -0.06% -0%
colony -0.05%
elementfi -0.23%
ens 0% 0% 0%
euler -0.1% -0.06% -0.35%
gnosis -0.03% -0.02% +0.01%
gp2 -0.03% -0.03% +0%
perpetual-pools -0.05% -0.05% -0%
pool-together -0.04% -0.05% -0%
prb-math 0% -0% 0%
trident -0.04% -0.03% +0.03%
uniswap -0.57% -0.51% -0.39%
yield_liquidator -0.05% -0.06% +0%
zeppelin !V !V !V
------------------ --------------- ---------------- ------------

matheusaaguiar avatar Jul 15 '22 19:07 matheusaaguiar

Click for Gas Benchmark

IR-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony +0%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.12% 0% 0%
brink 0%
chainlink -0.29% -0.34% -0.01%
colony -0.05%
elementfi -0.79%
ens 0% +0% 0%
euler -0.17% -0.18% -0.1%
gnosis -0.11% -0.03% +0%
gp2 -0.03% -0.03% -0%
perpetual-pools -0.02% -0.02% -0.02%
pool-together +0.02% +0.01% +0%
prb-math 0% -0% 0%
trident -0.48% -0.2% -0.13%
uniswap -1.12% -1.52% -0.32%
yield_liquidator -0.15% -0.19% +0%
zeppelin -0.02% -0.02% -0.03%
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.05%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

LEGACY-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink +0.01%
colony +0%
elementfi -0.02%
ens 0%
euler -0.02% -0.01% -0.3%
gnosis +0.01% +0.01% +0.01%
gp2 +0.01%
perpetual-pools +0% +0% -0.01%
pool-together +0.01% +0.01% +0%
prb-math 0% 0% 0%
trident +0.01% +0.01% +0.06%
uniswap -0.3% -0.29% -0.17%
yield_liquidator +0.02% +0.02% +0%
zeppelin +0% +0% -0.03%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.02% 0% 0%
brink 0%
chainlink -0.05% -0.05% -0%
colony -0.05%
elementfi -0.21%
ens 0% 0% 0%
euler -0.08% -0.05% -0.17%
gnosis -0.03% -0.03% +0%
gp2 -0.04% -0.04% +0%
perpetual-pools -0.05% -0.05% -0.02%
pool-together +0% +0% +0.01%
prb-math 0% -0% 0%
trident -0.03% -0.02% +0.03%
uniswap -0.49% -0.44% -0.34%
yield_liquidator -0.04% -0.04% +0.01%
zeppelin -0.03% -0.03% +0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.06% -0.06% -0%
colony -0.05%
elementfi -0.22%
ens 0% +0% 0%
euler -0.09% -0.06% -0.27%
gnosis -0.03% -0.02% +0%
gp2 -0.03% -0.03% +0%
perpetual-pools -0.05% -0.05% -0%
pool-together -0.04% -0.05% -0%
prb-math 0% +0% 0%
trident -0.04% -0.03% +0.03%
uniswap -0.51% -0.45% -0.34%
yield_liquidator -0.05% -0.06% -0%
zeppelin -0.02% -0.03% +0%
------------------ --------------- ---------------- ------------

matheusaaguiar avatar Jul 28 '22 20:07 matheusaaguiar

Click for Gas Benchmark

IR-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.04%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.12% 0% 0%
brink 0%
chainlink -0.29% -0.34% -0.01%
colony -0.06%
elementfi -2.21%
ens 0% +0% 0%
euler -0.21% -0.2% -0.35%
gnosis -0.11% -0.03% +0%
gp2 -0.03% -0.03% -0%
perpetual-pools -0.03% -0.03% -0.02%
pool-together +0.02% +0.01% +0%
prb-math 0% -0% 0%
trident -0.48% -0.2% -0.13%
uniswap -1.31% -1.7% -0.9%
yield_liquidator -0.15% -0.19% +0%
zeppelin -0.02% -0.02% -0.03%
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.06%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

LEGACY-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.01%
colony -0.04%
elementfi -0.3%
ens 0%
euler -0.05% -0.03% -0.58%
gnosis +0.01% +0.01% +0.01%
gp2 +0.01%
perpetual-pools -0.04% -0.04% -0.02%
pool-together +0.01% +0.01% +0%
prb-math 0% +0% 0%
trident +0.01% +0.01% +0.06%
uniswap -0.84% -0.79% -0.62%
yield_liquidator +0.02% +0.02% +0%
zeppelin -0.01% -0.01% +0.02%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.02% 0% 0%
brink 0%
chainlink -0.05% -0.06% -0%
colony -0.06%
elementfi -0.29%
ens 0% 0% 0%
euler -0.11% -0.07% -0.39%
gnosis -0.03% -0.03% +0%
gp2 -0.04% -0.04% +0%
perpetual-pools -0.06% -0.06% -0.04%
pool-together +0% +0% +0.01%
prb-math 0% 0% 0%
trident -0.03% -0.02% +0.03%
uniswap -0.77% -0.75% -0.52%
yield_liquidator -0.04% -0.04% +0.01%
zeppelin -0.03% -0.03% +0.05%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.06% -0.06% -0%
colony -0.06%
elementfi -0.27%
ens 0% -0% 0%
euler -0.11% -0.07% -0.43%
gnosis -0.03% -0.02% +0%
gp2 -0.03% -0.03% +0%
perpetual-pools -0.06% -0.06% -0.03%
pool-together -0.04% -0.05% -0%
prb-math 0% +0% 0%
trident -0.04% -0.03% +0.03%
uniswap -0.75% -0.67% -0.51%
yield_liquidator -0.05% -0.06% +0%
zeppelin -0.03% -0.03% +0%
------------------ --------------- ---------------- ------------

matheusaaguiar avatar Jul 28 '22 22:07 matheusaaguiar

Fixed a missing indentation in the code.

matheusaaguiar avatar Jul 29 '22 17:07 matheusaaguiar

Changed long decimal numbers for hex notation in test cases.

matheusaaguiar avatar Jul 29 '22 18:07 matheusaaguiar

Sorry about that, I will keep that in mind for future reviews.

matheusaaguiar avatar Aug 01 '22 12:08 matheusaaguiar

@chriseth I implemented your suggestion of using cleanupFunction. Formal tests still need to be changed to properly reflect the simplification achieved, but since the previous code was doing the same job as cleanupFunction, using bit operations directly in the Yul code, I think that the end result should be same for those tests.

matheusaaguiar avatar Aug 03 '22 00:08 matheusaaguiar

Gas Benchmark

IR-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.1%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps +0.04% 0% 0%
brink 0%
chainlink -0.25% -0.28% -0.02%
colony -0.07%
elementfi -1.98%
ens 0% -0% 0%
euler -0.22% -0.23% -0.42%
gnosis -0.15% -0.04% -0%
gp2 -0.05% -0.05% -0.01%
perpetual-pools -0.05% -0.05% +0.01%
pool-together +0.05% +0.03% +0%
prb-math 0% +0% 0%
trident -0.81% -0.36% -1.06%
uniswap -1.42% -1.79% -0.63%
yield_liquidator -0.17% -0.21% +0%
zeppelin -0.03% -0.03% +0%
------------------ --------------- ---------------- ------------

IR-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.07%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin
------------------ --------------- ---------------- ------------

LEGACY-NO-OPTIMIZE |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.13%
colony -0.1%
elementfi -0.38%
ens 0%
euler -0.2% -0.15% -0.5%
gnosis -0.08% -0.08% +0.02%
gp2 -0.11%
perpetual-pools -0.09% -0.1% +0%
pool-together -0.06% -0.07% +0.01%
prb-math 0% 0% 0%
trident -0.11% -0.08% +0.09%
uniswap -0.82% -0.73% -0.53%
yield_liquidator -0.13% -0.15% +0.02%
zeppelin -0.06% -0.07% +0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM+YUL |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps -0.04% 0% 0%
brink 0%
chainlink -0.08% -0.08% -0.01%
colony -0.07%
elementfi -0.31%
ens 0% -0% 0%
euler -0.15% -0.1% -0.47%
gnosis -0.04% -0.04% +0%
gp2 -0.06% -0.06% -0%
perpetual-pools -0.07% -0.07% -0.03%
pool-together -0.02% -0.02% +0%
prb-math 0% -0% 0%
trident -0.06% -0.04% -0.05%
uniswap -0.89% -0.85% -0.66%
yield_liquidator -0.07% -0.07% +0.01%
zeppelin -0.04% -0.04% -0%
------------------ --------------- ---------------- ------------

LEGACY-OPTIMIZE-EVM-ONLY |------------------|---------------|----------------|------------|

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.09% -0.09% -0%
colony -0.07%
elementfi -0.3%
ens 0% +0% 0%
euler -0.15% -0.1% -0.53%
gnosis -0.04% -0.04% +0%
gp2 -0.05% -0.06% -0%
perpetual-pools -0.07% -0.07% -0.02%
pool-together -0.06% -0.07% -0.01%
prb-math 0% +0% 0%
trident -0.06% -0.05% -0.05%
uniswap -0.86% -0.77% -0.67%
yield_liquidator -0.09% -0.1% +0%
zeppelin -0.04% -0.04% -0%
------------------ --------------- ---------------- ------------

matheusaaguiar avatar Aug 05 '22 03:08 matheusaaguiar

@matheusaaguiar Just a quick hint, you can use --output-format markdown with benchmark_diff.py to get a properly formatted markdown table you can paste on github. The one you have here is the output meant for console (the raw markdown does not look great on the console because the emojis make the table misaligned).

cameel avatar Aug 05 '22 13:08 cameel

Gas Benchmark

ir-no-optimize

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.1% ✅
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin

ir-optimize-evm+yul

project bytecode_size deployment_gas method_gas
bleeps +0.05% ❌ 0% 0%
brink 0%
chainlink -0.25% ✅ -0.28% ✅ -0.02% ✅
colony -0.07% ✅
elementfi -2.36% ✅
ens 0% -0% 0%
euler !V !V !V
gnosis -0.15% ✅ -0.04% ✅ -0%
gp2 -0.05% ✅ -0.05% ✅ -0.01% ✅
perpetual-pools -0.08% ✅ -0.08% ✅ -0.01% ✅
pool-together +0.03% ❌ -0.01% ✅ +0%
prb-math 0% 0% 0%
trident -0.38% ✅ -0.36% ✅ -1.06% ✅
uniswap -1.42% ✅ -1.79% ✅ -0.63% ✅
yield_liquidator -0.17% ✅ -0.21% ✅ +0%
zeppelin -0.03% ✅ -0.03% ✅ +0%

ir-optimize-evm-only

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.07% ✅
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin

legacy-no-optimize

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.13% ✅
colony -0.1% ✅
elementfi -0.38% ✅
ens 0%
euler !V !V !V
gnosis -0.08% ✅ -0.08% ✅ +0.02% ❌
gp2 -0.11% ✅
perpetual-pools -0.09% ✅ -0.1% ✅ +0%
pool-together -0.06% ✅ -0.07% ✅ +0.01% ❌
prb-math 0% 0% 0%
trident -0.11% ✅ -0.08% ✅ +0.09% ❌
uniswap -0.82% ✅ -0.73% ✅ -0.53% ✅
yield_liquidator -0.13% ✅ -0.14% ✅ +0.02% ❌
zeppelin -0.06% ✅ -0.07% ✅ +0.05% ❌

legacy-optimize-evm+yul

project bytecode_size deployment_gas method_gas
bleeps -0.04% ✅ 0% 0%
brink 0%
chainlink -0.08% ✅ -0.08% ✅ -0.01% ✅
colony -0.07% ✅
elementfi -0.31% ✅
ens 0% 0% 0%
euler !V !V !V
gnosis -0.04% ✅ -0.04% ✅ +0%
gp2 -0.06% ✅ -0.06% ✅ +0%
perpetual-pools -0.07% ✅ -0.07% ✅ -0%
pool-together -0.02% ✅ -0.02% ✅ +0%
prb-math 0% -0% 0%
trident -0.06% ✅ -0.04% ✅ -0.05% ✅
uniswap -0.89% ✅ -0.85% ✅ -0.66% ✅
yield_liquidator -0.07% ✅ -0.07% ✅ +0%
zeppelin -0.04% ✅ -0.04% ✅ -0%

legacy-optimize-evm-only

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.09% ✅ -0.09% ✅ -0%
colony -0.07% ✅
elementfi -0.3% ✅
ens 0% 0% 0%
euler !V !V !V
gnosis -0.04% ✅ -0.04% ✅ +0%
gp2 -0.05% ✅ -0.05% ✅ -0%
perpetual-pools -0.07% ✅ -0.07% ✅ -0%
pool-together -0.06% ✅ -0.07% ✅ -0.01% ✅
prb-math 0% -0% 0%
trident -0.06% ✅ -0.04% ✅ -0.05% ✅
uniswap -0.86% ✅ -0.77% ✅ -0.67% ✅
yield_liquidator -0.09% ✅ -0.1% ✅ +0%
zeppelin -0.04% ✅ -0.04% ✅ -0%

!V = version mismatch !B = no value in the "before" version !A = no value in the "after" version !T = one or both values were not numeric and could not be compared -0 = very small negative value rounded to zero +0 = very small positive value rounded to zero

matheusaaguiar avatar Aug 09 '22 21:08 matheusaaguiar

Gas Benchmark (256bit special case separated)

ir-no-optimize

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.1% ✅
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin

ir-optimize-evm+yul

project bytecode_size deployment_gas method_gas
bleeps +0.05% ❌ 0% 0%
brink 0%
chainlink -0.25% ✅ -0.28% ✅ -0.02% ✅
colony -0.07% ✅
elementfi -2.36% ✅
ens 0% -0% 0%
euler !V !V !V
gnosis -0.15% ✅ -0.04% ✅ -0%
gp2 -0.05% ✅ -0.05% ✅ -0.01% ✅
perpetual-pools -0.08% ✅ -0.08% ✅ -0.03% ✅
pool-together +0.03% ❌ -0.01% ✅ +0%
prb-math 0% +0% 0%
trident -0.38% ✅ -0.36% ✅ -1.06% ✅
uniswap -0.96% ✅ -0.91% ✅ -0.72% ✅
yield_liquidator -0.17% ✅ -0.21% ✅ +0%
zeppelin -0.03% ✅ -0.03% ✅ +0%

ir-optimize-evm-only

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.07% ✅
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin

legacy-no-optimize

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.13% ✅
colony -0.1% ✅
elementfi -0.38% ✅
ens 0%
euler !V !V !V
gnosis -0.08% ✅ -0.08% ✅ +0.02% ❌
gp2 -0.11% ✅
perpetual-pools -0.09% ✅ -0.1% ✅ +0%
pool-together -0.06% ✅ -0.07% ✅ +0.01% ❌
prb-math 0% 0% 0%
trident -0.11% ✅ -0.08% ✅ +0.09% ❌
uniswap -1.06% ✅ -0.95% ✅ -0.66% ✅
yield_liquidator -0.13% ✅ -0.14% ✅ +0.02% ❌
zeppelin -0.06% ✅ -0.07% ✅ +0%

legacy-optimize-evm+yul

project bytecode_size deployment_gas method_gas
bleeps -0.04% ✅ 0% 0%
brink 0%
chainlink -0.08% ✅ -0.08% ✅ -0.01% ✅
colony -0.07% ✅
elementfi -0.31% ✅
ens 0% 0% 0%
euler !V !V !V
gnosis -0.04% ✅ -0.04% ✅ -0%
gp2 -0.06% ✅ -0.06% ✅ +0%
perpetual-pools -0.07% ✅ -0.07% ✅ -0.01% ✅
pool-together -0.02% ✅ -0.02% ✅ +0%
prb-math 0% 0% 0%
trident -0.06% ✅ -0.04% ✅ -0.05% ✅
uniswap -1.06% ✅ -1.01% ✅ -0.76% ✅
yield_liquidator -0.07% ✅ -0.07% ✅ +0%
zeppelin -0.04% ✅ -0.04% ✅ +0.05% ❌

legacy-optimize-evm-only

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.09% ✅ -0.09% ✅ -0%
colony -0.07% ✅
elementfi -0.3% ✅
ens 0% -0% 0%
euler !V !V !V
gnosis -0.04% ✅ -0.04% ✅ +0%
gp2 -0.05% ✅ -0.05% ✅ -0%
perpetual-pools -0.07% ✅ -0.07% ✅ -0.01% ✅
pool-together -0.06% ✅ -0.07% ✅ -0.01% ✅
prb-math 0% -0% 0%
trident -0.06% ✅ -0.04% ✅ -0.05% ✅
uniswap -0.99% ✅ -0.88% ✅ -0.71% ✅
yield_liquidator -0.09% ✅ -0.1% ✅ +0%
zeppelin -0.04% ✅ -0.04% ✅ +0.05% ❌

!V = version mismatch !B = no value in the "before" version !A = no value in the "after" version !T = one or both values were not numeric and could not be compared -0 = very small negative value rounded to zero +0 = very small positive value rounded to zero

matheusaaguiar avatar Aug 10 '22 01:08 matheusaaguiar

I ran benchmark_diff.py comparing before (a23db3f) and after (79615af) the separation of the int256 special case.

Gas Benchmark diff

ir-no-optimize

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony 0%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin

ir-optimize-evm+yul

project bytecode_size deployment_gas method_gas
bleeps 0% 0% 0%
brink 0%
chainlink 0% +0% +0%
colony 0%
elementfi 0%
ens 0% 0% 0%
euler -0.04% ✅ -0.02% ✅ -0.25% ✅
gnosis 0% +0% +0%
gp2 0% +0% +0%
perpetual-pools 0% +0% -0.02% ✅
pool-together 0% +0% -0%
prb-math 0% +0% 0%
trident 0% +0% -0%
uniswap +0.46% ❌ +0.9% ❌ -0.08% ✅
yield_liquidator 0% -0% 0%
zeppelin 0% -0% +0%

ir-optimize-evm-only

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony 0%
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin

legacy-no-optimize

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink 0%
colony 0%
elementfi 0%
ens 0%
euler -0.03% ✅ -0.02% ✅ -0.28% ✅
gnosis 0% -0% -0%
gp2 0%
perpetual-pools 0% -0% -0%
pool-together 0% -0% -0%
prb-math 0% 0% 0%
trident 0% 0% +0%
uniswap -0.24% ✅ -0.22% ✅ -0.14% ✅
yield_liquidator 0% +0% 0%
zeppelin 0% +0% -0.05% ✅

legacy-optimize-evm+yul

project bytecode_size deployment_gas method_gas
bleeps 0% 0% 0%
brink 0%
chainlink 0% -0% -0%
colony 0%
elementfi 0%
ens 0% 0% 0%
euler -0.04% ✅ -0.02% ✅ -0.21% ✅
gnosis 0% 0% -0%
gp2 0% -0% -0%
perpetual-pools 0% +0% -0.01% ✅
pool-together 0% -0% +0%
prb-math 0% +0% 0%
trident 0% 0% +0%
uniswap -0.16% ✅ -0.15% ✅ -0.1% ✅
yield_liquidator 0% +0% 0%
zeppelin 0% -0% +0.05% ❌

legacy-optimize-evm-only

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink 0% -0% -0%
colony 0%
elementfi 0%
ens 0% -0% 0%
euler -0.03% ✅ -0.02% ✅ -0.18% ✅
gnosis 0% -0% 0%
gp2 0% 0% -0%
perpetual-pools 0% +0% -0.01% ✅
pool-together 0% -0% +0%
prb-math 0% 0% 0%
trident 0% -0% +0%
uniswap -0.13% ✅ -0.12% ✅ -0.04% ✅
yield_liquidator 0% +0% 0%
zeppelin 0% -0% +0.05% ❌

!V = version mismatch !B = no value in the "before" version !A = no value in the "after" version !T = one or both values were not numeric and could not be compared -0 = very small negative value rounded to zero +0 = very small positive value rounded to zero

matheusaaguiar avatar Aug 10 '22 01:08 matheusaaguiar

@matheusaaguiar Just to make this airtight, can you add the following proof scripts as sanity checks:

This checks that BVSignedCleanupFunction actually matches what YulUtilFunctions::cleanupFunction does, and that both of them actually perform proper cleanup:

signed_integer_cleanup_function.py
from opcodes import SIGNEXTEND
from rule import Rule
from util import BVSignedCleanupFunction, BVSignedUpCast
from z3 import BitVec, BitVecVal, Concat

"""
Overflow checked signed integer multiplication.
"""

n_bits = 256

# Check that YulUtilFunction::cleanupFunction cleanup matches BVSignedCleanupFunction
for type_bits in range(8,256,8):

	rule = Rule()

	# Input vars
	X = BitVec('X', n_bits)
	arg = BitVecVal(type_bits / 8 - 1, n_bits)

	cleaned_reference = BVSignedCleanupFunction(X, type_bits)
	cleaned = SIGNEXTEND(arg, X)

	rule.check(cleaned, cleaned_reference)


# Check that BVSignedCleanupFunction properly cleans up values.
for type_bits in range(8,256,8):

	rule = Rule()

	# Input vars
	X_short = BitVec('X', type_bits)
	dirt = BitVec('dirt', n_bits - type_bits)

	X = BVSignedUpCast(X_short, n_bits)
	X_dirty = Concat(dirt, X_short)
	X_cleaned = BVSignedCleanupFunction(X_dirty, type_bits)


	rule.check(X, X_cleaned)

This checks that BVUnsignedCleanupFunction actually matches what YulUtilFunctions::cleanupFunction does, and that both of them actually perform proper cleanup:

unsigned_integer_cleanup_function.py
from opcodes import AND
from rule import Rule
from util import BVUnsignedCleanupFunction, BVUnsignedUpCast
from z3 import BitVec, BitVecVal, Concat

"""
Overflow checked signed integer multiplication.
"""

n_bits = 256

# Check that YulUtilFunction::cleanupFunction cleanup matches BVUnsignedCleanupFunction
for type_bits in range(8,256,8):

	rule = Rule()

	# Input vars
	X = BitVec('X', n_bits)
	mask = BitVecVal((1 << type_bits) - 1, n_bits)

	cleaned_reference = BVUnsignedCleanupFunction(X, type_bits)
	cleaned = AND(X, mask)

	rule.check(cleaned, cleaned_reference)

# Check that BVUnsignedCleanupFunction properly cleans up values.
for type_bits in range(8,256,8):

	rule = Rule()

	# Input vars
	X_short = BitVec('X', type_bits)
	dirt = BitVec('dirt', n_bits - type_bits)

	X = BVUnsignedUpCast(X_short, n_bits)
	X_dirty = Concat(dirt, X_short)
	X_cleaned = BVUnsignedCleanupFunction(X_dirty, type_bits)


	rule.check(X, X_cleaned)

I was about to suggest to actually define BV*CleanupFunction just as the cleanup function is defined in YulUtilFunctions::cleanupFunction instead, but unfortunately that won't work, since SIGNEXTEND only works on types that are a multiple of 8 bits wide... but still, with those two additional proofs we can have higher confidence that the multiplication proofs actually match what the code does.

ekpyron avatar Aug 11 '22 08:08 ekpyron

Gas Benchmark

ir-no-optimize

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.1% ✅
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin

ir-optimize-evm+yul

project bytecode_size deployment_gas method_gas
bleeps +0.04% ❌ 0% 0%
brink 0%
chainlink -0.22% ✅ -0.23% ✅ -0.02% ✅
colony -0.08% ✅
elementfi -1.78% ✅
ens 0% -0% 0%
euler -0.27% ✅ -0.26% ✅ -0.7% ✅
gnosis -0.15% ✅ -0.04% ✅ -0%
gp2 -0.05% ✅ -0.05% ✅ -0.01% ✅
perpetual-pools -0.08% ✅ -0.09% ✅ -0.02% ✅
pool-together +0.02% ❌ -0.02% ✅ +0%
prb-math 0% +0% 0%
trident -0.15% ✅ -0.36% ✅ -1.06% ✅
uniswap -1.58% ✅ -1.95% ✅ -0.76% ✅
yield_liquidator -0.18% ✅ -0.22% ✅ -0%
zeppelin !V !V !V

ir-optimize-evm-only

project bytecode_size deployment_gas method_gas
bleeps
brink
chainlink
colony -0.05% ✅
elementfi
ens
euler
gnosis
gp2
perpetual-pools
pool-together
prb-math
trident
uniswap
yield_liquidator
zeppelin

legacy-no-optimize

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.13% ✅
colony -0.1% ✅
elementfi -0.38% ✅
ens 0%
euler -0.22% ✅ -0.16% ✅ -0.79% ✅
gnosis -0.07% ✅ -0.07% ✅ +0.02% ❌
gp2 -0.1% ✅
perpetual-pools -0.09% ✅ -0.1% ✅ +0%
pool-together -0.06% ✅ -0.07% ✅ +0.02% ❌
prb-math 0% 0% 0%
trident -0.1% ✅ -0.07% ✅ +0.13% ❌
uniswap -1.06% ✅ -0.96% ✅ -0.66% ✅
yield_liquidator -0.12% ✅ -0.14% ✅ +0.02% ❌
zeppelin !V !V !V

legacy-optimize-evm+yul

project bytecode_size deployment_gas method_gas
bleeps -0.05% ✅ 0% 0%
brink 0%
chainlink -0.09% ✅ -0.09% ✅ -0.01% ✅
colony -0.08% ✅
elementfi -0.32% ✅
ens 0% 0% 0%
euler -0.19% ✅ -0.13% ✅ -0.72% ✅
gnosis -0.04% ✅ -0.04% ✅ +0%
gp2 -0.06% ✅ -0.06% ✅ -0%
perpetual-pools -0.07% ✅ -0.07% ✅ -0.03% ✅
pool-together -0.02% ✅ -0.03% ✅ +0%
prb-math 0% 0% 0%
trident -0.06% ✅ -0.04% ✅ -0.05% ✅
uniswap -1.12% ✅ -1.07% ✅ -0.8% ✅
yield_liquidator -0.08% ✅ -0.08% ✅ -0%
zeppelin !V !V !V

legacy-optimize-evm-only

project bytecode_size deployment_gas method_gas
bleeps
brink 0%
chainlink -0.03% ✅ -0.04% ✅ +0%
colony -0.05% ✅
elementfi -0.25% ✅
ens 0% -0% 0%
euler -0.11% ✅ -0.07% ✅ -0.64% ✅
gnosis -0.01% ✅ -0.03% ✅ +0%
gp2 -0.04% ✅ -0.03% ✅ +0%
perpetual-pools -0.04% ✅ -0.04% ✅ -0.03% ✅
pool-together -0.03% ✅ -0.04% ✅ -0%
prb-math 0% 0% 0%
trident -0.01% ✅ -0% +0.03% ❌
uniswap -0.89% ✅ -0.81% ✅ -0.65% ✅
yield_liquidator -0.02% ✅ -0.03% ✅ +0%
zeppelin !V !V !V

!V = version mismatch !B = no value in the "before" version !A = no value in the "after" version !T = one or both values were not numeric and could not be compared -0 = very small negative value rounded to zero +0 = very small positive value rounded to zero

matheusaaguiar avatar Aug 12 '22 03:08 matheusaaguiar

Rebased and squashed commits.

matheusaaguiar avatar Aug 12 '22 13:08 matheusaaguiar

@bshastry Do we have infrastructure set up to easily fuzz develop pre- and post this change before our next release :-)? Affected is any solidity code with effects that depend on multiplication :-). But yeah, not high priority, since we're rather confident that it's correct, just in case it's easy to fuzz.

ekpyron avatar Aug 12 '22 17:08 ekpyron

@bshastry Do we have infrastructure set up to easily fuzz develop pre- and post this change before our next release :-)? Affected is any solidity code with effects that depend on multiplication :-). But yeah, not high priority, since we're rather confident that it's correct, just in case it's easy to fuzz.

Just to understand better: Does the change affect both legacy and IR codegens or only one of them? My impression looking at the tests is that it affects both, so it may be not suited for differential testing between them.

Also, differentially fuzzing no optimization and optimization does not seem a good option because this change happens pre optimization right?

bshastry avatar Aug 15 '22 10:08 bshastry

@bshastry Yes, this will affect legacy and IR code generations and it will indeed kick in before optimization.

So the only thing one could do here would be differential fuzzing across two versions of solidity, i.e. having some randomly generated solidity code (hoping that it will have side effects that depend on multiplication), and then checking if the compiler before this PR produces the same side-effects than the compiler after this PR.

I guess we've not done something like that before? May be worth a thought for the future - but not sure how often we will have cases like that and in this case here, it doesn't necessarily warrant much additional effort to put into for fuzzing it specifically, I was mainly wondering. (I.e. "Nope, we can't fuzz this" is a perfectly fine resolution to this discussion ;-)).

ekpyron avatar Aug 15 '22 10:08 ekpyron

Thanks for the clarification @ekpyron . Yeah, fuzzing this is tricky because we don't have infrastructure yet for a baseline and experiment groups that differ by versions/commits. I actually need to think of what that could look like because we would need to link a single binary against two different versions of libsolidity somehow.

One solution would be to refactor this PR into a flag that is propagated all the way up to the compile API and have the fuzzer differentially fuzz that. But yeah, I can understand if this may not be worth the effort for the current PR.

bshastry avatar Aug 15 '22 11:08 bshastry

Yeah, ok... can the fuzzers spawn processes? Then using two separate solc binaries and haviung them produce bytecode and then feeding those two bytecodes to evmhost separately (without actually ever linking to the compiler) would probably be an option for doing something like that.

But yeah, for this here specifically it's not worth setting anything like that up. So as far as I'm concerned, we can keep it at that for now and just revisit the next time we have something like that.

ekpyron avatar Aug 15 '22 14:08 ekpyron

Yeah, ok... can the fuzzers spawn processes? Then using two separate solc binaries and haviung them produce bytecode and then feeding those two bytecodes to evmhost separately (without actually ever linking to the compiler) would probably be an option for doing something like that.

Yup, this could be an option to experiment with. We could execv the solc binary (at least locally if not on the Google cluster where we'd need a single fuzzer binary blob with only certain system deps.

bshastry avatar Aug 15 '22 16:08 bshastry