Merge pull request #4148 from ethereum/develop

Merge develop into release for 0.4.24

9 files changed, 69 insertions, 19 deletions

diff --git a/libevmasm/Assembly.h b/libevmasm/Assembly.h
index 367c6daa..1ed9b859 100644
--- a/libevmasm/Assembly.h
+++ b/libevmasm/Assembly.h
@@ -47,8 +47,8 @@ class Assembly
 public:
 	Assembly() {}
 
-	AssemblyItem newTag() { return AssemblyItem(Tag, m_usedTags++); }
-	AssemblyItem newPushTag() { return AssemblyItem(PushTag, m_usedTags++); }
+	AssemblyItem newTag() { assertThrow(m_usedTags < 0xffffffff, AssemblyException, ""); return AssemblyItem(Tag, m_usedTags++); }
+	AssemblyItem newPushTag() { assertThrow(m_usedTags < 0xffffffff, AssemblyException, ""); return AssemblyItem(PushTag, m_usedTags++); }
 	/// Returns a tag identified by the given name. Creates it if it does not yet exist.
 	AssemblyItem namedTag(std::string const& _name);
 	AssemblyItem newData(bytes const& _data) { h256 h(dev::keccak256(asString(_data))); m_data[h] = _data; return AssemblyItem(PushData, h); }
diff --git a/libevmasm/AssemblyItem.cpp b/libevmasm/AssemblyItem.cpp
index 5af618ff..a3a4d6b6 100644
--- a/libevmasm/AssemblyItem.cpp
+++ b/libevmasm/AssemblyItem.cpp
@@ -26,27 +26,35 @@ using namespace std;
 using namespace dev;
 using namespace dev::eth;
 
+static_assert(sizeof(size_t) <= 8, "size_t must be at most 64-bits wide");
+
 AssemblyItem AssemblyItem::toSubAssemblyTag(size_t _subId) const
 {
 	assertThrow(data() < (u256(1) << 64), Exception, "Tag already has subassembly set.");
-
 	assertThrow(m_type == PushTag || m_type == Tag, Exception, "");
+	size_t tag = size_t(u256(data()) & 0xffffffffffffffffULL);
 	AssemblyItem r = *this;
 	r.m_type = PushTag;
-	r.setPushTagSubIdAndTag(_subId, size_t(data()));
+	r.setPushTagSubIdAndTag(_subId, tag);
 	return r;
 }
 
 pair<size_t, size_t> AssemblyItem::splitForeignPushTag() const
 {
 	assertThrow(m_type == PushTag || m_type == Tag, Exception, "");
-	return make_pair(size_t((data()) / (u256(1) << 64)) - 1, size_t(data()));
+	u256 combined = u256(data());
+	size_t subId = size_t((combined >> 64) - 1);
+	size_t tag = size_t(combined & 0xffffffffffffffffULL);
+	return make_pair(subId, tag);
 }
 
 void AssemblyItem::setPushTagSubIdAndTag(size_t _subId, size_t _tag)
 {
 	assertThrow(m_type == PushTag || m_type == Tag, Exception, "");
-	setData(_tag + (u256(_subId + 1) << 64));
+	u256 data = _tag;
+	if (_subId != size_t(-1))
+		data |= (u256(_subId) + 1) << 64;
+	setData(data);
 }
 
 unsigned AssemblyItem::bytesRequired(unsigned _addressLength) const
diff --git a/libevmasm/CMakeLists.txt b/libevmasm/CMakeLists.txt
index cfd59dff..86192c1b 100644
--- a/libevmasm/CMakeLists.txt
+++ b/libevmasm/CMakeLists.txt
@@ -2,4 +2,4 @@ file(GLOB sources "*.cpp")
 file(GLOB headers "*.h")
 
 add_library(evmasm ${sources} ${headers})
