From 9a4bec7e474a310c7f93ff3b84928e0e9ba9cce6 Mon Sep 17 00:00:00 2001 From: Christian Parpart Date: Mon, 15 Oct 2018 11:52:35 +0200 Subject: Renaming libjulia to libyul --- libyul/backends/evm/AbstractAssembly.h | 119 +++++++ libyul/backends/evm/EVMAssembly.cpp | 202 +++++++++++ libyul/backends/evm/EVMAssembly.h | 97 ++++++ libyul/backends/evm/EVMCodeTransform.cpp | 557 +++++++++++++++++++++++++++++++ libyul/backends/evm/EVMCodeTransform.h | 158 +++++++++ 5 files changed, 1133 insertions(+) create mode 100644 libyul/backends/evm/AbstractAssembly.h create mode 100644 libyul/backends/evm/EVMAssembly.cpp create mode 100644 libyul/backends/evm/EVMAssembly.h create mode 100644 libyul/backends/evm/EVMCodeTransform.cpp create mode 100644 libyul/backends/evm/EVMCodeTransform.h (limited to 'libyul/backends/evm') diff --git a/libyul/backends/evm/AbstractAssembly.h b/libyul/backends/evm/AbstractAssembly.h new file mode 100644 index 00000000..b6818923 --- /dev/null +++ b/libyul/backends/evm/AbstractAssembly.h @@ -0,0 +1,119 @@ +/* + 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 . +*/ +/** + * @date 2017 + * Abstract assembly interface, subclasses of which are to be used with the generic + * bytecode generator. + */ + +#pragma once + +#include + +#include + +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; + /// 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; + /// 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/libyul/backends/evm/EVMAssembly.cpp b/libyul/backends/evm/EVMAssembly.cpp new file mode 100644 index 00000000..af0ddbb8 --- /dev/null +++ b/libyul/backends/evm/EVMAssembly.cpp @@ -0,0 +1,202 @@ +/* + 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 . +*/ +/** + * Assembly interface for EVM and EVM1.5. + */ + +#include + +#include + +#include + +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/libyul/backends/evm/EVMAssembly.h b/libyul/backends/evm/EVMAssembly.h new file mode 100644 index 00000000..30abad97 --- /dev/null +++ b/libyul/backends/evm/EVMAssembly.h @@ -0,0 +1,97 @@ +/* + 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 . +*/ +/** + * Assembly interface for EVM and EVM1.5. + */ + +#pragma once + +#include + +#include + +#include + +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 m_namedLabels; + std::map m_labelPositions; + std::map m_labelReferences; + std::vector m_assemblySizePositions; +}; + +} +} diff --git a/libyul/backends/evm/EVMCodeTransform.cpp b/libyul/backends/evm/EVMCodeTransform.cpp new file mode 100644 index 00000000..afc9e608 --- /dev/null +++ b/libyul/backends/evm/EVMCodeTransform.cpp @@ -0,0 +1,557 @@ +/* + 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 . +*/ +/** + * Common code generator for translating Yul / inline assembly to EVM and EVM1.5. + */ + +#include + +#include +#include + +#include + +#include + +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(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(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(_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 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(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(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(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: + // ? + // But we would like it to be: + // ? + // 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 stackLayout; + if (!m_evm15) + stackLayout.push_back(_function.returnVariables.size()); // Move return label to the top + stackLayout += vector(_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 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 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(*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/libyul/backends/evm/EVMCodeTransform.h b/libyul/backends/evm/EVMCodeTransform.h new file mode 100644 index 00000000..6a0941b6 --- /dev/null +++ b/libyul/backends/evm/EVMCodeTransform.h @@ -0,0 +1,158 @@ +/* + 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 . +*/ +/** + * Common code generator for translating Yul / inline assembly to EVM and EVM1.5. + */ + +#include + +#include + +#include + +#include +#include + +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() + ) + { + } + +protected: + struct Context + { + using Scope = solidity::assembly::Scope; + std::map labelIDs; + std::map functionEntryIDs; + std::map variableStackHeights; + }; + + CodeTransform( + julia::AbstractAssembly& _assembly, + solidity::assembly::AsmAnalysisInfo& _analysisInfo, + bool _yul, + bool _evm15, + ExternalIdentifierAccess const& _identifierAccess, + bool _useNamedLabelsForFunctions, + int _stackAdjustment, + std::shared_ptr _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 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 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 m_context; +}; + +} +} -- cgit