Follow highest gas usage only for gas estimation.

3 files changed, 25 insertions, 5 deletions

diff --git a/Changelog.md b/Changelog.md
index 37e0b0a1..87669a62 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -3,6 +3,7 @@
 Features:
  * Build System: Update internal dependency of jsoncpp to 1.8.4, which introduces more strictness and reduces memory usage.
  * Code Generator: Use native shift instructions on target Constantinople.
+ * Gas Estimator: Only explore paths with higher gas costs. This reduces accuracy but greatly improves the speed of gas estimation.
  * Optimizer: Remove unnecessary masking of the result of known short instructions (``ADDRESS``, ``CALLER``, ``ORIGIN`` and ``COINBASE``).
  * Type Checker: Deprecate the ``years`` unit denomination and raise a warning for it (or an error as experimental 0.5.0 feature).
  * Type Checker: Make literals (without explicit type casting) an error for tight packing as experimental 0.5.0 feature.
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;