path: root/test/libsolidity/SolidityOptimizer.cpp

/*
    This file is part of cpp-ethereum.

    cpp-ethereum 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.

    cpp-ethereum 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 cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
*/
/**
 * @author Christian <c@ethdev.com>
 * @date 2014
 * Tests for the Solidity optimizer.
 */

#include <string>
#include <tuple>
#include <memory>
#include <boost/test/unit_test.hpp>
#include <boost/lexical_cast.hpp>
#include <test/libsolidity/SolidityExecutionFramework.h>
#include <libevmasm/CommonSubexpressionEliminator.h>
#include <libevmasm/ControlFlowGraph.h>
#include <libevmasm/Assembly.h>
#include <libevmasm/BlockDeduplicator.h>

using namespace std;
using namespace dev::eth;

namespace dev
{
namespace solidity
{
namespace test
{

class OptimizerTestFramework: public ExecutionFramework
{
public:
    OptimizerTestFramework() { }
    /// Compiles the source code with and without optimizing.
    void compileBothVersions(
        std::string const& _sourceCode,
        u256 const& _value = 0,
        std::string const& _contractName = ""
    )
    {
        m_optimize = false;
        bytes nonOptimizedBytecode = compileAndRun(_sourceCode, _value, _contractName);
        m_nonOptimizedContract = m_contractAddress;
        m_optimize = true;
        bytes optimizedBytecode = compileAndRun(_sourceCode, _value, _contractName);
        size_t nonOptimizedSize = 0;
        solidity::eachInstruction(nonOptimizedBytecode, [&](Instruction, u256 const&) {
            nonOptimizedSize++;
        });
        size_t optimizedSize = 0;
        solidity::eachInstruction(optimizedBytecode, [&](Instruction, u256 const&) {
            optimizedSize++;
        });
        BOOST_CHECK_MESSAGE(
            nonOptimizedSize > optimizedSize,
            "Optimizer did not reduce bytecode size."
        );
        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_contractAddress = m_optimizedContract;
        bytes optimizedOutput = callContractFunction(_sig, _arguments...);
        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));
    }

    AssemblyItems addDummyLocations(AssemblyItems const& _input)
    {
        // add dummy locations to each item so that we can check that they are not deleted
        AssemblyItems input = _input;
        for (AssemblyItem& item: input)
            item.setLocation(SourceLocation(1, 3, make_shared<string>("")));
        return input;
    }

    eth::KnownState createInitialState(AssemblyItems const& _input)
    {
        eth::KnownState state;
        for (auto const& item: addDummyLocations(_input))
            state.feedItem(item, true);
        return state;
    }

    AssemblyItems CSE(AssemblyItems const& _input, eth::KnownState const& _state = eth::KnownState())
    {
        AssemblyItems input = addDummyLocations(_input);

        eth::CommonSubexpressionEliminator cse(_state);
        BOOST_REQUIRE(cse.feedItems(input.begin(), input.end()) == input.end());
        AssemblyItems output = cse.getOptimizedItems();

        for (AssemblyItem const& item: output)
        {
            BOOST_CHECK(item == Instruction::POP || !item.location().isEmpty());
        }
        return output;
    }

    void checkCSE(
        AssemblyItems const& _input,
        AssemblyItems const& _expectation,
        KnownState const& _state = eth::KnownState()
    )
    {
        AssemblyItems output = CSE(_input, _state);
        BOOST_CHECK_EQUAL_COLLECTIONS(_expectation.begin(), _expectation.end(), output.begin(), output.end());
    }

    AssemblyItems CFG(AssemblyItems const& _input)
    {
        AssemblyItems output = _input;
        // Running it four times should be enough for these tests.
        for (unsigned i = 0; i < 4; ++i)
        {
            ControlFlowGraph cfg(output);
            AssemblyItems optItems;
            for (BasicBlock const& block: cfg.optimisedBlocks())
                copy(output.begin() + block.begin, output.begin() + block.end,
                     back_inserter(optItems));
            output = move(optItems);
        }
        return output;
    }

