Optimize DUP1, ISZERO and POP in ifStatement

[molly-ting]

Description

   function and(uint256 a, uint256 b) public returns(uint256) {
        if (a > b || a > 100) {
            return a - b;
        } else {
            return a+b;
        }
    }

The above function will generate the following opcode.

PUSH1 0x0 DUP2 DUP4 GT DUP1 PUSH2 0x70 JUMPI POP PUSH1 0x64 DUP4 GT JUMPDEST ISZERO PUSH2 0x88 JUMPI DUP2 DUP4

The corresponding assembly code is:

...
tag_7:
        /* "condition.sol":270:277  uint256 */
      0x00
        /* "condition.sol":297:298  b */
      dup2
        /* "condition.sol":293:294  a */
      dup4
        /* "condition.sol":293:298  a > b */
      gt
        /* "condition.sol":293:309  a > b || a > 100 */
      dup1
      tag_11
      jumpi
      pop
        /* "condition.sol":306:309  100 */
      0x64
        /* "condition.sol":302:303  a */
      dup4
        /* "condition.sol":302:309  a > 100 */
      gt
        /* "condition.sol":293:309  a > b || a > 100 */
tag_11:
        /* "condition.sol":289:348  if (a > b || a > 100) {... */
      iszero
      tag_12
      jumpi
        /* "condition.sol":336:337  b */
      dup2
        /* "condition.sol":332:333  a */
      dup4
        /* "condition.sol":332:337  a - b */
…

In tag_7, there is a 'POP' just after 'JUMPI', which means the original value of the DUP is not used. Although this value is used in the other branch(tag_11), this can also be optimized.

Optimization

Specifically, moving tag_11 after iszero tag_12 jumpi would achieve this optimization. The resulting assembly code is as follows:

...
tag_7:
        /* "condition.sol":270:277  uint256 */
      0x00
        /* "condition.sol":297:298  b */
      dup2
        /* "condition.sol":293:294  a */
      dup4
        /* "condition.sol":293:298  a > b */
      gt
        /* "condition.sol":293:309  a > b || a > 100 */
      tag_11
      jumpi
        /* "condition.sol":306:309  100 */
      0x64
        /* "condition.sol":302:303  a */
      dup4
        /* "condition.sol":302:309  a > 100 */
      gt
        /* "condition.sol":293:309  a > b || a > 100 */
      iszero
      tag_12
      jumpi
tag_11:
        /* "condition.sol":336:337  b */
      dup2
        /* "condition.sol":332:333  a */
      dup4
        /* "condition.sol":332:337  a - b */
…

In this way, for a>b, it will execute PUSH1 DUP2 DUP4 GT PUSH2 JUMPI JUMPDEST DUP2 DUP4 instead of PUSH1 DUP2 DUP4 GT DUP1 PUSH2 JUMPI JUMPDEST ISZERO PUSH2 JUMPI DUP2 DUP4 . For a<=b and a>100, it will execute PUSH1 DUP2 DUP4 GT PUSH2 JUMPI PUSH1 DUP4 GT ISZERO PUSH2 JUMPI JUMPDEST DUP2 DUP4 instead of PUSH1 DUP2 DUP4 GT DUP1 PUSH2 JUMPI POP PUSH1 DUP4 GT JUMPDEST ISZERO PUSH2 JUMPI DUP2 DUP4 .

solidity/libsolidity/codegen/ExpressionCompiler.cpp

Lines 2367 to 2380 in b849b32

	void ExpressionCompiler::appendAndOrOperatorCode(BinaryOperation const& _binaryOperation)
	{
	Token const c_op = _binaryOperation.getOperator();
	solAssert(c_op == Token::Or || c_op == Token::And, "");
	_binaryOperation.leftExpression().accept(*this);
	m_context << Instruction::DUP1;
	if (c_op == Token::And)
	m_context << Instruction::ISZERO;
	evmasm::AssemblyItem endLabel = m_context.appendConditionalJump();
	m_context << Instruction::POP;
	_binaryOperation.rightExpression().accept(*this);
	m_context << endLabel;
	}

In this function, the endLabel is tag_11 in this example.

solidity/libsolidity/codegen/ContractCompiler.cpp

