Merge remote-tracking branch 'upstream/develop' into addTests

Conflicts:
	test/ttTransactionTestFiller.json

1 files changed, 452 insertions, 23 deletions

diff --git a/SolidityOptimizer.cpp b/SolidityOptimizer.cpp
index 85b77d21..e69d5120 100644
--- a/SolidityOptimizer.cpp
+++ b/SolidityOptimizer.cpp
@@ -26,8 +26,11 @@
 #include <boost/test/unit_test.hpp>
 #include <boost/lexical_cast.hpp>
 #include <test/solidityExecutionFramework.h>
+#include <libevmcore/CommonSubexpressionEliminator.h>
+#include <libevmcore/Assembly.h>
 
 using namespace std;
+using namespace dev::eth;
 
 namespace dev
 {
@@ -41,16 +44,21 @@ class OptimizerTestFramework: public ExecutionFramework
 public:
 	OptimizerTestFramework() { }
 	/// Compiles the source code with and without optimizing.
-	void compileBothVersions(unsigned _expectedSizeDecrease, std::string const& _sourceCode, u256 const& _value = 0, std::string const& _contractName = "") {
+	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);
-		int sizeDiff = nonOptimizedBytecode.size() - optimizedBytecode.size();
-		BOOST_CHECK_MESSAGE(sizeDiff == int(_expectedSizeDecrease), "Bytecode shrank by "
-							+ boost::lexical_cast<string>(sizeDiff) + " bytes, expected: "
-							+ boost::lexical_cast<string>(_expectedSizeDecrease));
+		BOOST_CHECK_MESSAGE(
+			nonOptimizedBytecode.size() > optimizedBytecode.size(),
+			"Optimizer did not reduce bytecode size."
+		);
 		m_optimizedContract = m_contractAddress;
 	}
 
@@ -66,6 +74,14 @@ public:
 							"\nOptimized:     " + toHex(optimizedOutput));
 	}
 
+	void checkCSE(AssemblyItems const& _input, AssemblyItems const& _expectation)
+	{
+		eth::CommonSubexpressionEliminator cse;
+		BOOST_REQUIRE(cse.feedItems(_input.begin(), _input.end()) == _input.end());
+		AssemblyItems output = cse.getOptimizedItems();
+		BOOST_CHECK_EQUAL_COLLECTIONS(_expectation.begin(), _expectation.end(), output.begin(), output.end());
+	}
+
 protected:
 	Address m_optimizedContract;
 	Address m_nonOptimizedContract;
@@ -81,24 +97,11 @@ BOOST_AUTO_TEST_CASE(smoke_test)
 				return a;
 			}
 		})";
-	compileBothVersions(29, sourceCode);
+	compileBothVersions(sourceCode);
 	compareVersions("f(uint256)", u256(7));
 }
 
-BOOST_AUTO_TEST_CASE(large_integers)
-{
-	char const* sourceCode = R"(
-		contract test {
-			function f() returns (uint a, uint b) {
-				a = 0x234234872642837426347000000;
-				b = 0x10000000000000000000000002;
-			}
-		})";
-	compileBothVersions(36, sourceCode);
-	compareVersions("f()");
-}
-
-BOOST_AUTO_TEST_CASE(invariants)
+BOOST_AUTO_TEST_CASE(identities)
 {
 	char const* sourceCode = R"(
 		contract test {
@@ -106,7 +109,7 @@ BOOST_AUTO_TEST_CASE(invariants)
 				return int(0) | (int(1) * (int(0) ^ (0 + a)));
 			}
 		})";
-	compileBothVersions(41, sourceCode);
+	compileBothVersions(sourceCode);
 	compareVersions("f(uint256)", u256(0x12334664));
 }
 
@@ -120,7 +123,7 @@ BOOST_AUTO_TEST_CASE(unused_expressions)
 				data;
 			}
 		})";
-	compileBothVersions(36, sourceCode);
+	compileBothVersions(sourceCode);
 	compareVersions("f()");
 }
 
@@ -135,10 +138,436 @@ BOOST_AUTO_TEST_CASE(constant_folding_both_sides)
 				return 98 ^ (7 * ((1 | (x | 1000)) * 40) ^ 102);
 			}
 		})";
-	compileBothVersions(37, sourceCode);
+	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) {
+				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)", 36);
+}
+
+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(cse_intermediate_swap)
+{
+	eth::CommonSubexpressionEliminator cse;
+	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_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_SUITE_END()
 
 }