Merge pull request #1487 from ethereum/shift-ops

Shift operators

7 files changed, 543 insertions, 42 deletions

diff --git a/Changelog.md b/Changelog.md
index c3b3f5fa..dfeaa381 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -1,6 +1,7 @@
 ### 0.4.7 (unreleased)
 
 Features:
+ * Bitshift operators.
  * Type checker: Warn when ``msg.value`` is used in non-payable function.
  * Code generator: Inject the Swarm hash of a metadata file into the bytecode.
  * Code generator: Replace expensive memcpy precompile by simple assembly loop.
diff --git a/docs/control-structures.rst b/docs/control-structures.rst
index 974a093f..0802c085 100644
--- a/docs/control-structures.rst
+++ b/docs/control-structures.rst
@@ -382,17 +382,18 @@ In the following example, we show how ``throw`` can be used to easily revert an
         }
     }
 
-Currently, there are situations, where exceptions happen automatically in Solidity:
+Currently, Solidity automatically generates a runtime exception in the following situations:
 
 1. If you access an array at a too large or negative index (i.e. ``x[i]`` where ``i >= x.length`` or ``i < 0``).
-2. If you access a fixed-length ``bytesN`` at a too large or negative index.
-3. If you call a function via a message call but it does not finish properly (i.e. it runs out of gas, has no matching function, or throws an exception itself), except when a low level operation ``call``, ``send``, ``delegatecall`` or ``callcode`` is used.  The low level operations never throw exceptions but indicate failures by returning ``false``.
-4. If you create a contract using the ``new`` keyword but the contract creation does not finish properly (see above for the definition of "not finish properly").
-5. If you divide or modulo by zero (e.g. ``5 / 0`` or ``23 % 0``).
-6. If you convert a value too big or negative into an enum type.
-7. If you perform an external function call targeting a contract that contains no code.
-8. If your contract receives Ether via a public function without ``payable`` modifier (including the constructor and the fallback function).
-9. If your contract receives Ether via a public accessor function.
+1. If you access a fixed-length ``bytesN`` at a too large or negative index.
+1. If you call a function via a message call but it does not finish properly (i.e. it runs out of gas, has no matching function, or throws an exception itself), except when a low level operation ``call``, ``send``, ``delegatecall`` or ``callcode`` is used.  The low level operations never throw exceptions but indicate failures by returning ``false``.
+1. If you create a contract using the ``new`` keyword but the contract creation does not finish properly (see above for the definition of "not finish properly").
+1. If you divide or modulo by zero (e.g. ``5 / 0`` or ``23 % 0``).
+1. If you shift by a negative amount.
+1. If you convert a value too big or negative into an enum type.
+1. If you perform an external function call targeting a contract that contains no code.
+1. If your contract receives Ether via a public function without ``payable`` modifier (including the constructor and the fallback function).
+1. If your contract receives Ether via a public accessor function.
 
 Internally, Solidity performs an "invalid jump" when an exception is thrown and thus causes the EVM to revert all changes made to the state. The reason for this is that there is no safe way to continue execution, because an expected effect did not occur. Because we want to retain the atomicity of transactions, the safest thing to do is to revert all changes and make the whole transaction (or at least call) without effect.
 
diff --git a/docs/types.rst b/docs/types.rst
index 896910ff..069a9190 100644
--- a/docs/types.rst
+++ b/docs/types.rst
@@ -52,12 +52,17 @@ Operators:
 
 * Comparisons: ``<=``, ``<``, ``==``, ``!=``, ``>=``, ``>`` (evaluate to ``bool``)
 * Bit operators: ``&``, ``|``, ``^`` (bitwise exclusive or), ``~`` (bitwise negation)
-* Arithmetic operators: ``+``, ``-``, unary ``-``, unary ``+``, ``*``, ``/``, ``%`` (remainder), ``**`` (exponentiation)
+* Arithmetic operators: ``+``, ``-``, unary ``-``, unary ``+``, ``*``, ``/``, ``%`` (remainder), ``**`` (exponentiation), ``<<`` (left shift), ``>>`` (right shift)
 
 Division always truncates (it just maps to the DIV opcode of the EVM), but it does not truncate if both
 operators are :ref:`literals<rational_literals>` (or literal expressions).
 
