search

Uniswap / universal-router

Uniswap's Universal Router for NFT and ERC20 swapping
GNU General Public License v3.0
396 stars 204 forks source link

Save gas and clean the upper bits of computed pool address properly #291

Open shuhuiluo opened 1 year ago

shuhuiluo commented 1 year ago

Refactor _v2Swap to resolve stack too deep error

Previously UniversalRouter can only be compiled via the IR pipeline due to the "stack too deep" error which takes a long time especially in Foundry. After refactoring _v2Swap and modifying SignatureTransfer.permitWitnessTransferFrom to

bytes32 hash = permit.hashWithWitness(witness, witnessTypeString);
_permitTransferFrom(permit, transferDetails, owner, hash, signature);

it not only saves gas but the project can also be compiled with via_ir = false which allows for faster compilation and testing

Compute v2 and v3 pool address using inline assembly and explicitly clean the upper bits

Previously the pool address was computed in pure Solidity and casted via address(uint160(uint256())). However the upper 12 bytes are not explicitly cleaned and the address is later used in solmate::SafeTransferLib.safeTransfer which is written in inline assembly. When compiled with via_ir enabled, all tests pass. However, after making the aforementioned changes, some Foundry tests failed in a ERC20.transfer with via_ir disabled. It was discovered that the dirty upper bits of pool address are the culprit, but somehow the IR pipeline may clean the address after keccak256. Nonetheless, pairForPreSorted and computePoolAddress are rewritten in inline assembly to save gas and clean the upper bits. Closes #290.

Add Uniswap v3 Foundry tests for more granular gas comparison

There weren't Uniswap v3 tests in Foundry. In order to validate gas optimizations to be made, test contracts UniswapV3Test and V3MockMock have been added. forge snapshot --diff is run after each modification to validate the gas savings.

Replace conditional statements with bitwise operations

The current Solidity optimizer isn't smart enough to reduce ternary expressions to fewer opcodes and likely translate them to JUMPI. Therefore TernaryLib utils written in inline assembly have been added to replace ternary expressions as much as possible. sortTokens is also refactored to TernaryLib but inlined where appropriate.

In general for x = y ? a : b, when y = true

x = a = 0 ^ a = b ^ b ^ a = b ^ (b ^ a) * y

When y = false

x = b = b ^ 0 = b ^ (b ^ a) * y

Therefore x = y ? a : b is equivalent to x = b ^ (b ^ a) * y according to the properties of xor.