Lines 1153 to 1172 in b849b32

	bool ContractCompiler::visit(IfStatement const& _ifStatement)
	{
	StackHeightChecker checker(m_context);
	CompilerContext::LocationSetter locationSetter(m_context, _ifStatement);
	compileExpression(_ifStatement.condition());
	m_context << Instruction::ISZERO;
	evmasm::AssemblyItem falseTag = m_context.appendConditionalJump();
	evmasm::AssemblyItem endTag = falseTag;
	_ifStatement.trueStatement().accept(*this);
	if (_ifStatement.falseStatement())
	{
	endTag = m_context.appendJumpToNew();
	m_context << falseTag;
	_ifStatement.falseStatement()->accept(*this);
	}
	m_context << endTag;
	checker.check();
	return false;
	}

Is it possible to move the Instruction::ISZERO and conditionalJump in this function to the front of the endLabel in the function appendAndOrOperatorCode?

[molly-ting]

Another similar case is the external call.

Description

    function extcall(uint256 a) public returns(uint256) {
        uint256 res = 0;
        try l.lib(a) returns (uint256 tmp) {
            res=tmp*2;
        } catch {
            res = 1;
        }
        
        return res;
    }

The above function will generate the following opcode.

DUP1 ISZERO PUSH2 0xF5 JUMPI POP PUSH1 0x40 MLOAD ... JUMP JUMPDEST PUSH1 0x1 JUMPDEST PUSH2 0x102 JUMPI PUSH1 0x1 SWAP1 POP

The corresponding assembly code is:

...
tag_11:
      ...
      gas
      call
      swap3
      pop
      pop
      pop
      dup1
      iszero
      tag_12
      jumpi
      pop
      mload(0x40)
      …
      jump	// in
tag_13:
      0x01
tag_12:
        /* "extcall.sol":481:589  try l.lib(a) returns (uint256 tmp) {... */
      tag_15
      jumpi
        /* "extcall.sol":577:578  1 */
      0x01
        /* "extcall.sol":571:578  res = 1 */
      swap1
      pop
        /* "extcall.sol":481:589  try l.lib(a) returns (uint256 tmp) {... */
      jump(tag_19)
...

In tag_11, there is a 'POP' just after 'JUMPI', which means the original value of the DUP is not used. Although this value is used in the other branch(tag_12), this can also be optimized.

Optimization

Specifically, moving tag_12 after tag_15 jumpi would achieve this optimization. The resulting assembly code is as follows:

...
tag_11:
      ...
      gas
      call
      swap3
      pop
      pop
      pop
      iszero
      tag_12
      jumpi
      mload(0x40)
      …
      jump	// in
tag_13:
      0x01
        /* "extcall.sol":481:589  try l.lib(a) returns (uint256 tmp) {... */
      tag_15
      jumpi
tag_12:
        /* "extcall.sol":577:578  1 */
      0x01
        /* "extcall.sol":571:578  res = 1 */
      swap1
      pop
        /* "extcall.sol":481:589  try l.lib(a) returns (uint256 tmp) {... */
      jump(tag_19)
...

solidity/libsolidity/codegen/ExpressionCompiler.cpp

Lines 2854 to 2859 in b849b32

	if (_tryCall)
	{
	m_context << Instruction::DUP1 << Instruction::ISZERO;
	m_context.appendConditionalJumpTo(endTag);
	m_context << Instruction::POP;
	}

solidity/libsolidity/codegen/ExpressionCompiler.cpp

Lines 2923 to 2928 in b849b32

	if (_tryCall)
	{
	// Success branch will reach this, failure branch will directly jump to endTag.
	m_context << u256(1);
	m_context << endTag;
	}

In this function, endTag is tag_12 in this example.

solidity/libsolidity/codegen/ContractCompiler.cpp

Lines 965 to 977 in b849b32

	bool ContractCompiler::visit(TryStatement const& _tryStatement)
	{
	StackHeightChecker checker(m_context);
	CompilerContext::LocationSetter locationSetter(m_context, _tryStatement);
	compileExpression(_tryStatement.externalCall());
	int const returnSize = static_cast<int>(_tryStatement.externalCall().annotation().type->sizeOnStack());
	// Stack: [ return values] <success flag>
	evmasm::AssemblyItem successTag = m_context.appendConditionalJump();
	// Catch case.
	m_context.adjustStackOffset(-returnSize);

In this function, successTag is tag_15 in this example. Is it possible to move the conditionalJump in this function to the front of the endTag in the function appendExternalFunctionCall so that we can save one duplication and pop?

[molly-ting]

Could someone take a look at this? I believe it could reduce gas consumption