Merge pull request #3892 from ethereum/develop

Merge develop into release for 0.4.22

7 files changed, 73 insertions, 8 deletions

diff --git a/libevmasm/Assembly.cpp b/libevmasm/Assembly.cpp
index bd4ebf59..b71bc80c 100644
--- a/libevmasm/Assembly.cpp
+++ b/libevmasm/Assembly.cpp
@@ -438,13 +438,15 @@ map<u256, u256> Assembly::optimiseInternal(
 			// function types that can be stored in storage.
 			AssemblyItems optimisedItems;
 
+			bool usesMSize = (find(m_items.begin(), m_items.end(), AssemblyItem(Instruction::MSIZE)) != m_items.end());
+
 			auto iter = m_items.begin();
 			while (iter != m_items.end())
 			{
 				KnownState emptyState;
 				CommonSubexpressionEliminator eliminator(emptyState);
 				auto orig = iter;
-				iter = eliminator.feedItems(iter, m_items.end());
+				iter = eliminator.feedItems(iter, m_items.end(), usesMSize);
 				bool shouldReplace = false;
 				AssemblyItems optimisedChunk;
 				try
diff --git a/libevmasm/CommonSubexpressionEliminator.h b/libevmasm/CommonSubexpressionEliminator.h
index 0b957a0e..b20de246 100644
--- a/libevmasm/CommonSubexpressionEliminator.h
+++ b/libevmasm/CommonSubexpressionEliminator.h
@@ -65,8 +65,9 @@ public:
 
 	/// Feeds AssemblyItems into the eliminator and @returns the iterator pointing at the first
 	/// item that must be fed into a new instance of the eliminator.
+	/// @param _msizeImportant if false, do not consider modification of MSIZE a side-effect
 	template <class _AssemblyItemIterator>
-	_AssemblyItemIterator feedItems(_AssemblyItemIterator _iterator, _AssemblyItemIterator _end);
+	_AssemblyItemIterator feedItems(_AssemblyItemIterator _iterator, _AssemblyItemIterator _end, bool _msizeImportant);
 
 	/// @returns the resulting items after optimization.
 	AssemblyItems getOptimizedItems();
@@ -168,11 +169,12 @@ private:
 template <class _AssemblyItemIterator>
 _AssemblyItemIterator CommonSubexpressionEliminator::feedItems(
 	_AssemblyItemIterator _iterator,
-	_AssemblyItemIterator _end
+	_AssemblyItemIterator _end,
+	bool _msizeImportant
 )
 {
 	assertThrow(!m_breakingItem, OptimizerException, "Invalid use of CommonSubexpressionEliminator.");
-	for (; _iterator != _end && !SemanticInformation::breaksCSEAnalysisBlock(*_iterator); ++_iterator)
+	for (; _iterator != _end && !SemanticInformation::breaksCSEAnalysisBlock(*_iterator, _msizeImportant); ++_iterator)
 		feedItem(*_iterator);
 	if (_iterator != _end)
 		m_breakingItem = &(*_iterator++);
diff --git a/libevmasm/Instruction.cpp b/libevmasm/Instruction.cpp
index a677a631..f9bbad2c 100644
--- a/libevmasm/Instruction.cpp
+++ b/libevmasm/Instruction.cpp
@@ -199,7 +199,7 @@ static const std::map<Instruction, InstructionInfo> c_instructionInfo =
 	{ Instruction::ADDMOD,		{ "ADDMOD",			0, 3, 1, false, Tier::Mid } },
 	{ Instruction::MULMOD,		{ "MULMOD",			0, 3, 1, false, Tier::Mid } },
 	{ Instruction::SIGNEXTEND,	{ "SIGNEXTEND",		0, 2, 1, false, Tier::Low } },
-	{ Instruction::KECCAK256,	{ "KECCAK256",			0, 2, 1, false, Tier::Special } },
+	{ Instruction::KECCAK256,	{ "KECCAK256",			0, 2, 1, true, Tier::Special } },
 	{ Instruction::ADDRESS,		{ "ADDRESS",		0, 0, 1, false, Tier::Base } },
 	{ Instruction::BALANCE,		{ "BALANCE",		0, 1, 1, false, Tier::Balance } },
 	{ Instruction::ORIGIN,		{ "ORIGIN",			0, 0, 1, false, Tier::Base } },
diff --git a/libevmasm/PeepholeOptimiser.cpp b/libevmasm/PeepholeOptimiser.cpp
index 168d1109..8a39de24 100644
--- a/libevmasm/PeepholeOptimiser.cpp
+++ b/libevmasm/PeepholeOptimiser.cpp
@@ -154,6 +154,51 @@ struct DoublePush: SimplePeepholeOptimizerMethod<DoublePush, 2>
 	}
 };
 
+struct CommutativeSwap: SimplePeepholeOptimizerMethod<CommutativeSwap, 2>
+{
+	static bool applySimple(AssemblyItem const& _swap, AssemblyItem const& _op, std::back_insert_iterator<AssemblyItems> _out)
+	{
+		// Remove SWAP1 if following instruction is commutative
+		if (
+			_swap.type() == Operation &&
+			_swap.instruction() == Instruction::SWAP1 &&
+			SemanticInformation::isCommutativeOperation(_op)
+		)
+		{
+			*_out = _op;
+			return true;
+		}
+		else
+			return false;
+	}
+};
+
+struct SwapComparison: SimplePeepholeOptimizerMethod<SwapComparison, 2>
+{
+	static bool applySimple(AssemblyItem const& _swap, AssemblyItem const& _op, std::back_insert_iterator<AssemblyItems> _out)
+	{
+		map<Instruction, Instruction> swappableOps{
+			{ Instruction::LT, Instruction::GT },
+			{ Instruction::GT, Instruction::LT },
+			{ Instruction::SLT, Instruction::SGT },
+			{ Instruction::SGT, Instruction::SLT }
+		};
+
+		if (
+			_swap.type() == Operation &&
+			_swap.instruction() == Instruction::SWAP1 &&
+			_op.type() == Operation &&
+			swappableOps.count(_op.instruction())
+		)
+		{
+			*_out = swappableOps.at(_op.instruction());
+			return true;
+		}
+		else
+			return false;
+	}
+};
+
 struct JumpToNext: SimplePeepholeOptimizerMethod<JumpToNext, 3>
 {
 	static size_t applySimple(
@@ -260,7 +305,7 @@ bool PeepholeOptimiser::optimise()
 {
 	OptimiserState state {m_items, 0, std::back_inserter(m_optimisedItems)};
 	while (state.i < m_items.size())
-		applyMethods(state, PushPop(), OpPop(), DoublePush(), DoubleSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity());
+		applyMethods(state, PushPop(), OpPop(), DoublePush(), DoubleSwap(), CommutativeSwap(), SwapComparison(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity());
 	if (m_optimisedItems.size() < m_items.size() || (
 		m_optimisedItems.size() == m_items.size() && (
 			eth::bytesRequired(m_optimisedItems, 3) < eth::bytesRequired(m_items, 3) ||
diff --git a/libevmasm/RuleList.h b/libevmasm/RuleList.h
index da522cec..abcf170c 100644
--- a/libevmasm/RuleList.h
+++ b/libevmasm/RuleList.h
@@ -89,6 +89,16 @@ std::vector<SimplificationRule<Pattern>> simplificationRuleList(
 			u256 mask = (u256(1) << testBit) - 1;
 			return u256(boost::multiprecision::bit_test(B.d(), testBit) ? B.d() | ~mask : B.d() & mask);
 		}, false},
+		{{Instruction::SHL, {A, B}}, [=]{
+			if (A.d() > 255)
+				return u256(0);
+			return u256(bigint(B.d()) << unsigned(A.d()));
+		}, false},
+		{{Instruction::SHR, {A, B}}, [=]{
+			if (A.d() > 255)
+				return u256(0);
+			return B.d() >> unsigned(A.d());
+		}, false},
 
 		// invariants involving known constants
 		{{Instruction::ADD, {X, 0}}, [=]{ return X; }, false},
diff --git a/libevmasm/SemanticInformation.cpp b/libevmasm/SemanticInformation.cpp
index 03870f7c..71267ee8 100644
--- a/libevmasm/SemanticInformation.cpp
+++ b/libevmasm/SemanticInformation.cpp
@@ -28,7 +28,7 @@ using namespace std;
 using namespace dev;
 using namespace dev::eth;
 
-bool SemanticInformation::breaksCSEAnalysisBlock(AssemblyItem const& _item)
+bool SemanticInformation::breaksCSEAnalysisBlock(AssemblyItem const& _item, bool _msizeImportant)
 {
 	switch (_item.type())
 	{
@@ -59,6 +59,11 @@ bool SemanticInformation::breaksCSEAnalysisBlock(AssemblyItem const& _item)
 			return false;
 		if (_item.instruction() == Instruction::MSTORE)
 			return false;
+		if (!_msizeImportant && (
+			_item.instruction() == Instruction::MLOAD ||
+			_item.instruction() == Instruction::KECCAK256
+		))
+			return false;
 		//@todo: We do not handle the following memory instructions for now:
 		// calldatacopy, codecopy, extcodecopy, mstore8,
 		// msize (note that msize also depends on memory read access)
diff --git a/libevmasm/SemanticInformation.h b/libevmasm/SemanticInformation.h
index 83656252..8bdc70be 100644
--- a/libevmasm/SemanticInformation.h
+++ b/libevmasm/SemanticInformation.h
@@ -38,7 +38,8 @@ class AssemblyItem;
 struct SemanticInformation
 {
 	/// @returns true if the given items starts a new block for common subexpression analysis.
-	static bool breaksCSEAnalysisBlock(AssemblyItem const& _item);
+	/// @param _msizeImportant if false, consider an operation non-breaking if its only side-effect is that it modifies msize.
+	static bool breaksCSEAnalysisBlock(AssemblyItem const& _item, bool _msizeImportant);
 	/// @returns true if the item is a two-argument operation whose value does not depend on the
 	/// order of its arguments.
 	static bool isCommutativeOperation(AssemblyItem const& _item);