    void checkCFG(AssemblyItems const& _input, AssemblyItems const& _expectation)
    {
        AssemblyItems output = CFG(_input);
        BOOST_CHECK_EQUAL_COLLECTIONS(_expectation.begin(), _expectation.end(), output.begin(), output.end());
    }

protected:
    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) 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) 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() 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) returns (uint y) {
                return 98 ^ (7 * ((1 | (x | 1000)) * 40) ^ 102);
            }
        })";
    compileBothVersions(sourceCode);
    compareVersions("f(uint256)");
}

BOOST_AUTO_TEST_CASE(storage_access)
{
    char const* sourceCode = R"(
        contract test {
            uint8[40] data;
            function f(uint x) returns (uint y) {
                data[2] = data[7] = uint8(x);
                data[4] = data[2] * 10 + data[3];
            }
        }
    )";
    compileBothVersions(sourceCode);
    compareVersions("f(uint256)");
}

BOOST_AUTO_TEST_CASE(array_copy)
{
    char const* sourceCode = R"(
        contract test {
            bytes2[] data1;
            bytes5[] data2;
            function f(uint x) 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(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) returns (uint) { return x*x; }
            function f(uint x) 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) returns (uint r) {
                var 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);
}

BOOST_AUTO_TEST_CASE(retain_information_in_branches)
{
    // This tests that the optimizer knows that we already have "z == sha3(y)" inside both branches.
    char const* sourceCode = R"(
        contract c {
            bytes32 d;
            uint a;
            function f(uint x, bytes32 y) returns (uint r_a, bytes32 r_d) {
                bytes32 z = sha3(y);
                if (x > 8) {
                    z = sha3(y);
                    a = x;
                } else {
                    z = sha3(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");

    m_optimize = true;
    bytes optimizedBytecode = compileAndRun(sourceCode, 0, "c");
    size_t numSHA3s = 0;
    eachInstruction(optimizedBytecode, [&](Instruction _instr, u256 const&) {
        if (_instr == Instruction::SHA3)
            numSHA3s++;
    });
    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 sha3 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 = sha3(y);
                shared(y);
                r_d = sha3(y);
                r_a = 5;
            }
            function g(uint x, bytes32 y) external returns (uint r_a, bytes32 r_d) {
                r_d = sha3(y);
                shared(y);
                r_d = bytes32(uint(sha3(y)) + 2);
                r_a = 7;
            }
            function shared(bytes32 y) internal {
                data = sha3(y);
            }
        }
    )";
    compileBothVersions(sourceCode);
    compareVersions("f(uint256,bytes32)", 7, "abc");

    m_optimize = true;
    bytes optimizedBytecode = compileAndRun(sourceCode, 0, "test");
    size_t numSHA3s = 0;
    eachInstruction(optimizedBytecode, [&](Instruction _instr, u256 const&) {
        if (_instr == Instruction::SHA3)
            numSHA3s++;
    });
// TEST DISABLED UNTIL 93693404 IS IMPLEMENTED
//  BOOST_CHECK_EQUAL(2, numSHA3s);
}

BOOST_AUTO_TEST_CASE(successor_not_found_bug)
{
    // This bug was caused because MSVC chose to use the u256->bool conversion
    // instead of u256->unsigned
    char const* sourceCode = R"(
        contract greeter { function greeter() {} }
    )";
    compileBothVersions(sourceCode);
}

BOOST_AUTO_TEST_CASE(incorrect_storage_access_bug)
{
    // This bug appeared because a sha3 operation with too low sequence number was used,
    // resulting in memory not being rewritten before the sha3. 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() 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 a, string b) returns (bool) { return sha256(a) == sha256(b); }
        }
    )";
    compileBothVersions(sourceCode);
    compareVersions("f(string,string)", 0x40, 0x80, 3, "abc", 3, "def");
}

