Merge pull request #3797 from ethereum/shift-constantinople

Use native shift instructions on Constantinople

10 files changed, 126 insertions, 55 deletions

diff --git a/Changelog.md b/Changelog.md
index 1cb96833..817365b9 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -2,6 +2,7 @@
 
 Features:
  * Build System: Update internal dependency of jsoncpp to 1.8.4, which introduces more strictness and reduces memory usage.
+ * Code Generator: Use native shift instructions on target Constantinople.
  * Optimizer: Remove unnecessary masking of the result of known short instructions (``ADDRESS``, ``CALLER``, ``ORIGIN`` and ``COINBASE``).
  * Type Checker: Deprecate the ``years`` unit denomination and raise a warning for it (or an error as experimental 0.5.0 feature).
  * Type Checker: Make literals (without explicit type casting) an error for tight packing as experimental 0.5.0 feature.
diff --git a/libsolidity/codegen/ABIFunctions.cpp b/libsolidity/codegen/ABIFunctions.cpp
index 8e890854..3e3aa0ae 100644
--- a/libsolidity/codegen/ABIFunctions.cpp
+++ b/libsolidity/codegen/ABIFunctions.cpp
@@ -371,7 +371,7 @@ string ABIFunctions::conversionFunction(Type const& _from, Type const& _to)
 			if (toCategory == Type::Category::Integer)
 				body =
 					Whiskers("converted := <convert>(<shift>(value))")
-					("shift", shiftRightFunction(256 - from.numBytes() * 8, false))
+					("shift", shiftRightFunction(256 - from.numBytes() * 8))
 					("convert", conversionFunction(IntegerType(from.numBytes() * 8), _to))
 					.render();
 			else
@@ -458,8 +458,8 @@ string ABIFunctions::splitExternalFunctionIdFunction()
 			}
 		)")
 		("functionName", functionName)
-		("shr32", shiftRightFunction(32, false))
-		("shr64", shiftRightFunction(64, false))
+		("shr32", shiftRightFunction(32))
+		("shr64", shiftRightFunction(64))
 		.render();
 	});
 }
@@ -831,7 +831,7 @@ string ABIFunctions::abiEncodingFunctionCompactStorageArray(
 			templ("encodeToMemoryFun", encodeToMemoryFun);
 			std::vector<std::map<std::string, std::string>> items(itemsPerSlot);
 			for (size_t i = 0; i < itemsPerSlot; ++i)
-				items[i]["shiftRightFun"] = shiftRightFunction(i * storageBytes * 8, false);
+				items[i]["shiftRightFun"] = shiftRightFunction(i * storageBytes * 8);
 			templ("items", items);
 			return templ.render();
 		}
@@ -927,7 +927,7 @@ string ABIFunctions::abiEncodingFunctionStruct(
 					}
 					else
 						memberTempl("preprocess", "");
