diff options
Diffstat (limited to 'libjulia')
56 files changed, 0 insertions, 5418 deletions
diff --git a/libjulia/ASTDataForward.h b/libjulia/ASTDataForward.h deleted file mode 100644 index 143b9c46..00000000 --- a/libjulia/ASTDataForward.h +++ /dev/null @@ -1,54 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * @date 2017 - * Pull in some identifiers from the solidity::assembly namespace. - */ - -#pragma once - -#include <libsolidity/inlineasm/AsmDataForward.h> - -namespace dev -{ -namespace julia -{ - -using Instruction = solidity::assembly::Instruction; -using Literal = solidity::assembly::Literal; -using Label = solidity::assembly::Label; -using StackAssignment = solidity::assembly::StackAssignment; -using Identifier = solidity::assembly::Identifier; -using Assignment = solidity::assembly::Assignment; -using VariableDeclaration = solidity::assembly::VariableDeclaration; -using FunctionalInstruction = solidity::assembly::FunctionalInstruction; -using FunctionDefinition = solidity::assembly::FunctionDefinition; -using FunctionCall = solidity::assembly::FunctionCall; -using If = solidity::assembly::If; -using Case = solidity::assembly::Case; -using Switch = solidity::assembly::Switch; -using ForLoop = solidity::assembly::ForLoop; -using ExpressionStatement = solidity::assembly::ExpressionStatement; -using Block = solidity::assembly::Block; - -using TypedName = solidity::assembly::TypedName; - -using Expression = boost::variant<FunctionalInstruction, FunctionCall, Identifier, Literal>; -using Statement = boost::variant<ExpressionStatement, Instruction, Label, StackAssignment, Assignment, VariableDeclaration, FunctionDefinition, If, Switch, ForLoop, Block>; - -} -} diff --git a/libjulia/Exceptions.h b/libjulia/Exceptions.h deleted file mode 100644 index 48624a56..00000000 --- a/libjulia/Exceptions.h +++ /dev/null @@ -1,35 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Exceptions in Yul. - */ - -#pragma once - -#include <libdevcore/Exceptions.h> -#include <libdevcore/Assertions.h> - -namespace dev -{ -namespace julia -{ - -struct YulException: virtual Exception {}; -struct OptimizerException: virtual YulException {}; - -} -} diff --git a/libjulia/backends/evm/AbstractAssembly.h b/libjulia/backends/evm/AbstractAssembly.h deleted file mode 100644 index b6818923..00000000 --- a/libjulia/backends/evm/AbstractAssembly.h +++ /dev/null @@ -1,119 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * @date 2017 - * Abstract assembly interface, subclasses of which are to be used with the generic - * bytecode generator. - */ - -#pragma once - -#include <libdevcore/CommonData.h> - -#include <functional> - -namespace dev -{ -struct SourceLocation; -namespace solidity -{ -enum class Instruction: uint8_t; -namespace assembly -{ -struct Instruction; -struct Identifier; -} -} -namespace julia -{ - -/// -/// Assembly class that abstracts both the libevmasm assembly and the new Yul assembly. -/// -class AbstractAssembly -{ -public: - using LabelID = size_t; - - virtual ~AbstractAssembly() {} - - /// Set a new source location valid starting from the next instruction. - virtual void setSourceLocation(SourceLocation const& _location) = 0; - /// Retrieve the current height of the stack. This does not have to be zero - /// at the beginning. - virtual int stackHeight() const = 0; - /// Append an EVM instruction. - virtual void appendInstruction(solidity::Instruction _instruction) = 0; - /// Append a constant. - virtual void appendConstant(u256 const& _constant) = 0; - /// Append a label. - virtual void appendLabel(LabelID _labelId) = 0; - /// Append a label reference. - virtual void appendLabelReference(LabelID _labelId) = 0; - /// Generate a new unique label. - virtual LabelID newLabelId() = 0; - /// Returns a label identified by the given name. Creates it if it does not yet exist. - virtual LabelID namedLabel(std::string const& _name) = 0; - /// Append a reference to a to-be-linked symbol. - /// Currently, we assume that the value is always a 20 byte number. - virtual void appendLinkerSymbol(std::string const& _name) = 0; - - /// Append a jump instruction. - /// @param _stackDiffAfter the stack adjustment after this instruction. - /// This is helpful to stack height analysis if there is no continuing control flow. - virtual void appendJump(int _stackDiffAfter) = 0; - - /// Append a jump-to-immediate operation. - /// @param _stackDiffAfter the stack adjustment after this instruction. - virtual void appendJumpTo(LabelID _labelId, int _stackDiffAfter = 0) = 0; - /// Append a jump-to-if-immediate operation. - virtual void appendJumpToIf(LabelID _labelId) = 0; - /// Start a subroutine identified by @a _labelId that takes @a _arguments - /// stack slots as arguments. - virtual void appendBeginsub(LabelID _labelId, int _arguments) = 0; - /// Call a subroutine identified by @a _labelId, taking @a _arguments from the - /// stack upon call and putting @a _returns arguments onto the stack upon return. - virtual void appendJumpsub(LabelID _labelId, int _arguments, int _returns) = 0; - /// Return from a subroutine. - /// @param _stackDiffAfter the stack adjustment after this instruction. - virtual void appendReturnsub(int _returns, int _stackDiffAfter = 0) = 0; - - /// Append the assembled size as a constant. - virtual void appendAssemblySize() = 0; -}; - -enum class IdentifierContext { LValue, RValue }; - -/// Object that is used to resolve references and generate code for access to identifiers external -/// to inline assembly (not used in standalone assembly mode). -struct ExternalIdentifierAccess -{ - using Resolver = std::function<size_t(solidity::assembly::Identifier const&, IdentifierContext, bool /*_crossesFunctionBoundary*/)>; - /// Resolve an external reference given by the identifier in the given context. - /// @returns the size of the value (number of stack slots) or size_t(-1) if not found. - Resolver resolve; - using CodeGenerator = std::function<void(solidity::assembly::Identifier const&, IdentifierContext, julia::AbstractAssembly&)>; - /// Generate code for retrieving the value (rvalue context) or storing the value (lvalue context) - /// of an identifier. The code should be appended to the assembly. In rvalue context, the value is supposed - /// to be put onto the stack, in lvalue context, the value is assumed to be at the top of the stack. - CodeGenerator generateCode; -}; - - - -} -} diff --git a/libjulia/backends/evm/EVMAssembly.cpp b/libjulia/backends/evm/EVMAssembly.cpp deleted file mode 100644 index 07ad05c9..00000000 --- a/libjulia/backends/evm/EVMAssembly.cpp +++ /dev/null @@ -1,202 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Assembly interface for EVM and EVM1.5. - */ - -#include <libjulia/backends/evm/EVMAssembly.h> - -#include <libevmasm/Instruction.h> - -#include <libsolidity/interface/Exceptions.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -namespace -{ -/// Size of labels in bytes. Four-byte labels are required by some EVM1.5 instructions. -size_t constexpr labelReferenceSize = 4; - -size_t constexpr assemblySizeReferenceSize = 4; -} - - -void EVMAssembly::setSourceLocation(SourceLocation const&) -{ - // Ignored for now; -} - -void EVMAssembly::appendInstruction(solidity::Instruction _instr) -{ - m_bytecode.push_back(byte(_instr)); - m_stackHeight += solidity::instructionInfo(_instr).ret - solidity::instructionInfo(_instr).args; -} - -void EVMAssembly::appendConstant(u256 const& _constant) -{ - bytes data = toCompactBigEndian(_constant, 1); - appendInstruction(solidity::pushInstruction(data.size())); - m_bytecode += data; -} - -void EVMAssembly::appendLabel(LabelID _labelId) -{ - setLabelToCurrentPosition(_labelId); - appendInstruction(solidity::Instruction::JUMPDEST); -} - -void EVMAssembly::appendLabelReference(LabelID _labelId) -{ - solAssert(!m_evm15, "Cannot use plain label references in EMV1.5 mode."); - // @TODO we now always use labelReferenceSize for all labels, it could be shortened - // for some of them. - appendInstruction(solidity::pushInstruction(labelReferenceSize)); - m_labelReferences[m_bytecode.size()] = _labelId; - m_bytecode += bytes(labelReferenceSize); -} - -EVMAssembly::LabelID EVMAssembly::newLabelId() -{ - m_labelPositions[m_nextLabelId] = size_t(-1); - return m_nextLabelId++; -} - -AbstractAssembly::LabelID EVMAssembly::namedLabel(string const& _name) -{ - solAssert(!_name.empty(), ""); - if (!m_namedLabels.count(_name)) - m_namedLabels[_name] = newLabelId(); - return m_namedLabels[_name]; -} - -void EVMAssembly::appendLinkerSymbol(string const&) -{ - solAssert(false, "Linker symbols not yet implemented."); -} - -void EVMAssembly::appendJump(int _stackDiffAfter) -{ - solAssert(!m_evm15, "Plain JUMP used for EVM 1.5"); - appendInstruction(solidity::Instruction::JUMP); - m_stackHeight += _stackDiffAfter; -} - -void EVMAssembly::appendJumpTo(LabelID _labelId, int _stackDiffAfter) -{ - if (m_evm15) - { - m_bytecode.push_back(byte(solidity::Instruction::JUMPTO)); - appendLabelReferenceInternal(_labelId); - m_stackHeight += _stackDiffAfter; - } - else - { - appendLabelReference(_labelId); - appendJump(_stackDiffAfter); - } -} - -void EVMAssembly::appendJumpToIf(LabelID _labelId) -{ - if (m_evm15) - { - m_bytecode.push_back(byte(solidity::Instruction::JUMPIF)); - appendLabelReferenceInternal(_labelId); - m_stackHeight--; - } - else - { - appendLabelReference(_labelId); - appendInstruction(solidity::Instruction::JUMPI); - } -} - -void EVMAssembly::appendBeginsub(LabelID _labelId, int _arguments) -{ - solAssert(m_evm15, "BEGINSUB used for EVM 1.0"); - solAssert(_arguments >= 0, ""); - setLabelToCurrentPosition(_labelId); - m_bytecode.push_back(byte(solidity::Instruction::BEGINSUB)); - m_stackHeight += _arguments; -} - -void EVMAssembly::appendJumpsub(LabelID _labelId, int _arguments, int _returns) -{ - solAssert(m_evm15, "JUMPSUB used for EVM 1.0"); - solAssert(_arguments >= 0 && _returns >= 0, ""); - m_bytecode.push_back(byte(solidity::Instruction::JUMPSUB)); - appendLabelReferenceInternal(_labelId); - m_stackHeight += _returns - _arguments; -} - -void EVMAssembly::appendReturnsub(int _returns, int _stackDiffAfter) -{ - solAssert(m_evm15, "RETURNSUB used for EVM 1.0"); - solAssert(_returns >= 0, ""); - m_bytecode.push_back(byte(solidity::Instruction::RETURNSUB)); - m_stackHeight += _stackDiffAfter - _returns; -} - -eth::LinkerObject EVMAssembly::finalize() -{ - size_t bytecodeSize = m_bytecode.size(); - for (auto const& ref: m_assemblySizePositions) - updateReference(ref, assemblySizeReferenceSize, u256(bytecodeSize)); - - for (auto const& ref: m_labelReferences) - { - size_t referencePos = ref.first; - solAssert(m_labelPositions.count(ref.second), ""); - size_t labelPos = m_labelPositions.at(ref.second); - solAssert(labelPos != size_t(-1), "Undefined but allocated label used."); - updateReference(referencePos, labelReferenceSize, u256(labelPos)); - } - - eth::LinkerObject obj; - obj.bytecode = m_bytecode; - return obj; -} - -void EVMAssembly::setLabelToCurrentPosition(LabelID _labelId) -{ - solAssert(m_labelPositions.count(_labelId), "Label not found."); - solAssert(m_labelPositions[_labelId] == size_t(-1), "Label already set."); - m_labelPositions[_labelId] = m_bytecode.size(); -} - -void EVMAssembly::appendLabelReferenceInternal(LabelID _labelId) -{ - m_labelReferences[m_bytecode.size()] = _labelId; - m_bytecode += bytes(labelReferenceSize); -} - -void EVMAssembly::appendAssemblySize() -{ - appendInstruction(solidity::pushInstruction(assemblySizeReferenceSize)); - m_assemblySizePositions.push_back(m_bytecode.size()); - m_bytecode += bytes(assemblySizeReferenceSize); -} - -void EVMAssembly::updateReference(size_t pos, size_t size, u256 value) -{ - solAssert(m_bytecode.size() >= size && pos <= m_bytecode.size() - size, ""); - solAssert(value < (u256(1) << (8 * size)), ""); - for (size_t i = 0; i < size; i++) - m_bytecode[pos + i] = byte((value >> (8 * (size - i - 1))) & 0xff); -} diff --git a/libjulia/backends/evm/EVMAssembly.h b/libjulia/backends/evm/EVMAssembly.h deleted file mode 100644 index 56ae7655..00000000 --- a/libjulia/backends/evm/EVMAssembly.h +++ /dev/null @@ -1,97 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Assembly interface for EVM and EVM1.5. - */ - -#pragma once - -#include <libjulia/backends/evm/AbstractAssembly.h> - -#include <libevmasm/LinkerObject.h> - -#include <map> - -namespace dev -{ -namespace julia -{ - -class EVMAssembly: public AbstractAssembly -{ -public: - explicit EVMAssembly(bool _evm15 = false): m_evm15(_evm15) { } - virtual ~EVMAssembly() {} - - /// Set a new source location valid starting from the next instruction. - virtual void setSourceLocation(SourceLocation const& _location) override; - /// Retrieve the current height of the stack. This does not have to be zero - /// at the beginning. - virtual int stackHeight() const override { return m_stackHeight; } - /// Append an EVM instruction. - virtual void appendInstruction(solidity::Instruction _instruction) override; - /// Append a constant. - virtual void appendConstant(u256 const& _constant) override; - /// Append a label. - virtual void appendLabel(LabelID _labelId) override; - /// Append a label reference. - virtual void appendLabelReference(LabelID _labelId) override; - /// Generate a new unique label. - virtual LabelID newLabelId() override; - /// Returns a label identified by the given name. Creates it if it does not yet exist. - virtual LabelID namedLabel(std::string const& _name) override; - /// Append a reference to a to-be-linked symbol. - /// Currently, we assume that the value is always a 20 byte number. - virtual void appendLinkerSymbol(std::string const& _name) override; - - /// Append a jump instruction. - /// @param _stackDiffAfter the stack adjustment after this instruction. - virtual void appendJump(int _stackDiffAfter) override; - /// Append a jump-to-immediate operation. - virtual void appendJumpTo(LabelID _labelId, int _stackDiffAfter) override; - /// Append a jump-to-if-immediate operation. - virtual void appendJumpToIf(LabelID _labelId) override; - /// Start a subroutine. - virtual void appendBeginsub(LabelID _labelId, int _arguments) override; - /// Call a subroutine. - virtual void appendJumpsub(LabelID _labelId, int _arguments, int _returns) override; - /// Return from a subroutine. - virtual void appendReturnsub(int _returns, int _stackDiffAfter) override; - - /// Append the assembled size as a constant. - virtual void appendAssemblySize() override; - - /// Resolves references inside the bytecode and returns the linker object. - eth::LinkerObject finalize(); - -private: - void setLabelToCurrentPosition(AbstractAssembly::LabelID _labelId); - void appendLabelReferenceInternal(AbstractAssembly::LabelID _labelId); - void updateReference(size_t pos, size_t size, u256 value); - - bool m_evm15 = false; ///< if true, switch to evm1.5 mode - LabelID m_nextLabelId = 0; - int m_stackHeight = 0; - bytes m_bytecode; - std::map<std::string, LabelID> m_namedLabels; - std::map<LabelID, size_t> m_labelPositions; - std::map<size_t, LabelID> m_labelReferences; - std::vector<size_t> m_assemblySizePositions; -}; - -} -} diff --git a/libjulia/backends/evm/EVMCodeTransform.cpp b/libjulia/backends/evm/EVMCodeTransform.cpp deleted file mode 100644 index dc536f77..00000000 --- a/libjulia/backends/evm/EVMCodeTransform.cpp +++ /dev/null @@ -1,557 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Common code generator for translating Yul / inline assembly to EVM and EVM1.5. - */ - -#include <libjulia/backends/evm/EVMCodeTransform.h> - -#include <libsolidity/inlineasm/AsmAnalysisInfo.h> -#include <libsolidity/inlineasm/AsmData.h> - -#include <libsolidity/interface/Exceptions.h> - -#include <boost/range/adaptor/reversed.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - -using Scope = dev::solidity::assembly::Scope; - -void CodeTransform::operator()(VariableDeclaration const& _varDecl) -{ - solAssert(m_scope, ""); - - int const numVariables = _varDecl.variables.size(); - int height = m_assembly.stackHeight(); - if (_varDecl.value) - { - boost::apply_visitor(*this, *_varDecl.value); - expectDeposit(numVariables, height); - } - else - { - int variablesLeft = numVariables; - while (variablesLeft--) - m_assembly.appendConstant(u256(0)); - } - for (auto const& variable: _varDecl.variables) - { - auto& var = boost::get<Scope::Variable>(m_scope->identifiers.at(variable.name)); - m_context->variableStackHeights[&var] = height++; - } - checkStackHeight(&_varDecl); -} - -void CodeTransform::operator()(Assignment const& _assignment) -{ - int height = m_assembly.stackHeight(); - boost::apply_visitor(*this, *_assignment.value); - expectDeposit(_assignment.variableNames.size(), height); - - m_assembly.setSourceLocation(_assignment.location); - generateMultiAssignment(_assignment.variableNames); - checkStackHeight(&_assignment); -} - -void CodeTransform::operator()(StackAssignment const& _assignment) -{ - m_assembly.setSourceLocation(_assignment.location); - generateAssignment(_assignment.variableName); - checkStackHeight(&_assignment); -} - -void CodeTransform::operator()(ExpressionStatement const& _statement) -{ - m_assembly.setSourceLocation(_statement.location); - boost::apply_visitor(*this, _statement.expression); - checkStackHeight(&_statement); -} - -void CodeTransform::operator()(Label const& _label) -{ - m_assembly.setSourceLocation(_label.location); - solAssert(m_scope, ""); - solAssert(m_scope->identifiers.count(_label.name), ""); - Scope::Label& label = boost::get<Scope::Label>(m_scope->identifiers.at(_label.name)); - m_assembly.appendLabel(labelID(label)); - checkStackHeight(&_label); -} - -void CodeTransform::operator()(FunctionCall const& _call) -{ - solAssert(m_scope, ""); - - m_assembly.setSourceLocation(_call.location); - EVMAssembly::LabelID returnLabel(-1); // only used for evm 1.0 - if (!m_evm15) - { - returnLabel = m_assembly.newLabelId(); - m_assembly.appendLabelReference(returnLabel); - m_stackAdjustment++; - } - - Scope::Function* function = nullptr; - solAssert(m_scope->lookup(_call.functionName.name, Scope::NonconstVisitor( - [=](Scope::Variable&) { solAssert(false, "Expected function name."); }, - [=](Scope::Label&) { solAssert(false, "Expected function name."); }, - [&](Scope::Function& _function) { function = &_function; } - )), "Function name not found."); - solAssert(function, ""); - solAssert(function->arguments.size() == _call.arguments.size(), ""); - for (auto const& arg: _call.arguments | boost::adaptors::reversed) - visitExpression(arg); - m_assembly.setSourceLocation(_call.location); - if (m_evm15) - m_assembly.appendJumpsub(functionEntryID(_call.functionName.name, *function), function->arguments.size(), function->returns.size()); - else - { - m_assembly.appendJumpTo(functionEntryID(_call.functionName.name, *function), function->returns.size() - function->arguments.size() - 1); - m_assembly.appendLabel(returnLabel); - m_stackAdjustment--; - } - checkStackHeight(&_call); -} - -void CodeTransform::operator()(FunctionalInstruction const& _instruction) -{ - if (m_evm15 && ( - _instruction.instruction == solidity::Instruction::JUMP || - _instruction.instruction == solidity::Instruction::JUMPI - )) - { - bool const isJumpI = _instruction.instruction == solidity::Instruction::JUMPI; - if (isJumpI) - { - solAssert(_instruction.arguments.size() == 2, ""); - visitExpression(_instruction.arguments.at(1)); - } - else - { - solAssert(_instruction.arguments.size() == 1, ""); - } - m_assembly.setSourceLocation(_instruction.location); - auto label = labelFromIdentifier(boost::get<assembly::Identifier>(_instruction.arguments.at(0))); - if (isJumpI) - m_assembly.appendJumpToIf(label); - else - m_assembly.appendJumpTo(label); - } - else - { - for (auto const& arg: _instruction.arguments | boost::adaptors::reversed) - visitExpression(arg); - m_assembly.setSourceLocation(_instruction.location); - m_assembly.appendInstruction(_instruction.instruction); - } - checkStackHeight(&_instruction); -} - -void CodeTransform::operator()(assembly::Identifier const& _identifier) -{ - m_assembly.setSourceLocation(_identifier.location); - // First search internals, then externals. - solAssert(m_scope, ""); - if (m_scope->lookup(_identifier.name, Scope::NonconstVisitor( - [=](Scope::Variable& _var) - { - if (int heightDiff = variableHeightDiff(_var, false)) - m_assembly.appendInstruction(solidity::dupInstruction(heightDiff)); - else - // Store something to balance the stack - m_assembly.appendConstant(u256(0)); - }, - [=](Scope::Label& _label) - { - m_assembly.appendLabelReference(labelID(_label)); - }, - [=](Scope::Function&) - { - solAssert(false, "Function not removed during desugaring."); - } - ))) - { - return; - } - solAssert( - m_identifierAccess.generateCode, - "Identifier not found and no external access available." - ); - m_identifierAccess.generateCode(_identifier, IdentifierContext::RValue, m_assembly); - checkStackHeight(&_identifier); -} - -void CodeTransform::operator()(assembly::Literal const& _literal) -{ - m_assembly.setSourceLocation(_literal.location); - if (_literal.kind == assembly::LiteralKind::Number) - m_assembly.appendConstant(u256(_literal.value)); - else if (_literal.kind == assembly::LiteralKind::Boolean) - { - if (_literal.value == "true") - m_assembly.appendConstant(u256(1)); - else - m_assembly.appendConstant(u256(0)); - } - else - { - solAssert(_literal.value.size() <= 32, ""); - m_assembly.appendConstant(u256(h256(_literal.value, h256::FromBinary, h256::AlignLeft))); - } - checkStackHeight(&_literal); -} - -void CodeTransform::operator()(assembly::Instruction const& _instruction) -{ - solAssert(!m_evm15 || _instruction.instruction != solidity::Instruction::JUMP, "Bare JUMP instruction used for EVM1.5"); - solAssert(!m_evm15 || _instruction.instruction != solidity::Instruction::JUMPI, "Bare JUMPI instruction used for EVM1.5"); - m_assembly.setSourceLocation(_instruction.location); - m_assembly.appendInstruction(_instruction.instruction); - checkStackHeight(&_instruction); -} - -void CodeTransform::operator()(If const& _if) -{ - visitExpression(*_if.condition); - m_assembly.setSourceLocation(_if.location); - m_assembly.appendInstruction(solidity::Instruction::ISZERO); - AbstractAssembly::LabelID end = m_assembly.newLabelId(); - m_assembly.appendJumpToIf(end); - (*this)(_if.body); - m_assembly.setSourceLocation(_if.location); - m_assembly.appendLabel(end); - checkStackHeight(&_if); -} - -void CodeTransform::operator()(Switch const& _switch) -{ - //@TODO use JUMPV in EVM1.5? - - visitExpression(*_switch.expression); - int expressionHeight = m_assembly.stackHeight(); - map<Case const*, AbstractAssembly::LabelID> caseBodies; - AbstractAssembly::LabelID end = m_assembly.newLabelId(); - for (Case const& c: _switch.cases) - { - if (c.value) - { - (*this)(*c.value); - m_assembly.setSourceLocation(c.location); - AbstractAssembly::LabelID bodyLabel = m_assembly.newLabelId(); - caseBodies[&c] = bodyLabel; - solAssert(m_assembly.stackHeight() == expressionHeight + 1, ""); - m_assembly.appendInstruction(solidity::dupInstruction(2)); - m_assembly.appendInstruction(solidity::Instruction::EQ); - m_assembly.appendJumpToIf(bodyLabel); - } - else - // default case - (*this)(c.body); - } - m_assembly.setSourceLocation(_switch.location); - m_assembly.appendJumpTo(end); - - size_t numCases = caseBodies.size(); - for (auto const& c: caseBodies) - { - m_assembly.setSourceLocation(c.first->location); - m_assembly.appendLabel(c.second); - (*this)(c.first->body); - // Avoid useless "jump to next" for the last case. - if (--numCases > 0) - { - m_assembly.setSourceLocation(c.first->location); - m_assembly.appendJumpTo(end); - } - } - - m_assembly.setSourceLocation(_switch.location); - m_assembly.appendLabel(end); - m_assembly.appendInstruction(solidity::Instruction::POP); - checkStackHeight(&_switch); -} - -void CodeTransform::operator()(FunctionDefinition const& _function) -{ - solAssert(m_scope, ""); - solAssert(m_scope->identifiers.count(_function.name), ""); - Scope::Function& function = boost::get<Scope::Function>(m_scope->identifiers.at(_function.name)); - - int const localStackAdjustment = m_evm15 ? 0 : 1; - int height = localStackAdjustment; - solAssert(m_info.scopes.at(&_function.body), ""); - Scope* varScope = m_info.scopes.at(m_info.virtualBlocks.at(&_function).get()).get(); - solAssert(varScope, ""); - for (auto const& v: _function.parameters | boost::adaptors::reversed) - { - auto& var = boost::get<Scope::Variable>(varScope->identifiers.at(v.name)); - m_context->variableStackHeights[&var] = height++; - } - - m_assembly.setSourceLocation(_function.location); - int stackHeightBefore = m_assembly.stackHeight(); - AbstractAssembly::LabelID afterFunction = m_assembly.newLabelId(); - - if (m_evm15) - { - m_assembly.appendJumpTo(afterFunction, -stackHeightBefore); - m_assembly.appendBeginsub(functionEntryID(_function.name, function), _function.parameters.size()); - } - else - { - m_assembly.appendJumpTo(afterFunction, -stackHeightBefore + height); - m_assembly.appendLabel(functionEntryID(_function.name, function)); - } - m_stackAdjustment += localStackAdjustment; - - for (auto const& v: _function.returnVariables) - { - auto& var = boost::get<Scope::Variable>(varScope->identifiers.at(v.name)); - m_context->variableStackHeights[&var] = height++; - // Preset stack slots for return variables to zero. - m_assembly.appendConstant(u256(0)); - } - - CodeTransform( - m_assembly, - m_info, - m_yul, - m_evm15, - m_identifierAccess, - m_useNamedLabelsForFunctions, - localStackAdjustment, - m_context - )(_function.body); - - { - // The stack layout here is: - // <return label>? <arguments...> <return values...> - // But we would like it to be: - // <return values...> <return label>? - // So we have to append some SWAP and POP instructions. - - // This vector holds the desired target positions of all stack slots and is - // modified parallel to the actual stack. - vector<int> stackLayout; - if (!m_evm15) - stackLayout.push_back(_function.returnVariables.size()); // Move return label to the top - stackLayout += vector<int>(_function.parameters.size(), -1); // discard all arguments - for (size_t i = 0; i < _function.returnVariables.size(); ++i) - stackLayout.push_back(i); // Move return values down, but keep order. - - solAssert(stackLayout.size() <= 17, "Stack too deep"); - while (!stackLayout.empty() && stackLayout.back() != int(stackLayout.size() - 1)) - if (stackLayout.back() < 0) - { - m_assembly.appendInstruction(solidity::Instruction::POP); - stackLayout.pop_back(); - } - else - { - m_assembly.appendInstruction(swapInstruction(stackLayout.size() - stackLayout.back() - 1)); - swap(stackLayout[stackLayout.back()], stackLayout.back()); - } - for (int i = 0; size_t(i) < stackLayout.size(); ++i) - solAssert(i == stackLayout[i], "Error reshuffling stack."); - } - - if (m_evm15) - m_assembly.appendReturnsub(_function.returnVariables.size(), stackHeightBefore); - else - m_assembly.appendJump(stackHeightBefore - _function.returnVariables.size()); - m_stackAdjustment -= localStackAdjustment; - m_assembly.appendLabel(afterFunction); - checkStackHeight(&_function); -} - -void CodeTransform::operator()(ForLoop const& _forLoop) -{ - Scope* originalScope = m_scope; - // We start with visiting the block, but not finalizing it. - m_scope = m_info.scopes.at(&_forLoop.pre).get(); - int stackStartHeight = m_assembly.stackHeight(); - - visitStatements(_forLoop.pre.statements); - - // TODO: When we implement break and continue, the labels and the stack heights at that point - // have to be stored in a stack. - AbstractAssembly::LabelID loopStart = m_assembly.newLabelId(); - AbstractAssembly::LabelID loopEnd = m_assembly.newLabelId(); - AbstractAssembly::LabelID postPart = m_assembly.newLabelId(); - - m_assembly.setSourceLocation(_forLoop.location); - m_assembly.appendLabel(loopStart); - - visitExpression(*_forLoop.condition); - m_assembly.setSourceLocation(_forLoop.location); - m_assembly.appendInstruction(solidity::Instruction::ISZERO); - m_assembly.appendJumpToIf(loopEnd); - - (*this)(_forLoop.body); - - m_assembly.setSourceLocation(_forLoop.location); - m_assembly.appendLabel(postPart); - - (*this)(_forLoop.post); - - m_assembly.setSourceLocation(_forLoop.location); - m_assembly.appendJumpTo(loopStart); - m_assembly.appendLabel(loopEnd); - - finalizeBlock(_forLoop.pre, stackStartHeight); - m_scope = originalScope; -} - -void CodeTransform::operator()(Block const& _block) -{ - Scope* originalScope = m_scope; - m_scope = m_info.scopes.at(&_block).get(); - - int blockStartStackHeight = m_assembly.stackHeight(); - visitStatements(_block.statements); - - finalizeBlock(_block, blockStartStackHeight); - m_scope = originalScope; -} - -AbstractAssembly::LabelID CodeTransform::labelFromIdentifier(Identifier const& _identifier) -{ - AbstractAssembly::LabelID label = AbstractAssembly::LabelID(-1); - if (!m_scope->lookup(_identifier.name, Scope::NonconstVisitor( - [=](Scope::Variable&) { solAssert(false, "Expected label"); }, - [&](Scope::Label& _label) - { - label = labelID(_label); - }, - [=](Scope::Function&) { solAssert(false, "Expected label"); } - ))) - { - solAssert(false, "Identifier not found."); - } - return label; -} - -AbstractAssembly::LabelID CodeTransform::labelID(Scope::Label const& _label) -{ - if (!m_context->labelIDs.count(&_label)) - m_context->labelIDs[&_label] = m_assembly.newLabelId(); - return m_context->labelIDs[&_label]; -} - -AbstractAssembly::LabelID CodeTransform::functionEntryID(string const& _name, Scope::Function const& _function) -{ - if (!m_context->functionEntryIDs.count(&_function)) - { - AbstractAssembly::LabelID id = - m_useNamedLabelsForFunctions ? - m_assembly.namedLabel(_name) : - m_assembly.newLabelId(); - m_context->functionEntryIDs[&_function] = id; - } - return m_context->functionEntryIDs[&_function]; -} - -void CodeTransform::visitExpression(Expression const& _expression) -{ - int height = m_assembly.stackHeight(); - boost::apply_visitor(*this, _expression); - expectDeposit(1, height); -} - -void CodeTransform::visitStatements(vector<Statement> const& _statements) -{ - for (auto const& statement: _statements) - boost::apply_visitor(*this, statement); -} - -void CodeTransform::finalizeBlock(Block const& _block, int blockStartStackHeight) -{ - m_assembly.setSourceLocation(_block.location); - - // pop variables - solAssert(m_info.scopes.at(&_block).get() == m_scope, ""); - for (size_t i = 0; i < m_scope->numberOfVariables(); ++i) - m_assembly.appendInstruction(solidity::Instruction::POP); - - int deposit = m_assembly.stackHeight() - blockStartStackHeight; - solAssert(deposit == 0, "Invalid stack height at end of block."); - checkStackHeight(&_block); -} - -void CodeTransform::generateMultiAssignment(vector<Identifier> const& _variableNames) -{ - solAssert(m_scope, ""); - for (auto const& variableName: _variableNames | boost::adaptors::reversed) - generateAssignment(variableName); -} - -void CodeTransform::generateAssignment(Identifier const& _variableName) -{ - solAssert(m_scope, ""); - auto var = m_scope->lookup(_variableName.name); - if (var) - { - Scope::Variable const& _var = boost::get<Scope::Variable>(*var); - if (int heightDiff = variableHeightDiff(_var, true)) - m_assembly.appendInstruction(solidity::swapInstruction(heightDiff - 1)); - m_assembly.appendInstruction(solidity::Instruction::POP); - } - else - { - solAssert( - m_identifierAccess.generateCode, - "Identifier not found and no external access available." - ); - m_identifierAccess.generateCode(_variableName, IdentifierContext::LValue, m_assembly); - } -} - -int CodeTransform::variableHeightDiff(solidity::assembly::Scope::Variable const& _var, bool _forSwap) const -{ - solAssert(m_context->variableStackHeights.count(&_var), ""); - int heightDiff = m_assembly.stackHeight() - m_context->variableStackHeights[&_var]; - if (heightDiff <= (_forSwap ? 1 : 0) || heightDiff > (_forSwap ? 17 : 16)) - { - solUnimplemented( - "Variable inaccessible, too deep inside stack (" + to_string(heightDiff) + ")" - ); - return 0; - } - else - return heightDiff; -} - -void CodeTransform::expectDeposit(int _deposit, int _oldHeight) const -{ - solAssert(m_assembly.stackHeight() == _oldHeight + _deposit, "Invalid stack deposit."); -} - -void CodeTransform::checkStackHeight(void const* _astElement) const -{ - solAssert(m_info.stackHeightInfo.count(_astElement), "Stack height for AST element not found."); - int stackHeightInAnalysis = m_info.stackHeightInfo.at(_astElement); - int stackHeightInCodegen = m_assembly.stackHeight() - m_stackAdjustment; - solAssert( - stackHeightInAnalysis == stackHeightInCodegen, - "Stack height mismatch between analysis and code generation phase: Analysis: " + - to_string(stackHeightInAnalysis) + - " code gen: " + - to_string(stackHeightInCodegen) - ); -} diff --git a/libjulia/backends/evm/EVMCodeTransform.h b/libjulia/backends/evm/EVMCodeTransform.h deleted file mode 100644 index ed0785d3..00000000 --- a/libjulia/backends/evm/EVMCodeTransform.h +++ /dev/null @@ -1,158 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Common code generator for translating Yul / inline assembly to EVM and EVM1.5. - */ - -#include <libjulia/backends/evm/EVMAssembly.h> - -#include <libjulia/ASTDataForward.h> - -#include <libsolidity/inlineasm/AsmScope.h> - -#include <boost/variant.hpp> -#include <boost/optional.hpp> - -namespace dev -{ -namespace solidity -{ -class ErrorReporter; -namespace assembly -{ -struct AsmAnalysisInfo; -} -} -namespace julia -{ -class EVMAssembly; - -class CodeTransform: public boost::static_visitor<> -{ -public: - /// Create the code transformer. - /// @param _identifierAccess used to resolve identifiers external to the inline assembly - CodeTransform( - julia::AbstractAssembly& _assembly, - solidity::assembly::AsmAnalysisInfo& _analysisInfo, - bool _yul = false, - bool _evm15 = false, - ExternalIdentifierAccess const& _identifierAccess = ExternalIdentifierAccess(), - bool _useNamedLabelsForFunctions = false - ): CodeTransform( - _assembly, - _analysisInfo, - _yul, - _evm15, - _identifierAccess, - _useNamedLabelsForFunctions, - _assembly.stackHeight(), - std::make_shared<Context>() - ) - { - } - -protected: - struct Context - { - using Scope = solidity::assembly::Scope; - std::map<Scope::Label const*, AbstractAssembly::LabelID> labelIDs; - std::map<Scope::Function const*, AbstractAssembly::LabelID> functionEntryIDs; - std::map<Scope::Variable const*, int> variableStackHeights; - }; - - CodeTransform( - julia::AbstractAssembly& _assembly, - solidity::assembly::AsmAnalysisInfo& _analysisInfo, - bool _yul, - bool _evm15, - ExternalIdentifierAccess const& _identifierAccess, - bool _useNamedLabelsForFunctions, - int _stackAdjustment, - std::shared_ptr<Context> _context - ): - m_assembly(_assembly), - m_info(_analysisInfo), - m_yul(_yul), - m_evm15(_evm15), - m_useNamedLabelsForFunctions(_useNamedLabelsForFunctions), - m_identifierAccess(_identifierAccess), - m_stackAdjustment(_stackAdjustment), - m_context(_context) - {} - -public: - void operator()(Instruction const& _instruction); - void operator()(Literal const& _literal); - void operator()(Identifier const& _identifier); - void operator()(FunctionalInstruction const& _instr); - void operator()(FunctionCall const&); - void operator()(ExpressionStatement const& _statement); - void operator()(Label const& _label); - void operator()(StackAssignment const& _assignment); - void operator()(Assignment const& _assignment); - void operator()(VariableDeclaration const& _varDecl); - void operator()(If const& _if); - void operator()(Switch const& _switch); - void operator()(FunctionDefinition const&); - void operator()(ForLoop const&); - void operator()(Block const& _block); - -private: - AbstractAssembly::LabelID labelFromIdentifier(Identifier const& _identifier); - /// @returns the label ID corresponding to the given label, allocating a new one if - /// necessary. - AbstractAssembly::LabelID labelID(solidity::assembly::Scope::Label const& _label); - AbstractAssembly::LabelID functionEntryID(std::string const& _name, solidity::assembly::Scope::Function const& _function); - /// Generates code for an expression that is supposed to return a single value. - void visitExpression(Expression const& _expression); - - void visitStatements(std::vector<Statement> const& _statements); - - /// Pops all variables declared in the block and checks that the stack height is equal - /// to @a _blackStartStackHeight. - void finalizeBlock(Block const& _block, int _blockStartStackHeight); - - void generateMultiAssignment(std::vector<Identifier> const& _variableNames); - void generateAssignment(Identifier const& _variableName); - - /// Determines the stack height difference to the given variables. Throws - /// if it is not yet in scope or the height difference is too large. Returns - /// the (positive) stack height difference otherwise. - int variableHeightDiff(solidity::assembly::Scope::Variable const& _var, bool _forSwap) const; - - void expectDeposit(int _deposit, int _oldHeight) const; - - void checkStackHeight(void const* _astElement) const; - - julia::AbstractAssembly& m_assembly; - solidity::assembly::AsmAnalysisInfo& m_info; - solidity::assembly::Scope* m_scope = nullptr; - bool m_yul = false; - bool m_evm15 = false; - bool m_useNamedLabelsForFunctions = false; - ExternalIdentifierAccess m_identifierAccess; - /// Adjustment between the stack height as determined during the analysis phase - /// and the stack height in the assembly. This is caused by an initial stack being present - /// for inline assembly and different stack heights depending on the EVM backend used - /// (EVM 1.0 or 1.5). - int m_stackAdjustment = 0; - std::shared_ptr<Context> m_context; -}; - -} -} diff --git a/libjulia/optimiser/ASTCopier.cpp b/libjulia/optimiser/ASTCopier.cpp deleted file mode 100644 index a8a1e30f..00000000 --- a/libjulia/optimiser/ASTCopier.cpp +++ /dev/null @@ -1,184 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Creates an independent copy of an AST, renaming identifiers to be unique. - */ - -#include <libjulia/optimiser/ASTCopier.h> - -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/Common.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -Statement ASTCopier::operator()(Instruction const&) -{ - assertThrow(false, OptimizerException, "Invalid operation."); - return {}; -} - -Statement ASTCopier::operator()(ExpressionStatement const& _statement) -{ - return ExpressionStatement{ _statement.location, translate(_statement.expression) }; -} - -Statement ASTCopier::operator()(VariableDeclaration const& _varDecl) -{ - return VariableDeclaration{ - _varDecl.location, - translateVector(_varDecl.variables), - translate(_varDecl.value) - }; -} - -Statement ASTCopier::operator()(Assignment const& _assignment) -{ - return Assignment{ - _assignment.location, - translateVector(_assignment.variableNames), - translate(_assignment.value) - }; -} - -Statement ASTCopier::operator()(StackAssignment const&) -{ - assertThrow(false, OptimizerException, "Invalid operation."); - return {}; -} - -Statement ASTCopier::operator()(Label const&) -{ - assertThrow(false, OptimizerException, "Invalid operation."); - return {}; -} - -Expression ASTCopier::operator()(FunctionCall const& _call) -{ - return FunctionCall{ - _call.location, - translate(_call.functionName), - translateVector(_call.arguments) - }; -} - -Expression ASTCopier::operator()(FunctionalInstruction const& _instruction) -{ - return FunctionalInstruction{ - _instruction.location, - _instruction.instruction, - translateVector(_instruction.arguments) - }; -} - -Expression ASTCopier::operator()(Identifier const& _identifier) -{ - return Identifier{_identifier.location, translateIdentifier(_identifier.name)}; -} - -Expression ASTCopier::operator()(Literal const& _literal) -{ - return translate(_literal); -} - -Statement ASTCopier::operator()(If const& _if) -{ - return If{_if.location, translate(_if.condition), translate(_if.body)}; -} - -Statement ASTCopier::operator()(Switch const& _switch) -{ - return Switch{_switch.location, translate(_switch.expression), translateVector(_switch.cases)}; -} - -Statement ASTCopier::operator()(FunctionDefinition const& _function) -{ - string translatedName = translateIdentifier(_function.name); - - enterFunction(_function); - ScopeGuard g([&]() { this->leaveFunction(_function); }); - - return FunctionDefinition{ - _function.location, - move(translatedName), - translateVector(_function.parameters), - translateVector(_function.returnVariables), - translate(_function.body) - }; -} - -Statement ASTCopier::operator()(ForLoop const& _forLoop) -{ - enterScope(_forLoop.pre); - ScopeGuard g([&]() { this->leaveScope(_forLoop.pre); }); - - return ForLoop{ - _forLoop.location, - translate(_forLoop.pre), - translate(_forLoop.condition), - translate(_forLoop.post), - translate(_forLoop.body) - }; -} - -Statement ASTCopier::operator ()(Block const& _block) -{ - return translate(_block); -} - -Expression ASTCopier::translate(Expression const& _expression) -{ - return _expression.apply_visitor(static_cast<ExpressionCopier&>(*this)); -} - -Statement ASTCopier::translate(Statement const& _statement) -{ - return _statement.apply_visitor(static_cast<StatementCopier&>(*this)); -} - -Block ASTCopier::translate(Block const& _block) -{ - enterScope(_block); - ScopeGuard g([&]() { this->leaveScope(_block); }); - - return Block{_block.location, translateVector(_block.statements)}; -} - -Case ASTCopier::translate(Case const& _case) -{ - return Case{_case.location, translate(_case.value), translate(_case.body)}; -} - -Identifier ASTCopier::translate(Identifier const& _identifier) -{ - return Identifier{_identifier.location, translateIdentifier(_identifier.name)}; -} - -Literal ASTCopier::translate(Literal const& _literal) -{ - return _literal; -} - -TypedName ASTCopier::translate(TypedName const& _typedName) -{ - return TypedName{_typedName.location, translateIdentifier(_typedName.name), _typedName.type}; -} - diff --git a/libjulia/optimiser/ASTCopier.h b/libjulia/optimiser/ASTCopier.h deleted file mode 100644 index cb2925e3..00000000 --- a/libjulia/optimiser/ASTCopier.h +++ /dev/null @@ -1,124 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Creates an independent copy of an AST, renaming identifiers to be unique. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> - -#include <boost/variant.hpp> -#include <boost/optional.hpp> - -#include <vector> -#include <set> -#include <memory> - -namespace dev -{ -namespace julia -{ - -class ExpressionCopier: public boost::static_visitor<Expression> -{ -public: - virtual ~ExpressionCopier() = default; - virtual Expression operator()(Literal const& _literal) = 0; - virtual Expression operator()(Identifier const& _identifier) = 0; - virtual Expression operator()(FunctionalInstruction const& _instr) = 0; - virtual Expression operator()(FunctionCall const&) = 0; -}; - -class StatementCopier: public boost::static_visitor<Statement> -{ -public: - virtual ~StatementCopier() = default; - virtual Statement operator()(ExpressionStatement const& _statement) = 0; - virtual Statement operator()(Instruction const& _instruction) = 0; - virtual Statement operator()(Label const& _label) = 0; - virtual Statement operator()(StackAssignment const& _assignment) = 0; - virtual Statement operator()(Assignment const& _assignment) = 0; - virtual Statement operator()(VariableDeclaration const& _varDecl) = 0; - virtual Statement operator()(If const& _if) = 0; - virtual Statement operator()(Switch const& _switch) = 0; - virtual Statement operator()(FunctionDefinition const&) = 0; - virtual Statement operator()(ForLoop const&) = 0; - virtual Statement operator()(Block const& _block) = 0; -}; - -/** - * Creates a copy of a Yul AST potentially replacing identifier names. - * Base class to be extended. - */ -class ASTCopier: public ExpressionCopier, public StatementCopier -{ -public: - virtual ~ASTCopier() = default; - virtual Expression operator()(Literal const& _literal) override; - virtual Statement operator()(Instruction const& _instruction) override; - virtual Expression operator()(Identifier const& _identifier) override; - virtual Expression operator()(FunctionalInstruction const& _instr) override; - virtual Expression operator()(FunctionCall const&) override; - virtual Statement operator()(ExpressionStatement const& _statement) override; - virtual Statement operator()(Label const& _label) override; - virtual Statement operator()(StackAssignment const& _assignment) override; - virtual Statement operator()(Assignment const& _assignment) override; - virtual Statement operator()(VariableDeclaration const& _varDecl) override; - virtual Statement operator()(If const& _if) override; - virtual Statement operator()(Switch const& _switch) override; - virtual Statement operator()(FunctionDefinition const&) override; - virtual Statement operator()(ForLoop const&) override; - virtual Statement operator()(Block const& _block) override; - - virtual Expression translate(Expression const& _expression); - virtual Statement translate(Statement const& _statement); - -protected: - template <typename T> - std::vector<T> translateVector(std::vector<T> const& _values); - - template <typename T> - std::shared_ptr<T> translate(std::shared_ptr<T> const& _v) - { - return _v ? std::make_shared<T>(translate(*_v)) : nullptr; - } - Block translate(Block const& _block); - Case translate(Case const& _case); - Identifier translate(Identifier const& _identifier); - Literal translate(Literal const& _literal); - TypedName translate(TypedName const& _typedName); - - virtual void enterScope(Block const&) { } - virtual void leaveScope(Block const&) { } - virtual void enterFunction(FunctionDefinition const&) { } - virtual void leaveFunction(FunctionDefinition const&) { } - virtual std::string translateIdentifier(std::string const& _name) { return _name; } -}; - -template <typename T> -std::vector<T> ASTCopier::translateVector(std::vector<T> const& _values) -{ - std::vector<T> translated; - for (auto const& v: _values) - translated.emplace_back(translate(v)); - return translated; -} - - -} -} diff --git a/libjulia/optimiser/ASTWalker.cpp b/libjulia/optimiser/ASTWalker.cpp deleted file mode 100644 index dc94cc60..00000000 --- a/libjulia/optimiser/ASTWalker.cpp +++ /dev/null @@ -1,157 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Generic AST walker. - */ - -#include <libjulia/optimiser/ASTWalker.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <boost/range/adaptor/reversed.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - - -void ASTWalker::operator()(FunctionalInstruction const& _instr) -{ - walkVector(_instr.arguments | boost::adaptors::reversed); -} - -void ASTWalker::operator()(FunctionCall const& _funCall) -{ - walkVector(_funCall.arguments | boost::adaptors::reversed); -} - -void ASTWalker::operator()(ExpressionStatement const& _statement) -{ - visit(_statement.expression); -} - -void ASTWalker::operator()(Assignment const& _assignment) -{ - for (auto const& name: _assignment.variableNames) - (*this)(name); - visit(*_assignment.value); -} - -void ASTWalker::operator()(VariableDeclaration const& _varDecl) -{ - if (_varDecl.value) - visit(*_varDecl.value); -} - -void ASTWalker::operator()(If const& _if) -{ - visit(*_if.condition); - (*this)(_if.body); -} - -void ASTWalker::operator()(Switch const& _switch) -{ - visit(*_switch.expression); - for (auto const& _case: _switch.cases) - { - if (_case.value) - (*this)(*_case.value); - (*this)(_case.body); - } -} - -void ASTWalker::operator()(FunctionDefinition const& _fun) -{ - (*this)(_fun.body); -} - -void ASTWalker::operator()(ForLoop const& _for) -{ - (*this)(_for.pre); - visit(*_for.condition); - (*this)(_for.body); - (*this)(_for.post); -} - -void ASTWalker::operator()(Block const& _block) -{ - walkVector(_block.statements); -} - -void ASTModifier::operator()(FunctionalInstruction& _instr) -{ - walkVector(_instr.arguments | boost::adaptors::reversed); -} - -void ASTModifier::operator()(FunctionCall& _funCall) -{ - walkVector(_funCall.arguments | boost::adaptors::reversed); -} - -void ASTModifier::operator()(ExpressionStatement& _statement) -{ - visit(_statement.expression); -} - -void ASTModifier::operator()(Assignment& _assignment) -{ - for (auto& name: _assignment.variableNames) - (*this)(name); - visit(*_assignment.value); -} - -void ASTModifier::operator()(VariableDeclaration& _varDecl) -{ - if (_varDecl.value) - visit(*_varDecl.value); -} - -void ASTModifier::operator()(If& _if) -{ - visit(*_if.condition); - (*this)(_if.body); -} - -void ASTModifier::operator()(Switch& _switch) -{ - visit(*_switch.expression); - for (auto& _case: _switch.cases) - { - if (_case.value) - (*this)(*_case.value); - (*this)(_case.body); - } -} - -void ASTModifier::operator()(FunctionDefinition& _fun) -{ - (*this)(_fun.body); -} - -void ASTModifier::operator()(ForLoop& _for) -{ - (*this)(_for.pre); - visit(*_for.condition); - (*this)(_for.post); - (*this)(_for.body); -} - -void ASTModifier::operator()(Block& _block) -{ - walkVector(_block.statements); -} diff --git a/libjulia/optimiser/ASTWalker.h b/libjulia/optimiser/ASTWalker.h deleted file mode 100644 index e1f0f5bd..00000000 --- a/libjulia/optimiser/ASTWalker.h +++ /dev/null @@ -1,122 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Generic AST walker. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> - -#include <libjulia/Exceptions.h> - -#include <boost/variant.hpp> -#include <boost/optional.hpp> - -#include <vector> -#include <set> -#include <map> - -namespace dev -{ -namespace julia -{ - -/** - * Generic AST walker. - */ -class ASTWalker: public boost::static_visitor<> -{ -public: - virtual ~ASTWalker() = default; - virtual void operator()(Literal const&) {} - virtual void operator()(Instruction const&) { assertThrow(false, OptimizerException, ""); } - virtual void operator()(Identifier const&) {} - virtual void operator()(FunctionalInstruction const& _instr); - virtual void operator()(FunctionCall const& _funCall); - virtual void operator()(ExpressionStatement const& _statement); - virtual void operator()(Label const&) { assertThrow(false, OptimizerException, ""); } - virtual void operator()(StackAssignment const&) { assertThrow(false, OptimizerException, ""); } - virtual void operator()(Assignment const& _assignment); - virtual void operator()(VariableDeclaration const& _varDecl); - virtual void operator()(If const& _if); - virtual void operator()(Switch const& _switch); - virtual void operator()(FunctionDefinition const&); - virtual void operator()(ForLoop const&); - virtual void operator()(Block const& _block); - - virtual void visit(Statement const& _st) - { - boost::apply_visitor(*this, _st); - } - virtual void visit(Expression const& _e) - { - boost::apply_visitor(*this, _e); - } - -protected: - template <class T> - void walkVector(T const& _statements) - { - for (auto const& statement: _statements) - visit(statement); - } -}; - -/** - * Generic AST modifier (i.e. non-const version of ASTWalker). - */ -class ASTModifier: public boost::static_visitor<> -{ -public: - virtual ~ASTModifier() = default; - virtual void operator()(Literal&) {} - virtual void operator()(Instruction&) { assertThrow(false, OptimizerException, ""); } - virtual void operator()(Identifier&) {} - virtual void operator()(FunctionalInstruction& _instr); - virtual void operator()(FunctionCall& _funCall); - virtual void operator()(ExpressionStatement& _statement); - virtual void operator()(Label&) { assertThrow(false, OptimizerException, ""); } - virtual void operator()(StackAssignment&) { assertThrow(false, OptimizerException, ""); } - virtual void operator()(Assignment& _assignment); - virtual void operator()(VariableDeclaration& _varDecl); - virtual void operator()(If& _if); - virtual void operator()(Switch& _switch); - virtual void operator()(FunctionDefinition&); - virtual void operator()(ForLoop&); - virtual void operator()(Block& _block); - - virtual void visit(Statement& _st) - { - boost::apply_visitor(*this, _st); - } - virtual void visit(Expression& _e) - { - boost::apply_visitor(*this, _e); - } - -protected: - template <class T> - void walkVector(T&& _statements) - { - for (auto& st: _statements) - visit(st); - } -}; - -} -} diff --git a/libjulia/optimiser/CommonSubexpressionEliminator.cpp b/libjulia/optimiser/CommonSubexpressionEliminator.cpp deleted file mode 100644 index 458b3437..00000000 --- a/libjulia/optimiser/CommonSubexpressionEliminator.cpp +++ /dev/null @@ -1,71 +0,0 @@ -/*( - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimisation stage that replaces expressions known to be the current value of a variable - * in scope by a reference to that variable. - */ - -#include <libjulia/optimiser/CommonSubexpressionEliminator.h> - -#include <libjulia/optimiser/Metrics.h> -#include <libjulia/optimiser/SyntacticalEquality.h> -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -void CommonSubexpressionEliminator::visit(Expression& _e) -{ - // We visit the inner expression first to first simplify inner expressions, - // which hopefully allows more matches. - // Note that the DataFlowAnalyzer itself only has code for visiting Statements, - // so this basically invokes the AST walker directly and thus post-visiting - // is also fine with regards to data flow analysis. - DataFlowAnalyzer::visit(_e); - - if (_e.type() == typeid(Identifier)) - { - Identifier& identifier = boost::get<Identifier>(_e); - string const& name = identifier.name; - if (m_value.count(name)) - { - assertThrow(m_value.at(name), OptimizerException, ""); - if (m_value.at(name)->type() == typeid(Identifier)) - { - string const& value = boost::get<Identifier>(*m_value.at(name)).name; - if (inScope(value)) - _e = Identifier{locationOf(_e), value}; - } - } - } - else - { - // TODO this search is rather inefficient. - for (auto const& var: m_value) - { - assertThrow(var.second, OptimizerException, ""); - if (SyntacticalEqualityChecker::equal(_e, *var.second)) - { - _e = Identifier{locationOf(_e), var.first}; - break; - } - } - } -} diff --git a/libjulia/optimiser/CommonSubexpressionEliminator.h b/libjulia/optimiser/CommonSubexpressionEliminator.h deleted file mode 100644 index a8ca3abb..00000000 --- a/libjulia/optimiser/CommonSubexpressionEliminator.h +++ /dev/null @@ -1,45 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimisation stage that replaces expressions known to be the current value of a variable - * in scope by a reference to that variable. - */ - -#pragma once - -#include <libjulia/optimiser/DataFlowAnalyzer.h> - -namespace dev -{ -namespace julia -{ - -/** - * Optimisation stage that replaces expressions known to be the current value of a variable - * in scope by a reference to that variable. - * - * Prerequisite: Disambiguator - */ -class CommonSubexpressionEliminator: public DataFlowAnalyzer -{ -protected: - using ASTModifier::visit; - virtual void visit(Expression& _e) override; -}; - -} -} diff --git a/libjulia/optimiser/DataFlowAnalyzer.cpp b/libjulia/optimiser/DataFlowAnalyzer.cpp deleted file mode 100644 index 0ad0eac9..00000000 --- a/libjulia/optimiser/DataFlowAnalyzer.cpp +++ /dev/null @@ -1,193 +0,0 @@ -/*( - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Base class to perform data flow analysis during AST walks. - * Tracks assignments and is used as base class for both Rematerialiser and - * Common Subexpression Eliminator. - */ - -#include <libjulia/optimiser/DataFlowAnalyzer.h> - -#include <libjulia/optimiser/NameCollector.h> -#include <libjulia/optimiser/Semantics.h> -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/CommonData.h> - -#include <boost/range/adaptor/reversed.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -void DataFlowAnalyzer::operator()(Assignment& _assignment) -{ - set<string> names; - for (auto const& var: _assignment.variableNames) - names.insert(var.name); - assertThrow(_assignment.value, OptimizerException, ""); - visit(*_assignment.value); - handleAssignment(names, _assignment.value.get()); -} - -void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl) -{ - set<string> names; - for (auto const& var: _varDecl.variables) - names.insert(var.name); - m_variableScopes.back().variables += names; - if (_varDecl.value) - visit(*_varDecl.value); - handleAssignment(names, _varDecl.value.get()); -} - -void DataFlowAnalyzer::operator()(If& _if) -{ - ASTModifier::operator()(_if); - - Assignments assignments; - assignments(_if.body); - clearValues(assignments.names()); -} - -void DataFlowAnalyzer::operator()(Switch& _switch) -{ - visit(*_switch.expression); - set<string> assignedVariables; - for (auto& _case: _switch.cases) - { - (*this)(_case.body); - Assignments assignments; - assignments(_case.body); - assignedVariables += assignments.names(); - // This is a little too destructive, we could retain the old values. - clearValues(assignments.names()); - } - clearValues(assignedVariables); -} - -void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) -{ - m_variableScopes.emplace_back(true); - for (auto const& parameter: _fun.parameters) - m_variableScopes.back().variables.insert(parameter.name); - for (auto const& var: _fun.returnVariables) - m_variableScopes.back().variables.insert(var.name); - ASTModifier::operator()(_fun); - m_variableScopes.pop_back(); -} - -void DataFlowAnalyzer::operator()(ForLoop& _for) -{ - // Special scope handling of the pre block. - m_variableScopes.emplace_back(false); - for (auto& statement: _for.pre.statements) - visit(statement); - - Assignments assignments; - assignments(_for.body); - assignments(_for.post); - clearValues(assignments.names()); - - visit(*_for.condition); - (*this)(_for.body); - (*this)(_for.post); - - clearValues(assignments.names()); - - m_variableScopes.pop_back(); -} - -void DataFlowAnalyzer::operator()(Block& _block) -{ - size_t numScopes = m_variableScopes.size(); - m_variableScopes.emplace_back(false); - ASTModifier::operator()(_block); - m_variableScopes.pop_back(); - assertThrow(numScopes == m_variableScopes.size(), OptimizerException, ""); -} - -void DataFlowAnalyzer::handleAssignment(set<string> const& _variables, Expression* _value) -{ - clearValues(_variables); - - MovableChecker movableChecker; - if (_value) - movableChecker.visit(*_value); - if (_variables.size() == 1) - { - string const& name = *_variables.begin(); - // Expression has to be movable and cannot contain a reference - // to the variable that will be assigned to. - if (_value && movableChecker.movable() && !movableChecker.referencedVariables().count(name)) - m_value[name] = _value; - } - - auto const& referencedVariables = movableChecker.referencedVariables(); - for (auto const& name: _variables) - { - m_references[name] = referencedVariables; - for (auto const& ref: referencedVariables) - m_referencedBy[ref].insert(name); - } -} - -void DataFlowAnalyzer::clearValues(set<string> const& _variables) -{ - // All variables that reference variables to be cleared also have to be - // cleared, but not recursively, since only the value of the original - // variables changes. Example: - // let a := 1 - // let b := a - // let c := b - // let a := 2 - // add(b, c) - // In the last line, we can replace c by b, but not b by a. - // - // This cannot be easily tested since the substitutions will be done - // one by one on the fly, and the last line will just be add(1, 1) - - set<string> variables = _variables; - // Clear variables that reference variables to be cleared. - for (auto const& name: variables) - for (auto const& ref: m_referencedBy[name]) - variables.insert(ref); - - // Clear the value and update the reference relation. - for (auto const& name: variables) - m_value.erase(name); - for (auto const& name: variables) - { - for (auto const& ref: m_references[name]) - m_referencedBy[ref].erase(name); - m_references[name].clear(); - } -} - -bool DataFlowAnalyzer::inScope(string const& _variableName) const -{ - for (auto const& scope: m_variableScopes | boost::adaptors::reversed) - { - if (scope.variables.count(_variableName)) - return true; - if (scope.isFunction) - return false; - } - return false; -} diff --git a/libjulia/optimiser/DataFlowAnalyzer.h b/libjulia/optimiser/DataFlowAnalyzer.h deleted file mode 100644 index 66df2f48..00000000 --- a/libjulia/optimiser/DataFlowAnalyzer.h +++ /dev/null @@ -1,84 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Base class to perform data flow analysis during AST walks. - * Tracks assignments and is used as base class for both Rematerialiser and - * Common Subexpression Eliminator. - */ - -#pragma once - -#include <libjulia/optimiser/ASTWalker.h> - -#include <string> -#include <map> -#include <set> - -namespace dev -{ -namespace julia -{ - -/** - * Base class to perform data flow analysis during AST walks. - * Tracks assignments and is used as base class for both Rematerialiser and - * Common Subexpression Eliminator. - * - * Prerequisite: Disambiguator - */ -class DataFlowAnalyzer: public ASTModifier -{ -public: - using ASTModifier::operator(); - virtual void operator()(Assignment& _assignment) override; - virtual void operator()(VariableDeclaration& _varDecl) override; - virtual void operator()(If& _if) override; - virtual void operator()(Switch& _switch) override; - virtual void operator()(FunctionDefinition&) override; - virtual void operator()(ForLoop&) override; - virtual void operator()(Block& _block) override; - -protected: - /// Registers the assignment. - void handleAssignment(std::set<std::string> const& _names, Expression* _value); - - /// Clears information about the values assigned to the given variables, - /// for example at points where control flow is merged. - void clearValues(std::set<std::string> const& _names); - - /// Returns true iff the variable is in scope. - bool inScope(std::string const& _variableName) const; - - /// Current values of variables, always movable. - std::map<std::string, Expression const*> m_value; - /// m_references[a].contains(b) <=> the current expression assigned to a references b - std::map<std::string, std::set<std::string>> m_references; - /// m_referencedBy[b].contains(a) <=> the current expression assigned to a references b - std::map<std::string, std::set<std::string>> m_referencedBy; - - struct Scope - { - explicit Scope(bool _isFunction): isFunction(_isFunction) {} - std::set<std::string> variables; - bool isFunction; - }; - /// List of scopes. - std::vector<Scope> m_variableScopes; -}; - -} -} diff --git a/libjulia/optimiser/Disambiguator.cpp b/libjulia/optimiser/Disambiguator.cpp deleted file mode 100644 index 687be9b9..00000000 --- a/libjulia/optimiser/Disambiguator.cpp +++ /dev/null @@ -1,75 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that makes all identifiers unique. - */ - -#include <libjulia/optimiser/Disambiguator.h> - -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> -#include <libsolidity/inlineasm/AsmScope.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - -using Scope = dev::solidity::assembly::Scope; - -string Disambiguator::translateIdentifier(string const& _originalName) -{ - assertThrow(!m_scopes.empty() && m_scopes.back(), OptimizerException, ""); - Scope::Identifier const* id = m_scopes.back()->lookup(_originalName); - assertThrow(id, OptimizerException, ""); - if (!m_translations.count(id)) - m_translations[id] = m_nameDispenser.newName(_originalName); - return m_translations.at(id); -} - -void Disambiguator::enterScope(Block const& _block) -{ - enterScopeInternal(*m_info.scopes.at(&_block)); -} - -void Disambiguator::leaveScope(Block const& _block) -{ - leaveScopeInternal(*m_info.scopes.at(&_block)); -} - -void Disambiguator::enterFunction(FunctionDefinition const& _function) -{ - enterScopeInternal(*m_info.scopes.at(m_info.virtualBlocks.at(&_function).get())); -} - -void Disambiguator::leaveFunction(FunctionDefinition const& _function) -{ - leaveScopeInternal(*m_info.scopes.at(m_info.virtualBlocks.at(&_function).get())); -} - -void Disambiguator::enterScopeInternal(Scope& _scope) -{ - m_scopes.push_back(&_scope); -} - -void Disambiguator::leaveScopeInternal(Scope& _scope) -{ - assertThrow(!m_scopes.empty(), OptimizerException, ""); - assertThrow(m_scopes.back() == &_scope, OptimizerException, ""); - m_scopes.pop_back(); -} diff --git a/libjulia/optimiser/Disambiguator.h b/libjulia/optimiser/Disambiguator.h deleted file mode 100644 index 4ef43736..00000000 --- a/libjulia/optimiser/Disambiguator.h +++ /dev/null @@ -1,68 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that makes all identifiers unique. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> - -#include <libjulia/optimiser/ASTCopier.h> -#include <libjulia/optimiser/NameDispenser.h> - -#include <libsolidity/inlineasm/AsmAnalysisInfo.h> - -#include <boost/variant.hpp> -#include <boost/optional.hpp> - -#include <set> - -namespace dev -{ -namespace julia -{ - -/** - * Creates a copy of a Yul AST replacing all identifiers by unique names. - */ -class Disambiguator: public ASTCopier -{ -public: - Disambiguator(solidity::assembly::AsmAnalysisInfo const& _analysisInfo): - m_info(_analysisInfo) - {} - -protected: - virtual void enterScope(Block const& _block) override; - virtual void leaveScope(Block const& _block) override; - virtual void enterFunction(FunctionDefinition const& _function) override; - virtual void leaveFunction(FunctionDefinition const& _function) override; - virtual std::string translateIdentifier(std::string const& _name) override; - - void enterScopeInternal(solidity::assembly::Scope& _scope); - void leaveScopeInternal(solidity::assembly::Scope& _scope); - - solidity::assembly::AsmAnalysisInfo const& m_info; - - std::vector<solidity::assembly::Scope*> m_scopes; - std::map<void const*, std::string> m_translations; - NameDispenser m_nameDispenser; -}; - -} -} diff --git a/libjulia/optimiser/ExpressionInliner.cpp b/libjulia/optimiser/ExpressionInliner.cpp deleted file mode 100644 index 450769fd..00000000 --- a/libjulia/optimiser/ExpressionInliner.cpp +++ /dev/null @@ -1,74 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that performs function inlining inside expressions. - */ - -#include <libjulia/optimiser/ExpressionInliner.h> - -#include <libjulia/optimiser/InlinableExpressionFunctionFinder.h> -#include <libjulia/optimiser/Substitution.h> -#include <libjulia/optimiser/Semantics.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <boost/algorithm/cxx11/all_of.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - -void ExpressionInliner::run() -{ - InlinableExpressionFunctionFinder funFinder; - funFinder(m_block); - m_inlinableFunctions = funFinder.inlinableFunctions(); - - (*this)(m_block); -} - - -void ExpressionInliner::operator()(FunctionDefinition& _fun) -{ - ASTModifier::operator()(_fun); -} - -void ExpressionInliner::visit(Expression& _expression) -{ - ASTModifier::visit(_expression); - if (_expression.type() == typeid(FunctionCall)) - { - FunctionCall& funCall = boost::get<FunctionCall>(_expression); - - bool movable = boost::algorithm::all_of( - funCall.arguments, - [=](Expression const& _arg) { return MovableChecker(_arg).movable(); } - ); - if (m_inlinableFunctions.count(funCall.functionName.name) && movable) - { - FunctionDefinition const& fun = *m_inlinableFunctions.at(funCall.functionName.name); - map<string, Expression const*> substitutions; - for (size_t i = 0; i < fun.parameters.size(); ++i) - substitutions[fun.parameters[i].name] = &funCall.arguments[i]; - _expression = Substitution(substitutions).translate(*boost::get<Assignment>(fun.body.statements.front()).value); - - // TODO Add metric! This metric should perform well on a pair of functions who - // call each other recursively. - } - } -} diff --git a/libjulia/optimiser/ExpressionInliner.h b/libjulia/optimiser/ExpressionInliner.h deleted file mode 100644 index 3d24ef5d..00000000 --- a/libjulia/optimiser/ExpressionInliner.h +++ /dev/null @@ -1,72 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that performs function inlining. - */ -#pragma once - -#include <libjulia/optimiser/ASTWalker.h> - -#include <libjulia/ASTDataForward.h> - -#include <boost/variant.hpp> -#include <boost/optional.hpp> - -#include <set> - -namespace dev -{ -namespace julia -{ - -/** - * Optimiser component that modifies an AST in place, inlining functions that can be - * inlined inside functional expressions, i.e. functions that - * - return a single value - * - have a body like r := <functional expression> - * - neither reference themselves nor r in the right hand side - * - * Furthermore, the arguments of the function call cannot have any side-effects. - * - * This component can only be used on sources with unique names. - */ -class ExpressionInliner: public ASTModifier -{ -public: - ExpressionInliner(Block& _block): - m_block(_block) - {} - - void run(); - - using ASTModifier::operator(); - virtual void operator()(FunctionDefinition& _fun) override; - - virtual void visit(Expression& _expression) override; - -private: - std::map<std::string, FunctionDefinition const*> m_inlinableFunctions; - std::map<std::string, std::string> m_varReplacements; - /// Set of functions we are currently visiting inside. - std::set<std::string> m_currentFunctions; - - Block& m_block; -}; - - -} -} diff --git a/libjulia/optimiser/ExpressionJoiner.cpp b/libjulia/optimiser/ExpressionJoiner.cpp deleted file mode 100644 index 5b92e332..00000000 --- a/libjulia/optimiser/ExpressionJoiner.cpp +++ /dev/null @@ -1,166 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that undoes what the ExpressionSplitter did, i.e. - * it more or less inlines variable declarations. - */ - -#include <libjulia/optimiser/ExpressionJoiner.h> - -#include <libjulia/optimiser/NameCollector.h> -#include <libjulia/optimiser/Utilities.h> -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/CommonData.h> - -#include <boost/range/adaptor/reversed.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - -void ExpressionJoiner::operator()(FunctionalInstruction& _instruction) -{ - handleArguments(_instruction.arguments); -} - -void ExpressionJoiner::operator()(FunctionCall& _funCall) -{ - handleArguments(_funCall.arguments); -} - -void ExpressionJoiner::operator()(If& _if) -{ - visit(*_if.condition); - (*this)(_if.body); -} - -void ExpressionJoiner::operator()(Switch& _switch) -{ - visit(*_switch.expression); - for (auto& _case: _switch.cases) - // Do not visit the case expression, nothing to unbreak there. - (*this)(_case.body); -} - -void ExpressionJoiner::operator()(Block& _block) -{ - resetLatestStatementPointer(); - for (size_t i = 0; i < _block.statements.size(); ++i) - { - visit(_block.statements[i]); - m_currentBlock = &_block; - m_latestStatementInBlock = i; - } - - removeEmptyBlocks(_block); - resetLatestStatementPointer(); -} - -void ExpressionJoiner::visit(Expression& _e) -{ - if (_e.type() == typeid(Identifier)) - { - Identifier const& identifier = boost::get<Identifier>(_e); - if (isLatestStatementVarDeclOf(identifier) && m_references[identifier.name] == 1) - { - VariableDeclaration& varDecl = boost::get<VariableDeclaration>(*latestStatement()); - assertThrow(varDecl.variables.size() == 1, OptimizerException, ""); - assertThrow(varDecl.value, OptimizerException, ""); - - _e = std::move(*varDecl.value); - // Delete the variable declaration (also get the moved-from structure back into a sane state) - *latestStatement() = Block(); - - decrementLatestStatementPointer(); - } - } - else - ASTModifier::visit(_e); -} - -void ExpressionJoiner::run(Block& _ast) -{ - ExpressionJoiner{_ast}(_ast); -} - -ExpressionJoiner::ExpressionJoiner(Block& _ast) -{ - ReferencesCounter counter; - counter(_ast); - m_references = counter.references(); -} - -void ExpressionJoiner::handleArguments(vector<Expression>& _arguments) -{ - // We have to fill from left to right, but we can only - // fill if everything to the right is just an identifier - // or a literal. - // Also we only descend into function calls if everything - // on the right is an identifier or literal. - - size_t i = _arguments.size(); - for (Expression const& arg: _arguments | boost::adaptors::reversed) - { - --i; - if (arg.type() != typeid(Identifier) && arg.type() != typeid(Literal)) - break; - } - // i points to the last element that is neither an identifier nor a literal, - // or to the first element if all of them are identifiers or literals. - - for (; i < _arguments.size(); ++i) - visit(_arguments.at(i)); -} - -void ExpressionJoiner::decrementLatestStatementPointer() -{ - if (!m_currentBlock) - return; - if (m_latestStatementInBlock > 0) - --m_latestStatementInBlock; - else - resetLatestStatementPointer(); -} - -void ExpressionJoiner::resetLatestStatementPointer() -{ - m_currentBlock = nullptr; - m_latestStatementInBlock = size_t(-1); -} - -Statement* ExpressionJoiner::latestStatement() -{ - if (!m_currentBlock) - return nullptr; - else - return &m_currentBlock->statements.at(m_latestStatementInBlock); -} - -bool ExpressionJoiner::isLatestStatementVarDeclOf(Identifier const& _identifier) -{ - Statement const* statement = latestStatement(); - if (!statement || statement->type() != typeid(VariableDeclaration)) - return false; - VariableDeclaration const& varDecl = boost::get<VariableDeclaration>(*statement); - if (varDecl.variables.size() != 1 || !varDecl.value) - return false; - return varDecl.variables.at(0).name == _identifier.name; -} diff --git a/libjulia/optimiser/ExpressionJoiner.h b/libjulia/optimiser/ExpressionJoiner.h deleted file mode 100644 index 91b45b49..00000000 --- a/libjulia/optimiser/ExpressionJoiner.h +++ /dev/null @@ -1,102 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that undoes what the ExpressionSplitter did, i.e. - * it more or less inlines variable declarations. - */ -#pragma once - -#include <libjulia/ASTDataForward.h> - -#include <libjulia/optimiser/ASTWalker.h> - -#include <map> - -namespace dev -{ -namespace julia -{ - -class NameCollector; - - -/** - * Optimiser component that modifies an AST in place, turning sequences - * of variable declarations into complex expressions, if the variables - * are declared in the right order. This component does the opposite - * of ExpressionSplitter. - * Since the order of opcode or function evaluation is unchanged, - * this transformation does not need to care about conflicting opcodes. - * - * Code of the form - * - * let a1 := mload(y) - * let a2 := mul(x, 4) - * sstore(a2, a1) - * - * is transformed into - * - * sstore(mul(x, 4), mload(y)) - * - * The transformation is not applied to loop conditions, because those are - * evaluated with each loop. - * - * The component can be applied to sub-blocks of the AST, you do not - * need to pass a full AST. - * - * Prerequisites: Disambiguator - * - * Implementation note: We visit the AST, modifying it in place. - * The class starts counting references and will only replace variables - * that have exactly one reference. It keeps a "latest statement pointer" - * which always points to the statement right before the current statement. - * Any function call or opcode will reset this pointer. If an identifier - * is encountered that was declared in the "latest statement", it is replaced - * by the value of the declaration, the "latest statement" is replaced - * by an empty block and the pointer is decremented. - * A block also resets the latest statement pointer. - */ -class ExpressionJoiner: public ASTModifier -{ -public: - virtual void operator()(FunctionalInstruction&) override; - virtual void operator()(FunctionCall&) override; - virtual void operator()(If&) override; - virtual void operator()(Switch&) override; - virtual void operator()(Block& _block) override; - - using ASTModifier::visit; - virtual void visit(Expression& _e) override; - - static void run(Block& _ast); -private: - explicit ExpressionJoiner(Block& _ast); - - void handleArguments(std::vector<Expression>& _arguments); - - void decrementLatestStatementPointer(); - void resetLatestStatementPointer(); - Statement* latestStatement(); - bool isLatestStatementVarDeclOf(Identifier const& _identifier); - - Block* m_currentBlock = nullptr; - size_t m_latestStatementInBlock = 0; - std::map<std::string, size_t> m_references; -}; - -} -} diff --git a/libjulia/optimiser/ExpressionSimplifier.cpp b/libjulia/optimiser/ExpressionSimplifier.cpp deleted file mode 100644 index 8bd6b1c7..00000000 --- a/libjulia/optimiser/ExpressionSimplifier.cpp +++ /dev/null @@ -1,48 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that uses the simplification rules to simplify expressions. - */ - -#include <libjulia/optimiser/ExpressionSimplifier.h> - -#include <libjulia/optimiser/SimplificationRules.h> -#include <libjulia/optimiser/Semantics.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/CommonData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - - -void ExpressionSimplifier::visit(Expression& _expression) -{ - ASTModifier::visit(_expression); - while (auto match = SimplificationRules::findFirstMatch(_expression)) - { - // Do not apply the rule if it removes non-constant parts of the expression. - // TODO: The check could actually be less strict than "movable". - // We only require "Does not cause side-effects". - if (match->removesNonConstants && !MovableChecker(_expression).movable()) - return; - _expression = match->action().toExpression(locationOf(_expression)); - } -} diff --git a/libjulia/optimiser/ExpressionSimplifier.h b/libjulia/optimiser/ExpressionSimplifier.h deleted file mode 100644 index 8a9e0e20..00000000 --- a/libjulia/optimiser/ExpressionSimplifier.h +++ /dev/null @@ -1,45 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that uses the simplification rules to simplify expressions. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> - -#include <libjulia/optimiser/ASTWalker.h> - -namespace dev -{ -namespace julia -{ - -/** - * Applies simplification rules to all expressions. - */ -class ExpressionSimplifier: public ASTModifier -{ -public: - using ASTModifier::operator(); - virtual void visit(Expression& _expression); - -private: -}; - -} -} diff --git a/libjulia/optimiser/ExpressionSplitter.cpp b/libjulia/optimiser/ExpressionSplitter.cpp deleted file mode 100644 index f189f563..00000000 --- a/libjulia/optimiser/ExpressionSplitter.cpp +++ /dev/null @@ -1,105 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that turns complex expressions into multiple variable - * declarations. - */ - -#include <libjulia/optimiser/ExpressionSplitter.h> - -#include <libjulia/optimiser/ASTWalker.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/CommonData.h> - -#include <boost/range/adaptor/reversed.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - -void ExpressionSplitter::operator()(FunctionalInstruction& _instruction) -{ - for (auto& arg: _instruction.arguments | boost::adaptors::reversed) - outlineExpression(arg); -} - -void ExpressionSplitter::operator()(FunctionCall& _funCall) -{ - for (auto& arg: _funCall.arguments | boost::adaptors::reversed) - outlineExpression(arg); -} - -void ExpressionSplitter::operator()(If& _if) -{ - outlineExpression(*_if.condition); - (*this)(_if.body); -} - -void ExpressionSplitter::operator()(Switch& _switch) -{ - outlineExpression(*_switch.expression); - for (auto& _case: _switch.cases) - // Do not visit the case expression, nothing to break there. - (*this)(_case.body); -} - -void ExpressionSplitter::operator()(ForLoop& _loop) -{ - (*this)(_loop.pre); - // Do not visit the condition because we cannot break expressions there. - (*this)(_loop.post); - (*this)(_loop.body); -} - -void ExpressionSplitter::operator()(Block& _block) -{ - vector<Statement> saved; - swap(saved, m_statementsToPrefix); - - function<boost::optional<vector<Statement>>(Statement&)> f = - [&](Statement& _statement) -> boost::optional<vector<Statement>> { - m_statementsToPrefix.clear(); - visit(_statement); - if (m_statementsToPrefix.empty()) - return {}; - m_statementsToPrefix.emplace_back(std::move(_statement)); - return std::move(m_statementsToPrefix); - }; - iterateReplacing(_block.statements, f); - - swap(saved, m_statementsToPrefix); -} - -void ExpressionSplitter::outlineExpression(Expression& _expr) -{ - if (_expr.type() == typeid(Identifier)) - return; - - visit(_expr); - - SourceLocation location = locationOf(_expr); - string var = m_nameDispenser.newName(""); - m_statementsToPrefix.emplace_back(VariableDeclaration{ - location, - {{TypedName{location, var, ""}}}, - make_shared<Expression>(std::move(_expr)) - }); - _expr = Identifier{location, var}; -} diff --git a/libjulia/optimiser/ExpressionSplitter.h b/libjulia/optimiser/ExpressionSplitter.h deleted file mode 100644 index 324d2b13..00000000 --- a/libjulia/optimiser/ExpressionSplitter.h +++ /dev/null @@ -1,86 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that turns complex expressions into multiple variable - * declarations. - */ -#pragma once - -#include <libjulia/ASTDataForward.h> - -#include <libjulia/optimiser/ASTWalker.h> -#include <libjulia/optimiser/NameDispenser.h> - -#include <vector> - -namespace dev -{ -namespace julia -{ - -class NameCollector; - - -/** - * Optimiser component that modifies an AST in place, turning complex - * expressions into simple expressions and multiple variable declarations. - * - * Code of the form - * - * sstore(mul(x, 4), mload(y)) - * - * is transformed into - * - * let a1 := mload(y) - * let a2 := mul(x, 4) - * sstore(a2, a1) - * - * The transformation is not applied to loop conditions, because the loop control flow - * does not allow "outlining" the inner expressions in all cases. - * - * The final program should be in a form such that with the exception of a loop condition, - * function calls can only appear in the right-hand side of a variable declaration, - * assignments or expression statements and all arguments have to be constants or variables. - */ -class ExpressionSplitter: public ASTModifier -{ -public: - explicit ExpressionSplitter(NameDispenser& _nameDispenser): - m_nameDispenser(_nameDispenser) - { } - - virtual void operator()(FunctionalInstruction&) override; - virtual void operator()(FunctionCall&) override; - virtual void operator()(If&) override; - virtual void operator()(Switch&) override; - virtual void operator()(ForLoop&) override; - virtual void operator()(Block& _block) override; - -private: - /// Replaces the expression by a variable if it is a function call or functional - /// instruction. The declaration of the variable is appended to m_statementsToPrefix. - /// Recurses via visit(). - void outlineExpression(Expression& _expr); - - /// List of statements that should go in front of the currently visited AST element, - /// at the statement level. - std::vector<Statement> m_statementsToPrefix; - NameDispenser& m_nameDispenser; -}; - -} -} diff --git a/libjulia/optimiser/FullInliner.cpp b/libjulia/optimiser/FullInliner.cpp deleted file mode 100644 index f41dc198..00000000 --- a/libjulia/optimiser/FullInliner.cpp +++ /dev/null @@ -1,264 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that performs function inlining for arbitrary functions. - */ - -#include <libjulia/optimiser/FullInliner.h> - -#include <libjulia/optimiser/ASTCopier.h> -#include <libjulia/optimiser/ASTWalker.h> -#include <libjulia/optimiser/NameCollector.h> -#include <libjulia/optimiser/Semantics.h> -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/CommonData.h> - -#include <boost/range/adaptor/reversed.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - -FullInliner::FullInliner(Block& _ast): - m_ast(_ast) -{ - assertThrow(m_ast.statements.size() >= 1, OptimizerException, ""); - assertThrow(m_ast.statements.front().type() == typeid(Block), OptimizerException, ""); - m_nameDispenser.m_usedNames = NameCollector(m_ast).names(); - - for (size_t i = 1; i < m_ast.statements.size(); ++i) - { - assertThrow(m_ast.statements.at(i).type() == typeid(FunctionDefinition), OptimizerException, ""); - FunctionDefinition& fun = boost::get<FunctionDefinition>(m_ast.statements.at(i)); - m_functions[fun.name] = &fun; - m_functionsToVisit.insert(&fun); - } -} - -void FullInliner::run() -{ - assertThrow(m_ast.statements[0].type() == typeid(Block), OptimizerException, ""); - InlineModifier(*this, m_nameDispenser, "").visit(m_ast.statements[0]); - while (!m_functionsToVisit.empty()) - handleFunction(**m_functionsToVisit.begin()); -} - -void FullInliner::handleFunction(FunctionDefinition& _fun) -{ - if (!m_functionsToVisit.count(&_fun)) - return; - m_functionsToVisit.erase(&_fun); - (InlineModifier(*this, m_nameDispenser, _fun.name))(_fun.body); -} - -void InlineModifier::operator()(FunctionalInstruction& _instruction) -{ - visitArguments(_instruction.arguments); -} - -void InlineModifier::operator()(FunctionCall&) -{ - assertThrow(false, OptimizerException, "Should be handled in visit() instead."); -} - -void InlineModifier::operator()(ForLoop& _loop) -{ - (*this)(_loop.pre); - // Do not visit the condition because we cannot inline there. - (*this)(_loop.post); - (*this)(_loop.body); -} - -void InlineModifier::operator()(Block& _block) -{ - vector<Statement> saved; - saved.swap(m_statementsToPrefix); - - // This is only used if needed to minimize the number of move operations. - vector<Statement> modifiedStatements; - for (size_t i = 0; i < _block.statements.size(); ++i) - { - visit(_block.statements.at(i)); - if (!m_statementsToPrefix.empty()) - { - if (modifiedStatements.empty()) - std::move( - _block.statements.begin(), - _block.statements.begin() + i, - back_inserter(modifiedStatements) - ); - modifiedStatements += std::move(m_statementsToPrefix); - m_statementsToPrefix.clear(); - } - if (!modifiedStatements.empty()) - modifiedStatements.emplace_back(std::move(_block.statements[i])); - } - if (!modifiedStatements.empty()) - _block.statements = std::move(modifiedStatements); - - saved.swap(m_statementsToPrefix); -} - -void InlineModifier::visit(Expression& _expression) -{ - if (_expression.type() != typeid(FunctionCall)) - return ASTModifier::visit(_expression); - - FunctionCall& funCall = boost::get<FunctionCall>(_expression); - FunctionDefinition& fun = m_driver.function(funCall.functionName.name); - - m_driver.handleFunction(fun); - - // TODO: Insert good heuristic here. Perhaps implement that inside the driver. - bool doInline = funCall.functionName.name != m_currentFunction; - - if (fun.returnVariables.size() > 1) - doInline = false; - - { - vector<string> argNames; - vector<string> argTypes; - for (auto const& arg: fun.parameters) - { - argNames.push_back(fun.name + "_" + arg.name); - argTypes.push_back(arg.type); - } - visitArguments(funCall.arguments, argNames, argTypes, doInline); - } - - if (!doInline) - return; - - map<string, string> variableReplacements; - for (size_t i = 0; i < funCall.arguments.size(); ++i) - variableReplacements[fun.parameters[i].name] = boost::get<Identifier>(funCall.arguments[i]).name; - if (fun.returnVariables.empty()) - _expression = noop(funCall.location); - else - { - string returnVariable = fun.returnVariables[0].name; - variableReplacements[returnVariable] = newName(fun.name + "_" + returnVariable); - - m_statementsToPrefix.emplace_back(VariableDeclaration{ - funCall.location, - {{funCall.location, variableReplacements[returnVariable], fun.returnVariables[0].type}}, - {} - }); - _expression = Identifier{funCall.location, variableReplacements[returnVariable]}; - } - m_statementsToPrefix.emplace_back(BodyCopier(m_nameDispenser, fun.name + "_", variableReplacements)(fun.body)); -} - -void InlineModifier::visit(Statement& _statement) -{ - ASTModifier::visit(_statement); - // Replace pop(0) expression statemets (and others) by empty blocks. - if (_statement.type() == typeid(ExpressionStatement)) - { - ExpressionStatement& expSt = boost::get<ExpressionStatement>(_statement); - if (expSt.expression.type() == typeid(FunctionalInstruction)) - { - FunctionalInstruction& funInstr = boost::get<FunctionalInstruction>(expSt.expression); - if (funInstr.instruction == solidity::Instruction::POP) - if (MovableChecker(funInstr.arguments.at(0)).movable()) - _statement = Block{expSt.location, {}}; - } - } -} - -void InlineModifier::visitArguments( - vector<Expression>& _arguments, - vector<string> const& _nameHints, - vector<string> const& _types, - bool _moveToFront -) -{ - // If one of the elements moves parts to the front, all other elements right of it - // also have to be moved to the front to keep the order of evaluation. - vector<Statement> prefix; - for (size_t i = 0; i < _arguments.size(); ++i) - { - auto& arg = _arguments[i]; - // TODO optimize vector operations, check that it actually moves - auto internalPrefix = visitRecursively(arg); - if (!internalPrefix.empty()) - { - _moveToFront = true; - // We go through the arguments left to right, so we have to invert - // the prefixes. - prefix = std::move(internalPrefix) + std::move(prefix); - } - else if (_moveToFront) - { - auto location = locationOf(arg); - string var = newName(i < _nameHints.size() ? _nameHints[i] : ""); - prefix.emplace(prefix.begin(), VariableDeclaration{ - location, - {{TypedName{location, var, i < _types.size() ? _types[i] : ""}}}, - make_shared<Expression>(std::move(arg)) - }); - arg = Identifier{location, var}; - } - } - m_statementsToPrefix += std::move(prefix); -} - -vector<Statement> InlineModifier::visitRecursively(Expression& _expression) -{ - vector<Statement> saved; - saved.swap(m_statementsToPrefix); - visit(_expression); - saved.swap(m_statementsToPrefix); - return saved; -} - -string InlineModifier::newName(string const& _prefix) -{ - return m_nameDispenser.newName(_prefix); -} - -Expression InlineModifier::noop(SourceLocation const& _location) -{ - return FunctionalInstruction{_location, solidity::Instruction::POP, { - Literal{_location, assembly::LiteralKind::Number, "0", ""} - }}; -} - -Statement BodyCopier::operator()(VariableDeclaration const& _varDecl) -{ - for (auto const& var: _varDecl.variables) - m_variableReplacements[var.name] = m_nameDispenser.newName(m_varNamePrefix + var.name); - return ASTCopier::operator()(_varDecl); -} - -Statement BodyCopier::operator()(FunctionDefinition const& _funDef) -{ - assertThrow(false, OptimizerException, "Function hoisting has to be done before function inlining."); - return _funDef; -} - -string BodyCopier::translateIdentifier(string const& _name) -{ - if (m_variableReplacements.count(_name)) - return m_variableReplacements.at(_name); - else - return _name; -} diff --git a/libjulia/optimiser/FullInliner.h b/libjulia/optimiser/FullInliner.h deleted file mode 100644 index ff9e6854..00000000 --- a/libjulia/optimiser/FullInliner.h +++ /dev/null @@ -1,179 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that performs function inlining for arbitrary functions. - */ -#pragma once - -#include <libjulia/ASTDataForward.h> - -#include <libjulia/optimiser/ASTCopier.h> -#include <libjulia/optimiser/ASTWalker.h> -#include <libjulia/optimiser/NameDispenser.h> -#include <libjulia/Exceptions.h> - -#include <libevmasm/SourceLocation.h> - -#include <boost/variant.hpp> -#include <boost/optional.hpp> - -#include <set> - -namespace dev -{ -namespace julia -{ - -class NameCollector; - - -/** - * Optimiser component that modifies an AST in place, inlining arbitrary functions. - * - * Code of the form - * - * function f(a, b) -> c { ... } - * h(g(x(...), f(arg1(...), arg2(...)), y(...)), z(...)) - * - * is transformed into - * - * function f(a, b) -> c { ... } - * - * let z1 := z(...) let y1 := y(...) let a2 := arg2(...) let a1 := arg1(...) - * let c1 := 0 - * { code of f, with replacements: a -> a1, b -> a2, c -> c1, d -> d1 } - * h(g(x(...), c1, y1), z1) - * - * No temporary variable is created for expressions that are "movable" - * (i.e. they are "pure", have no side-effects and also do not depend on other code - * that might have side-effects). - * - * This component can only be used on sources with unique names and with hoisted functions, - * i.e. the root node has to be a block that itself contains a single block followed by all - * function definitions. - */ -class FullInliner: public ASTModifier -{ -public: - explicit FullInliner(Block& _ast); - - void run(); - - /// Perform inlining operations inside the given function. - void handleFunction(FunctionDefinition& _function); - - FunctionDefinition& function(std::string _name) { return *m_functions.at(_name); } - -private: - /// The AST to be modified. The root block itself will not be modified, because - /// we store pointers to functions. - Block& m_ast; - std::map<std::string, FunctionDefinition*> m_functions; - std::set<FunctionDefinition*> m_functionsToVisit; - NameDispenser m_nameDispenser; -}; - -/** - * Class that walks the AST of a block that does not contain function definitions and perform - * the actual code modifications. - */ -class InlineModifier: public ASTModifier -{ -public: - InlineModifier(FullInliner& _driver, NameDispenser& _nameDispenser, std::string _functionName): - m_currentFunction(std::move(_functionName)), - m_driver(_driver), - m_nameDispenser(_nameDispenser) - { } - ~InlineModifier() - { - assertThrow(m_statementsToPrefix.empty(), OptimizerException, ""); - } - - virtual void operator()(FunctionalInstruction&) override; - virtual void operator()(FunctionCall&) override; - virtual void operator()(ForLoop&) override; - virtual void operator()(Block& _block) override; - - using ASTModifier::visit; - virtual void visit(Expression& _expression) override; - virtual void visit(Statement& _st) override; - -private: - - /// Visits a list of expressions (usually an argument list to a function call) and tries - /// to inline them. If one of them is inlined, all right of it have to be moved to the front - /// (to keep the order of evaluation). If @a _moveToFront is true, all elements are moved - /// to the front. @a _nameHints and @_types are used for the newly created variables, but - /// both can be empty. - void visitArguments( - std::vector<Expression>& _arguments, - std::vector<std::string> const& _nameHints = {}, - std::vector<std::string> const& _types = {}, - bool _moveToFront = false - ); - - /// Visits an expression, but saves and restores the current statements to prefix and returns - /// the statements that should be prefixed for @a _expression. - std::vector<Statement> visitRecursively(Expression& _expression); - - std::string newName(std::string const& _prefix); - - /// @returns an expression returning nothing. - Expression noop(SourceLocation const& _location); - - /// List of statements that should go in front of the currently visited AST element, - /// at the statement level. - std::vector<Statement> m_statementsToPrefix; - std::string m_currentFunction; - FullInliner& m_driver; - NameDispenser& m_nameDispenser; -}; - -/** - * Creates a copy of a block that is supposed to be the body of a function. - * Applies replacements to referenced variables and creates new names for - * variable declarations. - */ -class BodyCopier: public ASTCopier -{ -public: - BodyCopier( - NameDispenser& _nameDispenser, - std::string const& _varNamePrefix, - std::map<std::string, std::string> const& _variableReplacements - ): - m_nameDispenser(_nameDispenser), - m_varNamePrefix(_varNamePrefix), - m_variableReplacements(_variableReplacements) - {} - - using ASTCopier::operator (); - - virtual Statement operator()(VariableDeclaration const& _varDecl) override; - virtual Statement operator()(FunctionDefinition const& _funDef) override; - - virtual std::string translateIdentifier(std::string const& _name) override; - - NameDispenser& m_nameDispenser; - std::string const& m_varNamePrefix; - std::map<std::string, std::string> m_variableReplacements; -}; - - -} -} diff --git a/libjulia/optimiser/FunctionGrouper.cpp b/libjulia/optimiser/FunctionGrouper.cpp deleted file mode 100644 index f1e99e6b..00000000 --- a/libjulia/optimiser/FunctionGrouper.cpp +++ /dev/null @@ -1,47 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that changes the code of a block so that all non-function definition - * statements are moved to a block of their own followed by all function definitions. - */ - -#include <libjulia/optimiser/FunctionGrouper.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <boost/range/algorithm_ext/erase.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - - -void FunctionGrouper::operator()(Block& _block) -{ - vector<Statement> reordered; - reordered.emplace_back(Block{_block.location, {}}); - - for (auto&& statement: _block.statements) - { - if (statement.type() == typeid(FunctionDefinition)) - reordered.emplace_back(std::move(statement)); - else - boost::get<Block>(reordered.front()).statements.emplace_back(std::move(statement)); - } - _block.statements = std::move(reordered); -} diff --git a/libjulia/optimiser/FunctionGrouper.h b/libjulia/optimiser/FunctionGrouper.h deleted file mode 100644 index 64a71318..00000000 --- a/libjulia/optimiser/FunctionGrouper.h +++ /dev/null @@ -1,46 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that changes the code of a black so that all non-function definition - * instructions are moved to a block of their own followed by all function definitions. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> - -namespace dev -{ -namespace julia -{ - -/** - * Moves all instructions in a block into a new block at the start of the block, followed by - * all function definitions. - * - * After this step, a block is of the form - * { { I...} F... } - * Where I are (non-function-definition) instructions and F are function definitions. - */ -class FunctionGrouper -{ -public: - void operator()(Block& _block); -}; - -} -} diff --git a/libjulia/optimiser/FunctionHoister.cpp b/libjulia/optimiser/FunctionHoister.cpp deleted file mode 100644 index 98fc714c..00000000 --- a/libjulia/optimiser/FunctionHoister.cpp +++ /dev/null @@ -1,51 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that changes the code so that it consists of a block starting with - * a single block followed only by function definitions and with no functions defined - * anywhere else. - */ - -#include <libjulia/optimiser/FunctionHoister.h> -#include <libjulia/optimiser/Utilities.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/CommonData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - -void FunctionHoister::operator()(Block& _block) -{ - bool topLevel = m_isTopLevel; - m_isTopLevel = false; - for (auto&& statement: _block.statements) - { - boost::apply_visitor(*this, statement); - if (statement.type() == typeid(FunctionDefinition)) - { - m_functions.emplace_back(std::move(statement)); - statement = Block{_block.location, {}}; - } - } - removeEmptyBlocks(_block); - if (topLevel) - _block.statements += std::move(m_functions); -} diff --git a/libjulia/optimiser/FunctionHoister.h b/libjulia/optimiser/FunctionHoister.h deleted file mode 100644 index f9f8bce0..00000000 --- a/libjulia/optimiser/FunctionHoister.h +++ /dev/null @@ -1,52 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that changes the code so that all function definitions are at the top - * level block. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> - -#include <libjulia/optimiser/ASTWalker.h> - -namespace dev -{ -namespace julia -{ - -/** - * Moves all functions to the top-level scope. - * Applying this transformation to source code that has ambiguous identifiers might - * lead to invalid code. - * - * Prerequisites: Disambiguator - */ -class FunctionHoister: public ASTModifier -{ -public: - using ASTModifier::operator(); - virtual void operator()(Block& _block); - -private: - bool m_isTopLevel = true; - std::vector<Statement> m_functions; -}; - -} -} diff --git a/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp b/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp deleted file mode 100644 index e237063d..00000000 --- a/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp +++ /dev/null @@ -1,70 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that identifies functions to be inlined. - */ - -#include <libjulia/optimiser/InlinableExpressionFunctionFinder.h> - -#include <libjulia/optimiser/Utilities.h> - -#include <libsolidity/inlineasm/AsmData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -void InlinableExpressionFunctionFinder::operator()(Identifier const& _identifier) -{ - checkAllowed(_identifier.name); - ASTWalker::operator()(_identifier); -} - -void InlinableExpressionFunctionFinder::operator()(FunctionCall const& _funCall) -{ - checkAllowed(_funCall.functionName.name); - ASTWalker::operator()(_funCall); -} - -void InlinableExpressionFunctionFinder::operator()(FunctionDefinition const& _function) -{ - if (_function.returnVariables.size() == 1 && _function.body.statements.size() == 1) - { - string const& retVariable = _function.returnVariables.front().name; - Statement const& bodyStatement = _function.body.statements.front(); - if (bodyStatement.type() == typeid(Assignment)) - { - Assignment const& assignment = boost::get<Assignment>(bodyStatement); - if (assignment.variableNames.size() == 1 && assignment.variableNames.front().name == retVariable) - { - // FIXME: use code size metric here - - // We cannot overwrite previous settings, because this function definition - // would not be valid here if we were searching inside a functionally inlinable - // function body. - assertThrow(m_disallowedIdentifiers.empty() && !m_foundDisallowedIdentifier, OptimizerException, ""); - m_disallowedIdentifiers = set<string>{retVariable, _function.name}; - boost::apply_visitor(*this, *assignment.value); - if (!m_foundDisallowedIdentifier) - m_inlinableFunctions[_function.name] = &_function; - m_disallowedIdentifiers.clear(); - m_foundDisallowedIdentifier = false; - } - } - } - ASTWalker::operator()(_function.body); -} diff --git a/libjulia/optimiser/InlinableExpressionFunctionFinder.h b/libjulia/optimiser/InlinableExpressionFunctionFinder.h deleted file mode 100644 index d11160d7..00000000 --- a/libjulia/optimiser/InlinableExpressionFunctionFinder.h +++ /dev/null @@ -1,69 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that identifies functions to be inlined. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> -#include <libjulia/optimiser/ASTWalker.h> - -#include <set> - -namespace dev -{ -namespace julia -{ - -/** - * Optimiser component that finds functions that can be - * inlined inside functional expressions, i.e. functions that - * - have a single return parameter r - * - have a body like r := <functional expression> - * - neither reference themselves nor r in the right hand side - * - * This component can only be used on sources with unique names. - */ -class InlinableExpressionFunctionFinder: public ASTWalker -{ -public: - - std::map<std::string, FunctionDefinition const*> const& inlinableFunctions() const - { - return m_inlinableFunctions; - } - - using ASTWalker::operator(); - virtual void operator()(Identifier const& _identifier) override; - virtual void operator()(FunctionCall const& _funCall) override; - virtual void operator()(FunctionDefinition const& _function) override; - -private: - void checkAllowed(std::string const& _name) - { - if (m_disallowedIdentifiers.count(_name)) - m_foundDisallowedIdentifier = true; - } - - bool m_foundDisallowedIdentifier = false; - std::set<std::string> m_disallowedIdentifiers; - std::map<std::string, FunctionDefinition const*> m_inlinableFunctions; -}; - -} -} diff --git a/libjulia/optimiser/MainFunction.cpp b/libjulia/optimiser/MainFunction.cpp deleted file mode 100644 index bcd2f178..00000000 --- a/libjulia/optimiser/MainFunction.cpp +++ /dev/null @@ -1,54 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Changes the topmost block to be a function with a specific name ("main") which has no - * inputs nor outputs. - */ - -#include <libjulia/optimiser/MainFunction.h> - -#include <libjulia/optimiser/NameCollector.h> -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/CommonData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - -void MainFunction::operator()(Block& _block) -{ - assertThrow(_block.statements.size() >= 1, OptimizerException, ""); - assertThrow(_block.statements[0].type() == typeid(Block), OptimizerException, ""); - for (size_t i = 1; i < _block.statements.size(); ++i) - assertThrow(_block.statements.at(i).type() == typeid(FunctionDefinition), OptimizerException, ""); - /// @todo this should handle scopes properly and instead of an assertion it should rename the conflicting function - assertThrow(NameCollector(_block).names().count("main") == 0, OptimizerException, ""); - - Block& block = boost::get<Block>(_block.statements[0]); - FunctionDefinition main{ - block.location, - "main", - {}, - {}, - std::move(block) - }; - _block.statements[0] = std::move(main); -} diff --git a/libjulia/optimiser/MainFunction.h b/libjulia/optimiser/MainFunction.h deleted file mode 100644 index 7201d89a..00000000 --- a/libjulia/optimiser/MainFunction.h +++ /dev/null @@ -1,41 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Changes the topmost block to be a function with a specific name ("main") which has no - * inputs nor outputs. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> - -namespace dev -{ -namespace julia -{ - -/** - * Prerequisites: Function Grouper - */ -class MainFunction -{ -public: - void operator()(Block& _block); -}; - -} -} diff --git a/libjulia/optimiser/Metrics.cpp b/libjulia/optimiser/Metrics.cpp deleted file mode 100644 index eaa1494f..00000000 --- a/libjulia/optimiser/Metrics.cpp +++ /dev/null @@ -1,52 +0,0 @@ -/*( - 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 <http://www.gnu.org/licenses/>. -*/ -/** -* Module providing metrics for the optimizer. -*/ - -#include <libjulia/optimiser/Metrics.h> - -#include <libsolidity/inlineasm/AsmData.h> - -using namespace dev; -using namespace dev::julia; - -size_t CodeSize::codeSize(Statement const& _statement) -{ - CodeSize cs; - cs.visit(_statement); - return cs.m_size; -} - -size_t CodeSize::codeSize(Expression const& _expression) -{ - CodeSize cs; - cs.visit(_expression); - return cs.m_size; -} - -void CodeSize::visit(Statement const& _statement) -{ - ++m_size; - ASTWalker::visit(_statement); -} - -void CodeSize::visit(Expression const& _expression) -{ - ++m_size; - ASTWalker::visit(_expression); -} diff --git a/libjulia/optimiser/Metrics.h b/libjulia/optimiser/Metrics.h deleted file mode 100644 index ff058fc3..00000000 --- a/libjulia/optimiser/Metrics.h +++ /dev/null @@ -1,49 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Module providing metrics for the optimizer. - */ - -#pragma once - -#include <libjulia/optimiser/ASTWalker.h> - -namespace dev -{ -namespace julia -{ - -class CodeSize: public ASTWalker -{ -public: - /// Returns a metric for the code size of an AST element. - /// More specifically, it returns the number of AST nodes. - static size_t codeSize(Statement const& _statement); - /// Returns a metric for the code size of an AST element. - /// More specifically, it returns the number of AST nodes. - static size_t codeSize(Expression const& _expression); - -private: - virtual void visit(Statement const& _statement) override; - virtual void visit(Expression const& _expression) override; - -private: - size_t m_size = 0; -}; - -} -} diff --git a/libjulia/optimiser/NameCollector.cpp b/libjulia/optimiser/NameCollector.cpp deleted file mode 100644 index c0d0b707..00000000 --- a/libjulia/optimiser/NameCollector.cpp +++ /dev/null @@ -1,74 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Specific AST walker that collects all defined names. - */ - -#include <libjulia/optimiser/NameCollector.h> - -#include <libsolidity/inlineasm/AsmData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -void NameCollector::operator()(VariableDeclaration const& _varDecl) -{ - for (auto const& var: _varDecl.variables) - m_names.insert(var.name); -} - -void NameCollector::operator ()(FunctionDefinition const& _funDef) -{ - m_names.insert(_funDef.name); - for (auto const arg: _funDef.parameters) - m_names.insert(arg.name); - for (auto const ret: _funDef.returnVariables) - m_names.insert(ret.name); - ASTWalker::operator ()(_funDef); -} - -void ReferencesCounter::operator()(Identifier const& _identifier) -{ - ++m_references[_identifier.name]; -} - -void ReferencesCounter::operator()(FunctionCall const& _funCall) -{ - ++m_references[_funCall.functionName.name]; - ASTWalker::operator()(_funCall); -} - -map<string, size_t> ReferencesCounter::countReferences(Block const& _block) -{ - ReferencesCounter counter; - counter(_block); - return counter.references(); -} - -map<string, size_t> ReferencesCounter::countReferences(Expression const& _expression) -{ - ReferencesCounter counter; - counter.visit(_expression); - return counter.references(); -} - -void Assignments::operator()(Assignment const& _assignment) -{ - for (auto const& var: _assignment.variableNames) - m_names.insert(var.name); -} diff --git a/libjulia/optimiser/NameCollector.h b/libjulia/optimiser/NameCollector.h deleted file mode 100644 index 29856172..00000000 --- a/libjulia/optimiser/NameCollector.h +++ /dev/null @@ -1,87 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Specific AST walkers that collect facts about identifiers and definitions. - */ - -#pragma once - -#include <libjulia/optimiser/ASTWalker.h> - -#include <string> -#include <map> -#include <set> - -namespace dev -{ -namespace julia -{ - -/** - * Specific AST walker that collects all defined names. - */ -class NameCollector: public ASTWalker -{ -public: - explicit NameCollector(Block const& _block) - { - (*this)(_block); - } - - using ASTWalker::operator (); - virtual void operator()(VariableDeclaration const& _varDecl) override; - virtual void operator()(FunctionDefinition const& _funDef) override; - - std::set<std::string> names() const { return m_names; } -private: - std::set<std::string> m_names; -}; - -/** - * Specific AST walker that counts all references to all declarations. - */ -class ReferencesCounter: public ASTWalker -{ -public: - using ASTWalker::operator (); - virtual void operator()(Identifier const& _identifier); - virtual void operator()(FunctionCall const& _funCall); - - static std::map<std::string, size_t> countReferences(Block const& _block); - static std::map<std::string, size_t> countReferences(Expression const& _expression); - - std::map<std::string, size_t> const& references() const { return m_references; } -private: - std::map<std::string, size_t> m_references; -}; - -/** - * Specific AST walker that finds all variables that are assigned to. - */ -class Assignments: public ASTWalker -{ -public: - using ASTWalker::operator (); - virtual void operator()(Assignment const& _assignment) override; - - std::set<std::string> const& names() const { return m_names; } -private: - std::set<std::string> m_names; -}; - -} -} diff --git a/libjulia/optimiser/NameDispenser.cpp b/libjulia/optimiser/NameDispenser.cpp deleted file mode 100644 index cae19381..00000000 --- a/libjulia/optimiser/NameDispenser.cpp +++ /dev/null @@ -1,38 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that can create new unique names. - */ - -#include <libjulia/optimiser/NameDispenser.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -string NameDispenser::newName(string const& _prefix) -{ - string name = _prefix; - size_t suffix = 0; - while (name.empty() || m_usedNames.count(name)) - { - suffix++; - name = _prefix + "_" + to_string(suffix); - } - m_usedNames.insert(name); - return name; -} diff --git a/libjulia/optimiser/NameDispenser.h b/libjulia/optimiser/NameDispenser.h deleted file mode 100644 index 91c43d54..00000000 --- a/libjulia/optimiser/NameDispenser.h +++ /dev/null @@ -1,37 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimiser component that can create new unique names. - */ -#pragma once - -#include <set> -#include <string> - -namespace dev -{ -namespace julia -{ - -struct NameDispenser -{ - std::string newName(std::string const& _prefix); - std::set<std::string> m_usedNames; -}; - -} -} diff --git a/libjulia/optimiser/README.md b/libjulia/optimiser/README.md deleted file mode 100644 index faef818b..00000000 --- a/libjulia/optimiser/README.md +++ /dev/null @@ -1,157 +0,0 @@ -Note that the Yul optimiser is still in research phase. Because of that, -the following description might not fully reflect the current or even -planned state of the optimiser. - -## Yul Optimiser - -The Yul optimiser consists of several stages and components that all transform -the AST in a semantically equivalent way. The goal is to end up either with code -that is shorter or at least only marginally longer but will allow further -optimisation steps. - -The optimiser currently follows a purely greedy strategy and does not do any -backtracking. - -## Disambiguator - -The disambiguator takes an AST and returns a fresh copy where all identifiers have -names unique to the input AST. This is a prerequisite for all other optimiser stages. -One of the benefits is that identifier lookup does not need to take scopes into account -and we can basically ignore the result of the analysis phase. - -All subsequent stages have the property that all names stay unique. This means if -a new identifier needs to be introduced, a new unique name is generated. - -## Function Hoister - -The function hoister moves all function definitions to the end of the topmost block. This is -a semantically equivalent transformation as long as it is performed after the -disambiguation stage. The reason is that moving a definition to a higher-level block cannot decrease -its visibility and it is impossible to reference variables defined in a different function. - -The benefit of this stage is that function definitions can be looked up more easily. - -## Function Grouper - -The function grouper has to be applied after the disambiguator and the function hoister. -Its effect is that all topmost elements that are not function definitions are moved -into a single block which is the first statement of the root block. - -After this step, a program has the following normal form: - - { I F... } - -Where I is a block that does not contain any function definitions (not even recursively) -and F is a list of function definitions such that no function contains a function definition. - -## Functional Inliner - -The functional inliner depends on the disambiguator, the function hoister and function grouper. -It performs function inlining such that the result of the inlining is an expression. This can -only be done if the body of the function to be inlined has the form ``{ r := E }`` where ``r`` -is the single return value of the function, ``E`` is an expression and all arguments in the -function call are so-called movable expressions. A movable expression is either a literal, a -variable or a function call (or EVM opcode) which does not have side-effects and also does not -depend on any side-effects. - -As an example, neither ``mload`` nor ``mstore`` would be allowed. - -## Expression Splitter - -The expression splitter turns expressions like ``add(mload(x), mul(mload(y), 0x20))`` -into a sequence of declarations of unique variables that are assigned sub-expressions -of that expression so that each function call has only variables or literals -as arguments. - -The above would be transformed into - - { - let _1 := mload(y) - let _2 := mul(_1, 0x20) - let _3 := mload(x) - let z := add(_3, _2) - } - -Note that this transformation does not change the order of opcodes or function calls. - -It is not applied to loop conditions, because the loop control flow does not allow -this "outlining" of the inner expressions in all cases. - -The final program should be in a form such that with the exception of loop conditions, -function calls can only appear in the right-hand side of a variable declaration, -assignments or expression statements and all arguments have to be constants or variables. - -The benefits of this form are that it is much easier to re-order the sequence of opcodes -and it is also easier to perform function call inlining. The drawback is that -such code is much harder to read for humans. - -## Expression Joiner - -This is the opposite operation of the expression splitter. It turns a sequence of -variable declarations that have exactly one reference into a complex expression. -This stage again fully preserves the order of function calls and opcode executions. -It does not make use of any information concerning the commutability of opcodes; -if moving the value of a variable to its place of use would change the order -of any function call or opcode execution, the transformation is not performed. - -Note that the component will not move the assigned value of a variable assignment -or a variable that is referenced more than once. - -## Common Subexpression Eliminator - -This step replaces a subexpression by the value of a pre-existing variable -that currently has the same value (only if the value is movable), based -on a syntactic comparison. - -This can be used to compute a local value numbering, especially if the -expression splitter is used before. - -The expression simplifier will be able to perform better replacements -if the common subexpression eliminator was run right before it. - -Prerequisites: Disambiguator - -## Full Function Inliner - -## Rematerialisation - -The rematerialisation stage tries to replace variable references by the expression that -was last assigned to the variable. This is of course only beneficial if this expression -is comparatively cheap to evaluate. Furthermore, it is only semantically equivalent if -the value of the expression did not change between the point of assignment and the -point of use. The main benefit of this stage is that it can save stack slots if it -leads to a variable being eliminated completely (see below), but it can also -save a DUP opcode on the EVM if the expression is very cheap. - -The algorithm only allows movable expressions (see above for a definition) in this case. -Expressions that contain other variables are also disallowed if one of those variables -have been assigned to in the meantime. This is also not applied to variables where -assignment and use span across loops and conditionals. - -## Unused Definition Pruner - -If a variable or function is not referenced, it is removed from the code. -If there are two assignments to a variable where the first one is a movable expression -and the variable is not used between the two assignments (and the second is not inside -a loop or conditional, the first one is not inside), the first assignment is removed. - - -## Function Unifier - -## Expression Simplifier - -This step can only be applied for the EVM-flavoured dialect of Yul. It applies -simple rules like ``x + 0 == x`` to simplify expressions. - -## Ineffective Statement Remover - -This step removes statements that have no side-effects. - -## WebAssembly specific - -### Main Function - -Changes the topmost block to be a function with a specific name ("main") which has no -inputs nor outputs. - -Depends on the Function Grouper. diff --git a/libjulia/optimiser/Rematerialiser.cpp b/libjulia/optimiser/Rematerialiser.cpp deleted file mode 100644 index 392099fb..00000000 --- a/libjulia/optimiser/Rematerialiser.cpp +++ /dev/null @@ -1,55 +0,0 @@ -/*( - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimisation stage that replaces variables by their most recently assigned expressions. - */ - -#include <libjulia/optimiser/Rematerialiser.h> - -#include <libjulia/optimiser/Metrics.h> -#include <libjulia/optimiser/ASTCopier.h> -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -void Rematerialiser::visit(Expression& _e) -{ - if (_e.type() == typeid(Identifier)) - { - Identifier& identifier = boost::get<Identifier>(_e); - if (m_value.count(identifier.name)) - { - string name = identifier.name; - bool expressionValid = true; - for (auto const& ref: m_references[name]) - if (!inScope(ref)) - { - expressionValid = false; - break; - } - assertThrow(m_value.at(name), OptimizerException, ""); - auto const& value = *m_value.at(name); - if (expressionValid && CodeSize::codeSize(value) <= 7) - _e = (ASTCopier{}).translate(value); - } - } - DataFlowAnalyzer::visit(_e); -} diff --git a/libjulia/optimiser/Rematerialiser.h b/libjulia/optimiser/Rematerialiser.h deleted file mode 100644 index 60dbfada..00000000 --- a/libjulia/optimiser/Rematerialiser.h +++ /dev/null @@ -1,48 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimisation stage that replaces variables by their most recently assigned expressions. - */ - -#pragma once - -#include <libjulia/optimiser/DataFlowAnalyzer.h> - -#include <string> -#include <map> -#include <set> - -namespace dev -{ -namespace julia -{ - -/** - * Optimisation stage that replaces variables by their most recently assigned expressions. - * - * Prerequisite: Disambiguator - */ -class Rematerialiser: public DataFlowAnalyzer -{ -protected: - using ASTModifier::visit; - virtual void visit(Expression& _e) override; - -}; - -} -} diff --git a/libjulia/optimiser/Semantics.cpp b/libjulia/optimiser/Semantics.cpp deleted file mode 100644 index f28925a4..00000000 --- a/libjulia/optimiser/Semantics.cpp +++ /dev/null @@ -1,62 +0,0 @@ -/*( - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Specific AST walkers that collect semantical facts. - */ - -#include <libjulia/optimiser/Semantics.h> - -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libevmasm/SemanticInformation.h> - -#include <libdevcore/CommonData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -MovableChecker::MovableChecker(Expression const& _expression) -{ - visit(_expression); -} - -void MovableChecker::operator()(Identifier const& _identifier) -{ - ASTWalker::operator()(_identifier); - m_variableReferences.insert(_identifier.name); -} - -void MovableChecker::operator()(FunctionalInstruction const& _instr) -{ - if (!eth::SemanticInformation::movable(_instr.instruction)) - m_movable = false; - else - ASTWalker::operator()(_instr); -} - -void MovableChecker::operator()(FunctionCall const&) -{ - m_movable = false; -} - -void MovableChecker::visit(Statement const&) -{ - assertThrow(false, OptimizerException, "Movability for statement requested."); -} diff --git a/libjulia/optimiser/Semantics.h b/libjulia/optimiser/Semantics.h deleted file mode 100644 index 6df5f01a..00000000 --- a/libjulia/optimiser/Semantics.h +++ /dev/null @@ -1,62 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Specific AST walkers that collect semantical facts. - */ - -#pragma once - -#include <libjulia/optimiser/ASTWalker.h> - -#include <string> -#include <map> -#include <set> - -namespace dev -{ -namespace julia -{ - -/** - * Specific AST walker that determines whether an expression is movable. - */ -class MovableChecker: public ASTWalker -{ -public: - MovableChecker() = default; - explicit MovableChecker(Expression const& _expression); - - virtual void operator()(Identifier const& _identifier) override; - virtual void operator()(FunctionalInstruction const& _functionalInstruction) override; - virtual void operator()(FunctionCall const& _functionCall) override; - - /// Disallow visiting anything apart from Expressions (this throws). - virtual void visit(Statement const&) override; - using ASTWalker::visit; - - bool movable() const { return m_movable; } - std::set<std::string> const& referencedVariables() const { return m_variableReferences; } - -private: - /// Which variables the current expression references. - std::set<std::string> m_variableReferences; - /// Is the current expression movable or not. - bool m_movable = true; -}; - -} -} diff --git a/libjulia/optimiser/SimplificationRules.cpp b/libjulia/optimiser/SimplificationRules.cpp deleted file mode 100644 index 56cb96ac..00000000 --- a/libjulia/optimiser/SimplificationRules.cpp +++ /dev/null @@ -1,189 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Module for applying replacement rules against Expressions. - */ - -#include <libjulia/optimiser/SimplificationRules.h> - -#include <libjulia/optimiser/Utilities.h> -#include <libjulia/optimiser/ASTCopier.h> -#include <libjulia/optimiser/Semantics.h> -#include <libjulia/optimiser/SyntacticalEquality.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libevmasm/RuleList.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - - -SimplificationRule<Pattern> const* SimplificationRules::findFirstMatch(Expression const& _expr) -{ - if (_expr.type() != typeid(FunctionalInstruction)) - return nullptr; - - static SimplificationRules rules; - assertThrow(rules.isInitialized(), OptimizerException, "Rule list not properly initialized."); - - FunctionalInstruction const& instruction = boost::get<FunctionalInstruction>(_expr); - for (auto const& rule: rules.m_rules[byte(instruction.instruction)]) - { - rules.resetMatchGroups(); - if (rule.pattern.matches(_expr)) - return &rule; - } - return nullptr; -} - -bool SimplificationRules::isInitialized() const -{ - return !m_rules[byte(solidity::Instruction::ADD)].empty(); -} - -void SimplificationRules::addRules(vector<SimplificationRule<Pattern>> const& _rules) -{ - for (auto const& r: _rules) - addRule(r); -} - -void SimplificationRules::addRule(SimplificationRule<Pattern> const& _rule) -{ - m_rules[byte(_rule.pattern.instruction())].push_back(_rule); -} - -SimplificationRules::SimplificationRules() -{ - // Multiple occurrences of one of these inside one rule must match the same equivalence class. - // Constants. - Pattern A(PatternKind::Constant); - Pattern B(PatternKind::Constant); - Pattern C(PatternKind::Constant); - // Anything. - Pattern X; - Pattern Y; - A.setMatchGroup(1, m_matchGroups); - B.setMatchGroup(2, m_matchGroups); - C.setMatchGroup(3, m_matchGroups); - X.setMatchGroup(4, m_matchGroups); - Y.setMatchGroup(5, m_matchGroups); - - addRules(simplificationRuleList(A, B, C, X, Y)); - assertThrow(isInitialized(), OptimizerException, "Rule list not properly initialized."); -} - -Pattern::Pattern(solidity::Instruction _instruction, vector<Pattern> const& _arguments): - m_kind(PatternKind::Operation), - m_instruction(_instruction), - m_arguments(_arguments) -{ -} - -void Pattern::setMatchGroup(unsigned _group, map<unsigned, Expression const*>& _matchGroups) -{ - m_matchGroup = _group; - m_matchGroups = &_matchGroups; -} - -bool Pattern::matches(Expression const& _expr) const -{ - if (m_kind == PatternKind::Constant) - { - if (_expr.type() != typeid(Literal)) - return false; - Literal const& literal = boost::get<Literal>(_expr); - if (literal.kind != assembly::LiteralKind::Number) - return false; - if (m_data && *m_data != u256(literal.value)) - return false; - assertThrow(m_arguments.empty(), OptimizerException, ""); - } - else if (m_kind == PatternKind::Operation) - { - if (_expr.type() != typeid(FunctionalInstruction)) - return false; - FunctionalInstruction const& instr = boost::get<FunctionalInstruction>(_expr); - if (m_instruction != instr.instruction) - return false; - assertThrow(m_arguments.size() == instr.arguments.size(), OptimizerException, ""); - for (size_t i = 0; i < m_arguments.size(); ++i) - if (!m_arguments[i].matches(instr.arguments.at(i))) - return false; - } - else - { - assertThrow(m_arguments.empty(), OptimizerException, ""); - } - // We support matching multiple expressions that require the same value - // based on identical ASTs, which have to be movable. - if (m_matchGroup) - { - if (m_matchGroups->count(m_matchGroup)) - { - Expression const* firstMatch = (*m_matchGroups)[m_matchGroup]; - assertThrow(firstMatch, OptimizerException, "Match set but to null."); - return - SyntacticalEqualityChecker::equal(*firstMatch, _expr) && - MovableChecker(_expr).movable(); - } - else - (*m_matchGroups)[m_matchGroup] = &_expr; - } - return true; -} - -solidity::Instruction Pattern::instruction() const -{ - assertThrow(m_kind == PatternKind::Operation, OptimizerException, ""); - return m_instruction; -} - -Expression Pattern::toExpression(SourceLocation const& _location) const -{ - if (matchGroup()) - return ASTCopier().translate(matchGroupValue()); - if (m_kind == PatternKind::Constant) - { - assertThrow(m_data, OptimizerException, "No match group and no constant value given."); - return Literal{_location, assembly::LiteralKind::Number, formatNumber(*m_data), ""}; - } - else if (m_kind == PatternKind::Operation) - { - vector<Expression> arguments; - for (auto const& arg: m_arguments) - arguments.emplace_back(arg.toExpression(_location)); - return FunctionalInstruction{_location, m_instruction, std::move(arguments)}; - } - assertThrow(false, OptimizerException, "Pattern of kind 'any', but no match group."); -} - -u256 Pattern::d() const -{ - Literal const& literal = boost::get<Literal>(matchGroupValue()); - assertThrow(literal.kind == assembly::LiteralKind::Number, OptimizerException, ""); - return u256(literal.value); -} - -Expression const& Pattern::matchGroupValue() const -{ - assertThrow(m_matchGroup > 0, OptimizerException, ""); - assertThrow(!!m_matchGroups, OptimizerException, ""); - assertThrow((*m_matchGroups)[m_matchGroup], OptimizerException, ""); - return *(*m_matchGroups)[m_matchGroup]; -} diff --git a/libjulia/optimiser/SimplificationRules.h b/libjulia/optimiser/SimplificationRules.h deleted file mode 100644 index e35e6466..00000000 --- a/libjulia/optimiser/SimplificationRules.h +++ /dev/null @@ -1,120 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Module for applying replacement rules against Expressions. - */ - -#pragma once - -#include <libevmasm/ExpressionClasses.h> -#include <libevmasm/SimplificationRule.h> - -#include <libjulia/ASTDataForward.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <boost/noncopyable.hpp> - -#include <functional> -#include <vector> - -namespace dev -{ -namespace julia -{ - -class Pattern; - -/** - * Container for all simplification rules. - */ -class SimplificationRules: public boost::noncopyable -{ -public: - SimplificationRules(); - - /// @returns a pointer to the first matching pattern and sets the match - /// groups accordingly. - static SimplificationRule<Pattern> const* findFirstMatch(Expression const& _expr); - - /// Checks whether the rulelist is non-empty. This is usually enforced - /// by the constructor, but we had some issues with static initialization. - bool isInitialized() const; -private: - void addRules(std::vector<SimplificationRule<Pattern>> const& _rules); - void addRule(SimplificationRule<Pattern> const& _rule); - - void resetMatchGroups() { m_matchGroups.clear(); } - - std::map<unsigned, Expression const*> m_matchGroups; - std::vector<SimplificationRule<Pattern>> m_rules[256]; -}; - -enum class PatternKind -{ - Operation, - Constant, - Any -}; - -/** - * Pattern to match against an expression. - * Also stores matched expressions to retrieve them later, for constructing new expressions using - * ExpressionTemplate. - */ -class Pattern -{ -public: - /// Matches any expression. - Pattern(PatternKind _kind = PatternKind::Any): m_kind(_kind) {} - // Matches a specific constant value. - Pattern(unsigned _value): Pattern(u256(_value)) {} - // Matches a specific constant value. - Pattern(u256 const& _value): m_kind(PatternKind::Constant), m_data(std::make_shared<u256>(_value)) {} - // Matches a given instruction with given arguments - Pattern(solidity::Instruction _instruction, std::vector<Pattern> const& _arguments = {}); - /// Sets this pattern to be part of the match group with the identifier @a _group. - /// Inside one rule, all patterns in the same match group have to match expressions from the - /// same expression equivalence class. - void setMatchGroup(unsigned _group, std::map<unsigned, Expression const*>& _matchGroups); - unsigned matchGroup() const { return m_matchGroup; } - bool matches(Expression const& _expr) const; - - std::vector<Pattern> arguments() const { return m_arguments; } - - /// @returns the data of the matched expression if this pattern is part of a match group. - u256 d() const; - - solidity::Instruction instruction() const; - - /// Turns this pattern into an actual expression. Should only be called - /// for patterns resulting from an action, i.e. with match groups assigned. - Expression toExpression(SourceLocation const& _location) const; - -private: - Expression const& matchGroupValue() const; - - PatternKind m_kind = PatternKind::Any; - solidity::Instruction m_instruction; ///< Only valid if m_kind is Operation - std::shared_ptr<u256> m_data; ///< Only valid if m_kind is Constant - std::vector<Pattern> m_arguments; - unsigned m_matchGroup = 0; - std::map<unsigned, Expression const*>* m_matchGroups = nullptr; -}; - -} -} diff --git a/libjulia/optimiser/Substitution.cpp b/libjulia/optimiser/Substitution.cpp deleted file mode 100644 index 668b6cb6..00000000 --- a/libjulia/optimiser/Substitution.cpp +++ /dev/null @@ -1,39 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Specific AST copier that replaces certain identifiers with expressions. - */ - -#include <libjulia/optimiser/Substitution.h> - -#include <libsolidity/inlineasm/AsmData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -Expression Substitution::translate(Expression const& _expression) -{ - if (_expression.type() == typeid(Identifier)) - { - string const& name = boost::get<Identifier>(_expression).name; - if (m_substitutions.count(name)) - // No recursive substitution - return ASTCopier().translate(*m_substitutions.at(name)); - } - return ASTCopier::translate(_expression); -} diff --git a/libjulia/optimiser/Substitution.h b/libjulia/optimiser/Substitution.h deleted file mode 100644 index 313a08d7..00000000 --- a/libjulia/optimiser/Substitution.h +++ /dev/null @@ -1,50 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Specific AST copier that replaces certain identifiers with expressions. - */ - -#pragma once - -#include <libjulia/optimiser/ASTCopier.h> - -#include <string> -#include <map> -#include <set> - -namespace dev -{ -namespace julia -{ - -/** - * Specific AST copier that replaces certain identifiers with expressions. - */ -class Substitution: public ASTCopier -{ -public: - Substitution(std::map<std::string, Expression const*> const& _substitutions): - m_substitutions(_substitutions) - {} - virtual Expression translate(Expression const& _expression) override; - -private: - std::map<std::string, Expression const*> const& m_substitutions; -}; - -} -} diff --git a/libjulia/optimiser/SyntacticalEquality.cpp b/libjulia/optimiser/SyntacticalEquality.cpp deleted file mode 100644 index c497336d..00000000 --- a/libjulia/optimiser/SyntacticalEquality.cpp +++ /dev/null @@ -1,76 +0,0 @@ -/*( - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Component that can compare ASTs for equality on a syntactic basis. - */ - -#include <libjulia/optimiser/SyntacticalEquality.h> - -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/CommonData.h> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -bool SyntacticalEqualityChecker::equal(Expression const& _e1, Expression const& _e2) -{ - if (_e1.type() != _e2.type()) - return false; - - // TODO This should be replaced by some kind of AST walker as soon as it gets - // more complex. - if (_e1.type() == typeid(FunctionalInstruction)) - { - auto const& e1 = boost::get<FunctionalInstruction>(_e1); - auto const& e2 = boost::get<FunctionalInstruction>(_e2); - return - e1.instruction == e2.instruction && - equalVector(e1.arguments, e2.arguments); - } - else if (_e1.type() == typeid(FunctionCall)) - { - auto const& e1 = boost::get<FunctionCall>(_e1); - auto const& e2 = boost::get<FunctionCall>(_e2); - return - equal(e1.functionName, e2.functionName) && - equalVector(e1.arguments, e2.arguments); - } - else if (_e1.type() == typeid(Identifier)) - return boost::get<Identifier>(_e1).name == boost::get<Identifier>(_e2).name; - else if (_e1.type() == typeid(Literal)) - { - auto const& e1 = boost::get<Literal>(_e1); - auto const& e2 = boost::get<Literal>(_e2); - return e1.kind == e2.kind && e1.value == e2.value && e1.type == e2.type; - } - else - { - assertThrow(false, OptimizerException, "Invalid expression"); - } - return false; -} - -bool SyntacticalEqualityChecker::equalVector(vector<Expression> const& _e1, vector<Expression> const& _e2) -{ - return _e1.size() == _e2.size() && - std::equal(begin(_e1), end(_e1), begin(_e2), SyntacticalEqualityChecker::equal); - -} diff --git a/libjulia/optimiser/SyntacticalEquality.h b/libjulia/optimiser/SyntacticalEquality.h deleted file mode 100644 index b7c09330..00000000 --- a/libjulia/optimiser/SyntacticalEquality.h +++ /dev/null @@ -1,50 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Component that can compare ASTs for equality on a syntactic basis. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> - -#include <vector> - -namespace dev -{ -namespace julia -{ - -/** - * Component that can compare ASTs for equality on a syntactic basis. - * Ignores source locations but requires exact matches otherwise. - * - * TODO: Only implemented for Expressions for now. - * A future version might also recognize renamed variables and thus could be used to - * remove duplicate functions. - */ -class SyntacticalEqualityChecker -{ -public: - static bool equal(Expression const& _e1, Expression const& _e2); - -protected: - static bool equalVector(std::vector<Expression> const& _e1, std::vector<Expression> const& _e2); -}; - -} -} diff --git a/libjulia/optimiser/UnusedPruner.cpp b/libjulia/optimiser/UnusedPruner.cpp deleted file mode 100644 index af503712..00000000 --- a/libjulia/optimiser/UnusedPruner.cpp +++ /dev/null @@ -1,117 +0,0 @@ -/*( - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimisation stage that removes unused variables and functions. - */ - -#include <libjulia/optimiser/UnusedPruner.h> - -#include <libjulia/optimiser/NameCollector.h> -#include <libjulia/optimiser/Semantics.h> -#include <libjulia/optimiser/Utilities.h> -#include <libjulia/Exceptions.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <boost/algorithm/cxx11/none_of.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -UnusedPruner::UnusedPruner(Block& _ast) -{ - ReferencesCounter counter; - counter(_ast); - - m_references = counter.references(); -} - -void UnusedPruner::operator()(Block& _block) -{ - for (auto&& statement: _block.statements) - if (statement.type() == typeid(FunctionDefinition)) - { - FunctionDefinition& funDef = boost::get<FunctionDefinition>(statement); - if (!used(funDef.name)) - { - subtractReferences(ReferencesCounter::countReferences(funDef.body)); - statement = Block{std::move(funDef.location), {}}; - } - } - else if (statement.type() == typeid(VariableDeclaration)) - { - VariableDeclaration& varDecl = boost::get<VariableDeclaration>(statement); - // Multi-variable declarations are special. We can only remove it - // if all vairables are unused and the right-hand-side is either - // movable or it return a single value. In the latter case, we - // replace `let a := f()` by `pop(f())` (in pure Yul, this will be - // `drop(f())`). - if (boost::algorithm::none_of( - varDecl.variables, - [=](TypedName const& _typedName) { return used(_typedName.name); } - )) - { - if (!varDecl.value) - statement = Block{std::move(varDecl.location), {}}; - else if (MovableChecker(*varDecl.value).movable()) - { - subtractReferences(ReferencesCounter::countReferences(*varDecl.value)); - statement = Block{std::move(varDecl.location), {}}; - } - else if (varDecl.variables.size() == 1) - // In pure Yul, this should be replaced by a function call to `drop` - // instead of `pop`. - statement = ExpressionStatement{varDecl.location, FunctionalInstruction{ - varDecl.location, - solidity::Instruction::POP, - {*std::move(varDecl.value)} - }}; - } - } - - removeEmptyBlocks(_block); - - ASTModifier::operator()(_block); -} - -void UnusedPruner::runUntilStabilised(Block& _ast) -{ - while (true) - { - UnusedPruner pruner(_ast); - pruner(_ast); - if (!pruner.shouldRunAgain()) - return; - } -} - -bool UnusedPruner::used(string const& _name) const -{ - return m_references.count(_name) && m_references.at(_name) > 0; -} - -void UnusedPruner::subtractReferences(map<string, size_t> const& _subtrahend) -{ - for (auto const& ref: _subtrahend) - { - assertThrow(m_references.count(ref.first), OptimizerException, ""); - assertThrow(m_references.at(ref.first) >= ref.second, OptimizerException, ""); - m_references[ref.first] -= ref.second; - m_shouldRunAgain = true; - } -} diff --git a/libjulia/optimiser/UnusedPruner.h b/libjulia/optimiser/UnusedPruner.h deleted file mode 100644 index 73e8de7c..00000000 --- a/libjulia/optimiser/UnusedPruner.h +++ /dev/null @@ -1,67 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Optimisation stage that removes unused variables and functions. - */ - -#pragma once - -#include <libjulia/optimiser/ASTWalker.h> - -#include <string> -#include <map> -#include <set> - -namespace dev -{ -namespace julia -{ - -/** - * Optimisation stage that removes unused variables and functions. - * - * TODO: Also remove intermediate variable assignments from movable expressions - * which are not referenced until after the next assignment to the same variable. - * - * Note that this does not remove circular references. - * - * Prerequisite: Disambiguator - */ -class UnusedPruner: public ASTModifier -{ -public: - explicit UnusedPruner(Block& _ast); - - using ASTModifier::operator(); - virtual void operator()(Block& _block) override; - - // @returns true iff the code changed in the previous run. - bool shouldRunAgain() const { return m_shouldRunAgain; } - - // Run the pruner until the code does not change anymore. - static void runUntilStabilised(Block& _ast); - -private: - bool used(std::string const& _name) const; - void subtractReferences(std::map<std::string, size_t> const& _subtrahend); - - bool m_shouldRunAgain = false; - std::map<std::string, size_t> m_references; -}; - -} -} diff --git a/libjulia/optimiser/Utilities.cpp b/libjulia/optimiser/Utilities.cpp deleted file mode 100644 index ff108b89..00000000 --- a/libjulia/optimiser/Utilities.cpp +++ /dev/null @@ -1,39 +0,0 @@ -/*( - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Some useful snippets for the optimiser. - */ - -#include <libjulia/optimiser/Utilities.h> - -#include <libsolidity/inlineasm/AsmData.h> - -#include <libdevcore/CommonData.h> - -#include <boost/range/algorithm_ext/erase.hpp> - -using namespace std; -using namespace dev; -using namespace dev::julia; - -void dev::julia::removeEmptyBlocks(Block& _block) -{ - auto isEmptyBlock = [](Statement const& _st) -> bool { - return _st.type() == typeid(Block) && boost::get<Block>(_st).statements.empty(); - }; - boost::range::remove_erase_if(_block.statements, isEmptyBlock); -} diff --git a/libjulia/optimiser/Utilities.h b/libjulia/optimiser/Utilities.h deleted file mode 100644 index 88ba3f47..00000000 --- a/libjulia/optimiser/Utilities.h +++ /dev/null @@ -1,34 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/>. -*/ -/** - * Small useful snippets for the optimiser. - */ - -#pragma once - -#include <libjulia/ASTDataForward.h> - -namespace dev -{ -namespace julia -{ - -/// Removes statements that are just empty blocks (non-recursive). -void removeEmptyBlocks(Block& _block); - -} -} |