BOOST_AUTO_TEST_CASE(cse_intermediate_swap)
{
    eth::KnownState state;
    eth::CommonSubexpressionEliminator cse(state);
    AssemblyItems input{
        Instruction::SWAP1, Instruction::POP, Instruction::ADD, u256(0), Instruction::SWAP1,
        Instruction::SLOAD, Instruction::SWAP1, u256(100), Instruction::EXP, Instruction::SWAP1,
        Instruction::DIV, u256(0xff), Instruction::AND
    };
    BOOST_REQUIRE(cse.feedItems(input.begin(), input.end()) == input.end());
    AssemblyItems output = cse.getOptimizedItems();
    BOOST_CHECK(!output.empty());
}

BOOST_AUTO_TEST_CASE(cse_negative_stack_access)
{
    AssemblyItems input{Instruction::DUP2, u256(0)};
    checkCSE(input, input);
}

BOOST_AUTO_TEST_CASE(cse_negative_stack_end)
{
    AssemblyItems input{Instruction::ADD};
    checkCSE(input, input);
}

BOOST_AUTO_TEST_CASE(cse_intermediate_negative_stack)
{
    AssemblyItems input{Instruction::ADD, u256(1), Instruction::DUP1};
    checkCSE(input, input);
}

BOOST_AUTO_TEST_CASE(cse_pop)
{
    checkCSE({Instruction::POP}, {Instruction::POP});
}

BOOST_AUTO_TEST_CASE(cse_unneeded_items)
{
    AssemblyItems input{
        Instruction::ADD,
        Instruction::SWAP1,
        Instruction::POP,
        u256(7),
        u256(8),
    };
    checkCSE(input, input);
}

BOOST_AUTO_TEST_CASE(cse_constant_addition)
{
    AssemblyItems input{u256(7), u256(8), Instruction::ADD};
    checkCSE(input, {u256(7 + 8)});
}

BOOST_AUTO_TEST_CASE(cse_invariants)
{
    AssemblyItems input{
        Instruction::DUP1,
        Instruction::DUP1,
        u256(0),
        Instruction::OR,
        Instruction::OR
    };
    checkCSE(input, {Instruction::DUP1});
}

BOOST_AUTO_TEST_CASE(cse_subself)
{
    checkCSE({Instruction::DUP1, Instruction::SUB}, {Instruction::POP, u256(0)});
}

BOOST_AUTO_TEST_CASE(cse_subother)
{
    checkCSE({Instruction::SUB}, {Instruction::SUB});
}

BOOST_AUTO_TEST_CASE(cse_double_negation)
{
    checkCSE({Instruction::DUP5, Instruction::NOT, Instruction::NOT}, {Instruction::DUP5});
}

BOOST_AUTO_TEST_CASE(cse_double_iszero)
{
    checkCSE({Instruction::GT, Instruction::ISZERO, Instruction::ISZERO}, {Instruction::GT});
    checkCSE({Instruction::GT, Instruction::ISZERO}, {Instruction::GT, Instruction::ISZERO});
    checkCSE(
        {Instruction::ISZERO, Instruction::ISZERO, Instruction::ISZERO},
        {Instruction::ISZERO}
    );
}

BOOST_AUTO_TEST_CASE(cse_associativity)
{
    AssemblyItems input{
        Instruction::DUP1,
        Instruction::DUP1,
        u256(0),
        Instruction::OR,
        Instruction::OR
    };
    checkCSE(input, {Instruction::DUP1});
}

BOOST_AUTO_TEST_CASE(cse_associativity2)
{
    AssemblyItems input{
        u256(0),
        Instruction::DUP2,
        u256(2),
        u256(1),
        Instruction::DUP6,
        Instruction::ADD,
        u256(2),
        Instruction::ADD,
        Instruction::ADD,
        Instruction::ADD,
        Instruction::ADD
    };
    checkCSE(input, {Instruction::DUP2, Instruction::DUP2, Instruction::ADD, u256(5), Instruction::ADD});
}