-target_link_libraries(evmasm PUBLIC jsoncpp devcore)
+target_link_libraries(evmasm PUBLIC devcore)
diff --git a/libevmasm/ConstantOptimiser.h b/libevmasm/ConstantOptimiser.h
index 9b60b26b..f0deb387 100644
--- a/libevmasm/ConstantOptimiser.h
+++ b/libevmasm/ConstantOptimiser.h
@@ -67,6 +67,7 @@ public:
 
 	explicit ConstantOptimisationMethod(Params const& _params, u256 const& _value):
 		m_params(_params), m_value(_value) {}
+	virtual ~ConstantOptimisationMethod() = default;
 	virtual bigint gasNeeded() const = 0;
 	/// Executes the method, potentially appending to the assembly and returns a vector of
 	/// assembly items the constant should be relpaced with in one sweep.
diff --git a/libevmasm/Instruction.h b/libevmasm/Instruction.h
index be788ddb..dc116f88 100644
--- a/libevmasm/Instruction.h
+++ b/libevmasm/Instruction.h
@@ -39,7 +39,7 @@ enum class Instruction: uint8_t
 {
 	STOP = 0x00,		///< halts execution
 	ADD,				///< addition operation
-	MUL,				///< mulitplication operation
+	MUL,				///< multiplication operation
 	SUB,				///< subtraction operation
 	DIV,				///< integer division operation
 	SDIV,				///< signed integer division operation
@@ -50,11 +50,11 @@ enum class Instruction: uint8_t
 	EXP,				///< exponential operation
 	SIGNEXTEND,			///< extend length of signed integer
 
-	LT = 0x10,			///< less-than comparision
-	GT,					///< greater-than comparision
-	SLT,				///< signed less-than comparision
-	SGT,				///< signed greater-than comparision
-	EQ,					///< equality comparision
+	LT = 0x10,			///< less-than comparison
+	GT,					///< greater-than comparison
+	SLT,				///< signed less-than comparison
+	SGT,				///< signed greater-than comparison
+	EQ,					///< equality comparison
 	ISZERO,				///< simple not operator
 	AND,				///< bitwise AND operation
 	OR,					///< bitwise OR operation
@@ -293,7 +293,7 @@ struct InstructionInfo
 /// Information on all the instructions.
 InstructionInfo instructionInfo(Instruction _inst);
 
-/// check whether instructions exists
+/// check whether instructions exists.
 bool isValidInstruction(Instruction _inst);
 
 /// Convert from string mnemonic to Instruction type.
diff --git a/libevmasm/PathGasMeter.cpp b/libevmasm/PathGasMeter.cpp
index 3fe682b7..cdadba76 100644
--- a/libevmasm/PathGasMeter.cpp
+++ b/libevmasm/PathGasMeter.cpp
@@ -43,7 +43,7 @@ GasMeter::GasConsumption PathGasMeter::estimateMax(
 	auto path = unique_ptr<GasPath>(new GasPath());
 	path->index = _startIndex;
 	path->state = _state->copy();
-	m_queue.push_back(move(path));
+	queue(move(path));
 
 	GasMeter::GasConsumption gas;
 	while (!m_queue.empty() && !gas.isInfinite)
@@ -51,12 +51,23 @@ GasMeter::GasConsumption PathGasMeter::estimateMax(
 	return gas;
 }
 
+void PathGasMeter::queue(std::unique_ptr<GasPath>&& _newPath)
+{
+	if (
+		m_highestGasUsagePerJumpdest.count(_newPath->index) &&
+		_newPath->gas < m_highestGasUsagePerJumpdest.at(_newPath->index)
+	)
+		return;
+	m_highestGasUsagePerJumpdest[_newPath->index] = _newPath->gas;
+	m_queue[_newPath->index] = move(_newPath);
+}
+
 GasMeter::GasConsumption PathGasMeter::handleQueueItem()
 {
 	assertThrow(!m_queue.empty(), OptimizerException, "");
 
-	unique_ptr<GasPath> path = move(m_queue.back());
-	m_queue.pop_back();
+	unique_ptr<GasPath> path = move(m_queue.rbegin()->second);
+	m_queue.erase(--m_queue.end());
 
 	shared_ptr<KnownState> state = path->state;
 	GasMeter meter(state, m_evmVersion, path->largestMemoryAccess);
@@ -117,7 +128,7 @@ GasMeter::GasConsumption PathGasMeter::handleQueueItem()
 			newPath->largestMemoryAccess = meter.largestMemoryAccess();
 			newPath->state = state->copy();
 			newPath->visitedJumpdests = path->visitedJumpdests;
-			m_queue.push_back(move(newPath));
+			queue(move(newPath));
 		}
 
 		if (branchStops)
diff --git a/libevmasm/PathGasMeter.h b/libevmasm/PathGasMeter.h
index 2527d7fb..9537b176 100644
--- a/libevmasm/PathGasMeter.h
+++ b/libevmasm/PathGasMeter.h
@@ -58,9 +58,17 @@ public:
 	GasMeter::GasConsumption estimateMax(size_t _startIndex, std::shared_ptr<KnownState> const& _state);
 
 private:
+	/// Adds a new path item to the queue, but only if we do not already have
+	/// a higher gas usage at that point.
+	/// This is not exact as different state might influence higher gas costs at a later
+	/// point in time, but it greatly reduces computational overhead.
+	void queue(std::unique_ptr<GasPath>&& _newPath);
 	GasMeter::GasConsumption handleQueueItem();
 
-	std::vector<std::unique_ptr<GasPath>> m_queue;
+	/// Map of jumpdest -> gas path, so not really a queue. We only have one queued up
+	/// item per jumpdest, because of the behaviour of `queue` above.
+	std::map<size_t, std::unique_ptr<GasPath>> m_queue;
+	std::map<size_t, GasMeter::GasConsumption> m_highestGasUsagePerJumpdest;
 	std::map<u256, size_t> m_tagPositions;
 	AssemblyItems const& m_items;
 	solidity::EVMVersion m_evmVersion;
diff --git a/libevmasm/PeepholeOptimiser.h b/libevmasm/PeepholeOptimiser.h
index a74cc8b3..a651143d 100644
--- a/libevmasm/PeepholeOptimiser.h
+++ b/libevmasm/PeepholeOptimiser.h
@@ -34,6 +34,7 @@ using AssemblyItems = std::vector<AssemblyItem>;
 class PeepholeOptimisationMethod
 {
 public:
+	virtual ~PeepholeOptimisationMethod() = default;
 	virtual size_t windowSize() const;
 	virtual bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out);
 };
@@ -42,6 +43,7 @@ class PeepholeOptimiser
 {
 public:
 	explicit PeepholeOptimiser(AssemblyItems& _items): m_items(_items) {}
+	virtual ~PeepholeOptimiser() = default;
 
 	bool optimise();
 
diff --git a/libevmasm/RuleList.h b/libevmasm/RuleList.h
index abcf170c..2b7da01b 100644
--- a/libevmasm/RuleList.h
+++ b/libevmasm/RuleList.h
@@ -174,6 +174,26 @@ std::vector<SimplificationRule<Pattern>> simplificationRuleList(
 		});
 	}
 
+	for (auto const& op: std::vector<Instruction>{
+		Instruction::ADDRESS,
+		Instruction::CALLER,
+		Instruction::ORIGIN,
+		Instruction::COINBASE
+	})
+	{
+		u256 const mask = (u256(1) << 160) - 1;
+		rules.push_back({
+			{Instruction::AND, {{op, mask}}},
+			[=]() -> Pattern { return op; },
+			false
+		});
+		rules.push_back({
+			{Instruction::AND, {{mask, op}}},
+			[=]() -> Pattern { return op; },
+			false
+		});
+	}
+
 	// Double negation of opcodes with boolean result
 	for (auto const& op: std::vector<Instruction>{
 		Instruction::EQ,