-					memberTempl("retrieveValue", shiftRightFunction(intraSlotOffset * 8, false) + "(slotValue)");
+					memberTempl("retrieveValue", shiftRightFunction(intraSlotOffset * 8) + "(slotValue)");
 				}
 				else
 				{
@@ -1401,37 +1401,75 @@ string ABIFunctions::copyToMemoryFunction(bool _fromCalldata)
 
 string ABIFunctions::shiftLeftFunction(size_t _numBits)
 {
+	solAssert(_numBits < 256, "");
+
 	string functionName = "shift_left_" + to_string(_numBits);
-	return createFunction(functionName, [&]() {
-		solAssert(_numBits < 256, "");
-		return
-			Whiskers(R"(
-			function <functionName>(value) -> newValue {
-				newValue := mul(value, <multiplier>)
-			}
-			)")
-			("functionName", functionName)
-			("multiplier", toCompactHexWithPrefix(u256(1) << _numBits))
-			.render();
-	});
+	if (m_evmVersion.hasBitwiseShifting())
+	{
+		return createFunction(functionName, [&]() {
+			return
+				Whiskers(R"(
+				function <functionName>(value) -> newValue {
+					newValue := shl(<numBits>, value)
+				}
+				)")
+				("functionName", functionName)
+				("numBits", to_string(_numBits))
+				.render();
+		});
+	}
+	else
+	{
+		return createFunction(functionName, [&]() {
+			return
+				Whiskers(R"(
+				function <functionName>(value) -> newValue {
+					newValue := mul(value, <multiplier>)
+				}
+				)")
+				("functionName", functionName)
+				("multiplier", toCompactHexWithPrefix(u256(1) << _numBits))
+				.render();
+		});
+	}
 }
 
-string ABIFunctions::shiftRightFunction(size_t _numBits, bool _signed)
+string ABIFunctions::shiftRightFunction(size_t _numBits)
 {
-	string functionName = "shift_right_" + to_string(_numBits) + (_signed ? "_signed" : "_unsigned");
-	return createFunction(functionName, [&]() {
-		solAssert(_numBits < 256, "");
-		return
-			Whiskers(R"(
-			function <functionName>(value) -> newValue {
-				newValue := <div>(value, <multiplier>)
-			}
-			)")
-			("functionName", functionName)
-			("div", _signed ? "sdiv" : "div")
-			("multiplier", toCompactHexWithPrefix(u256(1) << _numBits))
-			.render();
-	});
+	solAssert(_numBits < 256, "");
+
+	// Note that if this is extended with signed shifts,
+	// the opcodes SAR and SDIV behave differently with regards to rounding!
+
+	string functionName = "shift_right_" + to_string(_numBits) + "_unsigned";
+	if (m_evmVersion.hasBitwiseShifting())
+	{
+		return createFunction(functionName, [&]() {
+			return
+				Whiskers(R"(
+				function <functionName>(value) -> newValue {
+					newValue := shr(<numBits>, value)
+				}
+				)")
+				("functionName", functionName)
+				("numBits", to_string(_numBits))
+				.render();
+		});
+	}
+	else
+	{
+		return createFunction(functionName, [&]() {
+			return
+				Whiskers(R"(
+				function <functionName>(value) -> newValue {
+					newValue := div(value, <multiplier>)
+				}
+				)")
+				("functionName", functionName)
+				("multiplier", toCompactHexWithPrefix(u256(1) << _numBits))
+				.render();
+		});
+	}
 }
 
 string ABIFunctions::roundUpFunction()
diff --git a/libsolidity/codegen/ABIFunctions.h b/libsolidity/codegen/ABIFunctions.h
index 2b582e84..db4d40f5 100644
--- a/libsolidity/codegen/ABIFunctions.h
+++ b/libsolidity/codegen/ABIFunctions.h
@@ -22,6 +22,8 @@
 
 #pragma once
 
+#include <libsolidity/interface/EVMVersion.h>
+
 #include <libsolidity/ast/ASTForward.h>
 
 #include <vector>
@@ -48,6 +50,8 @@ using TypePointers = std::vector<TypePointer>;
 class ABIFunctions
 {
 public:
+	explicit ABIFunctions(EVMVersion _evmVersion = EVMVersion{}) : m_evmVersion(_evmVersion) {}
+
 	/// @returns name of an assembly function to ABI-encode values of @a _givenTypes
 	/// into memory, converting the types to @a _targetTypes on the fly.
 	/// Parameters are: <headStart> <value_n> ... <value_1>, i.e.
@@ -191,7 +195,7 @@ private:
 	std::string copyToMemoryFunction(bool _fromCalldata);
 
 	std::string shiftLeftFunction(size_t _numBits);
-	std::string shiftRightFunction(size_t _numBits, bool _signed);
+	std::string shiftRightFunction(size_t _numBits);
 	/// @returns the name of a function that rounds its input to the next multiple
 	/// of 32 or the input if it is a multiple of 32.
 	std::string roundUpFunction();
@@ -225,6 +229,8 @@ private:
 
 	/// Map from function name to code for a multi-use function.
 	std::map<std::string, std::string> m_requestedFunctions;
+
+	EVMVersion m_evmVersion;
 };
 
 }
