/*
This file is part of solidity.
solidity is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
solidity is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with solidity. If not, see <http://www.gnu.org/licenses/>.
*/
/**
* @author Christian <c@ethdev.com>
* @date 2014
* Tests for the Solidity optimizer.
*/
#include <test/libsolidity/SolidityExecutionFramework.h>
#include <libevmasm/Instruction.h>
#include <boost/test/unit_test.hpp>
#include <boost/lexical_cast.hpp>
#include <chrono>
#include <string>
#include <tuple>
#include <memory>
using namespace std;
using namespace dev::eth;
using namespace dev::test;
namespace dev
{
namespace solidity
{
namespace test
{
class OptimizerTestFramework: public SolidityExecutionFramework
{
public:
OptimizerTestFramework() { }
bytes const& compileAndRunWithOptimizer(
std::string const& _sourceCode,
u256 const& _value = 0,
std::string const& _contractName = "",
bool const _optimize = true,
unsigned const _optimizeRuns = 200
)
{
bool const c_optimize = m_optimize;
unsigned const c_optimizeRuns = m_optimizeRuns;
m_optimize = _optimize;
m_optimizeRuns = _optimizeRuns;
bytes const& ret = compileAndRun(_sourceCode, _value, _contractName);
m_optimize = c_optimize;
m_optimizeRuns = c_optimizeRuns;
return ret;
}
/// Compiles the source code with and without optimizing.
void compileBothVersions(
std::string const& _sourceCode,
u256 const& _value = 0,
std::string const& _contractName = "",
unsigned const _optimizeRuns = 200
)
{
m_nonOptimizedBytecode = compileAndRunWithOptimizer(_sourceCode, _value, _contractName, false, _optimizeRuns);
m_nonOptimizedContract = m_contractAddress;
m_optimizedBytecode = compileAndRunWithOptimizer(_sourceCode, _value, _contractName, true, _optimizeRuns);
size_t nonOptimizedSize = numInstructions(m_nonOptimizedBytecode);
size_t optimizedSize = numInstructions(m_optimizedBytecode);
BOOST_CHECK_MESSAGE(
_optimizeRuns < 50 || optimizedSize < nonOptimizedSize,
string("Optimizer did not reduce bytecode size. Non-optimized size: ") +
std::to_string(nonOptimizedSize) + " - optimized size: " +
std::to_string(optimizedSize)
);
m_optimizedContract = m_contractAddress;
}
template <class... Args>
void compareVersions(std::string _sig, Args const&... _arguments)
{
m_contractAddress = m_nonOptimizedContract;
bytes nonOptimizedOutput = callContractFunction(_sig, _arguments...);
m_gasUsedNonOptimized = m_gasUsed;
m_contractAddress = m_optimizedContract;
bytes optimizedOutput = callContractFunction(_sig, _arguments...);
m_gasUsedOptimized = m_gasUsed;
BOOST_CHECK_MESSAGE(!optimizedOutput.empty(), "No optimized output for " + _sig);
BOOST_CHECK_MESSAGE(!nonOptimizedOutput.empty(), "No un-optimized output for " + _sig);
BOOST_CHECK_MESSAGE(nonOptimizedOutput == optimizedOutput, "Computed values do not match."
"\nNon-Optimized: " + toHex(nonOptimizedOutput) +
"\nOptimized: " + toHex(optimizedOutput));
}
/// @returns the number of instructions in the given bytecode, not taking the metadata hash
/// into account.
size_t numInstructions(bytes const& _bytecode, boost::optional<Instruction> _which = boost::optional<Instruction>{})
{
BOOST_REQUIRE(_bytecode.size() > 5);
size_t metadataSize = (_bytecode[_bytecode.size() - 2] << 8) + _bytecode[_bytecode.size() - 1];
BOOST_REQUIRE_MESSAGE(metadataSize == 0x29, "Invalid metadata size");
BOOST_REQUIRE(_bytecode.size() >= metadataSize + 2);
bytes realCode = bytes(_bytecode.begin(), _bytecode.end() - metadataSize - 2);
size_t instructions = 0;
solidity::eachInstruction(realCode, [&](Instruction _instr, u256 const&) {
if (!_which || *_which == _instr)
instructions++;
});
return instructions;
}
protected:
u256 m_gasUsedOptimized;
u256 m_gasUsedNonOptimized;
bytes m_nonOptimizedBytecode;
bytes m_optimizedBytecode;
Address m_optimizedContract;
Address m_nonOptimizedContract;
};
BOOST_FIXTURE_TEST_SUITE(SolidityOptimizer, OptimizerTestFramework)
BOOST_AUTO_TEST_CASE(smoke_test)
{
char const* sourceCode = R"(
contract test {
function f(uint a) public returns (uint b) {
return a;
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f(uint256)", u256(7));
}
BOOST_AUTO_TEST_CASE(identities)
{
char const* sourceCode = R"(
contract test {
function f(int a) public returns (int b) {
return int(0) | (int(1) * (int(0) ^ (0 + a)));
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f(int256)", u256(0x12334664));
}
BOOST_AUTO_TEST_CASE(unused_expressions)
{
char const* sourceCode = R"(
contract test {
uint data;
function f() public returns (uint a, uint b) {
10 + 20;
data;
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f()");
}
BOOST_AUTO_TEST_CASE(constant_folding_both_sides)
{
// if constants involving the same associative and commutative operator are applied from both
// sides, the operator should be applied only once, because the expression compiler pushes
// literals as late as possible
char const* sourceCode = R"(
contract test {
function f(uint x) public returns (uint y) {
return 98 ^ (7 * ((1 | (x | 1000)) * 40) ^ 102);
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f(uint256)", 7);
}
BOOST_AUTO_TEST_CASE(storage_access)
{
char const* sourceCode = R"(
contract test {
uint8[40] data;
function f(uint x) public returns (uint y) {
data[2] = data[7] = uint8(x);
data[4] = data[2] * 10 + data[3];
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f(uint256)", 7);
}
BOOST_AUTO_TEST_CASE(array_copy)
{
char const* sourceCode = R"(
contract test {
bytes2[] data1;
bytes5[] data2;
function f(uint x) public returns (uint l, uint y) {
data1.length = msg.data.length;
for (uint i = 0; i < msg.data.length; ++i)
data1[i] = msg.data[i];
data2 = data1;
l = data2.length;
y = uint(uint40(data2[x]));
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f(uint256)", 0);
compareVersions("f(uint256)", 10);
compareVersions("f(uint256)", 35);
}
BOOST_AUTO_TEST_CASE(function_calls)
{
char const* sourceCode = R"(
contract test {
function f1(uint x) public returns (uint) { return x*x; }
function f(uint x) public returns (uint) { return f1(7+x) - this.f1(x**9); }
}
)";
compileBothVersions(sourceCode);
compareVersions("f(uint256)", 0);
compareVersions("f(uint256)", 10);
compareVersions("f(uint256)", 36);
}
BOOST_AUTO_TEST_CASE(storage_write_in_loops)
{
char const* sourceCode = R"(
contract test {
uint d;
function f(uint a) public returns (uint r) {
uint x = d;
for (uint i = 1; i < a * a; i++) {
r = d;
d = i;
}
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f(uint256)", 0);
compareVersions("f(uint256)", 10);
compareVersions("f(uint256)", 36);
}
// Test disabled with https://github.com/ethereum/solidity/pull/762
// Information in joining branches is not retained anymore.
BOOST_AUTO_TEST_CASE(retain_information_in_branches)
{
// This tests that the optimizer knows that we already have "z == keccak256(abi.encodePacked(y))" inside both branches.
char const* sourceCode = R"(
contract c {
bytes32 d;
uint a;
function f(uint x, bytes32 y) public returns (uint r_a, bytes32 r_d) {
bytes32 z = keccak256(abi.encodePacked(y));
if (x > 8) {
z = keccak256(abi.encodePacked(y));
a = x;
} else {
z = keccak256(abi.encodePacked(y));
a = x;
}
r_a = a;
r_d = d;
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f(uint256,bytes32)", 0, "abc");
compareVersions("f(uint256,bytes32)", 8, "def");
compareVersions("f(uint256,bytes32)", 10, "ghi");
bytes optimizedBytecode = compileAndRunWithOptimizer(sourceCode, 0, "c", true);
size_t numSHA3s = 0;
eachInstruction(optimizedBytecode, [&](Instruction _instr, u256 const&) {
if (_instr == Instruction::KECCAK256)
numSHA3s++;
});
// TEST DISABLED - OPTIMIZER IS NOT EFFECTIVE ON THIS ONE ANYMORE
// BOOST_CHECK_EQUAL(1, numSHA3s);
}
BOOST_AUTO_TEST_CASE(store_tags_as_unions)
{
// This calls the same function from two sources and both calls have a certain Keccak-256 on
// the stack at the same position.
// Without storing tags as unions, the return from the shared function would not know where to
// jump and thus all jumpdests are forced to clear their state and we do not know about the
// sha3 anymore.
// Note that, for now, this only works if the functions have the same number of return
// parameters since otherwise, the return jump addresses are at different stack positions
// which triggers the "unknown jump target" situation.
char const* sourceCode = R"(
contract test {
bytes32 data;
function f(uint x, bytes32 y) external returns (uint r_a, bytes32 r_d) {
r_d = keccak256(abi.encodePacked(y));
shared(y);
r_d = keccak256(abi.encodePacked(y));
r_a = 5;
}
function g(uint x, bytes32 y) external returns (uint r_a, bytes32 r_d) {
r_d = keccak256(abi.encodePacked(y));
shared(y);
r_d = bytes32(uint(keccak256(abi.encodePacked(y))) + 2);
r_a = 7;
}
function shared(bytes32 y) internal {
data = keccak256(abi.encodePacked(y));
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f(uint256,bytes32)", 7, "abc");
bytes optimizedBytecode = compileAndRunWithOptimizer(sourceCode, 0, "test", true);
size_t numSHA3s = 0;
eachInstruction(optimizedBytecode, [&](Instruction _instr, u256 const&) {
if (_instr == Instruction::KECCAK256)
numSHA3s++;
});
// TEST DISABLED UNTIL 93693404 IS IMPLEMENTED
// BOOST_CHECK_EQUAL(2, numSHA3s);
}
BOOST_AUTO_TEST_CASE(incorrect_storage_access_bug)
{
// This bug appeared because a Keccak-256 operation with too low sequence number was used,
// resulting in memory not being rewritten before the Keccak-256. The fix was to
// take the max of the min sequence numbers when merging the states.
char const* sourceCode = R"(
contract C
{
mapping(uint => uint) data;
function f() public returns (uint)
{
if(data[now] == 0)
data[uint(-7)] = 5;
return data[now];
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f()");
}
BOOST_AUTO_TEST_CASE(sequence_number_for_calls)
{
// This is a test for a bug that was present because we did not increment the sequence
// number for CALLs - CALLs can read and write from memory (and DELEGATECALLs can do the same
// to storage), so the sequence number should be incremented.
char const* sourceCode = R"(
contract test {
function f(string memory a, string memory b) public returns (bool) { return sha256(bytes(a)) == sha256(bytes(b)); }
}
)";
compileBothVersions(sourceCode);
compareVersions("f(string,string)", 0x40, 0x80, 3, "abc", 3, "def");
}
BOOST_AUTO_TEST_CASE(computing_constants)
{
char const* sourceCode = R"(
contract C {
uint m_a;
uint m_b;
uint m_c;
uint m_d;
constructor() public {
set();
}
function set() public returns (uint) {
m_a = 0x77abc0000000000000000000000000000000000000000000000000000000001;
m_b = 0x817416927846239487123469187231298734162934871263941234127518276;
g();
return 1;
}
function g() public {
m_b = 0x817416927846239487123469187231298734162934871263941234127518276;
m_c = 0x817416927846239487123469187231298734162934871263941234127518276;
h();
}
function h() public {
m_d = 0xff05694900000000000000000000000000000000000000000000000000000000;
}
function get() public returns (uint ra, uint rb, uint rc, uint rd) {
ra = m_a;
rb = m_b;
rc = m_c;
rd = m_d;
}
}
)";
compileBothVersions(sourceCode, 0, "C", 1);
compareVersions("get()");
compareVersions("set()");
compareVersions("get()");
bytes optimizedBytecode = compileAndRunWithOptimizer(sourceCode, 0, "C", true, 1);
bytes complicatedConstant = toBigEndian(u256("0x817416927846239487123469187231298734162934871263941234127518276"));
unsigned occurrences = 0;
for (auto iter = optimizedBytecode.cbegin(); iter < optimizedBytecode.cend(); ++occurrences)
{
iter = search(iter, optimizedBytecode.cend(), complicatedConstant.cbegin(), complicatedConstant.cend());
if (iter < optimizedBytecode.cend())
++iter;
}
BOOST_CHECK_EQUAL(2, occurrences);
bytes constantWithZeros = toBigEndian(u256("0x77abc0000000000000000000000000000000000000000000000000000000001"));
BOOST_CHECK(search(
optimizedBytecode.cbegin(),
optimizedBytecode.cend(),
constantWithZeros.cbegin(),
constantWithZeros.cend()
) == optimizedBytecode.cend());
}
BOOST_AUTO_TEST_CASE(constant_optimization_early_exit)
{
// This tests that the constant optimizer does not try to find the best representation
// indefinitely but instead stops after some number of iterations.
char const* sourceCode = R"(
pragma solidity ^0.4.0;
contract HexEncoding {
function hexEncodeTest(address addr) public returns (bytes32 ret) {
uint x = uint(addr) / 2**32;
// Nibble interleave
x = x & 0x00000000000000000000000000000000ffffffffffffffffffffffffffffffff;
x = (x | (x * 2**64)) & 0x0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff;
x = (x | (x * 2**32)) & 0x00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff;
x = (x | (x * 2**16)) & 0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff;
x = (x | (x * 2** 8)) & 0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff;
x = (x | (x * 2** 4)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f;
// Hex encode
uint h = (x & 0x0808080808080808080808080808080808080808080808080808080808080808) / 8;
uint i = (x & 0x0404040404040404040404040404040404040404040404040404040404040404) / 4;
uint j = (x & 0x0202020202020202020202020202020202020202020202020202020202020202) / 2;
x = x + (h & (i | j)) * 0x27 + 0x3030303030303030303030303030303030303030303030303030303030303030;
// Store and load next batch
assembly {
mstore(0, x)
}
x = uint(addr) * 2**96;
// Nibble interleave
x = x & 0x00000000000000000000000000000000ffffffffffffffffffffffffffffffff;
x = (x | (x * 2**64)) & 0x0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff;
x = (x | (x * 2**32)) & 0x00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff;
x = (x | (x * 2**16)) & 0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff;
x = (x | (x * 2** 8)) & 0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff;
x = (x | (x * 2** 4)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f;
// Hex encode
h = (x & 0x0808080808080808080808080808080808080808080808080808080808080808) / 8;
i = (x & 0x0404040404040404040404040404040404040404040404040404040404040404) / 4;
j = (x & 0x0202020202020202020202020202020202020202020202020202020202020202) / 2;
x = x + (h & (i | j)) * 0x27 + 0x3030303030303030303030303030303030303030303030303030303030303030;
// Store and hash
assembly {
mstore(32, x)
ret := keccak256(0, 40)
}
}
}
)";
auto start = std::chrono::steady_clock::now();
compileBothVersions(sourceCode);
double duration = std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
BOOST_CHECK_MESSAGE(duration < 20, "Compilation of constants took longer than 20 seconds.");
compareVersions("hexEncodeTest(address)", u256(0x123456789));
}
BOOST_AUTO_TEST_CASE(inconsistency)
{
// This is a test of a bug in the optimizer.
char const* sourceCode = R"(
contract Inconsistency {
struct Value {
uint badnum;
uint number;
}
struct Container {
uint[] valueIndices;
Value[] values;
}
Container[] containers;
uint[] valueIndices;
uint INDEX_ZERO = 0;
uint debug;
// Called with params: containerIndex=0, valueIndex=0
function levelIII(uint containerIndex, uint valueIndex) private {
Container storage container = containers[containerIndex];
Value storage value = container.values[valueIndex];
debug = container.valueIndices[value.number];
}
function levelII() private {
for (uint i = 0; i < valueIndices.length; i++) {
levelIII(INDEX_ZERO, valueIndices[i]);
}
}
function trigger() public returns (uint) {
containers.length++;
Container storage container = containers[0];
container.values.push(Value({
badnum: 9000,
number: 0
}));
container.valueIndices.length++;
valueIndices.length++;
levelII();
return debug;
}
function DoNotCallButDoNotDelete() public {
levelII();
levelIII(1, 2);
}
}
)";
compileBothVersions(sourceCode);
compareVersions("trigger()");
}
BOOST_AUTO_TEST_CASE(dead_code_elimination_across_assemblies)
{
// This tests that a runtime-function that is stored in storage in the constructor
// is not removed as part of dead code elimination.
char const* sourceCode = R"(
contract DCE {
function () internal returns (uint) stored;
constructor() public {
stored = f;
}
function f() internal returns (uint) { return 7; }
function test() public returns (uint) { return stored(); }
}
)";
compileBothVersions(sourceCode);
compareVersions("test()");
}
BOOST_AUTO_TEST_CASE(invalid_state_at_control_flow_join)
{
char const* sourceCode = R"(
contract Test {
uint256 public totalSupply = 100;
function f() public returns (uint r) {
if (false)
r = totalSupply;
totalSupply -= 10;
}
function test() public returns (uint) {
f();
return this.totalSupply();
}
}
)";
compileBothVersions(sourceCode);
compareVersions("test()");
}
BOOST_AUTO_TEST_CASE(init_empty_dynamic_arrays)
{
// This is not so much an optimizer test, but rather a test
// that allocating empty arrays is implemented efficiently.
// In particular, initializing a dynamic memory array does
// not use any memory.
char const* sourceCode = R"(
contract Test {
function f() public pure returns (uint r) {
uint[][] memory x = new uint[][](20000);
return x.length;
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f()");
BOOST_CHECK_LE(m_gasUsedNonOptimized, 1900000);
BOOST_CHECK_LE(1600000, m_gasUsedNonOptimized);
}
BOOST_AUTO_TEST_CASE(optimise_multi_stores)
{
char const* sourceCode = R"(
contract Test {
struct S { uint16 a; uint16 b; uint16[3] c; uint[] dyn; }
uint padding;
S[] s;
function f() public returns (uint16, uint16, uint16[3] memory, uint) {
uint16[3] memory c;
c[0] = 7;
c[1] = 8;
c[2] = 9;
s.push(S(1, 2, c, new uint[](4)));
return (s[0].a, s[0].b, s[0].c, s[0].dyn[2]);
}
}
)";
compileBothVersions(sourceCode);
compareVersions("f()");
BOOST_CHECK_EQUAL(numInstructions(m_nonOptimizedBytecode, Instruction::SSTORE), 9);
BOOST_CHECK_EQUAL(numInstructions(m_optimizedBytecode, Instruction::SSTORE), 8);
}
BOOST_AUTO_TEST_SUITE_END()
}
}
} // end namespaces
