diff options
Diffstat (limited to 'libevmasm')
31 files changed, 685 insertions, 248 deletions
diff --git a/libevmasm/Assembly.cpp b/libevmasm/Assembly.cpp index e881c1e2..edbb9828 100644 --- a/libevmasm/Assembly.cpp +++ b/libevmasm/Assembly.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file Assembly.cpp * @author Gav Wood <i@gavwood.com> @@ -20,13 +20,17 @@ */ #include "Assembly.h" -#include <fstream> + #include <libevmasm/CommonSubexpressionEliminator.h> #include <libevmasm/ControlFlowGraph.h> +#include <libevmasm/PeepholeOptimiser.h> #include <libevmasm/BlockDeduplicator.h> #include <libevmasm/ConstantOptimiser.h> #include <libevmasm/GasMeter.h> + +#include <fstream> #include <json/json.h> + using namespace std; using namespace dev; using namespace dev::eth; @@ -75,17 +79,17 @@ string Assembly::out() const return ret.str(); } -unsigned Assembly::bytesRequired() const +unsigned Assembly::bytesRequired(unsigned subTagSize) const { - for (unsigned br = 1;; ++br) + for (unsigned tagSize = subTagSize; true; ++tagSize) { unsigned ret = 1; for (auto const& i: m_data) ret += i.second.size(); for (AssemblyItem const& i: m_items) - ret += i.bytesRequired(br); - if (dev::bytesRequired(ret) <= br) + ret += i.bytesRequired(tagSize); + if (dev::bytesRequired(ret) <= tagSize) return ret; } } @@ -132,13 +136,19 @@ ostream& Assembly::streamAsm(ostream& _out, string const& _prefix, StringMap con if (i.data() == 0) _out << " PUSH [ErrorTag]"; else - _out << " PUSH [tag" << dec << i.data() << "]"; + { + size_t subId = i.splitForeignPushTag().first; + if (subId == size_t(-1)) + _out << " PUSH [tag" << dec << i.splitForeignPushTag().second << "]"; + else + _out << " PUSH [tag" << dec << subId << ":" << i.splitForeignPushTag().second << "]"; + } break; case PushSub: - _out << " PUSH [$" << h256(i.data()).abridgedMiddle() << "]"; + _out << " PUSH [$" << size_t(i.data()) << "]"; break; case PushSubSize: - _out << " PUSH #[$" << h256(i.data()).abridgedMiddle() << "]"; + _out << " PUSH #[$" << size_t(i.data()) << "]"; break; case PushProgramSize: _out << " PUSHSIZE"; @@ -167,7 +177,7 @@ ostream& Assembly::streamAsm(ostream& _out, string const& _prefix, StringMap con for (size_t i = 0; i < m_subs.size(); ++i) { _out << _prefix << " " << hex << i << ": " << endl; - m_subs[i].stream(_out, _prefix + " ", _sourceCodes); + m_subs[i]->stream(_out, _prefix + " ", _sourceCodes); } } return _out; @@ -266,7 +276,7 @@ Json::Value Assembly::streamAsmJson(ostream& _out, StringMap const& _sourceCodes { std::stringstream hexStr; hexStr << hex << i; - data[hexStr.str()] = m_subs[i].stream(_out, "", _sourceCodes, true); + data[hexStr.str()] = m_subs[i]->stream(_out, "", _sourceCodes, true); } root[".data"] = data; _out << root; @@ -308,63 +318,78 @@ void Assembly::injectStart(AssemblyItem const& _i) Assembly& Assembly::optimise(bool _enable, bool _isCreation, size_t _runs) { - if (!_enable) - return *this; + optimiseInternal(_enable, _isCreation, _runs); + return *this; +} +map<u256, u256> Assembly::optimiseInternal(bool _enable, bool _isCreation, size_t _runs) +{ + for (size_t subId = 0; subId < m_subs.size(); ++subId) + { + map<u256, u256> subTagReplacements = m_subs[subId]->optimiseInternal(_enable, false, _runs); + BlockDeduplicator::applyTagReplacement(m_items, subTagReplacements, subId); + } + + map<u256, u256> tagReplacements; unsigned total = 0; for (unsigned count = 1; count > 0; total += count) { count = 0; + PeepholeOptimiser peepOpt(m_items); + while (peepOpt.optimise()) + count++; + + if (!_enable) + continue; + // This only modifies PushTags, we have to run again to actually remove code. BlockDeduplicator dedup(m_items); if (dedup.deduplicate()) + { + tagReplacements.insert(dedup.replacedTags().begin(), dedup.replacedTags().end()); count++; + } { - // Control flow graph that resets knowledge at path joins. - ControlFlowGraph cfg(m_items, false); + // Control flow graph optimization has been here before but is disabled because it + // assumes we only jump to tags that are pushed. This is not the case anymore with + // function types that can be stored in storage. AssemblyItems optimisedItems; - for (BasicBlock const& block: cfg.optimisedBlocks()) + + auto iter = m_items.begin(); + while (iter != m_items.end()) { - // We used to start with the block's initial state but it caused - // too many inconsistencies. KnownState emptyState; CommonSubexpressionEliminator eliminator(emptyState); - auto iter = m_items.begin() + block.begin; - auto const end = m_items.begin() + block.end; - while (iter < end) + auto orig = iter; + iter = eliminator.feedItems(iter, m_items.end()); + bool shouldReplace = false; + AssemblyItems optimisedChunk; + try { - auto orig = iter; - iter = eliminator.feedItems(iter, end); - bool shouldReplace = false; - AssemblyItems optimisedChunk; - try - { - optimisedChunk = eliminator.getOptimizedItems(); - shouldReplace = (optimisedChunk.size() < size_t(iter - orig)); - } - catch (StackTooDeepException const&) - { - // This might happen if the opcode reconstruction is not as efficient - // as the hand-crafted code. - } - catch (ItemNotAvailableException const&) - { - // This might happen if e.g. associativity and commutativity rules - // reorganise the expression tree, but not all leaves are available. - } - - if (shouldReplace) - { - count++; - optimisedItems += optimisedChunk; - } - else - copy(orig, iter, back_inserter(optimisedItems)); + optimisedChunk = eliminator.getOptimizedItems(); + shouldReplace = (optimisedChunk.size() < size_t(iter - orig)); + } + catch (StackTooDeepException const&) + { + // This might happen if the opcode reconstruction is not as efficient + // as the hand-crafted code. + } + catch (ItemNotAvailableException const&) + { + // This might happen if e.g. associativity and commutativity rules + // reorganise the expression tree, but not all leaves are available. } - } + if (shouldReplace) + { + count++; + optimisedItems += optimisedChunk; + } + else + copy(orig, iter, back_inserter(optimisedItems)); + } if (optimisedItems.size() < m_items.size()) { m_items = move(optimisedItems); @@ -373,17 +398,15 @@ Assembly& Assembly::optimise(bool _enable, bool _isCreation, size_t _runs) } } - total += ConstantOptimisationMethod::optimiseConstants( - _isCreation, - _isCreation ? 1 : _runs, - *this, - m_items - ); - - for (auto& sub: m_subs) - sub.optimise(true, false, _runs); + if (_enable) + total += ConstantOptimisationMethod::optimiseConstants( + _isCreation, + _isCreation ? 1 : _runs, + *this, + m_items + ); - return *this; + return tagReplacements; } LinkerObject const& Assembly::assemble() const @@ -391,20 +414,28 @@ LinkerObject const& Assembly::assemble() const if (!m_assembledObject.bytecode.empty()) return m_assembledObject; + size_t subTagSize = 1; + for (auto const& sub: m_subs) + { + sub->assemble(); + if (!sub->m_tagPositionsInBytecode.empty()) + subTagSize = max(subTagSize, *max_element(sub->m_tagPositionsInBytecode.begin(), sub->m_tagPositionsInBytecode.end())); + } + LinkerObject& ret = m_assembledObject; - unsigned totalBytes = bytesRequired(); - vector<unsigned> tagPos(m_usedTags); - map<unsigned, unsigned> tagRef; + size_t bytesRequiredForCode = bytesRequired(subTagSize); + m_tagPositionsInBytecode = vector<size_t>(m_usedTags, -1); + map<size_t, pair<size_t, size_t>> tagRef; multimap<h256, unsigned> dataRef; multimap<size_t, size_t> subRef; vector<unsigned> sizeRef; ///< Pointers to code locations where the size of the program is inserted - unsigned bytesPerTag = dev::bytesRequired(totalBytes); + unsigned bytesPerTag = dev::bytesRequired(bytesRequiredForCode); byte tagPush = (byte)Instruction::PUSH1 - 1 + bytesPerTag; - unsigned bytesRequiredIncludingData = bytesRequired(); + unsigned bytesRequiredIncludingData = bytesRequiredForCode + 1; for (auto const& sub: m_subs) - bytesRequiredIncludingData += sub.assemble().bytecode.size(); + bytesRequiredIncludingData += sub->assemble().bytecode.size(); unsigned bytesPerDataRef = dev::bytesRequired(bytesRequiredIncludingData); byte dataRefPush = (byte)Instruction::PUSH1 - 1 + bytesPerDataRef; @@ -413,8 +444,8 @@ LinkerObject const& Assembly::assemble() const for (AssemblyItem const& i: m_items) { // store position of the invalid jump destination - if (i.type() != Tag && tagPos[0] == 0) - tagPos[0] = ret.bytecode.size(); + if (i.type() != Tag && m_tagPositionsInBytecode[0] == size_t(-1)) + m_tagPositionsInBytecode[0] = ret.bytecode.size(); switch (i.type()) { @@ -446,7 +477,7 @@ LinkerObject const& Assembly::assemble() const case PushTag: { ret.bytecode.push_back(tagPush); - tagRef[ret.bytecode.size()] = (unsigned)i.data(); + tagRef[ret.bytecode.size()] = i.splitForeignPushTag(); ret.bytecode.resize(ret.bytecode.size() + bytesPerTag); break; } @@ -462,7 +493,7 @@ LinkerObject const& Assembly::assemble() const break; case PushSubSize: { - auto s = m_subs.at(size_t(i.data())).assemble().bytecode.size(); + auto s = m_subs.at(size_t(i.data()))->assemble().bytecode.size(); i.setPushedValue(u256(s)); byte b = max<unsigned>(1, dev::bytesRequired(s)); ret.bytecode.push_back((byte)Instruction::PUSH1 - 1 + b); @@ -484,25 +515,16 @@ LinkerObject const& Assembly::assemble() const ret.bytecode.resize(ret.bytecode.size() + 20); break; case Tag: - tagPos[(unsigned)i.data()] = ret.bytecode.size(); assertThrow(i.data() != 0, AssemblyException, ""); + assertThrow(i.splitForeignPushTag().first == size_t(-1), AssemblyException, "Foreign tag."); + assertThrow(ret.bytecode.size() < 0xffffffffL, AssemblyException, "Tag too large."); + m_tagPositionsInBytecode[size_t(i.data())] = ret.bytecode.size(); ret.bytecode.push_back((byte)Instruction::JUMPDEST); break; default: BOOST_THROW_EXCEPTION(InvalidOpcode()); } } - for (auto const& i: tagRef) - { - bytesRef r(ret.bytecode.data() + i.first, bytesPerTag); - auto tag = i.second; - if (tag >= tagPos.size()) - tag = 0; - if (tag == 0) - assertThrow(tagPos[tag] != 0, AssemblyException, ""); - - toBigEndian(tagPos[tag], r); - } if (!dataRef.empty() && !subRef.empty()) ret.bytecode.push_back(0); @@ -516,7 +538,24 @@ LinkerObject const& Assembly::assemble() const bytesRef r(ret.bytecode.data() + ref->second, bytesPerDataRef); toBigEndian(ret.bytecode.size(), r); } - ret.append(m_subs[i].assemble()); + ret.append(m_subs[i]->assemble()); + } + for (auto const& i: tagRef) + { + size_t subId; + size_t tagId; + tie(subId, tagId) = i.second; + assertThrow(subId == size_t(-1) || subId < m_subs.size(), AssemblyException, "Invalid sub id"); + std::vector<size_t> const& tagPositions = + subId == size_t(-1) ? + m_tagPositionsInBytecode : + m_subs[subId]->m_tagPositionsInBytecode; + assertThrow(tagId < tagPositions.size(), AssemblyException, "Reference to non-existing tag."); + size_t pos = tagPositions[tagId]; + assertThrow(pos != size_t(-1), AssemblyException, "Reference to tag without position."); + assertThrow(dev::bytesRequired(pos) <= bytesPerTag, AssemblyException, "Tag too large for reserved space."); + bytesRef r(ret.bytecode.data() + i.first, bytesPerTag); + toBigEndian(pos, r); } for (auto const& dataItem: m_data) { diff --git a/libevmasm/Assembly.h b/libevmasm/Assembly.h index dae1e1da..a5fd4d51 100644 --- a/libevmasm/Assembly.h +++ b/libevmasm/Assembly.h @@ -1,43 +1,45 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ -/** @file Assembly.h - * @author Gav Wood <i@gavwood.com> - * @date 2014 - */ #pragma once -#include <iostream> -#include <sstream> -#include <libdevcore/Common.h> -#include <libdevcore/Assertions.h> -#include <libdevcore/SHA3.h> #include <libevmasm/Instruction.h> #include <libevmasm/SourceLocation.h> #include <libevmasm/AssemblyItem.h> #include <libevmasm/LinkerObject.h> -#include "Exceptions.h" +#include <libevmasm/Exceptions.h> + +#include <libdevcore/Common.h> +#include <libdevcore/Assertions.h> +#include <libdevcore/SHA3.h> + #include <json/json.h> +#include <iostream> +#include <sstream> +#include <memory> + namespace dev { namespace eth { +using AssemblyPointer = std::shared_ptr<Assembly>; + class Assembly { public: @@ -46,20 +48,18 @@ public: AssemblyItem newTag() { return AssemblyItem(Tag, m_usedTags++); } AssemblyItem newPushTag() { return AssemblyItem(PushTag, m_usedTags++); } AssemblyItem newData(bytes const& _data) { h256 h(dev::keccak256(asString(_data))); m_data[h] = _data; return AssemblyItem(PushData, h); } - AssemblyItem newSub(Assembly const& _sub) { m_subs.push_back(_sub); return AssemblyItem(PushSub, m_subs.size() - 1); } - Assembly const& sub(size_t _sub) const { return m_subs.at(_sub); } - Assembly& sub(size_t _sub) { return m_subs.at(_sub); } + AssemblyItem newSub(AssemblyPointer const& _sub) { m_subs.push_back(_sub); return AssemblyItem(PushSub, m_subs.size() - 1); } + Assembly const& sub(size_t _sub) const { return *m_subs.at(_sub); } + Assembly& sub(size_t _sub) { return *m_subs.at(_sub); } AssemblyItem newPushString(std::string const& _data) { h256 h(dev::keccak256(_data)); m_strings[h] = _data; return AssemblyItem(PushString, h); } AssemblyItem newPushSubSize(u256 const& _subId) { return AssemblyItem(PushSubSize, _subId); } AssemblyItem newPushLibraryAddress(std::string const& _identifier); - AssemblyItem append() { return append(newTag()); } void append(Assembly const& _a); void append(Assembly const& _a, int _deposit); AssemblyItem const& append(AssemblyItem const& _i); AssemblyItem const& append(std::string const& _data) { return append(newPushString(_data)); } AssemblyItem const& append(bytes const& _data) { return append(newData(_data)); } - AssemblyItem appendSubSize(Assembly const& _a) { auto ret = newSub(_a); append(newPushSubSize(ret.data())); return ret; } /// Pushes the final size of the current assembly itself. Use this when the code is modified /// after compilation and CODESIZE is not an option. void appendProgramSize() { append(AssemblyItem(PushProgramSize)); } @@ -101,6 +101,7 @@ public: /// execution gas usage is optimised. @a _isCreation should be true for the top-level assembly. /// @a _runs specifes an estimate on how often each opcode in this assembly will be executed, /// i.e. use a small value to optimise for size and a large value to optimise for runtime. + /// If @a _enable is not set, will perform some simple peephole optimizations. Assembly& optimise(bool _enable, bool _isCreation = true, size_t _runs = 200); Json::Value stream( std::ostream& _out, @@ -110,9 +111,13 @@ public: ) const; protected: + /// Does the same operations as @a optimise, but should only be applied to a sub and + /// returns the replaced tags. + std::map<u256, u256> optimiseInternal(bool _enable, bool _isCreation, size_t _runs); + std::string locationFromSources(StringMap const& _sourceCodes, SourceLocation const& _location) const; void donePath() { if (m_totalDeposit != INT_MAX && m_totalDeposit != m_deposit) BOOST_THROW_EXCEPTION(InvalidDeposit()); } - unsigned bytesRequired() const; + unsigned bytesRequired(unsigned subTagSize) const; private: Json::Value streamAsmJson(std::ostream& _out, StringMap const& _sourceCodes) const; @@ -124,11 +129,12 @@ protected: unsigned m_usedTags = 1; AssemblyItems m_items; std::map<h256, bytes> m_data; - std::vector<Assembly> m_subs; + std::vector<std::shared_ptr<Assembly>> m_subs; std::map<h256, std::string> m_strings; std::map<h256, std::string> m_libraries; ///< Identifiers of libraries to be linked. mutable LinkerObject m_assembledObject; + mutable std::vector<size_t> m_tagPositionsInBytecode; int m_deposit = 0; int m_baseDeposit = 0; diff --git a/libevmasm/AssemblyItem.cpp b/libevmasm/AssemblyItem.cpp index 599ded85..54e38de8 100644 --- a/libevmasm/AssemblyItem.cpp +++ b/libevmasm/AssemblyItem.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file Assembly.cpp * @author Gav Wood <i@gavwood.com> @@ -26,6 +26,29 @@ using namespace std; using namespace dev; using namespace dev::eth; +AssemblyItem AssemblyItem::toSubAssemblyTag(size_t _subId) const +{ + assertThrow(m_data < (u256(1) << 64), Exception, "Tag already has subassembly set."); + + assertThrow(m_type == PushTag || m_type == Tag, Exception, ""); + AssemblyItem r = *this; + r.m_type = PushTag; + r.setPushTagSubIdAndTag(_subId, size_t(m_data)); + return r; +} + +pair<size_t, size_t> AssemblyItem::splitForeignPushTag() const +{ + assertThrow(m_type == PushTag || m_type == Tag, Exception, ""); + return make_pair(size_t(m_data / (u256(1) << 64)) - 1, size_t(m_data)); +} + +void AssemblyItem::setPushTagSubIdAndTag(size_t _subId, size_t _tag) +{ + assertThrow(m_type == PushTag || m_type == Tag, Exception, ""); + setData(_tag + (u256(_subId + 1) << 64)); +} + unsigned AssemblyItem::bytesRequired(unsigned _addressLength) const { switch (m_type) @@ -104,8 +127,14 @@ ostream& dev::eth::operator<<(ostream& _out, AssemblyItem const& _item) _out << " PushString" << hex << (unsigned)_item.data(); break; case PushTag: - _out << " PushTag " << _item.data(); + { + size_t subId = _item.splitForeignPushTag().first; + if (subId == size_t(-1)) + _out << " PushTag " << _item.splitForeignPushTag().second; + else + _out << " PushTag " << subId << ":" << _item.splitForeignPushTag().second; break; + } case Tag: _out << " Tag " << _item.data(); break; @@ -113,10 +142,10 @@ ostream& dev::eth::operator<<(ostream& _out, AssemblyItem const& _item) _out << " PushData " << hex << (unsigned)_item.data(); break; case PushSub: - _out << " PushSub " << hex << h256(_item.data()).abridgedMiddle(); + _out << " PushSub " << hex << size_t(_item.data()); break; case PushSubSize: - _out << " PushSubSize " << hex << h256(_item.data()).abridgedMiddle(); + _out << " PushSubSize " << hex << size_t(_item.data()); break; case PushProgramSize: _out << " PushProgramSize"; diff --git a/libevmasm/AssemblyItem.h b/libevmasm/AssemblyItem.h index 1c3d9789..b5bd3ed8 100644 --- a/libevmasm/AssemblyItem.h +++ b/libevmasm/AssemblyItem.h @@ -1,20 +1,20 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ -/** @file Assembly.h +/** @file AssemblyItem.h * @author Gav Wood <i@gavwood.com> * @date 2014 */ @@ -69,6 +69,14 @@ public: AssemblyItem tag() const { assertThrow(m_type == PushTag || m_type == Tag, Exception, ""); return AssemblyItem(Tag, m_data); } AssemblyItem pushTag() const { assertThrow(m_type == PushTag || m_type == Tag, Exception, ""); return AssemblyItem(PushTag, m_data); } + /// Converts the tag to a subassembly tag. This has to be called in order to move a tag across assemblies. + /// @param _subId the identifier of the subassembly the tag is taken from. + AssemblyItem toSubAssemblyTag(size_t _subId) const; + /// @returns splits the data of the push tag into sub assembly id and actual tag id. + /// The sub assembly id of non-foreign push tags is -1. + std::pair<size_t, size_t> splitForeignPushTag() const; + /// Sets sub-assembly part and tag for a push tag. + void setPushTagSubIdAndTag(size_t _subId, size_t _tag); AssemblyItemType type() const { return m_type; } u256 const& data() const { return m_data; } diff --git a/libevmasm/BlockDeduplicator.cpp b/libevmasm/BlockDeduplicator.cpp index 3bb7a797..d21be07e 100644 --- a/libevmasm/BlockDeduplicator.cpp +++ b/libevmasm/BlockDeduplicator.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file BlockDeduplicator.cpp @@ -77,7 +77,6 @@ bool BlockDeduplicator::deduplicate() { //@todo this should probably be optimized. set<size_t, function<bool(size_t, size_t)>> blocksSeen(comparator); - map<u256, u256> tagReplacement; for (size_t i = 0; i < m_items.size(); ++i) { if (m_items.at(i).type() != Tag) @@ -86,22 +85,40 @@ bool BlockDeduplicator::deduplicate() if (it == blocksSeen.end()) blocksSeen.insert(i); else - tagReplacement[m_items.at(i).data()] = m_items.at(*it).data(); + m_replacedTags[m_items.at(i).data()] = m_items.at(*it).data(); } - bool changed = false; - for (AssemblyItem& item: m_items) - if (item.type() == PushTag && tagReplacement.count(item.data())) - { - changed = true; - item.setData(tagReplacement.at(item.data())); - } - if (!changed) + if (!applyTagReplacement(m_items, m_replacedTags)) break; } return iterations > 0; } +bool BlockDeduplicator::applyTagReplacement( + AssemblyItems& _items, + map<u256, u256> const& _replacements, + size_t _subId +) +{ + bool changed = false; + for (AssemblyItem& item: _items) + if (item.type() == PushTag) + { + size_t subId; + size_t tagId; + tie(subId, tagId) = item.splitForeignPushTag(); + if (subId != _subId) + continue; + auto it = _replacements.find(tagId); + if (it != _replacements.end()) + { + changed = true; + item.setPushTagSubIdAndTag(subId, size_t(it->second)); + } + } + return changed; +} + BlockDeduplicator::BlockIterator& BlockDeduplicator::BlockIterator::operator++() { if (it == end) diff --git a/libevmasm/BlockDeduplicator.h b/libevmasm/BlockDeduplicator.h index c48835fd..797c2476 100644 --- a/libevmasm/BlockDeduplicator.h +++ b/libevmasm/BlockDeduplicator.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file BlockDeduplicator.h @@ -23,9 +23,12 @@ #pragma once +#include <libdevcore/Common.h> + #include <cstddef> #include <vector> #include <functional> +#include <map> namespace dev { @@ -45,6 +48,18 @@ public: BlockDeduplicator(AssemblyItems& _items): m_items(_items) {} /// @returns true if something was changed bool deduplicate(); + /// @returns the tags that were replaced. + std::map<u256, u256> const& replacedTags() const { return m_replacedTags; } + + /// Replaces all PushTag operations insied @a _items that match a key in + /// @a _replacements by the respective value. If @a _subID is not -1, only + /// apply the replacement for foreign tags from this sub id. + /// @returns true iff a replacement was performed. + static bool applyTagReplacement( + AssemblyItems& _items, + std::map<u256, u256> const& _replacements, + size_t _subID = size_t(-1) + ); private: /// Iterator that skips tags and skips to the end if (all branches of) the control @@ -70,6 +85,7 @@ private: AssemblyItem const* replaceWith; }; + std::map<u256, u256> m_replacedTags; AssemblyItems& m_items; }; diff --git a/libevmasm/CommonSubexpressionEliminator.cpp b/libevmasm/CommonSubexpressionEliminator.cpp index 0797dd29..6294e579 100644 --- a/libevmasm/CommonSubexpressionEliminator.cpp +++ b/libevmasm/CommonSubexpressionEliminator.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file CommonSubexpressionEliminator.cpp diff --git a/libevmasm/CommonSubexpressionEliminator.h b/libevmasm/CommonSubexpressionEliminator.h index f6c43c57..83fc9732 100644 --- a/libevmasm/CommonSubexpressionEliminator.h +++ b/libevmasm/CommonSubexpressionEliminator.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file CommonSubexpressionEliminator.h diff --git a/libevmasm/ConstantOptimiser.cpp b/libevmasm/ConstantOptimiser.cpp index 27f630f5..f4a50c2d 100644 --- a/libevmasm/ConstantOptimiser.cpp +++ b/libevmasm/ConstantOptimiser.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file ConstantOptimiser.cpp * @author Christian <c@ethdev.com> diff --git a/libevmasm/ConstantOptimiser.h b/libevmasm/ConstantOptimiser.h index e75eff38..b35b2a69 100644 --- a/libevmasm/ConstantOptimiser.h +++ b/libevmasm/ConstantOptimiser.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file ConstantOptimiser.cpp * @author Christian <c@ethdev.com> diff --git a/libevmasm/ControlFlowGraph.cpp b/libevmasm/ControlFlowGraph.cpp index d4801562..86f16d48 100644 --- a/libevmasm/ControlFlowGraph.cpp +++ b/libevmasm/ControlFlowGraph.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file ControlFlowGraph.cpp diff --git a/libevmasm/ControlFlowGraph.h b/libevmasm/ControlFlowGraph.h index 03a1f717..ebef543f 100644 --- a/libevmasm/ControlFlowGraph.h +++ b/libevmasm/ControlFlowGraph.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file ControlFlowGraph.h @@ -89,6 +89,11 @@ struct BasicBlock using BasicBlocks = std::vector<BasicBlock>; +/** + * Control flow graph optimizer. + * ASSUMES THAT WE ONLY JUMP TO TAGS THAT WERE PREVIOUSLY PUSHED. THIS IS NOT TRUE ANYMORE + * NOW THAT FUNCTION TAGS CAN BE STORED IN STORAGE. + */ class ControlFlowGraph { public: diff --git a/libevmasm/EVMSchedule.h b/libevmasm/EVMSchedule.h index 02a34b16..f882f006 100644 --- a/libevmasm/EVMSchedule.h +++ b/libevmasm/EVMSchedule.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file EVMSchedule.h * @author Gav <i@gavwood.com> diff --git a/libevmasm/Exceptions.h b/libevmasm/Exceptions.h index 03b8afde..06b0ac78 100644 --- a/libevmasm/Exceptions.h +++ b/libevmasm/Exceptions.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file Exceptions.h * @author Christian <c@ethdev.com> diff --git a/libevmasm/ExpressionClasses.cpp b/libevmasm/ExpressionClasses.cpp index cf5e6a0e..e32b2da2 100644 --- a/libevmasm/ExpressionClasses.cpp +++ b/libevmasm/ExpressionClasses.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file ExpressionClasses.cpp diff --git a/libevmasm/ExpressionClasses.h b/libevmasm/ExpressionClasses.h index 4bfd7d24..11a698dd 100644 --- a/libevmasm/ExpressionClasses.h +++ b/libevmasm/ExpressionClasses.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file ExpressionClasses.h diff --git a/libevmasm/GasMeter.cpp b/libevmasm/GasMeter.cpp index 51f3cf1d..21db3565 100644 --- a/libevmasm/GasMeter.cpp +++ b/libevmasm/GasMeter.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file GasMeter.cpp * @author Christian <c@ethdev.com> @@ -39,7 +39,7 @@ GasMeter::GasConsumption& GasMeter::GasConsumption::operator+=(GasConsumption co return *this; } -GasMeter::GasConsumption GasMeter::estimateMax(AssemblyItem const& _item) +GasMeter::GasConsumption GasMeter::estimateMax(AssemblyItem const& _item, bool _includeExternalCosts) { GasConsumption gas; switch (_item.type()) @@ -128,23 +128,35 @@ GasMeter::GasConsumption GasMeter::estimateMax(AssemblyItem const& _item) case Instruction::CALLCODE: case Instruction::DELEGATECALL: { - gas = GasCosts::callGas; - if (u256 const* value = classes.knownConstant(m_state->relativeStackElement(0))) - gas += (*value); - else + if (_includeExternalCosts) + // We assume that we do not know the target contract and thus, the consumption is infinite. gas = GasConsumption::infinite(); - if (_item.instruction() == Instruction::CALL) - gas += GasCosts::callNewAccountGas; // We very rarely know whether the address exists. - int valueSize = _item.instruction() == Instruction::DELEGATECALL ? 0 : 1; - if (!classes.knownZero(m_state->relativeStackElement(-1 - valueSize))) - gas += GasCosts::callValueTransferGas; - gas += memoryGas(-2 - valueSize, -3 - valueSize); - gas += memoryGas(-4 - valueSize, -5 - valueSize); + else + { + gas = GasCosts::callGas; + if (u256 const* value = classes.knownConstant(m_state->relativeStackElement(0))) + gas += (*value); + else + gas = GasConsumption::infinite(); + if (_item.instruction() == Instruction::CALL) + gas += GasCosts::callNewAccountGas; // We very rarely know whether the address exists. + int valueSize = _item.instruction() == Instruction::DELEGATECALL ? 0 : 1; + if (!classes.knownZero(m_state->relativeStackElement(-1 - valueSize))) + gas += GasCosts::callValueTransferGas; + gas += memoryGas(-2 - valueSize, -3 - valueSize); + gas += memoryGas(-4 - valueSize, -5 - valueSize); + } break; } case Instruction::CREATE: - gas = GasCosts::createGas; - gas += memoryGas(-1, -2); + if (_includeExternalCosts) + // We assume that we do not know the target contract and thus, the consumption is infinite. + gas = GasConsumption::infinite(); + else + { + gas = GasCosts::createGas; + gas += memoryGas(-1, -2); + } break; case Instruction::EXP: gas = GasCosts::expGas; diff --git a/libevmasm/GasMeter.h b/libevmasm/GasMeter.h index 1a607a9f..0bc10f1f 100644 --- a/libevmasm/GasMeter.h +++ b/libevmasm/GasMeter.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file GasMeter.cpp * @author Christian <c@ethdev.com> @@ -102,7 +102,8 @@ public: /// @returns an upper bound on the gas consumed by the given instruction and updates /// the state. - GasConsumption estimateMax(AssemblyItem const& _item); + /// @param _inculdeExternalCosts if true, include costs caused by other contracts in calls. + GasConsumption estimateMax(AssemblyItem const& _item, bool _includeExternalCosts = true); u256 const& largestMemoryAccess() const { return m_largestMemoryAccess; } diff --git a/libevmasm/Instruction.cpp b/libevmasm/Instruction.cpp index 2aaa6f1d..5244a91f 100644 --- a/libevmasm/Instruction.cpp +++ b/libevmasm/Instruction.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file Instruction.cpp * @author Gav Wood <i@gavwood.com> diff --git a/libevmasm/Instruction.h b/libevmasm/Instruction.h index 0b06a677..c7fad1c5 100644 --- a/libevmasm/Instruction.h +++ b/libevmasm/Instruction.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file Instruction.h * @author Gav Wood <i@gavwood.com> diff --git a/libevmasm/KnownState.cpp b/libevmasm/KnownState.cpp index 0b6e0ac5..6e3130dd 100644 --- a/libevmasm/KnownState.cpp +++ b/libevmasm/KnownState.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file KnownState.cpp diff --git a/libevmasm/KnownState.h b/libevmasm/KnownState.h index c1c602dc..fd6a26c1 100644 --- a/libevmasm/KnownState.h +++ b/libevmasm/KnownState.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file KnownState.h diff --git a/libevmasm/LinkerObject.cpp b/libevmasm/LinkerObject.cpp index ceb864a1..93e4067c 100644 --- a/libevmasm/LinkerObject.cpp +++ b/libevmasm/LinkerObject.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file LinkerObject.cpp * @author Christian R <c@ethdev.com> diff --git a/libevmasm/LinkerObject.h b/libevmasm/LinkerObject.h index 83d2bd7e..d3ec3e97 100644 --- a/libevmasm/LinkerObject.h +++ b/libevmasm/LinkerObject.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file Assembly.h * @author Gav Wood <i@gavwood.com> diff --git a/libevmasm/PathGasMeter.cpp b/libevmasm/PathGasMeter.cpp index 2113008b..c56e2f8b 100644 --- a/libevmasm/PathGasMeter.cpp +++ b/libevmasm/PathGasMeter.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file PathGasMeter.cpp * @author Christian <c@ethdev.com> diff --git a/libevmasm/PathGasMeter.h b/libevmasm/PathGasMeter.h index 1ada460a..0a0fe5d0 100644 --- a/libevmasm/PathGasMeter.h +++ b/libevmasm/PathGasMeter.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** @file PathGasMeter.cpp * @author Christian <c@ethdev.com> diff --git a/libevmasm/PeepholeOptimiser.cpp b/libevmasm/PeepholeOptimiser.cpp new file mode 100644 index 00000000..b96b0295 --- /dev/null +++ b/libevmasm/PeepholeOptimiser.cpp @@ -0,0 +1,245 @@ +/* + 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/>. +*/ +/** + * @file PeepholeOptimiser.cpp + * Performs local optimising code changes to assembly. + */ + +#include "PeepholeOptimiser.h" + +#include <libevmasm/AssemblyItem.h> +#include <libevmasm/SemanticInformation.h> + +using namespace std; +using namespace dev::eth; +using namespace dev; + +// TODO: Extend this to use the tools from ExpressionClasses.cpp + +struct OptimiserState +{ + AssemblyItems const& items; + size_t i; + std::back_insert_iterator<AssemblyItems> out; +}; + +template <class Method, size_t Arguments> +struct ApplyRule +{ +}; +template <class Method> +struct ApplyRule<Method, 3> +{ + static bool applyRule(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out) + { + return Method::applySimple(_in[0], _in[1], _in[2], _out); + } +}; +template <class Method> +struct ApplyRule<Method, 2> +{ + static bool applyRule(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out) + { + return Method::applySimple(_in[0], _in[1], _out); + } +}; +template <class Method> +struct ApplyRule<Method, 1> +{ + static bool applyRule(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out) + { + return Method::applySimple(_in[0], _out); + } +}; + +template <class Method, size_t WindowSize> +struct SimplePeepholeOptimizerMethod +{ + static bool apply(OptimiserState& _state) + { + if ( + _state.i + WindowSize <= _state.items.size() && + ApplyRule<Method, WindowSize>::applyRule(_state.items.begin() + _state.i, _state.out) + ) + { + _state.i += WindowSize; + return true; + } + else + return false; + } +}; + +struct Identity: SimplePeepholeOptimizerMethod<Identity, 1> +{ + static bool applySimple(AssemblyItem const& _item, std::back_insert_iterator<AssemblyItems> _out) + { + *_out = _item; + return true; + } +}; + +struct PushPop: SimplePeepholeOptimizerMethod<PushPop, 2> +{ + static bool applySimple(AssemblyItem const& _push, AssemblyItem const& _pop, std::back_insert_iterator<AssemblyItems>) + { + auto t = _push.type(); + return _pop == Instruction::POP && ( + SemanticInformation::isDupInstruction(_push) || + t == Push || t == PushString || t == PushTag || t == PushSub || + t == PushSubSize || t == PushProgramSize || t == PushData || t == PushLibraryAddress + ); + } +}; + +struct OpPop: SimplePeepholeOptimizerMethod<OpPop, 2> +{ + static bool applySimple( + AssemblyItem const& _op, + AssemblyItem const& _pop, + std::back_insert_iterator<AssemblyItems> _out + ) + { + if (_pop == Instruction::POP && _op.type() == Operation) + { + Instruction instr = _op.instruction(); + if (instructionInfo(instr).ret == 1 && !instructionInfo(instr).sideEffects) + { + for (int j = 0; j < instructionInfo(instr).args; j++) + *_out = Instruction::POP; + return true; + } + } + return false; + } +}; + +struct DoubleSwap: SimplePeepholeOptimizerMethod<DoubleSwap, 2> +{ + static size_t applySimple(AssemblyItem const& _s1, AssemblyItem const& _s2, std::back_insert_iterator<AssemblyItems>) + { + return _s1 == _s2 && SemanticInformation::isSwapInstruction(_s1); + } +}; + +struct JumpToNext: SimplePeepholeOptimizerMethod<JumpToNext, 3> +{ + static size_t applySimple( + AssemblyItem const& _pushTag, + AssemblyItem const& _jump, + AssemblyItem const& _tag, + std::back_insert_iterator<AssemblyItems> _out + ) + { + if ( + _pushTag.type() == PushTag && + (_jump == Instruction::JUMP || _jump == Instruction::JUMPI) && + _tag.type() == Tag && + _pushTag.data() == _tag.data() + ) + { + if (_jump == Instruction::JUMPI) + *_out = AssemblyItem(Instruction::POP, _jump.location()); + *_out = _tag; + return true; + } + else + return false; + } +}; + +struct TagConjunctions: SimplePeepholeOptimizerMethod<TagConjunctions, 3> +{ + static bool applySimple( + AssemblyItem const& _pushTag, + AssemblyItem const& _pushConstant, + AssemblyItem const& _and, + std::back_insert_iterator<AssemblyItems> _out + ) + { + if ( + _pushTag.type() == PushTag && + _and == Instruction::AND && + _pushConstant.type() == Push && + (_pushConstant.data() & u256(0xFFFFFFFF)) == u256(0xFFFFFFFF) + ) + { + *_out = _pushTag; + return true; + } + else + return false; + } +}; + +/// Removes everything after a JUMP (or similar) until the next JUMPDEST. +struct UnreachableCode +{ + static bool apply(OptimiserState& _state) + { + auto it = _state.items.begin() + _state.i; + auto end = _state.items.end(); + if (it == end) + return false; + if ( + it[0] != Instruction::JUMP && + it[0] != Instruction::RETURN && + it[0] != Instruction::STOP && + it[0] != Instruction::SUICIDE + ) + return false; + + size_t i = 1; + while (it + i != end && it[i].type() != Tag) + i++; + if (i > 1) + { + *_state.out = it[0]; + _state.i += i; + return true; + } + else + return false; + } +}; + +void applyMethods(OptimiserState&) +{ + assertThrow(false, OptimizerException, "Peephole optimizer failed to apply identity."); +} + +template <typename Method, typename... OtherMethods> +void applyMethods(OptimiserState& _state, Method, OtherMethods... _other) +{ + if (!Method::apply(_state)) + applyMethods(_state, _other...); +} + +bool PeepholeOptimiser::optimise() +{ + OptimiserState state {m_items, 0, std::back_inserter(m_optimisedItems)}; + while (state.i < m_items.size()) + applyMethods(state, PushPop(), OpPop(), DoubleSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity()); + if (m_optimisedItems.size() < m_items.size()) + { + m_items = std::move(m_optimisedItems); + return true; + } + else + return false; + +} diff --git a/libevmasm/PeepholeOptimiser.h b/libevmasm/PeepholeOptimiser.h new file mode 100644 index 00000000..a74cc8b3 --- /dev/null +++ b/libevmasm/PeepholeOptimiser.h @@ -0,0 +1,54 @@ +/* + 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/>. +*/ +/** + * @file PeepholeOptimiser.h + * Performs local optimising code changes to assembly. + */ +#pragma once + +#include <vector> +#include <cstddef> +#include <iterator> + +namespace dev +{ +namespace eth +{ +class AssemblyItem; +using AssemblyItems = std::vector<AssemblyItem>; + +class PeepholeOptimisationMethod +{ +public: + virtual size_t windowSize() const; + virtual bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out); +}; + +class PeepholeOptimiser +{ +public: + explicit PeepholeOptimiser(AssemblyItems& _items): m_items(_items) {} + + bool optimise(); + +private: + AssemblyItems& m_items; + AssemblyItems m_optimisedItems; +}; + +} +} diff --git a/libevmasm/SemanticInformation.cpp b/libevmasm/SemanticInformation.cpp index ea579b83..23a00d95 100644 --- a/libevmasm/SemanticInformation.cpp +++ b/libevmasm/SemanticInformation.cpp @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file SemanticInformation.cpp diff --git a/libevmasm/SemanticInformation.h b/libevmasm/SemanticInformation.h index 0eda5ed5..5b02061f 100644 --- a/libevmasm/SemanticInformation.h +++ b/libevmasm/SemanticInformation.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @file SemanticInformation.h diff --git a/libevmasm/SourceLocation.h b/libevmasm/SourceLocation.h index 05304d14..b42c3aa9 100644 --- a/libevmasm/SourceLocation.h +++ b/libevmasm/SourceLocation.h @@ -1,18 +1,18 @@ /* - This file is part of cpp-ethereum. + This file is part of solidity. - cpp-ethereum is free software: you can redistribute it and/or modify + 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. - cpp-ethereum is distributed in the hope that it will be useful, + 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 cpp-ethereum. If not, see <http://www.gnu.org/licenses/>. + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @author Lefteris Karapetsas <lefteris@ethdev.com> @@ -55,7 +55,11 @@ struct SourceLocation return *this; } - bool operator==(SourceLocation const& _other) const { return start == _other.start && end == _other.end;} + bool operator==(SourceLocation const& _other) const + { + return start == _other.start && end == _other.end && + ((!sourceName && !_other.sourceName) || (sourceName && _other.sourceName && *sourceName == *_other.sourceName)); + } bool operator!=(SourceLocation const& _other) const { return !operator==(_other); } inline bool operator<(SourceLocation const& _other) const; inline bool contains(SourceLocation const& _other) const; @@ -79,20 +83,21 @@ inline std::ostream& operator<<(std::ostream& _out, SourceLocation const& _locat bool SourceLocation::operator<(SourceLocation const& _other) const { if (!sourceName || !_other.sourceName) - return int(!!sourceName) < int(!!_other.sourceName); - return make_tuple(*sourceName, start, end) < make_tuple(*_other.sourceName, _other.start, _other.end); + return std::make_tuple(int(!!sourceName), start, end) < std::make_tuple(int(!!_other.sourceName), _other.start, _other.end); + else + return std::make_tuple(*sourceName, start, end) < std::make_tuple(*_other.sourceName, _other.start, _other.end); } bool SourceLocation::contains(SourceLocation const& _other) const { - if (isEmpty() || _other.isEmpty() || !sourceName || !_other.sourceName || *sourceName != *_other.sourceName) + if (isEmpty() || _other.isEmpty() || ((!sourceName || !_other.sourceName || *sourceName != *_other.sourceName) && (sourceName || _other.sourceName))) return false; return start <= _other.start && _other.end <= end; } bool SourceLocation::intersects(SourceLocation const& _other) const { - if (isEmpty() || _other.isEmpty() || !sourceName || !_other.sourceName || *sourceName != *_other.sourceName) + if (isEmpty() || _other.isEmpty() || ((!sourceName || !_other.sourceName || *sourceName != *_other.sourceName) && (sourceName || _other.sourceName))) return false; return _other.start < end && start < _other.end; } |