diff options
Diffstat (limited to 'libevmasm/Assembly.cpp')
| -rw-r--r-- | libevmasm/Assembly.cpp | 166 |
1 files changed, 108 insertions, 58 deletions
diff --git a/libevmasm/Assembly.cpp b/libevmasm/Assembly.cpp index e881c1e2..a3037456 100644 --- a/libevmasm/Assembly.cpp +++ b/libevmasm/Assembly.cpp @@ -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,41 +318,67 @@ 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); + if (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. + auto end = iter; + while (end != m_items.end()) + if (SemanticInformation::altersControlFlow(*end++)) + break; + KnownState emptyState; CommonSubexpressionEliminator eliminator(emptyState); - auto iter = m_items.begin() + block.begin; - auto const end = m_items.begin() + block.end; - while (iter < end) + auto blockIter = iter; + auto const blockEnd = end; + while (blockIter < blockEnd) { - auto orig = iter; - iter = eliminator.feedItems(iter, end); + auto orig = blockIter; + blockIter = eliminator.feedItems(blockIter, blockEnd); bool shouldReplace = false; AssemblyItems optimisedChunk; try { optimisedChunk = eliminator.getOptimizedItems(); - shouldReplace = (optimisedChunk.size() < size_t(iter - orig)); + shouldReplace = (optimisedChunk.size() < size_t(blockIter - orig)); } catch (StackTooDeepException const&) { @@ -361,10 +397,10 @@ Assembly& Assembly::optimise(bool _enable, bool _isCreation, size_t _runs) optimisedItems += optimisedChunk; } else - copy(orig, iter, back_inserter(optimisedItems)); + copy(orig, blockIter, back_inserter(optimisedItems)); } + iter = end; } - if (optimisedItems.size() < m_items.size()) { m_items = move(optimisedItems); @@ -373,17 +409,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 +425,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 +455,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 +488,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 +504,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 +526,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 +549,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) { |