Create empty dynamic memory arrays more efficiently.

8 files changed, 107 insertions, 20 deletions

diff --git a/docs/assembly.rst b/docs/assembly.rst
index cf9bf840..705cd1b8 100644
--- a/docs/assembly.rst
+++ b/docs/assembly.rst
@@ -647,6 +647,11 @@ Solidity manages memory in a very simple way: There is a "free memory pointer"
 at position ``0x40`` in memory. If you want to allocate memory, just use the memory
 from that point on and update the pointer accordingly.
 
+The first 64 bytes of memory can be used as "scratch space" for short-term
+allocation. The 32 bytes after the free memory pointer (i.e. starting at ``0x60``)
+is meant to be zero permanently and is used as the initial value for
+empty dynamic memory arrays.
+
 Elements in memory arrays in Solidity always occupy multiples of 32 bytes (yes, this is
 even true for ``byte[]``, but not for ``bytes`` and ``string``). Multi-dimensional memory
 arrays are pointers to memory arrays. The length of a dynamic array is stored at the
diff --git a/docs/miscellaneous.rst b/docs/miscellaneous.rst
index 01154854..20400aa2 100644
--- a/docs/miscellaneous.rst
+++ b/docs/miscellaneous.rst
@@ -64,12 +64,15 @@ The position of ``data[4][9].b`` is at ``keccak256(uint256(9) . keccak256(uint25
 Layout in Memory
 ****************
 
-Solidity reserves three 256-bit slots:
+Solidity reserves four 32 byte slots:
 
--  0 - 64: scratch space for hashing methods
-- 64 - 96: currently allocated memory size (aka. free memory pointer)
+- ``0x00`` - ``0x3f``: scratch space for hashing methods
+- ``0x40`` - ``0x5f``: currently allocated memory size (aka. free memory pointer)
+- ``0x60`` - ``0x7f``: zero slot
 
-Scratch space can be used between statements (ie. within inline assembly).
+Scratch space can be used between statements (ie. within inline assembly). The zero slot
+is used as initial value for dynamic memory arrays and should never be written to
+(the free memory pointer points to ``0x80`` initially).
 
 Solidity always places new objects at the free memory pointer and memory is never freed (this might change in the future).
 
diff --git a/libsolidity/codegen/CompilerUtils.cpp b/libsolidity/codegen/CompilerUtils.cpp
index deaef017..79aef7b0 100644
--- a/libsolidity/codegen/CompilerUtils.cpp
+++ b/libsolidity/codegen/CompilerUtils.cpp
@@ -21,6 +21,7 @@
  */
 
 #include <libsolidity/codegen/CompilerUtils.h>
+
 #include <libsolidity/ast/AST.h>
 #include <libsolidity/codegen/ArrayUtils.h>
 #include <libsolidity/codegen/LValue.h>
@@ -39,11 +40,17 @@ namespace solidity
 
 const unsigned CompilerUtils::dataStartOffset = 4;
 const size_t CompilerUtils::freeMemoryPointer = 64;
+const size_t CompilerUtils::zeroPointer = CompilerUtils::freeMemoryPointer + 32;
+const size_t CompilerUtils::generalPurposeMemoryStart = CompilerUtils::zeroPointer + 32;
 const unsigned CompilerUtils::identityContractAddress = 4;
 
+static_assert(CompilerUtils::freeMemoryPointer >= 64, "Free memory pointer must not overlap with scratch area.");
+static_assert(CompilerUtils::zeroPointer >= CompilerUtils::freeMemoryPointer + 32, "Zero pointer must not overlap with free memory pointer.");
+static_assert(CompilerUtils::generalPurposeMemoryStart >= CompilerUtils::zeroPointer + 32, "General purpose memory must not overlap with zero area.");
+
 void CompilerUtils::initialiseFreeMemoryPointer()
 {
-	m_context << u256(freeMemoryPointer + 32);
+	m_context << u256(generalPurposeMemoryStart);
 	storeFreeMemoryPointer();
 }
 
@@ -1051,6 +1058,13 @@ void CompilerUtils::pushZeroValue(Type const& _type)
 		return;
 	}
 	solAssert(referenceType->location() == DataLocation::Memory, "");
+	if (auto arrayType = dynamic_cast<ArrayType const*>(&_type))
+		if (arrayType->isDynamicallySized())
+		{
+			// Push a memory location that is (hopefully) always zero.
+			pushZeroPointer();
+			return;
+		}
 
 	TypePointer type = _type.shared_from_this();
 	m_context.callLowLevelFunction(
@@ -1071,13 +1085,8 @@ void CompilerUtils::pushZeroValue(Type const& _type)
 				}
 			else if (auto arrayType = dynamic_cast<ArrayType const*>(type.get()))
 			{
-				if (arrayType->isDynamicallySized())
-				{
-					// zero length
-					_context << u256(0);
-					utils.storeInMemoryDynamic(IntegerType(256));
-				}
-				else if (arrayType->length() > 0)
+				solAssert(!arrayType->isDynamicallySized(), "");
+				if (arrayType->length() > 0)
 				{
 					_context << arrayType->length() << Instruction::SWAP1;
 					// stack: items_to_do memory_pos
@@ -1094,6 +1103,11 @@ void CompilerUtils::pushZeroValue(Type const& _type)
 	);
 }
 
+void CompilerUtils::pushZeroPointer()
+{
+	m_context << u256(zeroPointer);
+}
+
 void CompilerUtils::moveToStackVariable(VariableDeclaration const& _variable)
 {
 	unsigned const stackPosition = m_context.baseToCurrentStackOffset(m_context.baseStackOffsetOfVariable(_variable));
diff --git a/libsolidity/codegen/CompilerUtils.h b/libsolidity/codegen/CompilerUtils.h
index 389673ef..a32c5c6e 100644
--- a/libsolidity/codegen/CompilerUtils.h
+++ b/libsolidity/codegen/CompilerUtils.h
@@ -210,6 +210,9 @@ public:
 	/// Creates a zero-value for the given type and puts it onto the stack. This might allocate
 	/// memory for memory references.
 	void pushZeroValue(Type const& _type);
+	/// Pushes a pointer to the stack that points to a (potentially shared) location in memory
+	/// that always contains a zero. It is not allowed to write there.
+	void pushZeroPointer();
 
 	/// Moves the value that is at the top of the stack to a stack variable.
 	void moveToStackVariable(VariableDeclaration const& _variable);
@@ -255,6 +258,10 @@ public:
 
 	/// Position of the free-memory-pointer in memory;
 	static const size_t freeMemoryPointer;
+	/// Position of the memory slot that is always zero.
+	static const size_t zeroPointer;
+	/// Starting offset for memory available to the user (aka the contract).
+	static const size_t generalPurposeMemoryStart;
 
 private:
 	/// Address of the precompiled identity contract.
diff --git a/test/libsolidity/JSONCompiler.cpp b/test/libsolidity/JSONCompiler.cpp
index aed0a370..cdcc22a6 100644
--- a/test/libsolidity/JSONCompiler.cpp
+++ b/test/libsolidity/JSONCompiler.cpp
@@ -111,12 +111,12 @@ BOOST_AUTO_TEST_CASE(basic_compilation)
 	BOOST_CHECK(contract["bytecode"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["bytecode"].asString()),
-		"60606040523415600e57600080fd5b603580601b6000396000f3006060604052600080fd00"
+		"60806040523415600e57600080fd5b603580601b6000396000f3006080604052600080fd00"
 	);
 	BOOST_CHECK(contract["runtimeBytecode"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["runtimeBytecode"].asString()),
-		"6060604052600080fd00"
+		"6080604052600080fd00"
 	);
 	BOOST_CHECK(contract["functionHashes"].isObject());
 	BOOST_CHECK(contract["gasEstimates"].isObject());
@@ -153,12 +153,12 @@ BOOST_AUTO_TEST_CASE(single_compilation)
 	BOOST_CHECK(contract["bytecode"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["bytecode"].asString()),
-		"60606040523415600e57600080fd5b603580601b6000396000f3006060604052600080fd00"
+		"60806040523415600e57600080fd5b603580601b6000396000f3006080604052600080fd00"
 	);
 	BOOST_CHECK(contract["runtimeBytecode"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["runtimeBytecode"].asString()),
-		"6060604052600080fd00"
+		"6080604052600080fd00"
 	);
 	BOOST_CHECK(contract["functionHashes"].isObject());
 	BOOST_CHECK(contract["gasEstimates"].isObject());
diff --git a/test/libsolidity/SolidityEndToEndTest.cpp b/test/libsolidity/SolidityEndToEndTest.cpp
index 38d3ce4d..b58ebee4 100644
--- a/test/libsolidity/SolidityEndToEndTest.cpp
+++ b/test/libsolidity/SolidityEndToEndTest.cpp
@@ -7687,7 +7687,6 @@ BOOST_AUTO_TEST_CASE(create_memory_array_allocation_size)
 	ABI_CHECK(callContractFunction("f()"), encodeArgs(0x40, 0x40, 0x20 + 256));
 }
 
-
 BOOST_AUTO_TEST_CASE(memory_arrays_of_various_sizes)
 {
 	// Computes binomial coefficients the chinese way
@@ -7710,6 +7709,41 @@ BOOST_AUTO_TEST_CASE(memory_arrays_of_various_sizes)
 	ABI_CHECK(callContractFunction("f(uint256,uint256)", encodeArgs(u256(9), u256(5))), encodeArgs(u256(70)));
 }
 
+BOOST_AUTO_TEST_CASE(create_multiple_dynamic_arrays)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f() returns (uint) {
+				uint[][] memory x = new uint[][](42);
+				assert(x[0].length == 0);
+				x[0] = new uint[](1);
+				x[0][0] = 1;
+				assert(x[4].length == 0);
+				x[4] = new uint[](1);
+				x[4][0] = 2;
+				assert(x[10].length == 0);
+				x[10] = new uint[](1);
+				x[10][0] = 44;
+				uint[][] memory y = new uint[][](24);
+				assert(y[0].length == 0);
+				y[0] = new uint[](1);
+				y[0][0] = 1;
+				assert(y[4].length == 0);
+				y[4] = new uint[](1);
+				y[4][0] = 2;
+				assert(y[10].length == 0);
+				y[10] = new uint[](1);
+				y[10][0] = 88;
+				if ((x[0][0] == y[0][0]) && (x[4][0] == y[4][0]) && (x[10][0] == 44) && (y[10][0] == 88))
+					return 7;
+				return 0;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	ABI_CHECK(callContractFunction("f()"), encodeArgs(u256(7)));
+}
+
 BOOST_AUTO_TEST_CASE(memory_overwrite)
 {
 	char const* sourceCode = R"(
diff --git a/test/libsolidity/SolidityOptimizer.cpp b/test/libsolidity/SolidityOptimizer.cpp
index cf4550c7..a0df76f3 100644
--- a/test/libsolidity/SolidityOptimizer.cpp
+++ b/test/libsolidity/SolidityOptimizer.cpp
@@ -93,8 +93,10 @@ public:
 	{
 		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."
@@ -120,6 +122,8 @@ public:
 	}
 
 protected:
+	u256 m_gasUsedOptimized;
+	u256 m_gasUsedNonOptimized;
 	bytes m_nonOptimizedBytecode;
 	bytes m_optimizedBytecode;
 	Address m_optimizedContract;
@@ -584,6 +588,26 @@ BOOST_AUTO_TEST_CASE(invalid_state_at_control_flow_join)
 	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() 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"(
diff --git a/test/libsolidity/StandardCompiler.cpp b/test/libsolidity/StandardCompiler.cpp
index dd6eb7c4..b285a2a0 100644
--- a/test/libsolidity/StandardCompiler.cpp
+++ b/test/libsolidity/StandardCompiler.cpp
@@ -261,14 +261,14 @@ BOOST_AUTO_TEST_CASE(basic_compilation)
 	BOOST_CHECK(contract["evm"]["bytecode"]["object"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["evm"]["bytecode"]["object"].asString()),
-		"60606040523415600e57600080fd5b603580601b6000396000f3006060604052600080fd00"
+		"60806040523415600e57600080fd5b603580601b6000396000f3006080604052600080fd00"
 	);
 	BOOST_CHECK(contract["evm"]["assembly"].isString());
 	BOOST_CHECK(contract["evm"]["assembly"].asString().find(
-		"    /* \"fileA\":0:14  contract A { } */\n  mstore(0x40, 0x60)\n  jumpi(tag_1, iszero(callvalue))\n"
+		"    /* \"fileA\":0:14  contract A { } */\n  mstore(0x40, 0x80)\n  jumpi(tag_1, iszero(callvalue))\n"
 		"  0x0\n  dup1\n  revert\ntag_1:\n  dataSize(sub_0)\n  dup1\n  dataOffset(sub_0)\n  0x0\n  codecopy\n  0x0\n"
 		"  return\nstop\n\nsub_0: assembly {\n        /* \"fileA\":0:14  contract A { } */\n"
-		"      mstore(0x40, 0x60)\n      0x0\n      dup1\n      revert\n\n"
+		"      mstore(0x40, 0x80)\n      0x0\n      dup1\n      revert\n\n"
 		"    auxdata: 0xa165627a7a7230582") == 0);
 	BOOST_CHECK(contract["evm"]["gasEstimates"].isObject());
 	BOOST_CHECK_EQUAL(