-Division by zero and modulus with zero throws an exception.
+Division by zero and modulus with zero throws a runtime exception.
+
+The result of a shift operation is the type of the left operand. The
+expression ``x << y`` is equivalent to ``x * 2**y`` and ``x >> y`` is
+equivalent to ``x / 2**y``. This means that shifting negative numbers
+sign extends. Shifting by a negative amount throws a runtime exception.
 
 .. index:: address, balance, send, call, callcode, delegatecall
 
@@ -136,9 +141,13 @@ Fixed-size byte arrays
 Operators:
 
 * Comparisons: ``<=``, ``<``, ``==``, ``!=``, ``>=``, ``>`` (evaluate to ``bool``)
-* Bit operators: ``&``, ``|``, ``^`` (bitwise exclusive or), ``~`` (bitwise negation)
+* Bit operators: ``&``, ``|``, ``^`` (bitwise exclusive or), ``~`` (bitwise negation), ``<<`` (left shift), ``>>`` (right shift)
 * Index access: If ``x`` is of type ``bytesI``, then ``x[k]`` for ``0 <= k < I`` returns the ``k`` th byte (read-only).
 
+The shifting operator works with any integer type as right operand (but will
+return the type of the left operand), which denotes the number of bits to shift by.
+Shifting by a negative amount will cause a runtime exception.
+
 Members:
 
 * ``.length`` yields the fixed length of the byte array (read-only).
diff --git a/libsolidity/ast/Types.cpp b/libsolidity/ast/Types.cpp
index d9660bc0..03ff8471 100644
--- a/libsolidity/ast/Types.cpp
+++ b/libsolidity/ast/Types.cpp
@@ -251,6 +251,19 @@ MemberList::MemberMap Type::boundFunctions(Type const& _type, ContractDefinition
 	return members;
 }
 
