Merge remote-tracking branch 'origin/develop' into release

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)
 	{