BOOST_AUTO_TEST_CASE(cse_storage)
{
    AssemblyItems input{
        u256(0),
        Instruction::SLOAD,
        u256(0),
        Instruction::SLOAD,
        Instruction::ADD,
        u256(0),
        Instruction::SSTORE
    };
    checkCSE(input, {
        u256(0),
        Instruction::DUP1,
        Instruction::SLOAD,
        Instruction::DUP1,
        Instruction::ADD,
        Instruction::SWAP1,
        Instruction::SSTORE
    });
}

BOOST_AUTO_TEST_CASE(cse_noninterleaved_storage)
{
    // two stores to the same location should be replaced by only one store, even if we
    // read in the meantime
    AssemblyItems input{
        u256(7),
        Instruction::DUP2,
        Instruction::SSTORE,
        Instruction::DUP1,
        Instruction::SLOAD,
        u256(8),
        Instruction::DUP3,
        Instruction::SSTORE
    };
    checkCSE(input, {
        u256(8),
        Instruction::DUP2,
        Instruction::SSTORE,
        u256(7)
    });
}

BOOST_AUTO_TEST_CASE(cse_interleaved_storage)
{
    // stores and reads to/from two unknown locations, should not optimize away the first store
    AssemblyItems input{
        u256(7),
        Instruction::DUP2,
        Instruction::SSTORE, // store to "DUP1"
        Instruction::DUP2,
        Instruction::SLOAD, // read from "DUP2", might be equal to "DUP1"
        u256(0),
        Instruction::DUP3,
        Instruction::SSTORE // store different value to "DUP1"
    };
    checkCSE(input, input);
}

BOOST_AUTO_TEST_CASE(cse_interleaved_storage_same_value)
{
    // stores and reads to/from two unknown locations, should not optimize away the first store
    // but it should optimize away the second, since we already know the value will be the same
    AssemblyItems input{
        u256(7),
        Instruction::DUP2,
        Instruction::SSTORE, // store to "DUP1"
        Instruction::DUP2,
        Instruction::SLOAD, // read from "DUP2", might be equal to "DUP1"
        u256(6),
        u256(1),
        Instruction::ADD,
        Instruction::DUP3,
        Instruction::SSTORE // store same value to "DUP1"
    };
    checkCSE(input, {
        u256(7),
        Instruction::DUP2,
        Instruction::SSTORE,
        Instruction::DUP2,
        Instruction::SLOAD
    });
}

BOOST_AUTO_TEST_CASE(cse_interleaved_storage_at_known_location)
{
    // stores and reads to/from two known locations, should optimize away the first store,
    // because we know that the location is different
    AssemblyItems input{
        u256(0x70),
        u256(1),
        Instruction::SSTORE, // store to 1
        u256(2),
        Instruction::SLOAD, // read from 2, is different from 1
        u256(0x90),
        u256(1),
        Instruction::SSTORE // store different value at 1
    };
    checkCSE(input, {
        u256(2),
        Instruction::SLOAD,
        u256(0x90),
        u256(1),
        Instruction::SSTORE
    });
}

BOOST_AUTO_TEST_CASE(cse_interleaved_storage_at_known_location_offset)
{
    // stores and reads to/from two locations which are known to be different,
    // should optimize away the first store, because we know that the location is different
    AssemblyItems input{
        u256(0x70),
        Instruction::DUP2,
        u256(1),
        Instruction::ADD,
        Instruction::SSTORE, // store to "DUP1"+1
        Instruction::DUP1,
        u256(2),
        Instruction::ADD,
        Instruction::SLOAD, // read from "DUP1"+2, is different from "DUP1"+1
        u256(0x90),
        Instruction::DUP3,
        u256(1),
        Instruction::ADD,
        Instruction::SSTORE // store different value at "DUP1"+1
    };
    checkCSE(input, {
        u256(2),
        Instruction::DUP2,
        Instruction::ADD,
        Instruction::SLOAD,
        u256(0x90),
        u256(1),
        Instruction::DUP4,
        Instruction::ADD,
        Instruction::SSTORE
    });
}

