Merge pull request #3690 from ethereum/incrementArraySize

More specific push implementation.

6 files changed, 139 insertions, 15 deletions

diff --git a/Changelog.md b/Changelog.md
index 9618dfa7..0db5df96 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -2,6 +2,7 @@
 
 Features:
  * Code Generator: Initialize arrays without using ``msize()``.
+ * Code Generator: More specialized and thus optimized implementation for ``x.push(...)``
  * Commandline interface: Error when missing or inaccessible file detected. Suppress it with the ``--ignore-missing`` flag.
  * General: Support accessing dynamic return data in post-byzantium EVMs.
  * Interfaces: Allow overriding external functions in interfaces with public in an implementing contract.
diff --git a/libsolidity/codegen/ArrayUtils.cpp b/libsolidity/codegen/ArrayUtils.cpp
index 4703fc1f..0fe66d2d 100644
--- a/libsolidity/codegen/ArrayUtils.cpp
+++ b/libsolidity/codegen/ArrayUtils.cpp
@@ -774,6 +774,55 @@ void ArrayUtils::resizeDynamicArray(ArrayType const& _typeIn) const
 	);
 }
 
+void ArrayUtils::incrementDynamicArraySize(ArrayType const& _type) const
+{
+	solAssert(_type.location() == DataLocation::Storage, "");
+	solAssert(_type.isDynamicallySized(), "");
+	if (!_type.isByteArray() && _type.baseType()->storageBytes() < 32)
+		solAssert(_type.baseType()->isValueType(), "Invalid storage size for non-value type.");
+
+	if (_type.isByteArray())
+	{
+		// We almost always just add 2 (length of byte arrays is shifted left by one)
+		// except for the case where we transition from a short byte array
+		// to a long byte array, there we have to copy.
+		// This happens if the length is exactly 31, which means that the
+		// lowest-order byte (we actually use a mask with fewer bits) must
+		// be (31*2+0) = 62
+
+		m_context.appendInlineAssembly(R"({
+			let data := sload(ref)
+			let shifted_length := and(data, 63)
+			// We have to copy if length is exactly 31, because that marks
+			// the transition between in-place and out-of-place storage.
+			switch shifted_length
+			case 62
+			{
+				mstore(0, ref)
+				let data_area := keccak256(0, 0x20)
+				sstore(data_area, and(data, not(0xff)))
+				// New length is 32, encoded as (32 * 2 + 1)
+				sstore(ref, 65)
+				// Replace ref variable by new length
+				ref := 32
+			}
+			default
+			{
+				sstore(ref, add(data, 2))
+				// Replace ref variable by new length
+				if iszero(and(data, 1)) { data := shifted_length }
+				ref := add(div(data, 2), 1)
+			}
+		})", {"ref"});
+	}
+	else
+		m_context.appendInlineAssembly(R"({
+			let new_length := add(sload(ref), 1)
+			sstore(ref, new_length)
+			ref := new_length
+		})", {"ref"});
+}
+
 void ArrayUtils::clearStorageLoop(TypePointer const& _type) const
 {
 	m_context.callLowLevelFunction(
diff --git a/libsolidity/codegen/ArrayUtils.h b/libsolidity/codegen/ArrayUtils.h
index f3ddc4ee..99786397 100644
--- a/libsolidity/codegen/ArrayUtils.h
+++ b/libsolidity/codegen/ArrayUtils.h
@@ -67,6 +67,12 @@ public:
 	/// Stack pre: reference (excludes byte offset) new_length
 	/// Stack post:
 	void resizeDynamicArray(ArrayType const& _type) const;
+	/// Increments the size of a dynamic array by one.
+	/// Does not touch the new data element. In case of a byte array, this might move the
+	/// data.
+	/// Stack pre: reference (excludes byte offset)
+	/// Stack post: new_length
+	void incrementDynamicArraySize(ArrayType const& _type) const;
 	/// Appends a loop that clears a sequence of storage slots of the given type (excluding end).
 	/// Stack pre: end_ref start_ref
 	/// Stack post: end_ref
diff --git a/libsolidity/codegen/ExpressionCompiler.cpp b/libsolidity/codegen/ExpressionCompiler.cpp
index 76aa6843..57d49ac6 100644
--- a/libsolidity/codegen/ExpressionCompiler.cpp
+++ b/libsolidity/codegen/ExpressionCompiler.cpp
@@ -821,24 +821,27 @@ bool ExpressionCompiler::visit(FunctionCall const& _functionCall)
 				function.kind() == FunctionType::Kind::ArrayPush ?
 				make_shared<ArrayType>(DataLocation::Storage, paramType) :
 				make_shared<ArrayType>(DataLocation::Storage);
-			// get the current length
-			ArrayUtils(m_context).retrieveLength(*arrayType);
-			m_context << Instruction::DUP1;
-			// stack: ArrayReference currentLength currentLength
-			m_context << u256(1) << Instruction::ADD;
-			// stack: ArrayReference currentLength newLength
-			m_context << Instruction::DUP3 << Instruction::DUP2;
-			ArrayUtils(m_context).resizeDynamicArray(*arrayType);
-			m_context << Instruction::SWAP2 << Instruction::SWAP1;
-			// stack: newLength ArrayReference oldLength
-			ArrayUtils(m_context).accessIndex(*arrayType, false);
 
-			// stack: newLength storageSlot slotOffset
+			// stack: ArrayReference
 			arguments[0]->accept(*this);
+			TypePointer const& argType = arguments[0]->annotation().type;
+			// stack: ArrayReference argValue
+			utils().moveToStackTop(argType->sizeOnStack(), 1);
+			// stack: argValue ArrayReference
+			m_context << Instruction::DUP1;
+			ArrayUtils(m_context).incrementDynamicArraySize(*arrayType);
+			// stack: argValue ArrayReference newLength
+			m_context << Instruction::SWAP1;
+			// stack: argValue newLength ArrayReference
+			m_context << u256(1) << Instruction::DUP3 << Instruction::SUB;
+			// stack: argValue newLength ArrayReference (newLength-1)
+			ArrayUtils(m_context).accessIndex(*arrayType, false);
+			// stack: argValue newLength storageSlot slotOffset
+			utils().moveToStackTop(3, argType->sizeOnStack());
 			// stack: newLength storageSlot slotOffset argValue
 			TypePointer type = arguments[0]->annotation().type->closestTemporaryType(arrayType->baseType());
 			solAssert(type, "");
-			utils().convertType(*arguments[0]->annotation().type, *type);
+			utils().convertType(*argType, *type);
 			utils().moveToStackTop(1 + type->sizeOnStack());
 			utils().moveToStackTop(1 + type->sizeOnStack());
 			// stack: newLength argValue storageSlot slotOffset
diff --git a/test/libsolidity/SolidityEndToEndTest.cpp b/test/libsolidity/SolidityEndToEndTest.cpp
index b58ebee4..07aa437e 100644
--- a/test/libsolidity/SolidityEndToEndTest.cpp
+++ b/test/libsolidity/SolidityEndToEndTest.cpp
@@ -4884,6 +4884,48 @@ BOOST_AUTO_TEST_CASE(array_push)
 	ABI_CHECK(callContractFunction("test()"), encodeArgs(5, 4, 3, 3));
 }
 
+BOOST_AUTO_TEST_CASE(array_push_struct)
+{
+	char const* sourceCode = R"(
+		contract c {
+			struct S { uint16 a; uint16 b; uint16[3] c; uint16[] d; }
+			S[] data;
+			function test() returns (uint16, uint16, uint16, uint16) {
+				S memory s;
+				s.a = 2;
+				s.b = 3;
+				s.c[2] = 4;
+				s.d = new uint16[](4);
+				s.d[2] = 5;
+				data.push(s);
+				return (data[0].a, data[0].b, data[0].c[2], data[0].d[2]);
+			}
+		}
+	)";
+	compileAndRun(sourceCode);
+	ABI_CHECK(callContractFunction("test()"), encodeArgs(2, 3, 4, 5));
+}
+
+BOOST_AUTO_TEST_CASE(array_push_packed_array)
+{
+	char const* sourceCode = R"(
+		contract c {
+			uint80[] x;
+			function test() returns (uint80, uint80, uint80, uint80) {
+				x.push(1);
+				x.push(2);
+				x.push(3);
+				x.push(4);
+				x.push(5);
+				x.length = 4;
+				return (x[0], x[1], x[2], x[3]);
+			}
+		}
+	)";
+	compileAndRun(sourceCode);
+	ABI_CHECK(callContractFunction("test()"), encodeArgs(1, 2, 3, 4));
+}
+
 BOOST_AUTO_TEST_CASE(byte_array_push)
 {
 	char const* sourceCode = R"(
@@ -4904,6 +4946,29 @@ BOOST_AUTO_TEST_CASE(byte_array_push)
 	ABI_CHECK(callContractFunction("test()"), encodeArgs(false));
 }
 