+bool isValidShiftAndAmountType(Token::Value _operator, Type const& _shiftAmountType)
+{
+	// Disable >>> here.
+	if (_operator == Token::SHR)
+		return false;
+	else if (IntegerType const* otherInt = dynamic_cast<decltype(otherInt)>(&_shiftAmountType))
+		return !otherInt->isAddress();
+	else if (RationalNumberType const* otherRat = dynamic_cast<decltype(otherRat)>(&_shiftAmountType))
+		return otherRat->integerType() && !otherRat->integerType()->isSigned();
+	else
+		return false;
+}
+
 IntegerType::IntegerType(int _bits, IntegerType::Modifier _modifier):
 	m_bits(_bits), m_modifier(_modifier)
 {
@@ -340,6 +353,17 @@ TypePointer IntegerType::binaryOperatorResult(Token::Value _operator, TypePointe
 		_other->category() != category()
 	)
 		return TypePointer();
+	if (Token::isShiftOp(_operator))
+	{
+		// Shifts are not symmetric with respect to the type
+		if (isAddress())
+			return TypePointer();
+		if (isValidShiftAndAmountType(_operator, *_other))
+			return shared_from_this();
+		else
+			return TypePointer();
+	}
+
 	auto commonType = Type::commonType(shared_from_this(), _other); //might be a integer or fixed point
 	if (!commonType)
 		return TypePointer();
@@ -954,6 +978,14 @@ TypePointer FixedBytesType::unaryOperatorResult(Token::Value _operator) const
 
 TypePointer FixedBytesType::binaryOperatorResult(Token::Value _operator, TypePointer const& _other) const
 {
+	if (Token::isShiftOp(_operator))
+	{
+		if (isValidShiftAndAmountType(_operator, *_other))
+			return shared_from_this();
+		else
+			return TypePointer();
+	}
+
 	auto commonType = dynamic_pointer_cast<FixedBytesType const>(Type::commonType(shared_from_this(), _other));
 	if (!commonType)
 		return TypePointer();
diff --git a/libsolidity/codegen/ExpressionCompiler.cpp b/libsolidity/codegen/ExpressionCompiler.cpp
index 5748d818..a7fb8408 100644
--- a/libsolidity/codegen/ExpressionCompiler.cpp
+++ b/libsolidity/codegen/ExpressionCompiler.cpp
@@ -197,21 +197,39 @@ bool ExpressionCompiler::visit(Conditional const& _condition)
 bool ExpressionCompiler::visit(Assignment const& _assignment)
 {
 	CompilerContext::LocationSetter locationSetter(m_context, _assignment);
+	Token::Value op = _assignment.assignmentOperator();
+	Token::Value binOp = op == Token::Assign ? op : Token::AssignmentToBinaryOp(op);
+	Type const& leftType = *_assignment.leftHandSide().annotation().type;
+	if (leftType.category() == Type::Category::Tuple)
+	{
+		solAssert(*_assignment.annotation().type == TupleType(), "");
+		solAssert(op == Token::Assign, "");
+	}
+	else
+		solAssert(*_assignment.annotation().type == leftType, "");
+	bool cleanupNeeded = false;
+	if (op != Token::Assign)
+		cleanupNeeded = cleanupNeededForOp(leftType.category(), binOp);
 	_assignment.rightHandSide().accept(*this);
 	// Perform some conversion already. This will convert storage types to memory and literals
 	// to their actual type, but will not convert e.g. memory to storage.
-	TypePointer type = _assignment.rightHandSide().annotation().type->closestTemporaryType(
-		_assignment.leftHandSide().annotation().type
-	);
-	utils().convertType(*_assignment.rightHandSide().annotation().type, *type);
+	TypePointer rightIntermediateType;
+	if (op != Token::Assign && Token::isShiftOp(binOp))
+		rightIntermediateType = _assignment.rightHandSide().annotation().type->mobileType();
+	else
+		rightIntermediateType = _assignment.rightHandSide().annotation().type->closestTemporaryType(
+			_assignment.leftHandSide().annotation().type
+		);
+	utils().convertType(*_assignment.rightHandSide().annotation().type, *rightIntermediateType, cleanupNeeded);
 
 	_assignment.leftHandSide().accept(*this);
 	solAssert(!!m_currentLValue, "LValue not retrieved.");
 
-	Token::Value op = _assignment.assignmentOperator();
-	if (op != Token::Assign) // compound assignment
+	if (op == Token::Assign)
+		m_currentLValue->storeValue(*rightIntermediateType, _assignment.location());
+	else  // compound assignment
 	{
-		solUnimplementedAssert(_assignment.annotation().type->isValueType(), "Compound operators not implemented for non-value types.");
+		solAssert(leftType.isValueType(), "Compound operators only available for value types.");
 		unsigned lvalueSize = m_currentLValue->sizeOnStack();
 		unsigned itemSize = _assignment.annotation().type->sizeOnStack();
 		if (lvalueSize > 0)
@@ -221,7 +239,15 @@ bool ExpressionCompiler::visit(Assignment const& _assignment)
 			// value lvalue_ref value lvalue_ref
 		}
 		m_currentLValue->retrieveValue(_assignment.location(), true);
-		appendOrdinaryBinaryOperatorCode(Token::AssignmentToBinaryOp(op), *_assignment.annotation().type);
+		utils().convertType(leftType, leftType, cleanupNeeded);
+
+		if (Token::isShiftOp(binOp))
+			appendShiftOperatorCode(binOp, leftType, *rightIntermediateType);
+		else
+		{
+			solAssert(leftType == *rightIntermediateType, "");
+			appendOrdinaryBinaryOperatorCode(binOp, leftType);
+		}
 		if (lvalueSize > 0)
 		{
 			solAssert(itemSize + lvalueSize <= 16, "Stack too deep, try removing local variables.");
@@ -229,8 +255,8 @@ bool ExpressionCompiler::visit(Assignment const& _assignment)
 			for (unsigned i = 0; i < itemSize; ++i)
 				m_context << swapInstruction(itemSize + lvalueSize) << Instruction::POP;
 		}
+		m_currentLValue->storeValue(*_assignment.annotation().type, _assignment.location());
 	}
-	m_currentLValue->storeValue(*type, _assignment.location());
 	m_currentLValue.reset();
 	return false;
 }
@@ -351,20 +377,19 @@ bool ExpressionCompiler::visit(BinaryOperation const& _binaryOperation)
 	Expression const& leftExpression = _binaryOperation.leftExpression();
 	Expression const& rightExpression = _binaryOperation.rightExpression();
 	solAssert(!!_binaryOperation.annotation().commonType, "");
-	Type const& commonType = *_binaryOperation.annotation().commonType;
+	TypePointer const& commonType = _binaryOperation.annotation().commonType;
 	Token::Value const c_op = _binaryOperation.getOperator();
 
 	if (c_op == Token::And || c_op == Token::Or) // special case: short-circuiting
 		appendAndOrOperatorCode(_binaryOperation);
-	else if (commonType.category() == Type::Category::RationalNumber)
-		m_context << commonType.literalValue(nullptr);
+	else if (commonType->category() == Type::Category::RationalNumber)
+		m_context << commonType->literalValue(nullptr);
 	else
 	{
-		bool cleanupNeeded = false;
-		if (Token::isCompareOp(c_op))
-			cleanupNeeded = true;
-		if (commonType.category() == Type::Category::Integer && (c_op == Token::Div || c_op == Token::Mod))
-			cleanupNeeded = true;
+		bool cleanupNeeded = cleanupNeededForOp(commonType->category(), c_op);
+
+		TypePointer leftTargetType = commonType;
+		TypePointer rightTargetType = Token::isShiftOp(c_op) ? rightExpression.annotation().type->mobileType() : commonType;
 
 		// for commutative operators, push the literal as late as possible to allow improved optimization
 		auto isLiteral = [](Expression const& _e)
@@ -375,21 +400,24 @@ bool ExpressionCompiler::visit(BinaryOperation const& _binaryOperation)
 		if (swap)
 		{
 			leftExpression.accept(*this);
-			utils().convertType(*leftExpression.annotation().type, commonType, cleanupNeeded);
+			utils().convertType(*leftExpression.annotation().type, *leftTargetType, cleanupNeeded);
 			rightExpression.accept(*this);
-			utils().convertType(*rightExpression.annotation().type, commonType, cleanupNeeded);
+			utils().convertType(*rightExpression.annotation().type, *rightTargetType, cleanupNeeded);
 		}
 		else
 		{
 			rightExpression.accept(*this);
-			utils().convertType(*rightExpression.annotation().type, commonType, cleanupNeeded);
+			utils().convertType(*rightExpression.annotation().type, *rightTargetType, cleanupNeeded);
 			leftExpression.accept(*this);
-			utils().convertType(*leftExpression.annotation().type, commonType, cleanupNeeded);
+			utils().convertType(*leftExpression.annotation().type, *leftTargetType, cleanupNeeded);
 		}
-		if (Token::isCompareOp(c_op))
-			appendCompareOperatorCode(c_op, commonType);
+		if (Token::isShiftOp(c_op))
+			// shift only cares about the signedness of both sides
+			appendShiftOperatorCode(c_op, *leftTargetType, *rightTargetType);
+		else if (Token::isCompareOp(c_op))
+			appendCompareOperatorCode(c_op, *commonType);
 		else
-			appendOrdinaryBinaryOperatorCode(c_op, commonType);
+			appendOrdinaryBinaryOperatorCode(c_op, *commonType);
 	}
 
 	// do not visit the child nodes, we already did that explicitly
@@ -1326,8 +1354,6 @@ void ExpressionCompiler::appendOrdinaryBinaryOperatorCode(Token::Value _operator
 		appendArithmeticOperatorCode(_operator, _type);
 	else if (Token::isBitOp(_operator))
 		appendBitOperatorCode(_operator);
-	else if (Token::isShiftOp(_operator))
-		appendShiftOperatorCode(_operator);
 	else
 		BOOST_THROW_EXCEPTION(InternalCompilerError() << errinfo_comment("Unknown binary operator."));
 }
@@ -1390,17 +1416,45 @@ void ExpressionCompiler::appendBitOperatorCode(Token::Value _operator)
 	}
 }
 