BOOST_AUTO_TEST_CASE(cse_interleaved_memory_at_known_location_offset)
{
    // stores and reads to/from two locations which are known to be different,
    // should not optimize away the first store, because the location overlaps with the load,
    // but it should optimize away the second, because we know that the location is different by 32
    AssemblyItems input{
        u256(0x50),
        Instruction::DUP2,
        u256(2),
        Instruction::ADD,
        Instruction::MSTORE, // ["DUP1"+2] = 0x50
        u256(0x60),
        Instruction::DUP2,
        u256(32),
        Instruction::ADD,
        Instruction::MSTORE, // ["DUP1"+32] = 0x60
        Instruction::DUP1,
        Instruction::MLOAD, // read from "DUP1"
        u256(0x70),
        Instruction::DUP3,
        u256(32),
        Instruction::ADD,
        Instruction::MSTORE, // ["DUP1"+32] = 0x70
        u256(0x80),
        Instruction::DUP3,
        u256(2),
        Instruction::ADD,
        Instruction::MSTORE, // ["DUP1"+2] = 0x80
    };
    // If the actual code changes too much, we could also simply check that the output contains
    // exactly 3 MSTORE and exactly 1 MLOAD instruction.
    checkCSE(input, {
        u256(0x50),
        u256(2),
        Instruction::DUP3,
        Instruction::ADD,
        Instruction::SWAP1,
        Instruction::DUP2,
        Instruction::MSTORE, // ["DUP1"+2] = 0x50
        Instruction::DUP2,
        Instruction::MLOAD, // read from "DUP1"
        u256(0x70),
        u256(32),
        Instruction::DUP5,
        Instruction::ADD,
        Instruction::MSTORE, // ["DUP1"+32] = 0x70
        u256(0x80),
        Instruction::SWAP1,
        Instruction::SWAP2,
        Instruction::MSTORE // ["DUP1"+2] = 0x80
    });
}

BOOST_AUTO_TEST_CASE(cse_deep_stack)
{
    AssemblyItems input{
        Instruction::ADD,
        Instruction::SWAP1,
        Instruction::POP,
        Instruction::SWAP8,
        Instruction::POP,
        Instruction::SWAP8,
        Instruction::POP,
        Instruction::SWAP8,
        Instruction::SWAP5,
        Instruction::POP,
        Instruction::POP,
        Instruction::POP,
        Instruction::POP,
        Instruction::POP,
    };
    checkCSE(input, {
        Instruction::SWAP4,
        Instruction::SWAP12,
        Instruction::SWAP3,
        Instruction::SWAP11,
        Instruction::POP,
        Instruction::SWAP1,
        Instruction::SWAP3,
        Instruction::ADD,
        Instruction::SWAP8,
        Instruction::POP,
        Instruction::SWAP6,
        Instruction::POP,
        Instruction::POP,
        Instruction::POP,
        Instruction::POP,
        Instruction::POP,
        Instruction::POP,
    });
}

BOOST_AUTO_TEST_CASE(cse_jumpi_no_jump)
{
    AssemblyItems input{
        u256(0),
        u256(1),
        Instruction::DUP2,
        AssemblyItem(PushTag, 1),
        Instruction::JUMPI
    };
    checkCSE(input, {
        u256(0),
        u256(1)
    });
}

BOOST_AUTO_TEST_CASE(cse_jumpi_jump)
{
    AssemblyItems input{
        u256(1),
        u256(1),
        Instruction::DUP2,
        AssemblyItem(PushTag, 1),
        Instruction::JUMPI
    };
    checkCSE(input, {
        u256(1),
        Instruction::DUP1,
        AssemblyItem(PushTag, 1),
        Instruction::JUMP
    });
}