diff --git a/libsolidity/codegen/CompilerContext.h b/libsolidity/codegen/CompilerContext.h
index 098472f7..5776b5d1 100644
--- a/libsolidity/codegen/CompilerContext.h
+++ b/libsolidity/codegen/CompilerContext.h
@@ -55,7 +55,8 @@ public:
 	explicit CompilerContext(EVMVersion _evmVersion = EVMVersion{}, CompilerContext* _runtimeContext = nullptr):
 		m_asm(std::make_shared<eth::Assembly>()),
 		m_evmVersion(_evmVersion),
-		m_runtimeContext(_runtimeContext)
+		m_runtimeContext(_runtimeContext),
+		m_abiFunctions(m_evmVersion)
 	{
 		if (m_runtimeContext)
 			m_runtimeSub = size_t(m_asm->newSub(m_runtimeContext->m_asm).data());
diff --git a/libsolidity/codegen/CompilerUtils.cpp b/libsolidity/codegen/CompilerUtils.cpp
index 4af7d905..48b77eb3 100644
--- a/libsolidity/codegen/CompilerUtils.cpp
+++ b/libsolidity/codegen/CompilerUtils.cpp
@@ -599,15 +599,15 @@ void CompilerUtils::splitExternalFunctionType(bool _leftAligned)
 	if (_leftAligned)
 	{
 		m_context << Instruction::DUP1;
-		rightShiftNumberOnStack(64 + 32, false);
+		rightShiftNumberOnStack(64 + 32);
 		// <input> <address>
 		m_context << Instruction::SWAP1;
-		rightShiftNumberOnStack(64, false);
+		rightShiftNumberOnStack(64);
 	}
 	else
 	{
 		m_context << Instruction::DUP1;
-		rightShiftNumberOnStack(32, false);
+		rightShiftNumberOnStack(32);
 		m_context << ((u256(1) << 160) - 1) << Instruction::AND << Instruction::SWAP1;
 	}
 	m_context << u256(0xffffffffUL) << Instruction::AND;
@@ -675,7 +675,7 @@ void CompilerUtils::convertType(
 			// conversion from bytes to integer. no need to clean the high bit
 			// only to shift right because of opposite alignment
 			IntegerType const& targetIntegerType = dynamic_cast<IntegerType const&>(_targetType);
-			rightShiftNumberOnStack(256 - typeOnStack.numBytes() * 8, false);
+			rightShiftNumberOnStack(256 - typeOnStack.numBytes() * 8);
 			if (targetIntegerType.numBits() < typeOnStack.numBytes() * 8)
 				convertType(IntegerType(typeOnStack.numBytes() * 8), _targetType, _cleanupNeeded);
 		}
@@ -1242,7 +1242,7 @@ unsigned CompilerUtils::loadFromMemoryHelper(Type const& _type, bool _fromCallda
 		bool leftAligned = _type.category() == Type::Category::FixedBytes;
 		// add leading or trailing zeros by dividing/multiplying depending on alignment
 		int shiftFactor = (32 - numBytes) * 8;
-		rightShiftNumberOnStack(shiftFactor, false);
+		rightShiftNumberOnStack(shiftFactor);
 		if (leftAligned)
 			leftShiftNumberOnStack(shiftFactor);
 	}
@@ -1265,13 +1265,20 @@ void CompilerUtils::cleanHigherOrderBits(IntegerType const& _typeOnStack)
 void CompilerUtils::leftShiftNumberOnStack(unsigned _bits)
 {
 	solAssert(_bits < 256, "");
-	m_context << (u256(1) << _bits) << Instruction::MUL;
+	if (m_context.evmVersion().hasBitwiseShifting())
+		m_context << _bits << Instruction::SHL;
+	else
+		m_context << (u256(1) << _bits) << Instruction::MUL;
 }
 
-void CompilerUtils::rightShiftNumberOnStack(unsigned _bits, bool _isSigned)
+void CompilerUtils::rightShiftNumberOnStack(unsigned _bits)
 {
 	solAssert(_bits < 256, "");
-	m_context << (u256(1) << _bits) << Instruction::SWAP1 << (_isSigned ? Instruction::SDIV : Instruction::DIV);
+	// NOTE: If we add signed right shift, SAR rounds differently than SDIV
+	if (m_context.evmVersion().hasBitwiseShifting())
+		m_context << _bits << Instruction::SHR;
+	else
+		m_context << (u256(1) << _bits) << Instruction::SWAP1 << Instruction::DIV;
 }
 
 unsigned CompilerUtils::prepareMemoryStore(Type const& _type, bool _padToWords)
diff --git a/libsolidity/codegen/CompilerUtils.h b/libsolidity/codegen/CompilerUtils.h
index 476a7559..8e3a8a5d 100644
--- a/libsolidity/codegen/CompilerUtils.h
+++ b/libsolidity/codegen/CompilerUtils.h
@@ -254,7 +254,7 @@ public:
 	/// Helper function to shift top value on the stack to the right.
 	/// Stack pre: <value> <shift_by_bits>
 	/// Stack post: <shifted_value>
-	void rightShiftNumberOnStack(unsigned _bits, bool _isSigned = false);
+	void rightShiftNumberOnStack(unsigned _bits);
 
 	/// Appends code that computes tha Keccak-256 hash of the topmost stack element of 32 byte type.
 	void computeHashStatic();
diff --git a/libsolidity/codegen/ExpressionCompiler.cpp b/libsolidity/codegen/ExpressionCompiler.cpp
index 3cf46a9d..a8222e21 100644
--- a/libsolidity/codegen/ExpressionCompiler.cpp
+++ b/libsolidity/codegen/ExpressionCompiler.cpp
@@ -548,7 +548,7 @@ bool ExpressionCompiler::visit(FunctionCall const& _functionCall)
 
 			if (m_context.runtimeContext())
 				// We have a runtime context, so we need the creation part.
-				utils().rightShiftNumberOnStack(32, false);
+				utils().rightShiftNumberOnStack(32);
 			else
 				// Extract the runtime part.
 				m_context << ((u256(1) << 32) - 1) << Instruction::AND;
@@ -1706,13 +1706,23 @@ void ExpressionCompiler::appendShiftOperatorCode(Token::Value _operator, Type co
 		m_context.appendConditionalInvalid();
 	}
 
+	m_context << Instruction::SWAP1;
+	// stack: value_to_shift shift_amount
+
 	switch (_operator)
 	{
 	case Token::SHL:
-		m_context << Instruction::SWAP1 << u256(2) << Instruction::EXP << Instruction::MUL;
+		if (m_context.evmVersion().hasBitwiseShifting())
+			m_context << Instruction::SHL;
+		else
+			m_context << u256(2) << Instruction::EXP << Instruction::MUL;
 		break;
 	case Token::SAR:
-		m_context << Instruction::SWAP1 << u256(2) << Instruction::EXP << Instruction::SWAP1 << (c_valueSigned ? Instruction::SDIV : Instruction::DIV);
+		// NOTE: SAR rounds differently than SDIV
+		if (m_context.evmVersion().hasBitwiseShifting() && !c_valueSigned)
+			m_context << Instruction::SHR;
+		else
+			m_context << u256(2) << Instruction::EXP << Instruction::SWAP1 << (c_valueSigned ? Instruction::SDIV : Instruction::DIV);
 		break;
 	case Token::SHR:
 	default:
diff --git a/libsolidity/codegen/LValue.cpp b/libsolidity/codegen/LValue.cpp
index e19cf41e..77684683 100644
--- a/libsolidity/codegen/LValue.cpp
+++ b/libsolidity/codegen/LValue.cpp
@@ -267,7 +267,7 @@ void StorageItem::storeValue(Type const& _sourceType, SourceLocation const& _loc
 			else if (m_dataType->category() == Type::Category::FixedBytes)
 			{
 				solAssert(_sourceType.category() == Type::Category::FixedBytes, "source not fixed bytes");
-				CompilerUtils(m_context).rightShiftNumberOnStack(256 - 8 * dynamic_cast<FixedBytesType const&>(*m_dataType).numBytes(), false);
+				CompilerUtils(m_context).rightShiftNumberOnStack(256 - 8 * dynamic_cast<FixedBytesType const&>(*m_dataType).numBytes());
 			}
 			else
 			{
diff --git a/libsolidity/interface/GasEstimator.cpp b/libsolidity/interface/GasEstimator.cpp
index a496cc21..a532f86e 100644
--- a/libsolidity/interface/GasEstimator.cpp
+++ b/libsolidity/interface/GasEstimator.cpp
@@ -136,13 +136,22 @@ GasEstimator::GasConsumption GasEstimator::functionalEstimation(
 		ExpressionClasses& classes = state->expressionClasses();
 		using Id = ExpressionClasses::Id;
 		using Ids = vector<Id>;
-		// div(calldataload(0), 1 << 224) equals to hashValue
 		Id hashValue = classes.find(u256(FixedHash<4>::Arith(FixedHash<4>(dev::keccak256(_signature)))));
 		Id calldata = classes.find(Instruction::CALLDATALOAD, Ids{classes.find(u256(0))});
-		classes.forceEqual(hashValue, Instruction::DIV, Ids{
-			calldata,
-			classes.find(u256(1) << 224)
-		});
+		if (!m_evmVersion.hasBitwiseShifting())
+			// div(calldataload(0), 1 << 224) equals to hashValue
+			classes.forceEqual(
+				hashValue,
+				Instruction::DIV,
+				Ids{calldata, classes.find(u256(1) << 224)}
+			);
+		else
+			// shr(0xe0, calldataload(0)) equals to hashValue
+			classes.forceEqual(
+				hashValue,
+				Instruction::SHR,
+				Ids{classes.find(u256(0xe0)), calldata}
+			);
 		// lt(calldatasize(), 4) equals to 0 (ignore the shortcut for fallback functions)
 		classes.forceEqual(
 			classes.find(u256(0)),
diff --git a/test/libsolidity/Assembly.cpp b/test/libsolidity/Assembly.cpp
index 77ca363a..7b3df043 100644
--- a/test/libsolidity/Assembly.cpp
+++ b/test/libsolidity/Assembly.cpp
@@ -158,8 +158,9 @@ BOOST_AUTO_TEST_CASE(location_test)
 	}
 	)";
 	AssemblyItems items = compileContract(sourceCode);
+	bool hasShifts = dev::test::Options::get().evmVersion().hasBitwiseShifting();
 	vector<SourceLocation> locations =
-		vector<SourceLocation>(24, SourceLocation(2, 75, make_shared<string>(""))) +
+		vector<SourceLocation>(hasShifts ? 23 : 24, SourceLocation(2, 75, make_shared<string>(""))) +
 		vector<SourceLocation>(2, SourceLocation(20, 72, make_shared<string>(""))) +
 		vector<SourceLocation>(1, SourceLocation(8, 17, make_shared<string>("--CODEGEN--"))) +
 		vector<SourceLocation>(3, SourceLocation(5, 7, make_shared<string>("--CODEGEN--"))) +
@@ -172,8 +173,6 @@ BOOST_AUTO_TEST_CASE(location_test)
 		vector<SourceLocation>(1, SourceLocation(65, 67, make_shared<string>(""))) +
 		vector<SourceLocation>(2, SourceLocation(58, 67, make_shared<string>(""))) +
 		vector<SourceLocation>(2, SourceLocation(20, 72, make_shared<string>("")));
-
-
 	checkAssemblyLocations(items, locations);
 }