/*
This file is part of solidity.
solidity is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
solidity is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with solidity. If not, see .
*/
// SPDX-License-Identifier: GPL-3.0
/**
* @file PeepholeOptimiser.cpp
* Performs local optimising code changes to assembly.
*/
#include
#include
#include
using namespace solidity;
using namespace solidity::evmasm;
// TODO: Extend this to use the tools from ExpressionClasses.cpp
namespace
{
struct OptimiserState
{
AssemblyItems const& items;
size_t i;
std::back_insert_iterator out;
};
template
struct FunctionParameterCount;
template
struct FunctionParameterCount
{
static constexpr auto value = sizeof...(Args);
};
template
struct SimplePeepholeOptimizerMethod
{
template
static bool applyRule(
AssemblyItems::const_iterator _in,
std::back_insert_iterator _out,
std::index_sequence
)
{
return Method::applySimple(_in[Indices]..., _out);
}
static bool apply(OptimiserState& _state)
{
static constexpr size_t WindowSize = FunctionParameterCount::value - 1;
if (
_state.i + WindowSize <= _state.items.size() &&
applyRule(_state.items.begin() + static_cast(_state.i), _state.out, std::make_index_sequence{})
)
{
_state.i += WindowSize;
return true;
}
else
return false;
}
};
struct Identity: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _item,
std::back_insert_iterator _out
)
{
*_out = _item;
return true;
}
};
struct PushPop: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _push,
AssemblyItem const& _pop,
std::back_insert_iterator
)
{
auto t = _push.type();
return _pop == Instruction::POP && (
SemanticInformation::isDupInstruction(_push) ||
t == Push || t == PushTag || t == PushSub ||
t == PushSubSize || t == PushProgramSize || t == PushData || t == PushLibraryAddress
);
}
};
struct OpPop: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _op,
AssemblyItem const& _pop,
std::back_insert_iterator _out
)
{
if (_pop == Instruction::POP && _op.type() == Operation)
{
Instruction instr = _op.instruction();
if (instructionInfo(instr, langutil::EVMVersion()).ret == 1 && !instructionInfo(instr, langutil::EVMVersion()).sideEffects)
{
for (int j = 0; j < instructionInfo(instr, langutil::EVMVersion()).args; j++)
*_out = {Instruction::POP, _op.location()};
return true;
}
}
return false;
}
};
struct OpStop: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _op,
AssemblyItem const& _stop,
std::back_insert_iterator _out
)
{
if (_stop == Instruction::STOP)
{
if (_op.type() == Operation)
{
Instruction instr = _op.instruction();
if (!instructionInfo(instr, langutil::EVMVersion()).sideEffects)
{
*_out = {Instruction::STOP, _op.location()};
return true;
}
}
else if (_op.type() == Push)
{
*_out = {Instruction::STOP, _op.location()};
return true;
}
}
return false;
}
};
struct OpReturnRevert: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _op,
AssemblyItem const& _push,
AssemblyItem const& _pushOrDup,
AssemblyItem const& _returnRevert,
std::back_insert_iterator _out
)
{
if (
(_returnRevert == Instruction::RETURN || _returnRevert == Instruction::REVERT) &&
_push.type() == Push &&
(_pushOrDup.type() == Push || _pushOrDup == dupInstruction(1))
)
if (
(_op.type() == Operation && !instructionInfo(_op.instruction(), langutil::EVMVersion()).sideEffects) ||
_op.type() == Push
)
{
*_out = _push;
*_out = _pushOrDup;
*_out = _returnRevert;
return true;
}
return false;
}
};
struct DoubleSwap: SimplePeepholeOptimizerMethod
{
static size_t applySimple(
AssemblyItem const& _s1,
AssemblyItem const& _s2,
std::back_insert_iterator
)
{
return _s1 == _s2 && SemanticInformation::isSwapInstruction(_s1);
}
};
struct DoublePush: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _push1,
AssemblyItem const& _push2,
std::back_insert_iterator _out
)
{
if (_push1.type() == Push && _push2.type() == Push && _push1.data() == _push2.data())
{
*_out = _push1;
*_out = {Instruction::DUP1, _push2.location()};
return true;
}
else
return false;
}
};
struct CommutativeSwap: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _swap,
AssemblyItem const& _op,
std::back_insert_iterator _out
)
{
// Remove SWAP1 if following instruction is commutative
if (
_swap == Instruction::SWAP1 &&
SemanticInformation::isCommutativeOperation(_op)
)
{
*_out = _op;
return true;
}
else
return false;
}
};
struct SwapComparison: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _swap,
AssemblyItem const& _op,
std::back_insert_iterator _out
)
{
static std::map const swappableOps{
{ Instruction::LT, Instruction::GT },
{ Instruction::GT, Instruction::LT },
{ Instruction::SLT, Instruction::SGT },
{ Instruction::SGT, Instruction::SLT }
};
if (
_swap == Instruction::SWAP1 &&
_op.type() == Operation &&
swappableOps.count(_op.instruction())
)
{
*_out = swappableOps.at(_op.instruction());
return true;
}
else
return false;
}
};
/// Remove swapN after dupN
struct DupSwap: SimplePeepholeOptimizerMethod
{
static size_t applySimple(
AssemblyItem const& _dupN,
AssemblyItem const& _swapN,
std::back_insert_iterator _out
)
{
if (
SemanticInformation::isDupInstruction(_dupN) &&
SemanticInformation::isSwapInstruction(_swapN) &&
getDupNumber(_dupN.instruction()) == getSwapNumber(_swapN.instruction())
)
{
*_out = _dupN;
return true;
}
else
return false;
}
};
struct IsZeroIsZeroJumpI: SimplePeepholeOptimizerMethod
{
static size_t applySimple(
AssemblyItem const& _iszero1,
AssemblyItem const& _iszero2,
AssemblyItem const& _pushTag,
AssemblyItem const& _jumpi,
std::back_insert_iterator _out
)
{
if (
_iszero1 == Instruction::ISZERO &&
_iszero2 == Instruction::ISZERO &&
_pushTag.type() == PushTag &&
_jumpi == Instruction::JUMPI
)
{
*_out = _pushTag;
*_out = _jumpi;
return true;
}
else
return false;
}
};
struct EqIsZeroJumpI: SimplePeepholeOptimizerMethod
{
static size_t applySimple(
AssemblyItem const& _eq,
AssemblyItem const& _iszero,
AssemblyItem const& _pushTag,
AssemblyItem const& _jumpi,
std::back_insert_iterator _out
)
{
if (
_eq == Instruction::EQ &&
_iszero == Instruction::ISZERO &&
_pushTag.type() == PushTag &&
_jumpi == Instruction::JUMPI
)
{
*_out = AssemblyItem(Instruction::SUB, _eq.location());
*_out = _pushTag;
*_out = _jumpi;
return true;
}
else
return false;
}
};
// push_tag_1 jumpi push_tag_2 jump tag_1: -> iszero push_tag_2 jumpi tag_1:
struct DoubleJump: SimplePeepholeOptimizerMethod
{
static size_t applySimple(
AssemblyItem const& _pushTag1,
AssemblyItem const& _jumpi,
AssemblyItem const& _pushTag2,
AssemblyItem const& _jump,
AssemblyItem const& _tag1,
std::back_insert_iterator _out
)
{
if (
_pushTag1.type() == PushTag &&
_jumpi == Instruction::JUMPI &&
_pushTag2.type() == PushTag &&
_jump == Instruction::JUMP &&
_tag1.type() == Tag &&
_pushTag1.data() == _tag1.data()
)
{
*_out = AssemblyItem(Instruction::ISZERO, _jumpi.location());
*_out = _pushTag2;
*_out = _jumpi;
*_out = _tag1;
return true;
}
else
return false;
}
};
struct JumpToNext: SimplePeepholeOptimizerMethod
{
static size_t applySimple(
AssemblyItem const& _pushTag,
AssemblyItem const& _jump,
AssemblyItem const& _tag,
std::back_insert_iterator _out
)
{
if (
_pushTag.type() == PushTag &&
(_jump == Instruction::JUMP || _jump == Instruction::JUMPI) &&
_tag.type() == Tag &&
_pushTag.data() == _tag.data()
)
{
if (_jump == Instruction::JUMPI)
*_out = AssemblyItem(Instruction::POP, _jump.location());
*_out = _tag;
return true;
}
else
return false;
}
};
struct TagConjunctions: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _pushTag,
AssemblyItem const& _pushConstant,
AssemblyItem const& _and,
std::back_insert_iterator _out
)
{
if (_and != Instruction::AND)
return false;
if (
_pushTag.type() == PushTag &&
_pushConstant.type() == Push &&
(_pushConstant.data() & u256(0xFFFFFFFF)) == u256(0xFFFFFFFF)
)
{
*_out = _pushTag;
return true;
}
else if (
// tag and constant are swapped
_pushConstant.type() == PushTag &&
_pushTag.type() == Push &&
(_pushTag.data() & u256(0xFFFFFFFF)) == u256(0xFFFFFFFF)
)
{
*_out = _pushConstant;
return true;
}
else
return false;
}
};
struct TruthyAnd: SimplePeepholeOptimizerMethod
{
static bool applySimple(
AssemblyItem const& _push,
AssemblyItem const& _not,
AssemblyItem const& _and,
std::back_insert_iterator
)
{
return (
_push.type() == Push && _push.data() == 0 &&
_not == Instruction::NOT &&
_and == Instruction::AND
);
}
};
/// Removes everything after a JUMP (or similar) until the next JUMPDEST.
struct UnreachableCode
{
static bool apply(OptimiserState& _state)
{
auto it = _state.items.begin() + static_cast(_state.i);
auto end = _state.items.end();
if (it == end)
return false;
if (
it[0] != Instruction::JUMP &&
it[0] != Instruction::RETURN &&
it[0] != Instruction::STOP &&
it[0] != Instruction::INVALID &&
it[0] != Instruction::SELFDESTRUCT &&
it[0] != Instruction::REVERT
)
return false;
ptrdiff_t i = 1;
while (it + i != end && it[i].type() != Tag)
i++;
if (i > 1)
{
*_state.out = it[0];
_state.i += static_cast(i);
return true;
}
else
return false;
}
};
void applyMethods(OptimiserState&)
{
assertThrow(false, OptimizerException, "Peephole optimizer failed to apply identity.");
}
template
void applyMethods(OptimiserState& _state, Method, OtherMethods... _other)
{
if (!Method::apply(_state))
applyMethods(_state, _other...);
}
size_t numberOfPops(AssemblyItems const& _items)
{
return static_cast(std::count(_items.begin(), _items.end(), Instruction::POP));
}
}
bool PeepholeOptimiser::optimise()
{
// Avoid referencing immutables too early by using approx. counting in bytesRequired()
auto const approx = evmasm::Precision::Approximate;
OptimiserState state {m_items, 0, back_inserter(m_optimisedItems)};
while (state.i < m_items.size())
applyMethods(
state,
PushPop(), OpPop(), OpStop(), OpReturnRevert(), DoublePush(), DoubleSwap(), CommutativeSwap(), SwapComparison(),
DupSwap(), IsZeroIsZeroJumpI(), EqIsZeroJumpI(), DoubleJump(), JumpToNext(), UnreachableCode(),
TagConjunctions(), TruthyAnd(), Identity()
);
if (m_optimisedItems.size() < m_items.size() || (
m_optimisedItems.size() == m_items.size() && (
evmasm::bytesRequired(m_optimisedItems, 3, m_evmVersion, approx) < evmasm::bytesRequired(m_items, 3, m_evmVersion, approx) ||
numberOfPops(m_optimisedItems) > numberOfPops(m_items)
)
))
{
m_items = std::move(m_optimisedItems);
return true;
}
else
return false;
}