From 1fdb7a1536209409010c6b6a69aedfce03c8372d Mon Sep 17 00:00:00 2001 From: Gav Wood Date: Tue, 27 May 2014 18:51:10 +0200 Subject: Pinhole optimise working fairly well... --- Assembly.cpp | 80 +++++++++++++++++++++++++++++++++++++++++++++------------- Assembly.h | 1 + CodeFragment.h | 7 +++-- Compiler.cpp | 14 +++++++--- Compiler.h | 4 +-- 5 files changed, 80 insertions(+), 26 deletions(-) diff --git a/Assembly.cpp b/Assembly.cpp index 053de61a..1d9cb4bc 100644 --- a/Assembly.cpp +++ b/Assembly.cpp @@ -186,6 +186,9 @@ inline bool matches(AssemblyItemsConstRef _a, AssemblyItemsConstRef _b) return true; } +struct OptimiserChannel: public LogChannel { static const char* name() { return "OPT"; } static const int verbosity = 12; }; +#define copt eth::LogOutputStream() + void Assembly::optimise() { map> c_simple = @@ -210,7 +213,7 @@ void Assembly::optimise() std::vector>> rules = { { { Push, Instruction::POP }, [](AssemblyItemsConstRef) -> AssemblyItems { return {}; } }, - { { Push, PushTag, Instruction::JUMPI }, [](AssemblyItemsConstRef m) -> AssemblyItems { return m[0].data() ? AssemblyItems({ m[1], Instruction::JUMP }) : AssemblyItems(); } }, + { { Push, PushTag, Instruction::JUMPI }, [](AssemblyItemsConstRef m) -> AssemblyItems { if (m[0].data()) return { m[1], Instruction::JUMP }; else return {}; } }, }; for (auto const& i: c_simple) @@ -219,19 +222,16 @@ void Assembly::optimise() { rules.push_back({ { Push, Push, i.first }, [&](AssemblyItemsConstRef m) -> AssemblyItems { return { i.second(m[1].data(), m[0].data()) }; } }); rules.push_back({ { Push, i.first, Push, i.first }, [&](AssemblyItemsConstRef m) -> AssemblyItems { return { i.second(m[2].data(), m[0].data()), i.first }; } }); - rules.push_back({ { PushTag, Instruction::JUMP, Tag }, [&](AssemblyItemsConstRef m) -> AssemblyItems - { - if (m[0].m_data == m[2].m_data) - return {}; - else - return m.toVector(); - }}); + rules.push_back({ { PushTag, Instruction::JUMP, Tag }, [&](AssemblyItemsConstRef m) -> AssemblyItems { if (m[0].m_data == m[2].m_data) return {}; else return m.toVector(); }}); } + copt << *this; + unsigned total = 0; for (unsigned count = 1; count > 0; total += count) { count = 0; + map tags; for (unsigned i = 0; i < m_items.size(); ++i) { for (auto const& r: rules) @@ -242,23 +242,64 @@ void Assembly::optimise() auto rw = r.second(vr); if (rw.size() < vr.size()) { - cnote << vr << "matches" << AssemblyItemsConstRef(&r.first) << "becomes..."; + copt << vr << "matches" << AssemblyItemsConstRef(&r.first) << "becomes..."; for (unsigned j = 0; j < vr.size(); ++j) if (j < rw.size()) m_items[i + j] = rw[j]; else m_items.erase(m_items.begin() + i + rw.size()); - cnote << AssemblyItemsConstRef(&rw); + copt << AssemblyItemsConstRef(&rw); count++; + copt << "Now:\n" << m_items; } } } + if (m_items[i].type() == Operation && m_items[i].data() == (byte)Instruction::JUMP) + { + bool o = false; + while (m_items.size() > i + 1 && m_items[i + 1].type() != Tag) + { + m_items.erase(m_items.begin() + i + 1); + o = true; + } + if (o) + { + copt << "Jump with no tag. Now:\n" << m_items; + ++count; + } + } } - } - // TODO: find all unused tags, for all those that have an unconditional jump immediately before, remove code between the tag and the next used tag (removing unused tags from the todo along the way). + for (unsigned i = 0; i < m_items.size(); ++i) + if (m_items[i].type() == Tag) + tags.insert(make_pair(m_items[i].data(), i)); + + for (auto const& i: m_items) + if (i.type() == PushTag) + tags.erase(i.data()); - cnote << total << " optimisations done."; + if (tags.size()) + { + auto t = *tags.begin(); + unsigned i = t.second; + if (i && m_items[i - 1].type() == Operation && m_items[i - 1].data() == (byte)Instruction::JUMP) + while (i < m_items.size() && (m_items[i].type() != Tag || tags.count(m_items[i].data()))) + { + if (m_items[i].type() == Tag && tags.count(m_items[i].data())) + tags.erase(m_items[i].data()); + m_items.erase(m_items.begin() + i); + } + else + { + m_items.erase(m_items.begin() + i); + tags.erase(t.first); + } + copt << "Unused tag. Now:\n" << m_items; + ++count; + } + } + + copt << total << " optimisations done."; } bytes Assembly::assemble() const @@ -333,13 +374,16 @@ bytes Assembly::assemble() const for (auto const& i: m_data) { auto its = dataRef.equal_range(i.first); - for (auto it = its.first; it != its.second; ++it) + if (its.first != its.second) { - bytesRef r(ret.data() + it->second, bytesPerTag); - toBigEndian(ret.size(), r); + for (auto it = its.first; it != its.second; ++it) + { + bytesRef r(ret.data() + it->second, bytesPerTag); + toBigEndian(ret.size(), r); + } + for (auto b: i.second) + ret.push_back(b); } - for (auto b: i.second) - ret.push_back(b); } } return ret; diff --git a/Assembly.h b/Assembly.h index 2efff943..a3bf998d 100644 --- a/Assembly.h +++ b/Assembly.h @@ -62,6 +62,7 @@ typedef std::vector AssemblyItems; typedef vector_ref AssemblyItemsConstRef; std::ostream& operator<<(std::ostream& _out, AssemblyItemsConstRef _i); +inline std::ostream& operator<<(std::ostream& _out, AssemblyItems const& _i) { return operator<<(_out, AssemblyItemsConstRef(&_i)); } class Assembly { diff --git a/CodeFragment.h b/CodeFragment.h index 6935a111..2c6f2cce 100644 --- a/CodeFragment.h +++ b/CodeFragment.h @@ -43,10 +43,13 @@ public: static CodeFragment compile(std::string const& _src, CompilerState& _s); /// Consolidates data and compiles code. - bytes code() { m_asm.optimise(); return m_asm.assemble(); } + bytes code() const { return m_asm.assemble(); } /// Consolidates data and compiles code. - std::string assembly() { m_asm.optimise(); return m_asm.out(); } + std::string assembly() const { return m_asm.out(); } + + /// Optimise the code. Best do this just before calling code() or assembly(). + void optimise() { m_asm.optimise(); } private: template void error() const { throw T(); } diff --git a/Compiler.cpp b/Compiler.cpp index 777bb72d..cd326341 100644 --- a/Compiler.cpp +++ b/Compiler.cpp @@ -27,12 +27,15 @@ using namespace std; using namespace eth; -bytes eth::compileLLL(string const& _src, vector* _errors) +bytes eth::compileLLL(string const& _src, bool _opt, vector* _errors) { try { CompilerState cs; - bytes ret = CodeFragment::compile(_src, cs).code(); + auto f = CodeFragment::compile(_src, cs); + if (_opt) + f.optimise(); + bytes ret = f.code(); for (auto i: cs.treesToKill) killBigints(i); return ret; @@ -50,12 +53,15 @@ bytes eth::compileLLL(string const& _src, vector* _errors) return bytes(); } -std::string eth::compileLLLToAsm(std::string const& _src, std::vector* _errors) +std::string eth::compileLLLToAsm(std::string const& _src, bool _opt, std::vector* _errors) { try { CompilerState cs; - string ret = CodeFragment::compile(_src, cs).assembly(); + auto f = CodeFragment::compile(_src, cs); + if (_opt) + f.optimise(); + string ret = f.assembly(); for (auto i: cs.treesToKill) killBigints(i); return ret; diff --git a/Compiler.h b/Compiler.h index 9dd5fc29..395d7909 100644 --- a/Compiler.h +++ b/Compiler.h @@ -29,8 +29,8 @@ namespace eth { std::string parseLLL(std::string const& _src); -std::string compileLLLToAsm(std::string const& _src, std::vector* _errors = nullptr); -bytes compileLLL(std::string const& _src, std::vector* _errors = nullptr); +std::string compileLLLToAsm(std::string const& _src, bool _opt = true, std::vector* _errors = nullptr); +bytes compileLLL(std::string const& _src, bool _opt = true, std::vector* _errors = nullptr); } -- cgit