BOOST_AUTO_TEST_CASE(cse_empty_sha3)
{
    AssemblyItems input{
        u256(0),
        Instruction::DUP2,
        Instruction::SHA3
    };
    checkCSE(input, {
        u256(sha3(bytesConstRef()))
    });
}

BOOST_AUTO_TEST_CASE(cse_partial_sha3)
{
    AssemblyItems input{
        u256(0xabcd) << (256 - 16),
        u256(0),
        Instruction::MSTORE,
        u256(2),
        u256(0),
        Instruction::SHA3
    };
    checkCSE(input, {
        u256(0xabcd) << (256 - 16),
        u256(0),
        Instruction::MSTORE,
        u256(sha3(bytes{0xab, 0xcd}))
    });
}

BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_location)
{
    // sha3 twice from same dynamic location
    AssemblyItems input{
        Instruction::DUP2,
        Instruction::DUP1,
        Instruction::MSTORE,
        u256(64),
        Instruction::DUP2,
        Instruction::SHA3,
        u256(64),
        Instruction::DUP3,
        Instruction::SHA3
    };
    checkCSE(input, {
        Instruction::DUP2,
        Instruction::DUP1,
        Instruction::MSTORE,
        u256(64),
        Instruction::DUP2,
        Instruction::SHA3,
        Instruction::DUP1
    });
}

BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_content)
{
    // sha3 twice from different dynamic location but with same content
    AssemblyItems input{
        Instruction::DUP1,
        u256(0x80),
        Instruction::MSTORE, // m[128] = DUP1
        u256(0x20),
        u256(0x80),
        Instruction::SHA3, // sha3(m[128..(128+32)])
        Instruction::DUP2,
        u256(12),
        Instruction::MSTORE, // m[12] = DUP1
        u256(0x20),
        u256(12),
        Instruction::SHA3 // sha3(m[12..(12+32)])
    };
    checkCSE(input, {
        u256(0x80),
        Instruction::DUP2,
        Instruction::DUP2,
        Instruction::MSTORE,
        u256(0x20),
        Instruction::SWAP1,
        Instruction::SHA3,
        u256(12),
        Instruction::DUP3,
        Instruction::SWAP1,
        Instruction::MSTORE,
        Instruction::DUP1
    });
}

BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_content_dynamic_store_in_between)
{
    // sha3 twice from different dynamic location but with same content,
    // dynamic mstore in between, which forces us to re-calculate the sha3
    AssemblyItems input{
        u256(0x80),
        Instruction::DUP2,
        Instruction::DUP2,
        Instruction::MSTORE, // m[128] = DUP1
        u256(0x20),
        Instruction::DUP1,
        Instruction::DUP3,
        Instruction::SHA3, // sha3(m[128..(128+32)])
        u256(12),
        Instruction::DUP5,
        Instruction::DUP2,
        Instruction::MSTORE, // m[12] = DUP1
        Instruction::DUP12,
        Instruction::DUP14,
        Instruction::MSTORE, // destroys memory knowledge
        Instruction::SWAP2,
        Instruction::SWAP1,
        Instruction::SWAP2,
        Instruction::SHA3 // sha3(m[12..(12+32)])
    };
    checkCSE(input, input);
}

BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_content_noninterfering_store_in_between)
{
    // sha3 twice from different dynamic location but with same content,
    // dynamic mstore in between, but does not force us to re-calculate the sha3
    AssemblyItems input{
        u256(0x80),
        Instruction::DUP2,
        Instruction::DUP2,
        Instruction::MSTORE, // m[128] = DUP1
        u256(0x20),
        Instruction::DUP1,
        Instruction::DUP3,
        Instruction::SHA3, // sha3(m[128..(128+32)])
        u256(12),
        Instruction::DUP5,
        Instruction::DUP2,
        Instruction::MSTORE, // m[12] = DUP1
        Instruction::DUP12,
        u256(12 + 32),
        Instruction::MSTORE, // does not destoy memory knowledge
        Instruction::DUP13,
        u256(128 - 32),
        Instruction::MSTORE, // does not destoy memory knowledge
        u256(0x20),
        u256(12),
        Instruction::SHA3 // sha3(m[12..(12+32)])
    };
    // if this changes too often, only count the number of SHA3 and MSTORE instructions
    AssemblyItems output = CSE(input);
    BOOST_CHECK_EQUAL(4, count(output.begin(), output.end(), AssemblyItem(Instruction::MSTORE)));
    BOOST_CHECK_EQUAL(1, count(output.begin(), output.end(), AssemblyItem(Instruction::SHA3)));
}

BOOST_AUTO_TEST_CASE(cse_with_initially_known_stack)
{
    eth::KnownState state = createInitialState(AssemblyItems{
        u256(0x12),
        u256(0x20),
        Instruction::ADD
    });
    AssemblyItems input{
        u256(0x12 + 0x20)
    };
    checkCSE(input, AssemblyItems{Instruction::DUP1}, state);
}

BOOST_AUTO_TEST_CASE(cse_equality_on_initially_known_stack)
{
    eth::KnownState state = createInitialState(AssemblyItems{Instruction::DUP1});
    AssemblyItems input{
        Instruction::EQ
    };
    AssemblyItems output = CSE(input, state);
    // check that it directly pushes 1 (true)
    BOOST_CHECK(find(output.begin(), output.end(), AssemblyItem(u256(1))) != output.end());
}

BOOST_AUTO_TEST_CASE(cse_access_previous_sequence)
{
    // Tests that the code generator detects whether it tries to access SLOAD instructions
    // from a sequenced expression which is not in its scope.
    eth::KnownState state = createInitialState(AssemblyItems{
        u256(0),
        Instruction::SLOAD,
        u256(1),
        Instruction::ADD,
        u256(0),
        Instruction::SSTORE
    });
    // now stored: val_1 + 1 (value at sequence 1)
    // if in the following instructions, the SLOAD cresolves to "val_1 + 1",
    // this cannot be generated because we cannot load from sequence 1 anymore.
    AssemblyItems input{
        u256(0),
        Instruction::SLOAD,
    };
    BOOST_CHECK_THROW(CSE(input, state), StackTooDeepException);
    // @todo for now, this throws an exception, but it should recover to the following
    // (or an even better version) at some point:
    // 0, SLOAD, 1, ADD, SSTORE, 0 SLOAD
}

BOOST_AUTO_TEST_CASE(cse_optimise_return)
{
    checkCSE(
        AssemblyItems{u256(0), u256(7), Instruction::RETURN},
        AssemblyItems{Instruction::STOP}
    );
}

BOOST_AUTO_TEST_CASE(control_flow_graph_remove_unused)
{
    // remove parts of the code that are unused
    AssemblyItems input{
        AssemblyItem(PushTag, 1),
        Instruction::JUMP,
        u256(7),
        AssemblyItem(Tag, 1),
    };
    checkCFG(input, {});
}

BOOST_AUTO_TEST_CASE(control_flow_graph_remove_unused_loop)
{
    AssemblyItems input{
        AssemblyItem(PushTag, 3),
        Instruction::JUMP,
        AssemblyItem(Tag, 1),
        u256(7),
        AssemblyItem(PushTag, 2),
        Instruction::JUMP,
        AssemblyItem(Tag, 2),
        u256(8),
        AssemblyItem(PushTag, 1),
        Instruction::JUMP,
        AssemblyItem(Tag, 3),
        u256(11)
    };
    checkCFG(input, {u256(11)});
}

