diff options
Diffstat (limited to 'libyul')
48 files changed, 1371 insertions, 606 deletions
diff --git a/libyul/AsmAnalysis.cpp b/libyul/AsmAnalysis.cpp index d3f6de84..0ecc5a30 100644 --- a/libyul/AsmAnalysis.cpp +++ b/libyul/AsmAnalysis.cpp @@ -101,8 +101,8 @@ bool AsmAnalyzer::operator()(Literal const& _literal) } else if (_literal.kind == LiteralKind::Boolean) { - solAssert(m_flavour == AsmFlavour::Yul, ""); - solAssert(_literal.value == YulString{string("true")} || _literal.value == YulString{string("false")}, ""); + solAssert(m_dialect->flavour == AsmFlavour::Yul, ""); + solAssert(_literal.value == "true"_yulstring || _literal.value == "false"_yulstring, ""); } m_info.stackHeightInfo[&_literal] = m_stackHeight; return true; @@ -164,7 +164,7 @@ bool AsmAnalyzer::operator()(Identifier const& _identifier) bool AsmAnalyzer::operator()(FunctionalInstruction const& _instr) { - solAssert(m_flavour != AsmFlavour::Yul, ""); + solAssert(m_dialect->flavour != AsmFlavour::Yul, ""); bool success = true; for (auto const& arg: _instr.arguments | boost::adaptors::reversed) if (!expectExpression(arg)) @@ -182,9 +182,9 @@ bool AsmAnalyzer::operator()(ExpressionStatement const& _statement) { int initialStackHeight = m_stackHeight; bool success = boost::apply_visitor(*this, _statement.expression); - if (m_stackHeight != initialStackHeight && (m_flavour != AsmFlavour::Loose || m_errorTypeForLoose)) + if (m_stackHeight != initialStackHeight && (m_dialect->flavour != AsmFlavour::Loose || m_errorTypeForLoose)) { - Error::Type errorType = m_flavour == AsmFlavour::Loose ? *m_errorTypeForLoose : Error::Type::TypeError; + Error::Type errorType = m_dialect->flavour == AsmFlavour::Loose ? *m_errorTypeForLoose : Error::Type::TypeError; string msg = "Top-level expressions are not supposed to return values (this expression returns " + to_string(m_stackHeight - initialStackHeight) + @@ -244,9 +244,18 @@ bool AsmAnalyzer::operator()(VariableDeclaration const& _varDecl) { int const stackHeight = m_stackHeight; success = boost::apply_visitor(*this, *_varDecl.value); - if ((m_stackHeight - stackHeight) != numVariables) + int numValues = m_stackHeight - stackHeight; + if (numValues != numVariables) { - m_errorReporter.declarationError(_varDecl.location, "Variable count mismatch."); + m_errorReporter.declarationError(_varDecl.location, + "Variable count mismatch: " + + to_string(numVariables) + + " variables and " + + to_string(numValues) + + " values." + ); + // Adjust stack height to avoid misleading additional errors. + m_stackHeight += numVariables - numValues; return false; } } @@ -288,9 +297,15 @@ bool AsmAnalyzer::operator()(FunctionCall const& _funCall) { solAssert(!_funCall.functionName.name.empty(), ""); bool success = true; - size_t arguments = 0; + size_t parameters = 0; size_t returns = 0; - if (!m_currentScope->lookup(_funCall.functionName.name, Scope::Visitor( + if (BuiltinFunction const* f = m_dialect->builtin(_funCall.functionName.name)) + { + // TODO: compare types, too + parameters = f->parameters.size(); + returns = f->returns.size(); + } + else if (!m_currentScope->lookup(_funCall.functionName.name, Scope::Visitor( [&](Scope::Variable const&) { m_errorReporter.typeError( @@ -310,7 +325,7 @@ bool AsmAnalyzer::operator()(FunctionCall const& _funCall) [&](Scope::Function const& _fun) { /// TODO: compare types too - arguments = _fun.arguments.size(); + parameters = _fun.arguments.size(); returns = _fun.returns.size(); } ))) @@ -319,21 +334,23 @@ bool AsmAnalyzer::operator()(FunctionCall const& _funCall) success = false; } if (success) - { - if (_funCall.arguments.size() != arguments) + if (_funCall.arguments.size() != parameters) { m_errorReporter.typeError( _funCall.functionName.location, - "Expected " + to_string(arguments) + " arguments but got " + + "Function expects " + + to_string(parameters) + + " arguments but got " + to_string(_funCall.arguments.size()) + "." ); success = false; } - } + for (auto const& arg: _funCall.arguments | boost::adaptors::reversed) if (!expectExpression(arg)) success = false; - m_stackHeight += int(returns) - int(arguments); + // Use argument size instead of parameter count to avoid misleading errors. + m_stackHeight += int(returns) - int(_funCall.arguments.size()); m_info.stackHeightInfo[&_funCall] = m_stackHeight; return success; } @@ -552,7 +569,7 @@ Scope& AsmAnalyzer::scope(Block const* _block) } void AsmAnalyzer::expectValidType(string const& type, SourceLocation const& _location) { - if (m_flavour != AsmFlavour::Yul) + if (m_dialect->flavour != AsmFlavour::Yul) return; if (!builtinTypes.count(type)) @@ -612,7 +629,9 @@ void AsmAnalyzer::warnOnInstructions(solidity::Instruction _instr, SourceLocatio if (_instr == solidity::Instruction::JUMP || _instr == solidity::Instruction::JUMPI || _instr == solidity::Instruction::JUMPDEST) { - solAssert(m_flavour == AsmFlavour::Loose, ""); + if (m_dialect->flavour != AsmFlavour::Loose) + solAssert(m_errorTypeForLoose && *m_errorTypeForLoose != Error::Type::Warning, ""); + m_errorReporter.error( m_errorTypeForLoose ? *m_errorTypeForLoose : Error::Type::Warning, _location, @@ -625,7 +644,7 @@ void AsmAnalyzer::warnOnInstructions(solidity::Instruction _instr, SourceLocatio void AsmAnalyzer::checkLooseFeature(SourceLocation const& _location, string const& _description) { - if (m_flavour != AsmFlavour::Loose) + if (m_dialect->flavour != AsmFlavour::Loose) solAssert(false, _description); else if (m_errorTypeForLoose) m_errorReporter.error(*m_errorTypeForLoose, _location, _description); diff --git a/libyul/AsmAnalysis.h b/libyul/AsmAnalysis.h index 34e32eb0..21cc1142 100644 --- a/libyul/AsmAnalysis.h +++ b/libyul/AsmAnalysis.h @@ -23,12 +23,12 @@ #include <liblangutil/Exceptions.h> #include <liblangutil/EVMVersion.h> +#include <libyul/Dialect.h> #include <libyul/AsmScope.h> +#include <libyul/AsmDataForward.h> #include <libyul/backends/evm/AbstractAssembly.h> -#include <libyul/AsmDataForward.h> - #include <boost/variant.hpp> #include <boost/optional.hpp> @@ -59,14 +59,14 @@ public: langutil::ErrorReporter& _errorReporter, dev::solidity::EVMVersion _evmVersion, boost::optional<langutil::Error::Type> _errorTypeForLoose, - AsmFlavour _flavour = AsmFlavour::Loose, + std::shared_ptr<Dialect> _dialect, ExternalIdentifierAccess::Resolver const& _resolver = ExternalIdentifierAccess::Resolver() ): m_resolver(_resolver), m_info(_analysisInfo), m_errorReporter(_errorReporter), m_evmVersion(_evmVersion), - m_flavour(_flavour), + m_dialect(std::move(_dialect)), m_errorTypeForLoose(_errorTypeForLoose) {} @@ -115,7 +115,7 @@ private: AsmAnalysisInfo& m_info; langutil::ErrorReporter& m_errorReporter; dev::solidity::EVMVersion m_evmVersion; - AsmFlavour m_flavour = AsmFlavour::Loose; + std::shared_ptr<Dialect> m_dialect; boost::optional<langutil::Error::Type> m_errorTypeForLoose; }; diff --git a/libyul/AsmCodeGen.cpp b/libyul/AsmCodeGen.cpp deleted file mode 100644 index 23bf395d..00000000 --- a/libyul/AsmCodeGen.cpp +++ /dev/null @@ -1,163 +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/>. -*/ -/** - * @author Christian <c@ethdev.com> - * @date 2016 - * Code-generating part of inline assembly. - */ - -#include <libyul/AsmCodeGen.h> - -#include <libyul/AsmParser.h> -#include <libyul/AsmData.h> -#include <libyul/AsmScope.h> -#include <libyul/AsmAnalysis.h> -#include <libyul/AsmAnalysisInfo.h> - -#include <libyul/backends/evm/AbstractAssembly.h> -#include <libyul/backends/evm/EVMCodeTransform.h> - -#include <libevmasm/Assembly.h> -#include <libevmasm/Instruction.h> - -#include <liblangutil/SourceLocation.h> - -#include <libdevcore/CommonIO.h> - -#include <boost/range/adaptor/reversed.hpp> -#include <boost/range/adaptor/map.hpp> -#include <boost/range/algorithm/count_if.hpp> - -#include <memory> -#include <functional> - -using namespace std; -using namespace dev; -using namespace langutil; -using namespace yul; -using namespace dev::solidity; - -class EthAssemblyAdapter: public AbstractAssembly -{ -public: - explicit EthAssemblyAdapter(eth::Assembly& _assembly): - m_assembly(_assembly) - { - } - virtual void setSourceLocation(SourceLocation const& _location) override - { - m_assembly.setSourceLocation(_location); - } - virtual int stackHeight() const override { return m_assembly.deposit(); } - virtual void appendInstruction(solidity::Instruction _instruction) override - { - m_assembly.append(_instruction); - } - virtual void appendConstant(u256 const& _constant) override - { - m_assembly.append(_constant); - } - /// Append a label. - virtual void appendLabel(LabelID _labelId) override - { - m_assembly.append(eth::AssemblyItem(eth::Tag, _labelId)); - } - /// Append a label reference. - virtual void appendLabelReference(LabelID _labelId) override - { - m_assembly.append(eth::AssemblyItem(eth::PushTag, _labelId)); - } - virtual size_t newLabelId() override - { - return assemblyTagToIdentifier(m_assembly.newTag()); - } - virtual size_t namedLabel(std::string const& _name) override - { - return assemblyTagToIdentifier(m_assembly.namedTag(_name)); - } - virtual void appendLinkerSymbol(std::string const& _linkerSymbol) override - { - m_assembly.appendLibraryAddress(_linkerSymbol); - } - virtual void appendJump(int _stackDiffAfter) override - { - appendInstruction(solidity::Instruction::JUMP); - m_assembly.adjustDeposit(_stackDiffAfter); - } - virtual void appendJumpTo(LabelID _labelId, int _stackDiffAfter) override - { - appendLabelReference(_labelId); - appendJump(_stackDiffAfter); - } - virtual void appendJumpToIf(LabelID _labelId) override - { - appendLabelReference(_labelId); - appendInstruction(solidity::Instruction::JUMPI); - } - virtual void appendBeginsub(LabelID, int) override - { - // TODO we could emulate that, though - solAssert(false, "BEGINSUB not implemented for EVM 1.0"); - } - /// Call a subroutine. - virtual void appendJumpsub(LabelID, int, int) override - { - // TODO we could emulate that, though - solAssert(false, "JUMPSUB not implemented for EVM 1.0"); - } - - /// Return from a subroutine. - virtual void appendReturnsub(int, int) override - { - // TODO we could emulate that, though - solAssert(false, "RETURNSUB not implemented for EVM 1.0"); - } - - virtual void appendAssemblySize() override - { - m_assembly.appendProgramSize(); - } - -private: - static LabelID assemblyTagToIdentifier(eth::AssemblyItem const& _tag) - { - u256 id = _tag.data(); - solAssert(id <= std::numeric_limits<LabelID>::max(), "Tag id too large."); - return LabelID(id); - } - - eth::Assembly& m_assembly; -}; - -void CodeGenerator::assemble( - Block const& _parsedData, - AsmAnalysisInfo& _analysisInfo, - eth::Assembly& _assembly, - ExternalIdentifierAccess const& _identifierAccess, - bool _useNamedLabelsForFunctions -) -{ - EthAssemblyAdapter assemblyAdapter(_assembly); - CodeTransform( - assemblyAdapter, - _analysisInfo, - false, - false, - _identifierAccess, - _useNamedLabelsForFunctions - )(_parsedData); -} diff --git a/libyul/AsmDataForward.h b/libyul/AsmDataForward.h index 046c8248..de564425 100644 --- a/libyul/AsmDataForward.h +++ b/libyul/AsmDataForward.h @@ -49,11 +49,4 @@ struct TypedName; using Expression = boost::variant<FunctionalInstruction, FunctionCall, Identifier, Literal>; using Statement = boost::variant<ExpressionStatement, Instruction, Label, StackAssignment, Assignment, VariableDeclaration, FunctionDefinition, If, Switch, ForLoop, Block>; -enum class AsmFlavour -{ - Loose, // no types, EVM instructions as function, jumps and direct stack manipulations - Strict, // no types, EVM instructions as functions, but no jumps and no direct stack manipulations - Yul // same as Strict mode with types -}; - } diff --git a/libyul/AsmParser.cpp b/libyul/AsmParser.cpp index 2ce94f85..f3ca6cd0 100644 --- a/libyul/AsmParser.cpp +++ b/libyul/AsmParser.cpp @@ -107,14 +107,16 @@ Statement Parser::parseStatement() return parseForLoop(); case Token::Assign: { - if (m_flavour != AsmFlavour::Loose) + if (m_dialect->flavour != AsmFlavour::Loose) break; StackAssignment assignment = createWithLocation<StackAssignment>(); advance(); expectToken(Token::Colon); assignment.variableName.location = location(); assignment.variableName.name = YulString(currentLiteral()); - if (instructions().count(assignment.variableName.name.str())) + if (m_dialect->builtin(assignment.variableName.name)) + fatalParserError("Identifier expected, got builtin symbol."); + else if (instructions().count(assignment.variableName.name.str())) fatalParserError("Identifier expected, got instruction name."); assignment.location.end = endPosition(); expectToken(Token::Identifier); @@ -174,7 +176,9 @@ Statement Parser::parseStatement() if (currentToken() == Token::Assign && peekNextToken() != Token::Colon) { Assignment assignment = createWithLocation<Assignment>(identifier.location); - if (m_flavour != AsmFlavour::Yul && instructions().count(identifier.name.str())) + if (m_dialect->builtin(identifier.name)) + fatalParserError("Cannot assign to builtin function \"" + identifier.name.str() + "\"."); + else if (m_dialect->flavour != AsmFlavour::Yul && instructions().count(identifier.name.str())) fatalParserError("Cannot use instruction names for identifier names."); advance(); assignment.variableNames.emplace_back(identifier); @@ -185,7 +189,7 @@ Statement Parser::parseStatement() else { // label - if (m_flavour != AsmFlavour::Loose) + if (m_dialect->flavour != AsmFlavour::Loose) fatalParserError("Labels are not supported."); Label label = createWithLocation<Label>(identifier.location); label.name = identifier.name; @@ -193,7 +197,7 @@ Statement Parser::parseStatement() } } default: - if (m_flavour != AsmFlavour::Loose) + if (m_dialect->flavour != AsmFlavour::Loose) fatalParserError("Call or assignment expected."); break; } @@ -269,7 +273,7 @@ Expression Parser::parseExpression() instructionNames().at(instr.instruction) + "\" not allowed in this context." ); - if (m_flavour != AsmFlavour::Loose && currentToken() != Token::LParen) + if (m_dialect->flavour != AsmFlavour::Loose && currentToken() != Token::LParen) fatalParserError( "Non-functional instructions are not allowed in this context." ); @@ -289,7 +293,7 @@ Expression Parser::parseExpression() else if (operation.type() == typeid(Instruction)) { // Instructions not taking arguments are allowed as expressions. - solAssert(m_flavour == AsmFlavour::Loose, ""); + solAssert(m_dialect->flavour == AsmFlavour::Loose, ""); Instruction& instr = boost::get<Instruction>(operation); return FunctionalInstruction{std::move(instr.location), instr.instruction, {}}; } @@ -348,23 +352,25 @@ Parser::ElementaryOperation Parser::parseElementaryOperation() case Token::Byte: case Token::Address: { - string literal; + YulString literal; if (currentToken() == Token::Return) - literal = "return"; + literal = "return"_yulstring; else if (currentToken() == Token::Byte) - literal = "byte"; + literal = "byte"_yulstring; else if (currentToken() == Token::Address) - literal = "address"; + literal = "address"_yulstring; else - literal = currentLiteral(); - // first search the set of instructions. - if (m_flavour != AsmFlavour::Yul && instructions().count(literal)) + literal = YulString{currentLiteral()}; + // first search the set of builtins, then the instructions. + if (m_dialect->builtin(literal)) + ret = Identifier{location(), literal}; + else if (m_dialect->flavour != AsmFlavour::Yul && instructions().count(literal.str())) { - dev::solidity::Instruction const& instr = instructions().at(literal); + dev::solidity::Instruction const& instr = instructions().at(literal.str()); ret = Instruction{location(), instr}; } else - ret = Identifier{location(), YulString{literal}}; + ret = Identifier{location(), literal}; advance(); break; } @@ -399,11 +405,11 @@ Parser::ElementaryOperation Parser::parseElementaryOperation() {} }; advance(); - if (m_flavour == AsmFlavour::Yul) + if (m_dialect->flavour == AsmFlavour::Yul) { expectToken(Token::Colon); literal.location.end = endPosition(); - literal.type = YulString{expectAsmIdentifier()}; + literal.type = expectAsmIdentifier(); } else if (kind == LiteralKind::Boolean) fatalParserError("True and false are not valid literals."); @@ -412,7 +418,7 @@ Parser::ElementaryOperation Parser::parseElementaryOperation() } default: fatalParserError( - m_flavour == AsmFlavour::Yul ? + m_dialect->flavour == AsmFlavour::Yul ? "Literal or identifier expected." : "Literal, identifier or instruction expected." ); @@ -450,7 +456,7 @@ FunctionDefinition Parser::parseFunctionDefinition() RecursionGuard recursionGuard(*this); FunctionDefinition funDef = createWithLocation<FunctionDefinition>(); expectToken(Token::Function); - funDef.name = YulString{expectAsmIdentifier()}; + funDef.name = expectAsmIdentifier(); expectToken(Token::LParen); while (currentToken() != Token::RParen) { @@ -482,7 +488,7 @@ Expression Parser::parseCall(Parser::ElementaryOperation&& _initialOp) RecursionGuard recursionGuard(*this); if (_initialOp.type() == typeid(Instruction)) { - solAssert(m_flavour != AsmFlavour::Yul, "Instructions are invalid in Yul"); + solAssert(m_dialect->flavour != AsmFlavour::Yul, "Instructions are invalid in Yul"); Instruction& instruction = boost::get<Instruction>(_initialOp); FunctionalInstruction ret; ret.instruction = instruction.instruction; @@ -553,7 +559,7 @@ Expression Parser::parseCall(Parser::ElementaryOperation&& _initialOp) } else fatalParserError( - m_flavour == AsmFlavour::Yul ? + m_dialect->flavour == AsmFlavour::Yul ? "Function name expected." : "Assembly instruction or function name required in front of \"(\")" ); @@ -565,20 +571,20 @@ TypedName Parser::parseTypedName() { RecursionGuard recursionGuard(*this); TypedName typedName = createWithLocation<TypedName>(); - typedName.name = YulString{expectAsmIdentifier()}; - if (m_flavour == AsmFlavour::Yul) + typedName.name = expectAsmIdentifier(); + if (m_dialect->flavour == AsmFlavour::Yul) { expectToken(Token::Colon); typedName.location.end = endPosition(); - typedName.type = YulString{expectAsmIdentifier()}; + typedName.type = expectAsmIdentifier(); } return typedName; } -string Parser::expectAsmIdentifier() +YulString Parser::expectAsmIdentifier() { - string name = currentLiteral(); - if (m_flavour == AsmFlavour::Yul) + YulString name = YulString{currentLiteral()}; + if (m_dialect->flavour == AsmFlavour::Yul) { switch (currentToken()) { @@ -592,7 +598,9 @@ string Parser::expectAsmIdentifier() break; } } - else if (instructions().count(name)) + else if (m_dialect->builtin(name)) + fatalParserError("Cannot use builtin function name \"" + name.str() + "\" as identifier name."); + else if (instructions().count(name.str())) fatalParserError("Cannot use instruction names for identifier names."); expectToken(Token::Identifier); return name; diff --git a/libyul/AsmParser.h b/libyul/AsmParser.h index 52166a20..a02f0b4d 100644 --- a/libyul/AsmParser.h +++ b/libyul/AsmParser.h @@ -22,21 +22,24 @@ #pragma once -#include <memory> -#include <vector> #include <libyul/AsmData.h> +#include <libyul/Dialect.h> + #include <liblangutil/SourceLocation.h> #include <liblangutil/Scanner.h> #include <liblangutil/ParserBase.h> +#include <memory> +#include <vector> + namespace yul { class Parser: public langutil::ParserBase { public: - explicit Parser(langutil::ErrorReporter& _errorReporter, AsmFlavour _flavour = AsmFlavour::Loose): - ParserBase(_errorReporter), m_flavour(_flavour) {} + explicit Parser(langutil::ErrorReporter& _errorReporter, std::shared_ptr<Dialect> _dialect): + ParserBase(_errorReporter), m_dialect(std::move(_dialect)) {} /// Parses an inline assembly block starting with `{` and ending with `}`. /// @param _reuseScanner if true, do check for end of input after the `}`. @@ -78,12 +81,12 @@ protected: FunctionDefinition parseFunctionDefinition(); Expression parseCall(ElementaryOperation&& _initialOp); TypedName parseTypedName(); - std::string expectAsmIdentifier(); + YulString expectAsmIdentifier(); static bool isValidNumberLiteral(std::string const& _literal); private: - AsmFlavour m_flavour = AsmFlavour::Loose; + std::shared_ptr<Dialect> m_dialect; }; } diff --git a/libyul/AsmPrinter.cpp b/libyul/AsmPrinter.cpp index eaaba9f3..b7af4778 100644 --- a/libyul/AsmPrinter.cpp +++ b/libyul/AsmPrinter.cpp @@ -40,14 +40,14 @@ using namespace dev::solidity; //@TODO source locations -string AsmPrinter::operator()(yul::Instruction const& _instruction) +string AsmPrinter::operator()(yul::Instruction const& _instruction) const { solAssert(!m_yul, ""); solAssert(isValidInstruction(_instruction.instruction), "Invalid instruction"); return boost::to_lower_copy(instructionInfo(_instruction.instruction).name); } -string AsmPrinter::operator()(Literal const& _literal) +string AsmPrinter::operator()(Literal const& _literal) const { switch (_literal.kind) { @@ -55,8 +55,8 @@ string AsmPrinter::operator()(Literal const& _literal) solAssert(isValidDecimal(_literal.value.str()) || isValidHex(_literal.value.str()), "Invalid number literal"); return _literal.value.str() + appendTypeName(_literal.type); case LiteralKind::Boolean: - solAssert(_literal.value.str() == "true" || _literal.value.str() == "false", "Invalid bool literal."); - return ((_literal.value.str() == "true") ? "true" : "false") + appendTypeName(_literal.type); + solAssert(_literal.value == "true"_yulstring || _literal.value == "false"_yulstring, "Invalid bool literal."); + return ((_literal.value == "true"_yulstring) ? "true" : "false") + appendTypeName(_literal.type); case LiteralKind::String: break; } @@ -90,13 +90,13 @@ string AsmPrinter::operator()(Literal const& _literal) return "\"" + out + "\"" + appendTypeName(_literal.type); } -string AsmPrinter::operator()(Identifier const& _identifier) +string AsmPrinter::operator()(Identifier const& _identifier) const { solAssert(!_identifier.name.empty(), "Invalid identifier."); return _identifier.name.str(); } -string AsmPrinter::operator()(FunctionalInstruction const& _functionalInstruction) +string AsmPrinter::operator()(FunctionalInstruction const& _functionalInstruction) const { solAssert(!m_yul, ""); solAssert(isValidInstruction(_functionalInstruction.instruction), "Invalid instruction"); @@ -109,26 +109,26 @@ string AsmPrinter::operator()(FunctionalInstruction const& _functionalInstructio ")"; } -string AsmPrinter::operator()(ExpressionStatement const& _statement) +string AsmPrinter::operator()(ExpressionStatement const& _statement) const { return boost::apply_visitor(*this, _statement.expression); } -string AsmPrinter::operator()(Label const& _label) +string AsmPrinter::operator()(Label const& _label) const { solAssert(!m_yul, ""); solAssert(!_label.name.empty(), "Invalid label."); return _label.name.str() + ":"; } -string AsmPrinter::operator()(StackAssignment const& _assignment) +string AsmPrinter::operator()(StackAssignment const& _assignment) const { solAssert(!m_yul, ""); solAssert(!_assignment.variableName.name.empty(), "Invalid variable name."); return "=: " + (*this)(_assignment.variableName); } -string AsmPrinter::operator()(Assignment const& _assignment) +string AsmPrinter::operator()(Assignment const& _assignment) const { solAssert(_assignment.variableNames.size() >= 1, ""); string variables = (*this)(_assignment.variableNames.front()); @@ -137,7 +137,7 @@ string AsmPrinter::operator()(Assignment const& _assignment) return variables + " := " + boost::apply_visitor(*this, *_assignment.value); } -string AsmPrinter::operator()(VariableDeclaration const& _variableDeclaration) +string AsmPrinter::operator()(VariableDeclaration const& _variableDeclaration) const { string out = "let "; out += boost::algorithm::join( @@ -154,7 +154,7 @@ string AsmPrinter::operator()(VariableDeclaration const& _variableDeclaration) return out; } -string AsmPrinter::operator()(FunctionDefinition const& _functionDefinition) +string AsmPrinter::operator()(FunctionDefinition const& _functionDefinition) const { solAssert(!_functionDefinition.name.empty(), "Invalid function name."); string out = "function " + _functionDefinition.name.str() + "("; @@ -179,7 +179,7 @@ string AsmPrinter::operator()(FunctionDefinition const& _functionDefinition) return out + "\n" + (*this)(_functionDefinition.body); } -string AsmPrinter::operator()(FunctionCall const& _functionCall) +string AsmPrinter::operator()(FunctionCall const& _functionCall) const { return (*this)(_functionCall.functionName) + "(" + @@ -189,13 +189,13 @@ string AsmPrinter::operator()(FunctionCall const& _functionCall) ")"; } -string AsmPrinter::operator()(If const& _if) +string AsmPrinter::operator()(If const& _if) const { solAssert(_if.condition, "Invalid if condition."); return "if " + boost::apply_visitor(*this, *_if.condition) + "\n" + (*this)(_if.body); } -string AsmPrinter::operator()(Switch const& _switch) +string AsmPrinter::operator()(Switch const& _switch) const { solAssert(_switch.expression, "Invalid expression pointer."); string out = "switch " + boost::apply_visitor(*this, *_switch.expression); @@ -210,7 +210,7 @@ string AsmPrinter::operator()(Switch const& _switch) return out; } -string AsmPrinter::operator()(ForLoop const& _forLoop) +string AsmPrinter::operator()(ForLoop const& _forLoop) const { solAssert(_forLoop.condition, "Invalid for loop condition."); string out = "for "; @@ -224,7 +224,7 @@ string AsmPrinter::operator()(ForLoop const& _forLoop) return out; } -string AsmPrinter::operator()(Block const& _block) +string AsmPrinter::operator()(Block const& _block) const { if (_block.statements.empty()) return "{\n}"; diff --git a/libyul/AsmPrinter.h b/libyul/AsmPrinter.h index 61dfc18c..a1b9d6cd 100644 --- a/libyul/AsmPrinter.h +++ b/libyul/AsmPrinter.h @@ -36,21 +36,21 @@ class AsmPrinter: public boost::static_visitor<std::string> public: explicit AsmPrinter(bool _yul = false): m_yul(_yul) {} - std::string operator()(Instruction const& _instruction); - std::string operator()(Literal const& _literal); - std::string operator()(Identifier const& _identifier); - std::string operator()(FunctionalInstruction const& _functionalInstruction); - std::string operator()(ExpressionStatement const& _expr); - std::string operator()(Label const& _label); - std::string operator()(StackAssignment const& _assignment); - std::string operator()(Assignment const& _assignment); - std::string operator()(VariableDeclaration const& _variableDeclaration); - std::string operator()(FunctionDefinition const& _functionDefinition); - std::string operator()(FunctionCall const& _functionCall); - std::string operator()(If const& _if); - std::string operator()(Switch const& _switch); - std::string operator()(ForLoop const& _forLoop); - std::string operator()(Block const& _block); + std::string operator()(Instruction const& _instruction) const; + std::string operator()(Literal const& _literal) const; + std::string operator()(Identifier const& _identifier) const; + std::string operator()(FunctionalInstruction const& _functionalInstruction) const; + std::string operator()(ExpressionStatement const& _expr) const; + std::string operator()(Label const& _label) const; + std::string operator()(StackAssignment const& _assignment) const; + std::string operator()(Assignment const& _assignment) const; + std::string operator()(VariableDeclaration const& _variableDeclaration) const; + std::string operator()(FunctionDefinition const& _functionDefinition) const; + std::string operator()(FunctionCall const& _functionCall) const; + std::string operator()(If const& _if) const; + std::string operator()(Switch const& _switch) const; + std::string operator()(ForLoop const& _forLoop) const; + std::string operator()(Block const& _block) const; private: std::string formatTypedName(TypedName _variable) const; diff --git a/libyul/CMakeLists.txt b/libyul/CMakeLists.txt index 7ed84ff5..52c4ac8e 100644 --- a/libyul/CMakeLists.txt +++ b/libyul/CMakeLists.txt @@ -1,45 +1,98 @@ add_library(yul AsmAnalysis.cpp + AsmAnalysis.h AsmAnalysisInfo.cpp - AsmCodeGen.cpp + AsmAnalysisInfo.h + AsmData.h + AsmDataForward.h AsmParser.cpp + AsmParser.h AsmPrinter.cpp + AsmPrinter.h AsmScope.cpp + AsmScope.h AsmScopeFiller.cpp + AsmScopeFiller.h + Dialect.cpp + Dialect.h + Exceptions.h Object.cpp + Object.h ObjectParser.cpp + ObjectParser.h + YulString.h + backends/evm/AbstractAssembly.h backends/evm/EVMAssembly.cpp + backends/evm/EVMAssembly.h backends/evm/EVMCodeTransform.cpp + backends/evm/EVMCodeTransform.h + backends/evm/EVMDialect.cpp + backends/evm/EVMDialect.h + backends/evm/EVMObjectCompiler.cpp + backends/evm/EVMObjectCompiler.h optimiser/ASTCopier.cpp + optimiser/ASTCopier.h optimiser/ASTWalker.cpp + optimiser/ASTWalker.h optimiser/BlockFlattener.cpp + optimiser/BlockFlattener.h optimiser/CommonSubexpressionEliminator.cpp + optimiser/CommonSubexpressionEliminator.h optimiser/DataFlowAnalyzer.cpp + optimiser/DataFlowAnalyzer.h optimiser/Disambiguator.cpp + optimiser/Disambiguator.h optimiser/ExpressionInliner.cpp + optimiser/ExpressionInliner.h optimiser/ExpressionJoiner.cpp + optimiser/ExpressionJoiner.h optimiser/ExpressionSimplifier.cpp + optimiser/ExpressionSimplifier.h optimiser/ExpressionSplitter.cpp + optimiser/ExpressionSplitter.h optimiser/ForLoopInitRewriter.cpp + optimiser/ForLoopInitRewriter.h optimiser/FullInliner.cpp + optimiser/FullInliner.h optimiser/FunctionGrouper.cpp + optimiser/FunctionGrouper.h optimiser/FunctionHoister.cpp + optimiser/FunctionHoister.h optimiser/InlinableExpressionFunctionFinder.cpp + optimiser/InlinableExpressionFunctionFinder.h optimiser/MainFunction.cpp + optimiser/MainFunction.h optimiser/Metrics.cpp + optimiser/Metrics.h optimiser/NameCollector.cpp + optimiser/NameCollector.h optimiser/NameDispenser.cpp + optimiser/NameDispenser.h optimiser/RedundantAssignEliminator.cpp + optimiser/RedundantAssignEliminator.h optimiser/Rematerialiser.cpp + optimiser/Rematerialiser.h optimiser/SSATransform.cpp + optimiser/SSATransform.h optimiser/SSAValueTracker.cpp + optimiser/SSAValueTracker.h optimiser/Semantics.cpp + optimiser/Semantics.h optimiser/SimplificationRules.cpp + optimiser/SimplificationRules.h + optimiser/StructuralSimplifier.cpp + optimiser/StructuralSimplifier.h optimiser/Substitution.cpp + optimiser/Substitution.h optimiser/Suite.cpp + optimiser/Suite.h optimiser/SyntacticalEquality.cpp + optimiser/SyntacticalEquality.h optimiser/UnusedPruner.cpp + optimiser/UnusedPruner.h optimiser/Utilities.cpp - optimiser/VarDeclPropagator.cpp + optimiser/Utilities.h + optimiser/VarDeclInitializer.cpp + optimiser/VarDeclInitializer.h ) -target_link_libraries(yul PUBLIC devcore) +target_link_libraries(yul PUBLIC evmasm devcore langutil) diff --git a/libyul/Dialect.cpp b/libyul/Dialect.cpp new file mode 100644 index 00000000..f6985c17 --- /dev/null +++ b/libyul/Dialect.cpp @@ -0,0 +1,29 @@ +/* + 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/>. +*/ +/** + * Yul dialect. + */ + +#include <libyul/Dialect.h> + +#include <libyul/Object.h> +#include <libyul/backends/evm/AbstractAssembly.h> + +#include <map> + +using namespace yul; +using namespace std; diff --git a/libyul/Dialect.h b/libyul/Dialect.h new file mode 100644 index 00000000..01fd98df --- /dev/null +++ b/libyul/Dialect.h @@ -0,0 +1,66 @@ +/* + 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/>. +*/ +/** + * Yul dialect. + */ + +#pragma once + +#include <libyul/YulString.h> + +#include <boost/noncopyable.hpp> + +#include <vector> + +namespace yul +{ + +class YulString; +using Type = YulString; + +enum class AsmFlavour +{ + Loose, // no types, EVM instructions as function, jumps and direct stack manipulations + Strict, // no types, EVM instructions as functions, but no jumps and no direct stack manipulations + Yul // same as Strict mode with types +}; + +struct BuiltinFunction +{ + YulString name; + std::vector<Type> parameters; + std::vector<Type> returns; + bool movable; +}; + +struct Dialect: boost::noncopyable +{ + AsmFlavour const flavour = AsmFlavour::Loose; + /// @returns the builtin function of the given name or a nullptr if it is not a builtin function. + virtual BuiltinFunction const* builtin(YulString /*_name*/) const { return nullptr; } + + Dialect(AsmFlavour _flavour): flavour(_flavour) {} + virtual ~Dialect() = default; + + static std::shared_ptr<Dialect> yul() + { + // Will have to add builtins later. + return std::make_shared<Dialect>(AsmFlavour::Yul); + } +}; + +} diff --git a/libyul/Exceptions.h b/libyul/Exceptions.h index e10e53ef..d1f1fe96 100644 --- a/libyul/Exceptions.h +++ b/libyul/Exceptions.h @@ -28,6 +28,7 @@ namespace yul struct YulException: virtual dev::Exception {}; struct OptimizerException: virtual YulException {}; +struct CodegenException: virtual YulException {}; struct YulAssertion: virtual YulException {}; /// Assertion that throws an YulAssertion containing the given description if it is not met. diff --git a/libyul/Object.h b/libyul/Object.h index cfd8d02d..8484eb53 100644 --- a/libyul/Object.h +++ b/libyul/Object.h @@ -37,7 +37,7 @@ struct AsmAnalysisInfo; */ struct ObjectNode { - virtual ~ObjectNode() {} + virtual ~ObjectNode() = default; virtual std::string toString(bool _yul) const = 0; YulString name; diff --git a/libyul/ObjectParser.cpp b/libyul/ObjectParser.cpp index 43dd4be9..5f1eadef 100644 --- a/libyul/ObjectParser.cpp +++ b/libyul/ObjectParser.cpp @@ -42,7 +42,7 @@ shared_ptr<Object> ObjectParser::parse(shared_ptr<Scanner> const& _scanner, bool { // Special case: Code-only form. object = make_shared<Object>(); - object->name = YulString{"object"}; + object->name = "object"_yulstring; object->code = parseBlock(); if (!object->code) return nullptr; @@ -104,7 +104,7 @@ shared_ptr<Block> ObjectParser::parseCode() shared_ptr<Block> ObjectParser::parseBlock() { - Parser parser(m_errorReporter, m_flavour); + Parser parser(m_errorReporter, m_dialect); shared_ptr<Block> block = parser.parse(m_scanner, true); yulAssert(block || m_errorReporter.hasErrors(), "Invalid block but no error!"); return block; diff --git a/libyul/ObjectParser.h b/libyul/ObjectParser.h index 1d88a119..e39f24cd 100644 --- a/libyul/ObjectParser.h +++ b/libyul/ObjectParser.h @@ -22,6 +22,7 @@ #include <libyul/YulString.h> #include <libyul/Object.h> +#include <libyul/Dialect.h> #include <liblangutil/ErrorReporter.h> #include <liblangutil/ParserBase.h> @@ -46,9 +47,9 @@ class ObjectParser: public langutil::ParserBase public: explicit ObjectParser( langutil::ErrorReporter& _errorReporter, - yul::AsmFlavour _flavour = yul::AsmFlavour::Loose + std::shared_ptr<Dialect> _dialect ): - ParserBase(_errorReporter), m_flavour(_flavour) {} + ParserBase(_errorReporter), m_dialect(std::move(_dialect)) {} /// Parses a Yul object. /// Falls back to code-only parsing if the source starts with `{`. @@ -66,7 +67,7 @@ private: YulString parseUniqueName(Object const* _containingObject); void addNamedSubObject(Object& _container, YulString _name, std::shared_ptr<ObjectNode> _subObject); - yul::AsmFlavour m_flavour; + std::shared_ptr<Dialect> m_dialect; }; } diff --git a/libyul/YulString.h b/libyul/YulString.h index 2179c23b..5cea5619 100644 --- a/libyul/YulString.h +++ b/libyul/YulString.h @@ -42,10 +42,9 @@ public: size_t id; std::uint64_t hash; }; - YulStringRepository(): - m_strings{std::make_shared<std::string>()}, - m_hashToID{std::make_pair(emptyHash(), 0)} - {} + + YulStringRepository() = default; + static YulStringRepository& instance() { static YulStringRepository inst; @@ -80,9 +79,10 @@ public: return hash; } static constexpr std::uint64_t emptyHash() { return 14695981039346656037u; } + private: - std::vector<std::shared_ptr<std::string>> m_strings; - std::unordered_multimap<std::uint64_t, size_t> m_hashToID; + std::vector<std::shared_ptr<std::string>> m_strings = {std::make_shared<std::string>()}; + std::unordered_multimap<std::uint64_t, size_t> m_hashToID = {{emptyHash(), 0}}; }; /// Wrapper around handles into the YulString repository. @@ -127,4 +127,9 @@ private: YulStringRepository::Handle m_handle{ 0, YulStringRepository::emptyHash() }; }; +inline YulString operator "" _yulstring(const char *_string, std::size_t _size) +{ + return YulString(std::string(_string, _size)); +} + } diff --git a/libyul/backends/evm/AbstractAssembly.h b/libyul/backends/evm/AbstractAssembly.h index 97b1d305..0cc41056 100644 --- a/libyul/backends/evm/AbstractAssembly.h +++ b/libyul/backends/evm/AbstractAssembly.h @@ -26,6 +26,7 @@ #include <libdevcore/CommonData.h> #include <functional> +#include <memory> namespace langutil { @@ -52,8 +53,9 @@ class AbstractAssembly { public: using LabelID = size_t; + using SubID = size_t; - virtual ~AbstractAssembly() {} + virtual ~AbstractAssembly() = default; /// Set a new source location valid starting from the next instruction. virtual void setSourceLocation(langutil::SourceLocation const& _location) = 0; @@ -98,6 +100,14 @@ public: /// Append the assembled size as a constant. virtual void appendAssemblySize() = 0; + /// Creates a new sub-assembly, which can be referenced using dataSize and dataOffset. + virtual std::pair<std::shared_ptr<AbstractAssembly>, SubID> createSubAssembly() = 0; + /// Appends the offset of the given sub-assembly or data. + virtual void appendDataOffset(SubID _sub) = 0; + /// Appends the size of the given sub-assembly or data. + virtual void appendDataSize(SubID _sub) = 0; + /// Appends the given data to the assembly and returns its ID. + virtual SubID appendData(dev::bytes const& _data) = 0; }; enum class IdentifierContext { LValue, RValue }; diff --git a/libyul/backends/evm/EVMAssembly.cpp b/libyul/backends/evm/EVMAssembly.cpp index 99506317..2cf9f001 100644 --- a/libyul/backends/evm/EVMAssembly.cpp +++ b/libyul/backends/evm/EVMAssembly.cpp @@ -194,6 +194,27 @@ void EVMAssembly::appendAssemblySize() m_bytecode += bytes(assemblySizeReferenceSize); } +pair<shared_ptr<AbstractAssembly>, AbstractAssembly::SubID> EVMAssembly::createSubAssembly() +{ + solAssert(false, "Sub assemblies not implemented."); + return {}; +} + +void EVMAssembly::appendDataOffset(AbstractAssembly::SubID) +{ + solAssert(false, "Data not implemented."); +} + +void EVMAssembly::appendDataSize(AbstractAssembly::SubID) +{ + solAssert(false, "Data not implemented."); +} + +AbstractAssembly::SubID EVMAssembly::appendData(bytes const&) +{ + solAssert(false, "Data not implemented."); +} + void EVMAssembly::updateReference(size_t pos, size_t size, u256 value) { solAssert(m_bytecode.size() >= size && pos <= m_bytecode.size() - size, ""); diff --git a/libyul/backends/evm/EVMAssembly.h b/libyul/backends/evm/EVMAssembly.h index d0a437cc..e62bc87e 100644 --- a/libyul/backends/evm/EVMAssembly.h +++ b/libyul/backends/evm/EVMAssembly.h @@ -38,7 +38,7 @@ class EVMAssembly: public AbstractAssembly { public: explicit EVMAssembly(bool _evm15 = false): m_evm15(_evm15) { } - virtual ~EVMAssembly() {} + virtual ~EVMAssembly() = default; /// Set a new source location valid starting from the next instruction. void setSourceLocation(langutil::SourceLocation const& _location) override; @@ -77,6 +77,10 @@ public: /// Append the assembled size as a constant. void appendAssemblySize() override; + std::pair<std::shared_ptr<AbstractAssembly>, SubID> createSubAssembly() override; + void appendDataOffset(SubID _sub) override; + void appendDataSize(SubID _sub) override; + SubID appendData(dev::bytes const& _data) override; /// Resolves references inside the bytecode and returns the linker object. dev::eth::LinkerObject finalize(); diff --git a/libyul/backends/evm/EVMCodeTransform.cpp b/libyul/backends/evm/EVMCodeTransform.cpp index 12abd754..04dc5040 100644 --- a/libyul/backends/evm/EVMCodeTransform.cpp +++ b/libyul/backends/evm/EVMCodeTransform.cpp @@ -20,6 +20,7 @@ #include <libyul/backends/evm/EVMCodeTransform.h> +#include <libyul/optimiser/NameCollector.h> #include <libyul/AsmAnalysisInfo.h> #include <libyul/AsmData.h> @@ -32,6 +33,144 @@ using namespace dev; using namespace yul; using namespace dev::solidity; +void VariableReferenceCounter::operator()(Identifier const& _identifier) +{ + increaseRefIfFound(_identifier.name); +} + +void VariableReferenceCounter::operator()(FunctionDefinition const& _function) +{ + Scope* originalScope = m_scope; + + solAssert(m_info.virtualBlocks.at(&_function), ""); + m_scope = m_info.scopes.at(m_info.virtualBlocks.at(&_function).get()).get(); + solAssert(m_scope, "Variable scope does not exist."); + + for (auto const& v: _function.returnVariables) + increaseRefIfFound(v.name); + + VariableReferenceCounter{m_context, m_info}(_function.body); + + m_scope = originalScope; +} + +void VariableReferenceCounter::operator()(ForLoop const& _forLoop) +{ + Scope* originalScope = m_scope; + // Special scoping rules. + m_scope = m_info.scopes.at(&_forLoop.pre).get(); + + walkVector(_forLoop.pre.statements); + visit(*_forLoop.condition); + (*this)(_forLoop.body); + (*this)(_forLoop.post); + + m_scope = originalScope; +} + + +void VariableReferenceCounter::operator()(Block const& _block) +{ + Scope* originalScope = m_scope; + m_scope = m_info.scopes.at(&_block).get(); + + ASTWalker::operator()(_block); + + m_scope = originalScope; +} + +void VariableReferenceCounter::increaseRefIfFound(YulString _variableName) +{ + m_scope->lookup(_variableName, Scope::Visitor( + [=](Scope::Variable const& _var) + { + ++m_context.variableReferences[&_var]; + }, + [=](Scope::Label const&) { }, + [=](Scope::Function const&) { } + )); +} + + +CodeTransform::CodeTransform( + AbstractAssembly& _assembly, + AsmAnalysisInfo& _analysisInfo, + Block const& _block, + bool _allowStackOpt, + EVMDialect const& _dialect, + bool _evm15, + ExternalIdentifierAccess const& _identifierAccess, + bool _useNamedLabelsForFunctions, + int _stackAdjustment, + shared_ptr<Context> _context +): + m_assembly(_assembly), + m_info(_analysisInfo), + m_dialect(_dialect), + m_allowStackOpt(_allowStackOpt), + m_evm15(_evm15), + m_useNamedLabelsForFunctions(_useNamedLabelsForFunctions), + m_identifierAccess(_identifierAccess), + m_stackAdjustment(_stackAdjustment), + m_context(_context) +{ + if (!m_context) + { + // initialize + m_context = make_shared<Context>(); + if (m_allowStackOpt) + VariableReferenceCounter{*m_context, m_info}(_block); + } +} + +void CodeTransform::decreaseReference(YulString, Scope::Variable const& _var) +{ + if (!m_allowStackOpt) + return; + + unsigned& ref = m_context->variableReferences.at(&_var); + solAssert(ref >= 1, ""); + --ref; + if (ref == 0) + m_variablesScheduledForDeletion.insert(&_var); +} + +bool CodeTransform::unreferenced(Scope::Variable const& _var) const +{ + return !m_context->variableReferences.count(&_var) || m_context->variableReferences[&_var] == 0; +} + +void CodeTransform::freeUnusedVariables() +{ + if (!m_allowStackOpt) + return; + + for (auto const& identifier: m_scope->identifiers) + if (identifier.second.type() == typeid(Scope::Variable)) + { + Scope::Variable const& var = boost::get<Scope::Variable>(identifier.second); + if (m_variablesScheduledForDeletion.count(&var)) + deleteVariable(var); + } + + while (m_unusedStackSlots.count(m_assembly.stackHeight() - 1)) + { + solAssert(m_unusedStackSlots.erase(m_assembly.stackHeight() - 1), ""); + m_assembly.appendInstruction(solidity::Instruction::POP); + --m_stackAdjustment; + } +} + +void CodeTransform::deleteVariable(Scope::Variable const& _var) +{ + solAssert(m_allowStackOpt, ""); + solAssert(m_context->variableStackHeights.count(&_var) > 0, ""); + m_unusedStackSlots.insert(m_context->variableStackHeights[&_var]); + m_context->variableStackHeights.erase(&_var); + m_context->variableReferences.erase(&_var); + m_variablesScheduledForDeletion.erase(&_var); +} + void CodeTransform::operator()(VariableDeclaration const& _varDecl) { solAssert(m_scope, ""); @@ -49,10 +188,40 @@ void CodeTransform::operator()(VariableDeclaration const& _varDecl) while (variablesLeft--) m_assembly.appendConstant(u256(0)); } - for (auto const& variable: _varDecl.variables) + + bool atTopOfStack = true; + for (int varIndex = numVariables - 1; varIndex >= 0; --varIndex) { - auto& var = boost::get<Scope::Variable>(m_scope->identifiers.at(variable.name)); - m_context->variableStackHeights[&var] = height++; + auto& var = boost::get<Scope::Variable>(m_scope->identifiers.at(_varDecl.variables[varIndex].name)); + m_context->variableStackHeights[&var] = height + varIndex; + if (!m_allowStackOpt) + continue; + + if (unreferenced(var)) + { + if (atTopOfStack) + { + m_context->variableStackHeights.erase(&var); + m_assembly.setSourceLocation(_varDecl.location); + m_assembly.appendInstruction(solidity::Instruction::POP); + --m_stackAdjustment; + } + else + m_variablesScheduledForDeletion.insert(&var); + } + else if (m_unusedStackSlots.empty()) + atTopOfStack = false; + else + { + int slot = *m_unusedStackSlots.begin(); + m_unusedStackSlots.erase(m_unusedStackSlots.begin()); + m_context->variableStackHeights[&var] = slot; + m_assembly.setSourceLocation(_varDecl.location); + if (int heightDiff = variableHeightDiff(var, true)) + m_assembly.appendInstruction(solidity::swapInstruction(heightDiff - 1)); + m_assembly.appendInstruction(solidity::Instruction::POP); + --m_stackAdjustment; + } } checkStackHeight(&_varDecl); } @@ -70,6 +239,7 @@ void CodeTransform::operator()(Assignment const& _assignment) void CodeTransform::operator()(StackAssignment const& _assignment) { + solAssert(!m_allowStackOpt, ""); m_assembly.setSourceLocation(_assignment.location); generateAssignment(_assignment.variableName); checkStackHeight(&_assignment); @@ -84,6 +254,7 @@ void CodeTransform::operator()(ExpressionStatement const& _statement) void CodeTransform::operator()(Label const& _label) { + solAssert(!m_allowStackOpt, ""); m_assembly.setSourceLocation(_label.location); solAssert(m_scope, ""); solAssert(m_scope->identifiers.count(_label.name), ""); @@ -96,35 +267,46 @@ 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) + if (BuiltinFunctionForEVM const* builtin = m_dialect.builtin(_call.functionName.name)) { - returnLabel = m_assembly.newLabelId(); - m_assembly.appendLabelReference(returnLabel); - m_stackAdjustment++; + builtin->generateCode(_call, m_assembly, [&]() { + for (auto const& arg: _call.arguments | boost::adaptors::reversed) + visitExpression(arg); + m_assembly.setSourceLocation(_call.location); + }); } - - 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--; + 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); } - checkStackHeight(&_call); } void CodeTransform::operator()(FunctionalInstruction const& _instruction) @@ -169,11 +351,14 @@ void CodeTransform::operator()(Identifier const& _identifier) if (m_scope->lookup(_identifier.name, Scope::NonconstVisitor( [=](Scope::Variable& _var) { + // TODO: opportunity for optimization: Do not DUP if this is the last reference + // to the top most element of the stack if (int heightDiff = variableHeightDiff(_var, false)) m_assembly.appendInstruction(solidity::dupInstruction(heightDiff)); else // Store something to balance the stack m_assembly.appendConstant(u256(0)); + decreaseReference(_identifier.name, _var); }, [=](Scope::Label& _label) { @@ -202,7 +387,7 @@ void CodeTransform::operator()(Literal const& _literal) m_assembly.appendConstant(u256(_literal.value.str())); else if (_literal.kind == LiteralKind::Boolean) { - if (_literal.value.str() == "true") + if (_literal.value == "true"_yulstring) m_assembly.appendConstant(u256(1)); else m_assembly.appendConstant(u256(0)); @@ -217,6 +402,7 @@ void CodeTransform::operator()(Literal const& _literal) void CodeTransform::operator()(yul::Instruction const& _instruction) { + solAssert(!m_allowStackOpt, ""); 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); @@ -329,7 +515,9 @@ void CodeTransform::operator()(FunctionDefinition const& _function) CodeTransform( m_assembly, m_info, - m_yul, + _function.body, + m_allowStackOpt, + m_dialect, m_evm15, m_identifierAccess, m_useNamedLabelsForFunctions, @@ -350,6 +538,7 @@ void CodeTransform::operator()(FunctionDefinition const& _function) 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. @@ -475,20 +664,37 @@ void CodeTransform::visitExpression(Expression const& _expression) void CodeTransform::visitStatements(vector<Statement> const& _statements) { for (auto const& statement: _statements) + { + freeUnusedVariables(); boost::apply_visitor(*this, statement); + } + freeUnusedVariables(); } void CodeTransform::finalizeBlock(Block const& _block, int blockStartStackHeight) { m_assembly.setSourceLocation(_block.location); + freeUnusedVariables(); + // 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); + for (auto const& id: m_scope->identifiers) + if (id.second.type() == typeid(Scope::Variable)) + { + Scope::Variable const& var = boost::get<Scope::Variable>(id.second); + if (m_allowStackOpt) + { + solAssert(!m_context->variableStackHeights.count(&var), ""); + solAssert(!m_context->variableReferences.count(&var), ""); + m_stackAdjustment++; + } + else + m_assembly.appendInstruction(solidity::Instruction::POP); + } int deposit = m_assembly.stackHeight() - blockStartStackHeight; - solAssert(deposit == 0, "Invalid stack height at end of block."); + solAssert(deposit == 0, "Invalid stack height at end of block: " + to_string(deposit)); checkStackHeight(&_block); } @@ -502,13 +708,13 @@ void CodeTransform::generateMultiAssignment(vector<Identifier> const& _variableN void CodeTransform::generateAssignment(Identifier const& _variableName) { solAssert(m_scope, ""); - auto var = m_scope->lookup(_variableName.name); - if (var) + if (auto var = m_scope->lookup(_variableName.name)) { 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); + decreaseReference(_variableName.name, _var); } else { diff --git a/libyul/backends/evm/EVMCodeTransform.h b/libyul/backends/evm/EVMCodeTransform.h index d559f85a..7be6f892 100644 --- a/libyul/backends/evm/EVMCodeTransform.h +++ b/libyul/backends/evm/EVMCodeTransform.h @@ -18,10 +18,13 @@ * Common code generator for translating Yul / inline assembly to EVM and EVM1.5. */ +#pragma once + #include <libyul/backends/evm/EVMAssembly.h> +#include <libyul/backends/evm/EVMDialect.h> +#include <libyul/optimiser/ASTWalker.h> #include <libyul/AsmDataForward.h> - #include <libyul/AsmScope.h> #include <boost/variant.hpp> @@ -37,6 +40,46 @@ namespace yul struct AsmAnalysisInfo; class EVMAssembly; +struct CodeTransformContext +{ + std::map<Scope::Label const*, AbstractAssembly::LabelID> labelIDs; + std::map<Scope::Function const*, AbstractAssembly::LabelID> functionEntryIDs; + std::map<Scope::Variable const*, int> variableStackHeights; + std::map<Scope::Variable const*, unsigned> variableReferences; +}; + +/** + * Counts the number of references to a variable. This includes actual (read) references + * but also assignments to the variable. It does not include the declaration itself or + * function parameters, but it does include function return parameters. + * + * This component can handle multiple variables of the same name. + * + * Can only be applied to strict assembly. + */ +class VariableReferenceCounter: public yul::ASTWalker +{ +public: + explicit VariableReferenceCounter( + CodeTransformContext& _context, + AsmAnalysisInfo const& _assemblyInfo + ): m_context(_context), m_info(_assemblyInfo) + {} + +public: + void operator()(Identifier const& _identifier); + void operator()(FunctionDefinition const&); + void operator()(ForLoop const&); + void operator()(Block const& _block); + +private: + void increaseRefIfFound(YulString _variableName); + + CodeTransformContext& m_context; + AsmAnalysisInfo const& m_info; + Scope* m_scope = nullptr; +}; + class CodeTransform: public boost::static_visitor<> { public: @@ -45,50 +88,51 @@ public: CodeTransform( AbstractAssembly& _assembly, AsmAnalysisInfo& _analysisInfo, - bool _yul = false, + Block const& _block, + EVMDialect const& _dialect, + bool _allowStackOpt = false, bool _evm15 = false, ExternalIdentifierAccess const& _identifierAccess = ExternalIdentifierAccess(), bool _useNamedLabelsForFunctions = false ): CodeTransform( _assembly, _analysisInfo, - _yul, + _block, + _allowStackOpt, + _dialect, _evm15, _identifierAccess, _useNamedLabelsForFunctions, _assembly.stackHeight(), - std::make_shared<Context>() + nullptr ) { } protected: - struct Context - { - std::map<Scope::Label const*, AbstractAssembly::LabelID> labelIDs; - std::map<Scope::Function const*, AbstractAssembly::LabelID> functionEntryIDs; - std::map<Scope::Variable const*, int> variableStackHeights; - }; + using Context = CodeTransformContext; CodeTransform( AbstractAssembly& _assembly, AsmAnalysisInfo& _analysisInfo, - bool _yul, + Block const& _block, + bool _allowStackOpt, + EVMDialect const& _dialect, 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) - {} + ); + + void decreaseReference(YulString _name, Scope::Variable const& _var); + bool unreferenced(Scope::Variable const& _var) const; + /// Marks slots of variables that are not used anymore + /// and were defined in the current scope for reuse. + /// Also POPs unused topmost stack slots. + void freeUnusedVariables(); + /// Marks the stack slot of @a _var to be reused. + void deleteVariable(Scope::Variable const& _var); public: void operator()(Instruction const& _instruction); @@ -137,9 +181,10 @@ private: AbstractAssembly& m_assembly; AsmAnalysisInfo& m_info; Scope* m_scope = nullptr; - bool m_yul = false; - bool m_evm15 = false; - bool m_useNamedLabelsForFunctions = false; + EVMDialect const& m_dialect; + bool const m_allowStackOpt = true; + bool const m_evm15 = false; + bool const 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 @@ -147,6 +192,12 @@ private: /// (EVM 1.0 or 1.5). int m_stackAdjustment = 0; std::shared_ptr<Context> m_context; + + /// Set of variables whose reference counter has reached zero, + /// and whose stack slot will be marked as unused once we reach + /// statement level in the scope where the variable was defined. + std::set<Scope::Variable const*> m_variablesScheduledForDeletion; + std::set<int> m_unusedStackSlots; }; } diff --git a/libyul/backends/evm/EVMDialect.cpp b/libyul/backends/evm/EVMDialect.cpp new file mode 100644 index 00000000..935f05c6 --- /dev/null +++ b/libyul/backends/evm/EVMDialect.cpp @@ -0,0 +1,141 @@ +/* + 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/>. +*/ +/** + * Yul dialects for EVM. + */ + +#include <libyul/backends/evm/EVMDialect.h> + +#include <libyul/AsmAnalysisInfo.h> +#include <libyul/AsmData.h> +#include <libyul/Object.h> +#include <libyul/backends/evm/AbstractAssembly.h> + +#include <liblangutil/Exceptions.h> + +#include <libyul/Exceptions.h> + +#include <boost/range/adaptor/reversed.hpp> + +using namespace std; +using namespace dev; +using namespace yul; +using namespace dev::solidity; + + +EVMDialect::EVMDialect(AsmFlavour _flavour, bool _objectAccess): + Dialect{_flavour}, m_objectAccess(_objectAccess) +{ + // The EVM instructions will be moved to builtins at some point. + if (!m_objectAccess) + return; + + addFunction("datasize", 1, 1, true, [this]( + FunctionCall const& _call, + AbstractAssembly& _assembly, + std::function<void()> + ) { + yulAssert(m_currentObject, "No object available."); + yulAssert(_call.arguments.size() == 1, ""); + Expression const& arg = _call.arguments.front(); + YulString dataName = boost::get<Literal>(arg).value; + if (m_currentObject->name == dataName) + _assembly.appendAssemblySize(); + else + _assembly.appendDataSize(m_subIDs.at(dataName)); + }); + addFunction("dataoffset", 1, 1, true, [this]( + FunctionCall const& _call, + AbstractAssembly& _assembly, + std::function<void()> + ) { + yulAssert(m_currentObject, "No object available."); + yulAssert(_call.arguments.size() == 1, ""); + Expression const& arg = _call.arguments.front(); + YulString dataName = boost::get<Literal>(arg).value; + if (m_currentObject->name == dataName) + _assembly.appendConstant(0); + else + _assembly.appendDataOffset(m_subIDs.at(dataName)); + }); + addFunction("datacopy", 3, 0, false, []( + FunctionCall const&, + AbstractAssembly& _assembly, + std::function<void()> _visitArguments + ) { + _visitArguments(); + _assembly.appendInstruction(solidity::Instruction::CODECOPY); + }); +} + +BuiltinFunctionForEVM const* EVMDialect::builtin(YulString _name) const +{ + auto it = m_functions.find(_name); + if (it != m_functions.end()) + return &it->second; + else + return nullptr; +} + +shared_ptr<EVMDialect> EVMDialect::looseAssemblyForEVM() +{ + return make_shared<EVMDialect>(AsmFlavour::Loose, false); +} + +shared_ptr<EVMDialect> EVMDialect::strictAssemblyForEVM() +{ + return make_shared<EVMDialect>(AsmFlavour::Strict, false); +} + +shared_ptr<EVMDialect> EVMDialect::strictAssemblyForEVMObjects() +{ + return make_shared<EVMDialect>(AsmFlavour::Strict, true); +} + +shared_ptr<yul::EVMDialect> EVMDialect::yulForEVM() +{ + return make_shared<EVMDialect>(AsmFlavour::Yul, false); +} + +void EVMDialect::setSubIDs(map<YulString, AbstractAssembly::SubID> _subIDs) +{ + yulAssert(m_objectAccess, "Sub IDs set with dialect that does not support object access."); + m_subIDs = std::move(_subIDs); +} + +void EVMDialect::setCurrentObject(Object const* _object) +{ + yulAssert(m_objectAccess, "Current object set with dialect that does not support object access."); + m_currentObject = _object; +} + +void EVMDialect::addFunction( + string _name, + size_t _params, + size_t _returns, + bool _movable, + std::function<void(FunctionCall const&, AbstractAssembly&, std::function<void()>)> _generateCode +) +{ + YulString name{std::move(_name)}; + BuiltinFunctionForEVM& f = m_functions[name]; + f.name = name; + f.parameters.resize(_params); + f.returns.resize(_returns); + f.movable = _movable; + f.generateCode = std::move(_generateCode); +} diff --git a/libyul/backends/evm/EVMDialect.h b/libyul/backends/evm/EVMDialect.h new file mode 100644 index 00000000..feb00b03 --- /dev/null +++ b/libyul/backends/evm/EVMDialect.h @@ -0,0 +1,85 @@ +/* + 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/>. +*/ +/** + * Yul dialects for EVM. + */ + +#pragma once + +#include <libyul/Dialect.h> + +#include <libyul/backends/evm/AbstractAssembly.h> + +#include <map> + +namespace yul +{ + +class YulString; +using Type = YulString; +struct FunctionCall; +struct Object; + +struct BuiltinFunctionForEVM: BuiltinFunction +{ + /// Function to generate code for the given function call and append it to the abstract + /// assembly. The third parameter is called to visit (and generate code for) the arguments + /// from right to left. + std::function<void(FunctionCall const&, AbstractAssembly&, std::function<void()>)> generateCode; +}; + +/** + * Yul dialect for EVM as a backend. + * The main difference is that the builtin functions take an AbstractAssembly for the + * code generation. + */ +struct EVMDialect: public Dialect +{ + EVMDialect(AsmFlavour _flavour, bool _objectAccess); + + /// @returns the builtin function of the given name or a nullptr if it is not a builtin function. + BuiltinFunctionForEVM const* builtin(YulString _name) const override; + + static std::shared_ptr<EVMDialect> looseAssemblyForEVM(); + static std::shared_ptr<EVMDialect> strictAssemblyForEVM(); + static std::shared_ptr<EVMDialect> strictAssemblyForEVMObjects(); + static std::shared_ptr<EVMDialect> yulForEVM(); + + bool providesObjectAccess() const { return m_objectAccess; } + + /// Sets the mapping of current sub assembly IDs. Used during code generation. + void setSubIDs(std::map<YulString, AbstractAssembly::SubID> _subIDs); + /// Sets the current object. Used during code generation. + void setCurrentObject(Object const* _object); + +private: + void addFunction( + std::string _name, + size_t _params, + size_t _returns, + bool _movable, + std::function<void(FunctionCall const&, AbstractAssembly&, std::function<void()>)> _generateCode + ); + + bool m_objectAccess; + Object const* m_currentObject = nullptr; + /// Mapping from named objects to abstract assembly sub IDs. + std::map<YulString, AbstractAssembly::SubID> m_subIDs; + std::map<YulString, BuiltinFunctionForEVM> m_functions; +}; + +} diff --git a/libyul/backends/evm/EVMObjectCompiler.cpp b/libyul/backends/evm/EVMObjectCompiler.cpp new file mode 100644 index 00000000..3f7634b2 --- /dev/null +++ b/libyul/backends/evm/EVMObjectCompiler.cpp @@ -0,0 +1,64 @@ +/* + 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/>. +*/ +/** + * Compiler that transforms Yul Objects to EVM bytecode objects. + */ + +#include <libyul/backends/evm/EVMObjectCompiler.h> + +#include <libyul/backends/evm/EVMCodeTransform.h> +#include <libyul/backends/evm/EVMDialect.h> + +#include <libyul/Object.h> +#include <libyul/Exceptions.h> + +using namespace yul; +using namespace std; + +void EVMObjectCompiler::compile(Object& _object, AbstractAssembly& _assembly, EVMDialect& _dialect, bool _evm15, bool _optimize) +{ + EVMObjectCompiler compiler(_assembly, _dialect, _evm15); + compiler.run(_object, _optimize); +} + +void EVMObjectCompiler::run(Object& _object, bool _optimize) +{ + map<YulString, AbstractAssembly::SubID> subIDs; + + for (auto& subNode: _object.subObjects) + if (Object* subObject = dynamic_cast<Object*>(subNode.get())) + { + auto subAssemblyAndID = m_assembly.createSubAssembly(); + subIDs[subObject->name] = subAssemblyAndID.second; + compile(*subObject, *subAssemblyAndID.first, m_dialect, m_evm15, _optimize); + } + else + { + Data const& data = dynamic_cast<Data const&>(*subNode); + subIDs[data.name] = m_assembly.appendData(data.data); + } + + if (m_dialect.providesObjectAccess()) + { + m_dialect.setSubIDs(std::move(subIDs)); + m_dialect.setCurrentObject(&_object); + } + + yulAssert(_object.analysisInfo, "No analysis info."); + yulAssert(_object.code, "No code."); + CodeTransform{m_assembly, *_object.analysisInfo, *_object.code, m_dialect, _optimize, m_evm15}(*_object.code); +} diff --git a/libyul/AsmCodeGen.h b/libyul/backends/evm/EVMObjectCompiler.h index fd5ac0a1..9325e072 100644 --- a/libyul/AsmCodeGen.h +++ b/libyul/backends/evm/EVMObjectCompiler.h @@ -15,40 +15,31 @@ along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** - * @author Christian <c@ethdev.com> - * @date 2016 - * Code-generating part of inline assembly. + * Compiler that transforms Yul Objects to EVM bytecode objects. */ #pragma once -#include <libyul/AsmAnalysis.h> - -#include <functional> - -namespace dev -{ -namespace eth -{ -class Assembly; -} -} - namespace yul { -struct Block; +struct Object; +class AbstractAssembly; +struct EVMDialect; -class CodeGenerator +class EVMObjectCompiler { public: - /// Performs code generation and appends generated to _assembly. - static void assemble( - Block const& _parsedData, - AsmAnalysisInfo& _analysisInfo, - dev::eth::Assembly& _assembly, - yul::ExternalIdentifierAccess const& _identifierAccess = yul::ExternalIdentifierAccess(), - bool _useNamedLabelsForFunctions = false - ); + static void compile(Object& _object, AbstractAssembly& _assembly, EVMDialect& _dialect, bool _evm15, bool _optimize); +private: + EVMObjectCompiler(AbstractAssembly& _assembly, EVMDialect& _dialect, bool _evm15): + m_assembly(_assembly), m_dialect(_dialect), m_evm15(_evm15) + {} + + void run(Object& _object, bool _optimize); + + AbstractAssembly& m_assembly; + EVMDialect& m_dialect; + bool m_evm15 = false; }; } diff --git a/libyul/optimiser/ASTWalker.cpp b/libyul/optimiser/ASTWalker.cpp index 0d568007..6adcb2e1 100644 --- a/libyul/optimiser/ASTWalker.cpp +++ b/libyul/optimiser/ASTWalker.cpp @@ -93,6 +93,16 @@ void ASTWalker::operator()(Block const& _block) walkVector(_block.statements); } +void ASTWalker::visit(Statement const& _st) +{ + boost::apply_visitor(*this, _st); +} + +void ASTWalker::visit(Expression const& _e) +{ + boost::apply_visitor(*this, _e); +} + void ASTModifier::operator()(FunctionalInstruction& _instr) { walkVector(_instr.arguments | boost::adaptors::reversed); @@ -155,3 +165,13 @@ void ASTModifier::operator()(Block& _block) { walkVector(_block.statements); } + +void ASTModifier::visit(Statement& _st) +{ + boost::apply_visitor(*this, _st); +} + +void ASTModifier::visit(Expression& _e) +{ + boost::apply_visitor(*this, _e); +} diff --git a/libyul/optimiser/ASTWalker.h b/libyul/optimiser/ASTWalker.h index b59b405e..272725f9 100644 --- a/libyul/optimiser/ASTWalker.h +++ b/libyul/optimiser/ASTWalker.h @@ -58,14 +58,8 @@ public: 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); - } + virtual void visit(Statement const& _st); + virtual void visit(Expression const& _e); protected: template <class T> @@ -99,14 +93,8 @@ public: 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); - } + virtual void visit(Statement& _st); + virtual void visit(Expression& _e); protected: template <class T> diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp index 64c67b38..c8d236dc 100644 --- a/libyul/optimiser/DataFlowAnalyzer.cpp +++ b/libyul/optimiser/DataFlowAnalyzer.cpp @@ -96,7 +96,10 @@ void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) for (auto const& parameter: _fun.parameters) m_variableScopes.back().variables.emplace(parameter.name); for (auto const& var: _fun.returnVariables) + { m_variableScopes.back().variables.emplace(var.name); + handleAssignment({var.name}, nullptr); + } ASTModifier::operator()(_fun); popScope(); @@ -136,17 +139,22 @@ void DataFlowAnalyzer::operator()(Block& _block) void DataFlowAnalyzer::handleAssignment(set<YulString> const& _variables, Expression* _value) { + static Expression const zero{Literal{{}, LiteralKind::Number, YulString{"0"}, {}}}; clearValues(_variables); MovableChecker movableChecker; if (_value) movableChecker.visit(*_value); - if (_variables.size() == 1) + else + for (auto const& var: _variables) + m_value[var] = &zero; + + if (_value && _variables.size() == 1) { YulString 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)) + if (movableChecker.movable() && !movableChecker.referencedVariables().count(name)) m_value[name] = _value; } diff --git a/libyul/optimiser/DataFlowAnalyzer.h b/libyul/optimiser/DataFlowAnalyzer.h index cd134d48..4f12ff6a 100644 --- a/libyul/optimiser/DataFlowAnalyzer.h +++ b/libyul/optimiser/DataFlowAnalyzer.h @@ -36,6 +36,8 @@ namespace yul * Tracks assignments and is used as base class for both Rematerialiser and * Common Subexpression Eliminator. * + * A special zero constant expression is used for the default value of variables. + * * Prerequisite: Disambiguator */ class DataFlowAnalyzer: public ASTModifier diff --git a/libyul/optimiser/ForLoopInitRewriter.cpp b/libyul/optimiser/ForLoopInitRewriter.cpp index 80d39248..36d5db68 100644 --- a/libyul/optimiser/ForLoopInitRewriter.cpp +++ b/libyul/optimiser/ForLoopInitRewriter.cpp @@ -27,17 +27,24 @@ void ForLoopInitRewriter::operator()(Block& _block) { iterateReplacing( _block.statements, - [](Statement& _stmt) -> boost::optional<vector<Statement>> + [&](Statement& _stmt) -> boost::optional<vector<Statement>> { if (_stmt.type() == typeid(ForLoop)) { auto& forLoop = boost::get<ForLoop>(_stmt); + (*this)(forLoop.pre); + (*this)(forLoop.body); + (*this)(forLoop.post); vector<Statement> rewrite; swap(rewrite, forLoop.pre.statements); rewrite.emplace_back(move(forLoop)); return rewrite; } - return {}; + else + { + visit(_stmt); + return {}; + } } ); } diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp index 8ae26fbb..95360dc3 100644 --- a/libyul/optimiser/FullInliner.cpp +++ b/libyul/optimiser/FullInliner.cpp @@ -49,6 +49,8 @@ FullInliner::FullInliner(Block& _ast, NameDispenser& _dispenser): if (ssaValue.second && ssaValue.second->type() == typeid(Literal)) m_constants.emplace(ssaValue.first); + // Store size of global statements. + m_functionSizes[YulString{}] = CodeSize::codeSize(_ast); map<YulString, size_t> references = ReferencesCounter::countReferences(m_ast); for (auto& statement: m_ast.statements) { @@ -58,7 +60,7 @@ FullInliner::FullInliner(Block& _ast, NameDispenser& _dispenser): m_functions[fun.name] = &fun; // Always inline functions that are only called once. if (references[fun.name] == 1) - m_alwaysInline.emplace(fun.name); + m_singleUse.emplace(fun.name); updateCodeSize(fun); } } @@ -94,8 +96,15 @@ bool FullInliner::shallInline(FunctionCall const& _funCall, YulString _callSite) if (_funCall.functionName.name == _callSite) return false; - FunctionDefinition& calledFunction = function(_funCall.functionName.name); - if (m_alwaysInline.count(calledFunction.name)) + FunctionDefinition* calledFunction = function(_funCall.functionName.name); + if (!calledFunction) + return false; + + // Do not inline into already big functions. + if (m_functionSizes.at(_callSite) > 100) + return false; + + if (m_singleUse.count(calledFunction->name)) return true; // Constant arguments might provide a means for further optimization, so they cause a bonus. @@ -110,8 +119,13 @@ bool FullInliner::shallInline(FunctionCall const& _funCall, YulString _callSite) break; } - size_t size = m_functionSizes.at(calledFunction.name); - return (size < 10 || (constantArg && size < 50)); + size_t size = m_functionSizes.at(calledFunction->name); + return (size < 10 || (constantArg && size < 30)); +} + +void FullInliner::tentativelyUpdateCodeSize(YulString _function, YulString _callSite) +{ + m_functionSizes.at(_callSite) += m_functionSizes.at(_function); } @@ -149,25 +163,32 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC vector<Statement> newStatements; map<YulString, YulString> variableReplacements; - FunctionDefinition& function = m_driver.function(_funCall.functionName.name); + FunctionDefinition* function = m_driver.function(_funCall.functionName.name); + assertThrow(!!function, OptimizerException, "Attempt to inline invalid function."); + + m_driver.tentativelyUpdateCodeSize(function->name, m_currentFunction); + + static Expression const zero{Literal{{}, LiteralKind::Number, YulString{"0"}, {}}}; // helper function to create a new variable that is supposed to model // an existing variable. auto newVariable = [&](TypedName const& _existingVariable, Expression* _value) { - YulString newName = m_nameDispenser.newName(_existingVariable.name, function.name); + YulString newName = m_nameDispenser.newName(_existingVariable.name, function->name); variableReplacements[_existingVariable.name] = newName; VariableDeclaration varDecl{_funCall.location, {{_funCall.location, newName, _existingVariable.type}}, {}}; if (_value) varDecl.value = make_shared<Expression>(std::move(*_value)); + else + varDecl.value = make_shared<Expression>(zero); newStatements.emplace_back(std::move(varDecl)); }; for (size_t i = 0; i < _funCall.arguments.size(); ++i) - newVariable(function.parameters[i], &_funCall.arguments[i]); - for (auto const& var: function.returnVariables) + newVariable(function->parameters[i], &_funCall.arguments[i]); + for (auto const& var: function->returnVariables) newVariable(var, nullptr); - Statement newBody = BodyCopier(m_nameDispenser, function.name, variableReplacements)(function.body); + Statement newBody = BodyCopier(m_nameDispenser, function->name, variableReplacements)(function->body); newStatements += std::move(boost::get<Block>(newBody).statements); boost::apply_visitor(GenericFallbackVisitor<Assignment, VariableDeclaration>{ @@ -179,7 +200,7 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC {_assignment.variableNames[i]}, make_shared<Expression>(Identifier{ _assignment.location, - variableReplacements.at(function.returnVariables[i].name) + variableReplacements.at(function->returnVariables[i].name) }) }); }, @@ -191,7 +212,7 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC {std::move(_varDecl.variables[i])}, make_shared<Expression>(Identifier{ _varDecl.location, - variableReplacements.at(function.returnVariables[i].name) + variableReplacements.at(function->returnVariables[i].name) }) }); } diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h index a8fe76c6..d2dd3229 100644 --- a/libyul/optimiser/FullInliner.h +++ b/libyul/optimiser/FullInliner.h @@ -63,8 +63,8 @@ class NameCollector; * code of f, with replacements: a -> f_a, b -> f_b, c -> f_c * let z := f_c * - * Prerequisites: Disambiguator, Function Hoister - * More efficient if run after: Expression Splitter + * Prerequisites: Disambiguator + * More efficient if run after: Function Hoister, Expression Splitter */ class FullInliner: public ASTModifier { @@ -77,7 +77,18 @@ public: /// @param _callSite the name of the function in which the function call is located. bool shallInline(FunctionCall const& _funCall, YulString _callSite); - FunctionDefinition& function(YulString _name) { return *m_functions.at(_name); } + FunctionDefinition* function(YulString _name) + { + auto it = m_functions.find(_name); + if (it != m_functions.end()) + return it->second; + return nullptr; + } + + /// Adds the size of _funCall to the size of _callSite. This is just + /// a rough estimate that is done during inlining. The proper size + /// should be determined after inlining is completed. + void tentativelyUpdateCodeSize(YulString _function, YulString _callSite); private: void updateCodeSize(FunctionDefinition& fun); @@ -88,7 +99,7 @@ private: Block& m_ast; std::map<YulString, FunctionDefinition*> m_functions; /// Names of functions to always inline. - std::set<YulString> m_alwaysInline; + std::set<YulString> m_singleUse; /// Variables that are constants (used for inlining heuristic) std::set<YulString> m_constants; std::map<YulString, size_t> m_functionSizes; diff --git a/libyul/optimiser/MainFunction.cpp b/libyul/optimiser/MainFunction.cpp index 63eea2db..fabbf66f 100644 --- a/libyul/optimiser/MainFunction.cpp +++ b/libyul/optimiser/MainFunction.cpp @@ -40,12 +40,12 @@ void MainFunction::operator()(Block& _block) 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(YulString{"main"}) == 0, OptimizerException, ""); + assertThrow(NameCollector(_block).names().count("main"_yulstring) == 0, OptimizerException, ""); Block& block = boost::get<Block>(_block.statements[0]); FunctionDefinition main{ block.location, - YulString{"main"}, + "main"_yulstring, {}, {}, std::move(block) diff --git a/libyul/optimiser/Metrics.cpp b/libyul/optimiser/Metrics.cpp index a5557fb3..8fc9476e 100644 --- a/libyul/optimiser/Metrics.cpp +++ b/libyul/optimiser/Metrics.cpp @@ -48,6 +48,9 @@ size_t CodeSize::codeSize(Block const& _block) void CodeSize::visit(Statement const& _statement) { + if (_statement.type() == typeid(FunctionDefinition)) + return; + ++m_size; ASTWalker::visit(_statement); } diff --git a/libyul/optimiser/Metrics.h b/libyul/optimiser/Metrics.h index ca244600..d26ecbd9 100644 --- a/libyul/optimiser/Metrics.h +++ b/libyul/optimiser/Metrics.h @@ -25,17 +25,17 @@ namespace yul { +/** + * Metric for the size of code. + * More specifically, the number of AST nodes. + * Ignores function definitions while traversing the AST. + * If you want to know the size of a function, you have to invoke this on its body. + */ 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); - /// Returns a metric for the code size of an AST element. - /// More specifically, it returns the number of AST nodes. static size_t codeSize(Block const& _block); private: diff --git a/libyul/optimiser/RedundantAssignEliminator.h b/libyul/optimiser/RedundantAssignEliminator.h index 54d65823..4f82e7a2 100644 --- a/libyul/optimiser/RedundantAssignEliminator.h +++ b/libyul/optimiser/RedundantAssignEliminator.h @@ -115,7 +115,7 @@ public: static void run(Block& _ast); private: - RedundantAssignEliminator() {} + RedundantAssignEliminator() = default; class State { diff --git a/libyul/optimiser/SSAValueTracker.cpp b/libyul/optimiser/SSAValueTracker.cpp index 35b29b04..23eb9ec2 100644 --- a/libyul/optimiser/SSAValueTracker.cpp +++ b/libyul/optimiser/SSAValueTracker.cpp @@ -33,13 +33,20 @@ void SSAValueTracker::operator()(Assignment const& _assignment) m_values.erase(var.name); } +void SSAValueTracker::operator()(FunctionDefinition const& _funDef) +{ + for (auto const& var: _funDef.returnVariables) + setValue(var.name, nullptr); + ASTWalker::operator()(_funDef); +} + void SSAValueTracker::operator()(VariableDeclaration const& _varDecl) { - if (_varDecl.variables.size() == 1) - setValue(_varDecl.variables.front().name, _varDecl.value.get()); - else + if (!_varDecl.value) for (auto const& var: _varDecl.variables) setValue(var.name, nullptr); + else if (_varDecl.variables.size() == 1) + setValue(_varDecl.variables.front().name, _varDecl.value.get()); } void SSAValueTracker::setValue(YulString _name, Expression const* _value) @@ -49,5 +56,8 @@ void SSAValueTracker::setValue(YulString _name, Expression const* _value) OptimizerException, "Source needs to be disambiguated." ); + static Expression const zero{Literal{{}, LiteralKind::Number, YulString{"0"}, {}}}; + if (!_value) + _value = &zero; m_values[_name] = _value; } diff --git a/libyul/optimiser/SSAValueTracker.h b/libyul/optimiser/SSAValueTracker.h index e182e013..0680485f 100644 --- a/libyul/optimiser/SSAValueTracker.h +++ b/libyul/optimiser/SSAValueTracker.h @@ -33,12 +33,15 @@ namespace yul * Class that walks the AST and stores the initial value of each variable * that is never assigned to. * + * A special zero constant expression is used for the default value of variables. + * * Prerequisite: Disambiguator */ class SSAValueTracker: public ASTWalker { public: using ASTWalker::operator(); + void operator()(FunctionDefinition const& _funDef) override; void operator()(VariableDeclaration const& _varDecl) override; void operator()(Assignment const& _assignment) override; diff --git a/libyul/optimiser/SimplificationRules.cpp b/libyul/optimiser/SimplificationRules.cpp index b3190fef..45b0ca2c 100644 --- a/libyul/optimiser/SimplificationRules.cpp +++ b/libyul/optimiser/SimplificationRules.cpp @@ -114,7 +114,8 @@ bool Pattern::matches(Expression const& _expr, map<YulString, Expression const*> { YulString varName = boost::get<Identifier>(_expr).name; if (_ssaValues.count(varName)) - expr = _ssaValues.at(varName); + if (Expression const* new_expr = _ssaValues.at(varName)) + expr = new_expr; } assertThrow(expr, OptimizerException, ""); @@ -207,10 +208,7 @@ Expression Pattern::toExpression(SourceLocation const& _location) const u256 Pattern::d() const { - Literal const& literal = boost::get<Literal>(matchGroupValue()); - assertThrow(literal.kind == LiteralKind::Number, OptimizerException, ""); - assertThrow(isValidDecimal(literal.value.str()) || isValidHex(literal.value.str()), OptimizerException, ""); - return u256(literal.value.str()); + return valueOfNumberLiteral(boost::get<Literal>(matchGroupValue())); } Expression const& Pattern::matchGroupValue() const diff --git a/libyul/optimiser/StructuralSimplifier.cpp b/libyul/optimiser/StructuralSimplifier.cpp new file mode 100644 index 00000000..bdf4cb2a --- /dev/null +++ b/libyul/optimiser/StructuralSimplifier.cpp @@ -0,0 +1,138 @@ +/* + 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/>. +*/ +#include <libyul/optimiser/StructuralSimplifier.h> +#include <libyul/optimiser/Semantics.h> +#include <libyul/optimiser/Utilities.h> +#include <libyul/AsmData.h> +#include <libdevcore/CommonData.h> +#include <libdevcore/Visitor.h> + +using namespace std; +using namespace dev; +using namespace yul; + +namespace { + +ExpressionStatement makePopExpressionStatement(langutil::SourceLocation const& _location, Expression&& _expression) +{ + return {_location, FunctionalInstruction{ + _location, + solidity::Instruction::POP, + {std::move(_expression)} + }}; +} + +} + +void StructuralSimplifier::operator()(Block& _block) +{ + pushScope(false); + simplify(_block.statements); + popScope(); +} + +void StructuralSimplifier::simplify(std::vector<yul::Statement>& _statements) +{ + using OptionalStatements = boost::optional<vector<Statement>>; + GenericFallbackReturnsVisitor<OptionalStatements, If, Switch, ForLoop> const visitor( + [&](If& _ifStmt) -> OptionalStatements { + if (_ifStmt.body.statements.empty()) + return {{makePopExpressionStatement(_ifStmt.location, std::move(*_ifStmt.condition))}}; + if (expressionAlwaysTrue(*_ifStmt.condition)) + return {std::move(_ifStmt.body.statements)}; + else if (expressionAlwaysFalse(*_ifStmt.condition)) + return {vector<Statement>{}}; + return {}; + }, + [](Switch& _switchStmt) -> OptionalStatements { + if (_switchStmt.cases.size() == 1) + { + auto& switchCase = _switchStmt.cases.front(); + auto loc = locationOf(*_switchStmt.expression); + if (switchCase.value) + return {{If{ + std::move(_switchStmt.location), + make_shared<Expression>(FunctionalInstruction{ + std::move(loc), + solidity::Instruction::EQ, + {std::move(*switchCase.value), std::move(*_switchStmt.expression)} + }), std::move(switchCase.body)}}}; + else + return {{ + makePopExpressionStatement(loc, std::move(*_switchStmt.expression)), + std::move(switchCase.body) + }}; + } + else + return {}; + }, + [&](ForLoop& _forLoop) -> OptionalStatements { + if (expressionAlwaysFalse(*_forLoop.condition)) + return {std::move(_forLoop.pre.statements)}; + else + return {}; + } + ); + + iterateReplacing( + _statements, + [&](Statement& _stmt) -> OptionalStatements + { + visit(_stmt); + OptionalStatements result = boost::apply_visitor(visitor, _stmt); + if (result) + simplify(*result); + return result; + } + ); +} + +bool StructuralSimplifier::expressionAlwaysTrue(Expression const& _expression) +{ + return boost::apply_visitor(GenericFallbackReturnsVisitor<bool, Identifier const, Literal const>( + [&](Identifier const& _identifier) -> bool { + if (auto expr = m_value[_identifier.name]) + return expressionAlwaysTrue(*expr); + return false; + }, + [](Literal const& _literal) -> bool { + static YulString const trueString("true"); + return + (_literal.kind == LiteralKind::Boolean && _literal.value == trueString) || + (_literal.kind == LiteralKind::Number && valueOfNumberLiteral(_literal) != u256(0)) + ; + } + ), _expression); +} + +bool StructuralSimplifier::expressionAlwaysFalse(Expression const& _expression) +{ + return boost::apply_visitor(GenericFallbackReturnsVisitor<bool, Identifier const, Literal const>( + [&](Identifier const& _identifier) -> bool { + if (auto expr = m_value[_identifier.name]) + return expressionAlwaysFalse(*expr); + return false; + }, + [](Literal const& _literal) -> bool { + static YulString const falseString("false"); + return + (_literal.kind == LiteralKind::Boolean && _literal.value == falseString) || + (_literal.kind == LiteralKind::Number && valueOfNumberLiteral(_literal) == u256(0)) + ; + } + ), _expression); +} diff --git a/libyul/optimiser/StructuralSimplifier.h b/libyul/optimiser/StructuralSimplifier.h new file mode 100644 index 00000000..bbd8e005 --- /dev/null +++ b/libyul/optimiser/StructuralSimplifier.h @@ -0,0 +1,49 @@ +/* + 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/>. +*/ +#pragma once + +#include <libyul/optimiser/ASTWalker.h> +#include <libyul/optimiser/DataFlowAnalyzer.h> + +namespace yul +{ + +/** + * Structural simplifier. Performs the following simplification steps: + * - replace if with empty body with pop(condition) + * - replace if with true condition with its body + * - remove if with false condition + * - turn switch with single case into if + * - replace switch with only default case with pop(expression) and body + * - remove for with false condition + * + * Prerequisites: Disambiguator + * + * Important: Can only be used on EVM code. + */ +class StructuralSimplifier: public DataFlowAnalyzer +{ +public: + using DataFlowAnalyzer::operator(); + void operator()(Block& _block) override; +private: + void simplify(std::vector<Statement>& _statements); + bool expressionAlwaysTrue(Expression const &_expression); + bool expressionAlwaysFalse(Expression const &_expression); +}; + +} diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp index 36f0e1eb..bfba8dfc 100644 --- a/libyul/optimiser/Suite.cpp +++ b/libyul/optimiser/Suite.cpp @@ -21,6 +21,7 @@ #include <libyul/optimiser/Suite.h> #include <libyul/optimiser/Disambiguator.h> +#include <libyul/optimiser/VarDeclInitializer.h> #include <libyul/optimiser/FunctionGrouper.h> #include <libyul/optimiser/FunctionHoister.h> #include <libyul/optimiser/ExpressionSplitter.h> @@ -33,8 +34,8 @@ #include <libyul/optimiser/ExpressionSimplifier.h> #include <libyul/optimiser/CommonSubexpressionEliminator.h> #include <libyul/optimiser/SSATransform.h> +#include <libyul/optimiser/StructuralSimplifier.h> #include <libyul/optimiser/RedundantAssignEliminator.h> -#include <libyul/optimiser/VarDeclPropagator.h> #include <libyul/AsmAnalysisInfo.h> #include <libyul/AsmData.h> #include <libyul/AsmPrinter.h> @@ -55,9 +56,11 @@ void OptimiserSuite::run( Block ast = boost::get<Block>(Disambiguator(_analysisInfo, reservedIdentifiers)(_ast)); + (VarDeclInitializer{})(ast); (FunctionHoister{})(ast); (FunctionGrouper{})(ast); (ForLoopInitRewriter{})(ast); + StructuralSimplifier{}(ast); NameDispenser dispenser{ast}; @@ -66,11 +69,11 @@ void OptimiserSuite::run( ExpressionSplitter{dispenser}(ast); SSATransform::run(ast, dispenser); RedundantAssignEliminator::run(ast); - VarDeclPropagator{}(ast); RedundantAssignEliminator::run(ast); CommonSubexpressionEliminator{}(ast); ExpressionSimplifier::run(ast); + StructuralSimplifier{}(ast); SSATransform::run(ast, dispenser); RedundantAssignEliminator::run(ast); RedundantAssignEliminator::run(ast); @@ -92,26 +95,22 @@ void OptimiserSuite::run( RedundantAssignEliminator::run(ast); CommonSubexpressionEliminator{}(ast); FullInliner{ast, dispenser}.run(); - VarDeclPropagator{}(ast); SSATransform::run(ast, dispenser); RedundantAssignEliminator::run(ast); - VarDeclPropagator{}(ast); RedundantAssignEliminator::run(ast); ExpressionSimplifier::run(ast); + StructuralSimplifier{}(ast); CommonSubexpressionEliminator{}(ast); SSATransform::run(ast, dispenser); RedundantAssignEliminator::run(ast); - VarDeclPropagator{}(ast); RedundantAssignEliminator::run(ast); UnusedPruner::runUntilStabilised(ast, reservedIdentifiers); } ExpressionJoiner::run(ast); - VarDeclPropagator{}(ast); UnusedPruner::runUntilStabilised(ast); ExpressionJoiner::run(ast); UnusedPruner::runUntilStabilised(ast); ExpressionJoiner::run(ast); - VarDeclPropagator{}(ast); UnusedPruner::runUntilStabilised(ast); ExpressionJoiner::run(ast); UnusedPruner::runUntilStabilised(ast); diff --git a/libyul/optimiser/Utilities.cpp b/libyul/optimiser/Utilities.cpp index b8cdd339..b3b580d5 100644 --- a/libyul/optimiser/Utilities.cpp +++ b/libyul/optimiser/Utilities.cpp @@ -21,6 +21,7 @@ #include <libyul/optimiser/Utilities.h> #include <libyul/AsmData.h> +#include <libyul/Exceptions.h> #include <libdevcore/CommonData.h> @@ -37,3 +38,11 @@ void yul::removeEmptyBlocks(Block& _block) }; boost::range::remove_erase_if(_block.statements, isEmptyBlock); } + +u256 yul::valueOfNumberLiteral(Literal const& _literal) +{ + assertThrow(_literal.kind == LiteralKind::Number, OptimizerException, ""); + std::string const& literalString = _literal.value.str(); + assertThrow(isValidDecimal(literalString) || isValidHex(literalString), OptimizerException, ""); + return u256(literalString); +} diff --git a/libyul/optimiser/Utilities.h b/libyul/optimiser/Utilities.h index c543b119..1cfff62b 100644 --- a/libyul/optimiser/Utilities.h +++ b/libyul/optimiser/Utilities.h @@ -20,6 +20,7 @@ #pragma once +#include <libdevcore/Common.h> #include <libyul/AsmDataForward.h> namespace yul @@ -28,4 +29,6 @@ namespace yul /// Removes statements that are just empty blocks (non-recursive). void removeEmptyBlocks(Block& _block); +dev::u256 valueOfNumberLiteral(Literal const& _literal); + } diff --git a/libyul/optimiser/VarDeclInitializer.cpp b/libyul/optimiser/VarDeclInitializer.cpp new file mode 100644 index 00000000..4a26757f --- /dev/null +++ b/libyul/optimiser/VarDeclInitializer.cpp @@ -0,0 +1,56 @@ +/* + 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/>. +*/ + +#include <libyul/optimiser/VarDeclInitializer.h> +#include <libyul/AsmData.h> + +#include <libdevcore/CommonData.h> +#include <libdevcore/Visitor.h> + +using namespace std; +using namespace dev; +using namespace yul; + +void VarDeclInitializer::operator()(Block& _block) +{ + ASTModifier::operator()(_block); + + static Expression const zero{Literal{{}, LiteralKind::Number, YulString{"0"}, {}}}; + + using OptionalStatements = boost::optional<vector<Statement>>; + GenericFallbackReturnsVisitor<OptionalStatements, VariableDeclaration> visitor{ + [](VariableDeclaration& _varDecl) -> OptionalStatements + { + if (_varDecl.value) + return {}; + else if (_varDecl.variables.size() == 1) + { + _varDecl.value = make_shared<Expression>(zero); + return {}; + } + else + { + OptionalStatements ret{vector<Statement>{}}; + langutil::SourceLocation loc{std::move(_varDecl.location)}; + for (auto& var: _varDecl.variables) + ret->push_back(VariableDeclaration{loc, {std::move(var)}, make_shared<Expression>(zero)}); + return ret; + } + } + }; + iterateReplacing(_block.statements, boost::apply_visitor(visitor)); +} diff --git a/libyul/optimiser/VarDeclInitializer.h b/libyul/optimiser/VarDeclInitializer.h new file mode 100644 index 00000000..41d0917c --- /dev/null +++ b/libyul/optimiser/VarDeclInitializer.h @@ -0,0 +1,38 @@ +/* + 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/>. +*/ + +#pragma once + +#include <libyul/AsmDataForward.h> +#include <libyul/optimiser/ASTWalker.h> + +namespace yul +{ + +/** + * Rewrites variable declarations so that all of them are initialized. + * Declarations like ``let x, y`` are split into multiple declaration + * statements. + * Only supports initializing with the zero literal for now. + */ +class VarDeclInitializer: public ASTModifier +{ +public: + void operator()(Block& _block) override; +}; + +} diff --git a/libyul/optimiser/VarDeclPropagator.cpp b/libyul/optimiser/VarDeclPropagator.cpp deleted file mode 100644 index bf974f44..00000000 --- a/libyul/optimiser/VarDeclPropagator.cpp +++ /dev/null @@ -1,126 +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/>. -*/ - -#include <libyul/optimiser/VarDeclPropagator.h> -#include <libyul/AsmData.h> -#include <libdevcore/CommonData.h> -#include <boost/range/algorithm_ext/erase.hpp> -#include <algorithm> -#include <map> - -using namespace std; -using namespace dev; -using namespace yul; - -void VarDeclPropagator::operator()(Block& _block) -{ - map<YulString, TypedName> outerEmptyVarDecls; - map<YulString, TypedName> outerLazyInitializedVarDecls; - swap(m_emptyVarDecls, outerEmptyVarDecls); - swap(m_lazyInitializedVarDecls, outerLazyInitializedVarDecls); - - ASTModifier::operator()(_block); - - iterateReplacing( - _block.statements, - [this](Statement& _stmt) -> boost::optional<vector<Statement>> - { - if (_stmt.type() == typeid(VariableDeclaration)) - { - VariableDeclaration& varDecl = boost::get<VariableDeclaration>(_stmt); - boost::remove_erase_if( - varDecl.variables, - [&](TypedName const& _typedName) { return m_lazyInitializedVarDecls.count(_typedName.name); } - ); - if (varDecl.variables.empty()) - return vector<Statement>{}; - else - return {}; - } - else if (_stmt.type() == typeid(Assignment)) - { - Assignment& assignment = boost::get<Assignment>(_stmt); - if (isFullyLazyInitialized(assignment.variableNames)) - return vector<Statement>{recreateVariableDeclaration(assignment)}; - else - return {}; - } - else - return {}; - } - ); - - swap(m_emptyVarDecls, outerEmptyVarDecls); - swap(m_lazyInitializedVarDecls, outerLazyInitializedVarDecls); -} - -void VarDeclPropagator::operator()(VariableDeclaration& _varDecl) -{ - if (_varDecl.value) - visit(*_varDecl.value); - else - for (TypedName const& typedName: _varDecl.variables) - m_emptyVarDecls[typedName.name] = typedName; -} - -void VarDeclPropagator::operator()(Assignment& _assignment) -{ - visit(*_assignment.value); - - if (allVarNamesUninitialized(_assignment.variableNames)) - for (Identifier const& ident: _assignment.variableNames) - m_lazyInitializedVarDecls[ident.name] = m_emptyVarDecls[ident.name]; - - for (Identifier& name: _assignment.variableNames) - (*this)(name); -} - -void VarDeclPropagator::operator()(Identifier& _ident) -{ - m_emptyVarDecls.erase(_ident.name); -} - -bool VarDeclPropagator::allVarNamesUninitialized(vector<Identifier> const& _variableNames) const -{ - return all_of( - begin(_variableNames), - end(_variableNames), - [&](Identifier const& _ident) -> bool { return m_emptyVarDecls.count(_ident.name); } - ); -} - -bool VarDeclPropagator::isFullyLazyInitialized(vector<Identifier> const& _variableNames) const -{ - return all_of( - begin(_variableNames), - end(_variableNames), - [&](Identifier const& ident) -> bool { return m_lazyInitializedVarDecls.count(ident.name); } - ); -} - -VariableDeclaration VarDeclPropagator::recreateVariableDeclaration(Assignment& _assignment) -{ - TypedNameList variables; - - for (Identifier const& varName: _assignment.variableNames) - { - variables.emplace_back(move(m_lazyInitializedVarDecls.at(varName.name))); - m_lazyInitializedVarDecls.erase(varName.name); - } - - return VariableDeclaration{move(_assignment.location), move(variables), std::move(_assignment.value)}; -} diff --git a/libyul/optimiser/VarDeclPropagator.h b/libyul/optimiser/VarDeclPropagator.h deleted file mode 100644 index 1908c214..00000000 --- a/libyul/optimiser/VarDeclPropagator.h +++ /dev/null @@ -1,60 +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/>. -*/ - -#pragma once - -#include <libyul/AsmDataForward.h> -#include <libyul/optimiser/ASTWalker.h> -#include <libyul/Exceptions.h> -#include <libyul/AsmDataForward.h> -#include <vector> -#include <set> -#include <map> - -namespace yul -{ - -/** - * Rewrites Assignment statements into VariableDeclaration when the assignment's LHS - * variables had no value yet. - * - * It recursively walks through the AST and moves each declaration of variables to - * the first assignment within the same block (if possible).. - */ -class VarDeclPropagator: public ASTModifier -{ -public: - using ASTModifier::operator(); - void operator()(Block& _block) override; - void operator()(VariableDeclaration& _varDecl) override; - void operator()(Assignment& _assignment) override; - void operator()(Identifier& _ident) override; - -private: - bool allVarNamesUninitialized(std::vector<Identifier> const& _variableNames) const; - bool isFullyLazyInitialized(std::vector<Identifier> const& _variableNames) const; - VariableDeclaration recreateVariableDeclaration(Assignment& _assignment); - -private: - /// Holds a list of variables from current Block that have no value assigned yet. - std::map<YulString, TypedName> m_emptyVarDecls; - - /// Holds a list variables (and their TypedName) within the current block. - std::map<YulString, TypedName> m_lazyInitializedVarDecls; -}; - -} |