+BOOST_AUTO_TEST_CASE(byte_array_push_transition)
+{
+	// Tests transition between short and long encoding
+	char const* sourceCode = R"(
+		contract c {
+			bytes data;
+			function test() returns (uint) {
+				for (uint i = 1; i < 40; i++)
+				{
+					data.push(byte(i));
+					if (data.length != i) return 0x1000 + i;
+					if (data[data.length - 1] != byte(i)) return i;
+				}
+				for (i = 1; i < 40; i++)
+					if (data[i - 1] != byte(i)) return 0x1000000 + i;
+				return 0;
+			}
+		}
+	)";
+	compileAndRun(sourceCode);
+	ABI_CHECK(callContractFunction("test()"), encodeArgs(0));
+}
+
 BOOST_AUTO_TEST_CASE(external_array_args)
 {
 	char const* sourceCode = R"(
diff --git a/test/libsolidity/SolidityOptimizer.cpp b/test/libsolidity/SolidityOptimizer.cpp
index a0df76f3..5326feaf 100644
--- a/test/libsolidity/SolidityOptimizer.cpp
+++ b/test/libsolidity/SolidityOptimizer.cpp
@@ -627,8 +627,8 @@ BOOST_AUTO_TEST_CASE(optimise_multi_stores)
 	)";
 	compileBothVersions(sourceCode);
 	compareVersions("f()");
-	BOOST_CHECK_EQUAL(numInstructions(m_nonOptimizedBytecode, Instruction::SSTORE), 13);
-	BOOST_CHECK_EQUAL(numInstructions(m_optimizedBytecode, Instruction::SSTORE), 11);
+	BOOST_CHECK_EQUAL(numInstructions(m_nonOptimizedBytecode, Instruction::SSTORE), 9);
+	BOOST_CHECK_EQUAL(numInstructions(m_optimizedBytecode, Instruction::SSTORE), 8);
 }
 
 BOOST_AUTO_TEST_SUITE_END()