-void ExpressionCompiler::appendShiftOperatorCode(Token::Value _operator)
+void ExpressionCompiler::appendShiftOperatorCode(Token::Value _operator, Type const& _valueType, Type const& _shiftAmountType)
 {
-	solUnimplemented("Shift operators not yet implemented.");
+	// stack: shift_amount value_to_shift
+
+	bool c_valueSigned = false;
+	if (auto valueType = dynamic_cast<IntegerType const*>(&_valueType))
+		c_valueSigned = valueType->isSigned();
+	else
+		solAssert(dynamic_cast<FixedBytesType const*>(&_valueType), "Only integer and fixed bytes type supported for shifts.");
+
+	// The amount can be a RationalNumberType too.
+	bool c_amountSigned = false;
+	if (auto amountType = dynamic_cast<RationalNumberType const*>(&_shiftAmountType))
+	{
+		// This should be handled by the type checker.
+		solAssert(amountType->integerType(), "");
+		solAssert(!amountType->integerType()->isSigned(), "");
+	}
+	else if (auto amountType = dynamic_cast<IntegerType const*>(&_shiftAmountType))
+		c_amountSigned = amountType->isSigned();
+	else
+		solAssert(false, "Invalid shift amount type.");
+
+	// shift by negative amount throws exception
+	if (c_amountSigned)
+	{
+		m_context << u256(0) << Instruction::DUP3 << Instruction::SLT;
+		m_context.appendConditionalJumpTo(m_context.errorTag());
+	}
+
 	switch (_operator)
 	{
 	case Token::SHL:
+		m_context << Instruction::SWAP1 << 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);
 		break;
 	case Token::SHR:
-		break;
 	default:
 		BOOST_THROW_EXCEPTION(InternalCompilerError() << errinfo_comment("Unknown shift operator."));
 	}
