From ced4720faa63eb7a1842eb1dbc17522a1ec458fd Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 12 May 2015 16:16:44 +0200 Subject: Unify blocks with shared code. --- Assembly.cpp | 10 ++++++ AssemblyItem.h | 2 ++ BlockDeduplicator.cpp | 93 +++++++++++++++++++++++++++++++++++++++++++++++++++ BlockDeduplicator.h | 69 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 174 insertions(+) create mode 100644 BlockDeduplicator.cpp create mode 100644 BlockDeduplicator.h diff --git a/Assembly.cpp b/Assembly.cpp index abcd4451..1011392b 100644 --- a/Assembly.cpp +++ b/Assembly.cpp @@ -24,6 +24,7 @@ #include #include #include +#include #include using namespace std; using namespace dev; @@ -348,8 +349,17 @@ Assembly& Assembly::optimise(bool _enable) copy(orig, iter, back_inserter(optimisedItems)); } } + if (optimisedItems.size() < m_items.size()) + { m_items = move(optimisedItems); + count++; + } + + // This only modifies PushTags, we have to run again to actually remove code. + BlockDeduplicator dedup(m_items); + if (dedup.deduplicate()) + count++; } } diff --git a/AssemblyItem.h b/AssemblyItem.h index 6f2a65de..b3012a7e 100644 --- a/AssemblyItem.h +++ b/AssemblyItem.h @@ -68,6 +68,8 @@ public: /// @returns true iff the type and data of the items are equal. bool operator==(AssemblyItem const& _other) const { return m_type == _other.m_type && m_data == _other.m_data; } bool operator!=(AssemblyItem const& _other) const { return !operator==(_other); } + /// Less-than operator compatible with operator==. + bool operator<(AssemblyItem const& _other) const { return std::tie(m_type, m_data) < std::tie(_other.m_type, _other.m_data); } /// @returns an upper bound for the number of bytes required by this item, assuming that /// the value of a jump tag takes @a _addressLength bytes. diff --git a/BlockDeduplicator.cpp b/BlockDeduplicator.cpp new file mode 100644 index 00000000..ca4f7e21 --- /dev/null +++ b/BlockDeduplicator.cpp @@ -0,0 +1,93 @@ +/* + This file is part of cpp-ethereum. + + cpp-ethereum 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, + 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 . +*/ +/** + * @file BlockDeduplicator.cpp + * @author Christian + * @date 2015 + * Unifies basic blocks that share content. + */ + +#include +#include +#include +#include + +#include + +using namespace std; +using namespace dev; +using namespace dev::eth; + + +bool BlockDeduplicator::deduplicate() +{ + // Compares indices based on the suffix that starts there, ignoring tags and stopping at + // opcodes that stop the control flow. + function comparator = [&](size_t _i, size_t _j) + { + if (_i == _j) + return false; + + BlockIterator first(m_items.begin() + _i, m_items.end()); + BlockIterator second(m_items.begin() + _j, m_items.end()); + BlockIterator end(m_items.end(), m_items.end()); + + if (first != end && (*first).type() == Tag) + ++first; + if (second != end && (*second).type() == Tag) + ++second; + + return std::lexicographical_compare(first, end, second, end); + }; + + set> blocksSeen(comparator); + map tagReplacement; + for (size_t i = 0; i < m_items.size(); ++i) + { + if (m_items.at(i).type() != Tag) + continue; + auto it = blocksSeen.find(i); + if (it == blocksSeen.end()) + blocksSeen.insert(i); + else + tagReplacement[m_items.at(i).data()] = m_items.at(*it).data(); + } + + bool ret = false; + for (AssemblyItem& item: m_items) + if (item.type() == PushTag && tagReplacement.count(item.data())) + { + ret = true; + item.setData(tagReplacement.at(item.data())); + } + return ret; +} + +BlockDeduplicator::BlockIterator& BlockDeduplicator::BlockIterator::operator++() +{ + if (it == end) + return *this; + if (SemanticInformation::altersControlFlow(*it) && *it != AssemblyItem(eth::Instruction::JUMPI)) + it = end; + else + { + ++it; + while (it != end && it->type() == Tag) + ++it; + } + return *this; +} diff --git a/BlockDeduplicator.h b/BlockDeduplicator.h new file mode 100644 index 00000000..8a82a1ed --- /dev/null +++ b/BlockDeduplicator.h @@ -0,0 +1,69 @@ +/* + This file is part of cpp-ethereum. + + cpp-ethereum 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, + 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 . +*/ +/** + * @file BlockDeduplicator.h + * @author Christian + * @date 2015 + * Unifies basic blocks that share content. + */ + +#pragma once + +#include +#include +#include + +namespace dev +{ +namespace eth +{ + +class AssemblyItem; +using AssemblyItems = std::vector; + +/** + * Optimizer class to be used to unify blocks that share content. + * Modifies the passed vector in place. + */ +class BlockDeduplicator +{ +public: + BlockDeduplicator(AssemblyItems& _items): m_items(_items) {} + /// @returns true if something was changed + bool deduplicate(); + +private: + /// Iterator that skips tags skips to the end if (all branches of) the control + /// flow does not continue to the next instruction. + struct BlockIterator: std::iterator + { + public: + BlockIterator(AssemblyItems::const_iterator _it, AssemblyItems::const_iterator _end): + it(_it), end(_end) { } + BlockIterator& operator++(); + bool operator==(BlockIterator const& _other) const { return it == _other.it; } + bool operator!=(BlockIterator const& _other) const { return it != _other.it; } + AssemblyItem const& operator*() const { return *it; } + AssemblyItems::const_iterator it; + AssemblyItems::const_iterator end; + }; + + AssemblyItems& m_items; +}; + +} +} -- cgit From 79f8a224ef848d30af3743f5f06c74b45ce1da5e Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 12 May 2015 17:00:23 +0200 Subject: Removed unnecessary include. --- BlockDeduplicator.cpp | 2 -- 1 file changed, 2 deletions(-) diff --git a/BlockDeduplicator.cpp b/BlockDeduplicator.cpp index ca4f7e21..eadbe1b4 100644 --- a/BlockDeduplicator.cpp +++ b/BlockDeduplicator.cpp @@ -26,8 +26,6 @@ #include #include -#include - using namespace std; using namespace dev; using namespace dev::eth; -- cgit