BOOST_AUTO_TEST_CASE(control_flow_graph_reconnect_single_jump_source)
{
    // move code that has only one unconditional jump source
    AssemblyItems input{
        u256(1),
        AssemblyItem(PushTag, 1),
        Instruction::JUMP,
        AssemblyItem(Tag, 2),
        u256(2),
        AssemblyItem(PushTag, 3),
        Instruction::JUMP,
        AssemblyItem(Tag, 1),
        u256(3),
        AssemblyItem(PushTag, 2),
        Instruction::JUMP,
        AssemblyItem(Tag, 3),
        u256(4),
    };
    checkCFG(input, {u256(1), u256(3), u256(2), u256(4)});
}

BOOST_AUTO_TEST_CASE(control_flow_graph_do_not_remove_returned_to)
{
    // do not remove parts that are "returned to"
    AssemblyItems input{
        AssemblyItem(PushTag, 1),
        AssemblyItem(PushTag, 2),
        Instruction::JUMP,
        AssemblyItem(Tag, 2),
        Instruction::JUMP,
        AssemblyItem(Tag, 1),
        u256(2)
    };
    checkCFG(input, {u256(2)});
}

BOOST_AUTO_TEST_CASE(block_deduplicator)
{
    AssemblyItems input{
        AssemblyItem(PushTag, 2),
        AssemblyItem(PushTag, 1),
        AssemblyItem(PushTag, 3),
        u256(6),
        Instruction::SWAP3,
        Instruction::JUMP,
        AssemblyItem(Tag, 1),
        u256(6),
        Instruction::SWAP3,
        Instruction::JUMP,
        AssemblyItem(Tag, 2),
        u256(6),
        Instruction::SWAP3,
        Instruction::JUMP,
        AssemblyItem(Tag, 3)
    };
    BlockDeduplicator dedup(input);
    dedup.deduplicate();

    set<u256> pushTags;
    for (AssemblyItem const& item: input)
        if (item.type() == PushTag)
            pushTags.insert(item.data());
    BOOST_CHECK_EQUAL(pushTags.size(), 2);
}

BOOST_AUTO_TEST_CASE(block_deduplicator_loops)
{
    AssemblyItems input{
        u256(0),
        Instruction::SLOAD,
        AssemblyItem(PushTag, 1),
        AssemblyItem(PushTag, 2),
        Instruction::JUMPI,
        Instruction::JUMP,
        AssemblyItem(Tag, 1),
        u256(5),
        u256(6),
        Instruction::SSTORE,
        AssemblyItem(PushTag, 1),
        Instruction::JUMP,
        AssemblyItem(Tag, 2),
        u256(5),
        u256(6),
        Instruction::SSTORE,
        AssemblyItem(PushTag, 2),
        Instruction::JUMP,
    };
    BlockDeduplicator dedup(input);
    dedup.deduplicate();

    set<u256> pushTags;
    for (AssemblyItem const& item: input)
        if (item.type() == PushTag)
            pushTags.insert(item.data());
    BOOST_CHECK_EQUAL(pushTags.size(), 1);
}

BOOST_AUTO_TEST_CASE(computing_constants)
{
    char const* sourceCode = R"(
        contract c {
            uint a;
            uint b;
            uint c;
            function set() returns (uint a, uint b, uint c) {
                a = 0x77abc0000000000000000000000000000000000000000000000000000000001;
                b = 0x817416927846239487123469187231298734162934871263941234127518276;
                g();
            }
            function g() {
                b = 0x817416927846239487123469187231298734162934871263941234127518276;
                c = 0x817416927846239487123469187231298734162934871263941234127518276;
            }
            function get() returns (uint ra, uint rb, uint rc) {
                ra = a;
                rb = b;
                rc = c ;
            }
        }
    )";
    compileBothVersions(sourceCode);
    compareVersions("set()");
    compareVersions("get()");

    m_optimize = true;
    m_optimizeRuns = 1;
    bytes optimizedBytecode = compileAndRun(sourceCode, 0, "c");
    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_SUITE_END()

}
}
} // end namespaces