@@ -1688,6 +1742,16 @@ void ExpressionCompiler::setLValueToStorageItem(Expression const& _expression)
 	setLValue<StorageItem>(_expression, *_expression.annotation().type);
 }
 
+bool ExpressionCompiler::cleanupNeededForOp(Type::Category _type, Token::Value _op)
+{
+	if (Token::isCompareOp(_op) || Token::isShiftOp(_op))
+		return true;
+	else if (_type == Type::Category::Integer && (_op == Token::Div || _op == Token::Mod))
+		return true;
+	else
+		return false;
+}
+
 CompilerUtils ExpressionCompiler::utils()
 {
 	return CompilerUtils(m_context);
diff --git a/libsolidity/codegen/ExpressionCompiler.h b/libsolidity/codegen/ExpressionCompiler.h
index f08bded9..d0a8ac15 100644
--- a/libsolidity/codegen/ExpressionCompiler.h
+++ b/libsolidity/codegen/ExpressionCompiler.h
@@ -91,7 +91,7 @@ private:
 
 	void appendArithmeticOperatorCode(Token::Value _operator, Type const& _type);
 	void appendBitOperatorCode(Token::Value _operator);
-	void appendShiftOperatorCode(Token::Value _operator);
+	void appendShiftOperatorCode(Token::Value _operator, Type const& _valueType, Type const& _shiftAmountType);
 	/// @}
 
 	/// Appends code to call a function of the given type with the given arguments.
@@ -117,6 +117,10 @@ private:
 	template <class _LValueType, class... _Arguments>
 	void setLValue(Expression const& _expression, _Arguments const&... _arguments);
 
+	/// @returns true if the operator applied to the given type requires a cleanup prior to the
+	/// operation.
+	bool cleanupNeededForOp(Type::Category _type, Token::Value _op);
+
 	/// @returns the CompilerUtils object containing the current context.
 	CompilerUtils utils();
 
diff --git a/test/libsolidity/SolidityEndToEndTest.cpp b/test/libsolidity/SolidityEndToEndTest.cpp
index 2df6e9f2..94d4fb7f 100644
--- a/test/libsolidity/SolidityEndToEndTest.cpp
+++ b/test/libsolidity/SolidityEndToEndTest.cpp
@@ -8456,6 +8456,396 @@ BOOST_AUTO_TEST_CASE(shift_negative_constant_right)
 	BOOST_CHECK(callContractFunction("a()") == encodeArgs(u256(-0x42)));
 }
 
+BOOST_AUTO_TEST_CASE(shift_left)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint a, uint b) returns (uint) {
+				return a << b;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(0)) == encodeArgs(u256(0x4266)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(8)) == encodeArgs(u256(0x426600)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(16)) == encodeArgs(u256(0x42660000)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(17)) == encodeArgs(u256(0x84cc0000)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(240)) == fromHex("4266000000000000000000000000000000000000000000000000000000000000"));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(256)) == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_left_uint32)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint32 a, uint32 b) returns (uint) {
+				return a << b;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint32,uint32)", u256(0x4266), u256(0)) == encodeArgs(u256(0x4266)));
+	BOOST_CHECK(callContractFunction("f(uint32,uint32)", u256(0x4266), u256(8)) == encodeArgs(u256(0x426600)));
+	BOOST_CHECK(callContractFunction("f(uint32,uint32)", u256(0x4266), u256(16)) == encodeArgs(u256(0x42660000)));
+	BOOST_CHECK(callContractFunction("f(uint32,uint32)", u256(0x4266), u256(17)) == encodeArgs(u256(0x84cc0000)));
+	BOOST_CHECK(callContractFunction("f(uint32,uint32)", u256(0x4266), u256(32)) == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_left_uint8)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint8 a, uint8 b) returns (uint) {
+				return a << b;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint8,uint8)", u256(0x66), u256(0)) == encodeArgs(u256(0x66)));
+	BOOST_CHECK(callContractFunction("f(uint8,uint8)", u256(0x66), u256(8)) == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_left_larger_type)
+{
+	// This basically tests proper cleanup and conversion. It should not convert x to int8.
+	char const* sourceCode = R"(
+		contract C {
+			function f() returns (int8) {
+				uint8 x = 254;
+				int8 y = 1;
+				return y << x;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f()") == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_left_assignment)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint a, uint b) returns (uint) {
+				a <<= b;
+				return a;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(0)) == encodeArgs(u256(0x4266)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(8)) == encodeArgs(u256(0x426600)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(16)) == encodeArgs(u256(0x42660000)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(17)) == encodeArgs(u256(0x84cc0000)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(240)) == fromHex("4266000000000000000000000000000000000000000000000000000000000000"));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(256)) == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_left_assignment_different_type)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint a, uint8 b) returns (uint) {
+				a <<= b;
+				return a;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint256,uint8)", u256(0x4266), u256(0)) == encodeArgs(u256(0x4266)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint8)", u256(0x4266), u256(8)) == encodeArgs(u256(0x426600)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint8)", u256(0x4266), u256(16)) == encodeArgs(u256(0x42660000)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint8)", u256(0x4266), u256(17)) == encodeArgs(u256(0x84cc0000)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint8)", u256(0x4266), u256(240)) == fromHex("4266000000000000000000000000000000000000000000000000000000000000"));
+}
+
+BOOST_AUTO_TEST_CASE(shift_right)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint a, uint b) returns (uint) {
+				return a >> b;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(0)) == encodeArgs(u256(0x4266)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(8)) == encodeArgs(u256(0x42)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(16)) == encodeArgs(u256(0)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(17)) == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_right_garbled)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint8 a, uint8 b) returns (uint) {
+				assembly {
+					a := 0xffffffff
+				}
+				// Higher bits should be cleared before the shift
+				return a >> b;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint8,uint8)", u256(0x0), u256(4)) == encodeArgs(u256(0xf)));
+	BOOST_CHECK(callContractFunction("f(uint8,uint8)", u256(0x0), u256(0x1004)) == encodeArgs(u256(0xf)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_right_uint32)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint32 a, uint32 b) returns (uint) {
+				return a >> b;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint32,uint32)", u256(0x4266), u256(0)) == encodeArgs(u256(0x4266)));
+	BOOST_CHECK(callContractFunction("f(uint32,uint32)", u256(0x4266), u256(8)) == encodeArgs(u256(0x42)));
+	BOOST_CHECK(callContractFunction("f(uint32,uint32)", u256(0x4266), u256(16)) == encodeArgs(u256(0)));
+	BOOST_CHECK(callContractFunction("f(uint32,uint32)", u256(0x4266), u256(17)) == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_right_uint8)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint8 a, uint8 b) returns (uint) {
+				return a >> b;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint8,uint8)", u256(0x66), u256(0)) == encodeArgs(u256(0x66)));
+	BOOST_CHECK(callContractFunction("f(uint8,uint8)", u256(0x66), u256(8)) == encodeArgs(u256(0x0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_right_assignment)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(uint a, uint b) returns (uint) {
+				a >>= b;
+				return a;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(0)) == encodeArgs(u256(0x4266)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(8)) == encodeArgs(u256(0x42)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(16)) == encodeArgs(u256(0)));
+	BOOST_CHECK(callContractFunction("f(uint256,uint256)", u256(0x4266), u256(17)) == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_right_negative_lvalue)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(int a, int b) returns (int) {
+				return a >> b;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(-4266), u256(0)) == encodeArgs(u256(-4266)));
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(-4266), u256(8)) == encodeArgs(u256(-16)));
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(-4266), u256(16)) == encodeArgs(u256(0)));
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(-4266), u256(17)) == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_right_negative_lvalue_assignment)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(int a, int b) returns (int) {
+				a >>= b;
+				return a;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(-4266), u256(0)) == encodeArgs(u256(-4266)));
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(-4266), u256(8)) == encodeArgs(u256(-16)));
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(-4266), u256(16)) == encodeArgs(u256(0)));
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(-4266), u256(17)) == encodeArgs(u256(0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_negative_rvalue)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(int a, int b) returns (int) {
+				return a << b;
+			}
+			function g(int a, int b) returns (int) {
+				return a >> b;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(1), u256(-1)) == encodeArgs());
+	BOOST_CHECK(callContractFunction("g(int256,int256)", u256(1), u256(-1)) == encodeArgs());
+}
+
+BOOST_AUTO_TEST_CASE(shift_negative_rvalue_assignment)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f(int a, int b) returns (int) {
+				a <<= b;
+				return a;
+			}
+			function g(int a, int b) returns (int) {
+				a >>= b;
+				return a;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f(int256,int256)", u256(1), u256(-1)) == encodeArgs());
+	BOOST_CHECK(callContractFunction("g(int256,int256)", u256(1), u256(-1)) == encodeArgs());
+}
+
+BOOST_AUTO_TEST_CASE(shift_constant_left_assignment)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f() returns (uint a) {
+				a = 0x42;
+				a <<= 8;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f()") == encodeArgs(u256(0x4200)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_constant_right_assignment)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f() returns (uint a) {
+				a = 0x4200;
+				a >>= 8;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f()") == encodeArgs(u256(0x42)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_cleanup)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f() returns (uint16 x) {
+				x = 0xffff;
+				x += 32;
+				x <<= 8;
+				x >>= 16;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f()") == encodeArgs(u256(0x0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_cleanup_garbled)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function f() returns (uint8 x) {
+				assembly {
+					x := 0xffff
+				}
+				x >>= 8;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f()") == encodeArgs(u256(0x0)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_overflow)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function leftU(uint8 x, uint8 y) returns (uint8) {
+				return x << y;
+			}
+			function leftS(int8 x, int8 y) returns (int8) {
+				return x << y;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("leftU(uint8,uint8)", 255, 8) == encodeArgs(u256(0)));
+	BOOST_CHECK(callContractFunction("leftU(uint8,uint8)", 255, 1) == encodeArgs(u256(254)));
+	BOOST_CHECK(callContractFunction("leftU(uint8,uint8)", 255, 0) == encodeArgs(u256(255)));
+
+	// Result is -128 and output is sign-extended, not zero-padded.
+	BOOST_CHECK(callContractFunction("leftS(int8,int8)", 1, 7) == encodeArgs(u256(0) - 128));
+	BOOST_CHECK(callContractFunction("leftS(int8,int8)", 1, 6) == encodeArgs(u256(64)));
+}
+
+BOOST_AUTO_TEST_CASE(shift_bytes)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function left(bytes20 x, uint8 y) returns (bytes20) {
+				return x << y;
+			}
+			function right(bytes20 x, uint8 y) returns (bytes20) {
+				return x >> y;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("left(bytes20,uint8)", "12345678901234567890", 8 * 8) == encodeArgs("901234567890" + string(8, 0)));
+	BOOST_CHECK(callContractFunction("right(bytes20,uint8)", "12345678901234567890", 8 * 8) == encodeArgs(string(8, 0) + "123456789012"));
+}
+
+BOOST_AUTO_TEST_CASE(shift_bytes_cleanup)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function left(uint8 y) returns (bytes20) {
+				bytes20 x;
+				assembly { x := "12345678901234567890abcde" }
+				return x << y;
+			}
+			function right(uint8 y) returns (bytes20) {
+				bytes20 x;
+				assembly { x := "12345678901234567890abcde" }
+				return x >> y;
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("left(uint8)", 8 * 8) == encodeArgs("901234567890" + string(8, 0)));
+	BOOST_CHECK(callContractFunction("right(uint8)", 8 * 8) == encodeArgs(string(8, 0) + "123456789012"));
+}
+
+BOOST_AUTO_TEST_CASE(cleanup_in_compound_assign)
+{
+	char const* sourceCode = R"(
+		contract C {
+			function test() returns (uint, uint) {
+				uint32 a = 0xffffffff;
+				uint16 x = uint16(a);
+				uint16 y = x;
+				x /= 0x100;
+				y = y / 0x100;
+				return (x, y);
+			}
+		}
+	)";
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("test()") == encodeArgs(u256(0xff), u256(0xff)));
+}
+
 BOOST_AUTO_TEST_CASE(inline_assembly_in_modifiers)
 {
 	char const* sourceCode = R"(