Path gas meter.

5 files changed, 207 insertions, 6 deletions

diff --git a/GasMeter.cpp b/GasMeter.cpp
index a8dc4dd5..3749e635 100644
--- a/GasMeter.cpp
+++ b/GasMeter.cpp
@@ -29,12 +29,13 @@ using namespace dev::eth;
 
 GasMeter::GasConsumption& GasMeter::GasConsumption::operator+=(GasConsumption const& _other)
 {
-	isInfinite = isInfinite || _other.isInfinite;
+	if (_other.isInfinite && !isInfinite)
+		*this = infinite();
 	if (isInfinite)
 		return *this;
 	bigint v = bigint(value) + _other.value;
 	if (v > std::numeric_limits<u256>::max())
-		isInfinite = true;
+		*this = infinite();
 	else
 		value = u256(v);
 	return *this;
diff --git a/GasMeter.h b/GasMeter.h
index ab6d5613..95593b56 100644
--- a/GasMeter.h
+++ b/GasMeter.h
@@ -22,6 +22,7 @@
 #pragma once
 
 #include <ostream>
+#include <tuple>
 #include <libevmasm/ExpressionClasses.h>
 #include <libevmasm/AssemblyItem.h>
 
@@ -46,20 +47,25 @@ public:
 		GasConsumption(u256 _value = 0, bool _infinite = false): value(_value), isInfinite(_infinite) {}
 		static GasConsumption infinite() { return GasConsumption(0, true); }
 
-		GasConsumption& operator+=(GasConsumption const& _otherS);
-		std::ostream& operator<<(std::ostream& _str) const;
+		GasConsumption& operator+=(GasConsumption const& _other);
+		bool operator<(GasConsumption const& _other) const { return this->tuple() < _other.tuple(); }
+
+		std::tuple<bool const&, u256 const&> tuple() const { return std::tie(isInfinite, value); }
 
 		u256 value;
 		bool isInfinite;
 	};
 
 	/// Constructs a new gas meter given the current state.
-	GasMeter(std::shared_ptr<KnownState> const& _state): m_state(_state) {}
+	explicit GasMeter(std::shared_ptr<KnownState> const& _state, u256 const& _largestMemoryAccess = 0):
+		m_state(_state), m_largestMemoryAccess(_largestMemoryAccess) {}
 
 	/// @returns an upper bound on the gas consumed by the given instruction and updates
 	/// the state.
 	GasConsumption estimateMax(AssemblyItem const& _item);
 
+	u256 const& largestMemoryAccess() const { return m_largestMemoryAccess; }
+
 private:
 	/// @returns _multiplier * (_value + 31) / 32, if _value is a known constant and infinite otherwise.
 	GasConsumption wordGas(u256 const& _multiplier, ExpressionClasses::Id _value);
diff --git a/PathGasMeter.cpp b/PathGasMeter.cpp
new file mode 100644
index 00000000..8f7314f8
--- /dev/null
+++ b/PathGasMeter.cpp
@@ -0,0 +1,128 @@
+/*
+	This file is part of cpp-ethereum.
+
+	cpp-ethereum is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	cpp-ethereum is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/** @file PathGasMeter.cpp
+ * @author Christian <c@ethdev.com>
+ * @date 2015
+ */
+
+#include "PathGasMeter.h"
+#include <libevmasm/KnownState.h>
+#include <libevmasm/SemanticInformation.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::eth;
+
+PathGasMeter::PathGasMeter(AssemblyItems const& _items):
+	m_items(_items)
+{
+	for (size_t i = 0; i < m_items.size(); ++i)
+		if (m_items[i].type() == Tag)
+			m_tagPositions[m_items[i].data()] = i;
+}
+
+GasMeter::GasConsumption PathGasMeter::estimateMax(
+	size_t _startIndex,
+	shared_ptr<KnownState> const& _state
+)
+{
+	auto path = unique_ptr<GasPath>(new GasPath());
+	path->index = _startIndex;
+	path->state = _state->copy();
+	m_queue.push_back(move(path));
+
+	GasMeter::GasConsumption gas;
+	while (!m_queue.empty() && !gas.isInfinite)
+		gas = max(gas, handleQueueItem());
+	return gas;
+}
+
+GasMeter::GasConsumption PathGasMeter::handleQueueItem()
+{
+	assertThrow(!m_queue.empty(), OptimizerException, "");
+
+	unique_ptr<GasPath> path = move(m_queue.back());
+	m_queue.pop_back();
+
+	shared_ptr<KnownState> state = path->state;
+	GasMeter meter(state, path->largestMemoryAccess);
+	ExpressionClasses& classes = state->expressionClasses();
+	GasMeter::GasConsumption gas = path->gas;
+	size_t index = path->index;
+
+	if (index >= m_items.size() || (index > 0 && m_items.at(index).type() != Tag))
+		// Invalid jump usually provokes an out-of-gas exception, but we want to give an upper
+		// bound on the gas that is needed without changing the behaviour, so it is fine to
+		// return the current gas value.
+		return gas;
+
+	set<u256> jumpTags;
+	for (; index < m_items.size() && !gas.isInfinite; ++index)
+	{
+		bool branchStops = false;
+		jumpTags.clear();
+		AssemblyItem const& item = m_items.at(index);
+		if (item.type() == Tag || item == AssemblyItem(eth::Instruction::JUMPDEST))
+		{
+			// Do not allow any backwards jump. This is quite restrictive but should work for
+			// the simplest things.
+			if (path->visitedJumpdests.count(index))
+				return GasMeter::GasConsumption::infinite();
+			path->visitedJumpdests.insert(index);
+		}
+		else if (item == AssemblyItem(eth::Instruction::JUMP))
+		{
+			branchStops = true;
+			jumpTags = state->tagsInExpression(state->relativeStackElement(0));
+			if (jumpTags.empty()) // unknown jump destination
+				return GasMeter::GasConsumption::infinite();
+		}
+		else if (item == AssemblyItem(eth::Instruction::JUMPI))
+		{
+			ExpressionClasses::Id condition = state->relativeStackElement(-1);
+			if (classes.knownNonZero(condition) || !classes.knownZero(condition))
+			{
+				jumpTags = state->tagsInExpression(state->relativeStackElement(0));
+				if (jumpTags.empty()) // unknown jump destination
+					return GasMeter::GasConsumption::infinite();
+			}
+			branchStops = classes.knownNonZero(condition);
+		}
+		else if (SemanticInformation::altersControlFlow(item))
+			branchStops = true;
+
+		gas += meter.estimateMax(item);
+
+		for (u256 const& tag: jumpTags)
+		{
+			auto newPath = unique_ptr<GasPath>(new GasPath());
+			newPath->index = m_items.size();
+			if (m_tagPositions.count(tag))
+				newPath->index = m_tagPositions.at(tag);
+			newPath->gas = gas;
+			newPath->largestMemoryAccess = meter.largestMemoryAccess();
+			newPath->state = state->copy();
+			newPath->visitedJumpdests = path->visitedJumpdests;
+			m_queue.push_back(move(newPath));
+		}
+
+		if (branchStops)
+			break;
+	}
+
+	return gas;
+}
diff --git a/PathGasMeter.h b/PathGasMeter.h
new file mode 100644
index 00000000..1ada460a
--- /dev/null
+++ b/PathGasMeter.h
@@ -0,0 +1,66 @@
+/*
+	This file is part of cpp-ethereum.
+
+	cpp-ethereum is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	cpp-ethereum is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/** @file PathGasMeter.cpp
+ * @author Christian <c@ethdev.com>
+ * @date 2015
+ */
+
+#pragma once
+
+#include <set>
+#include <vector>
+#include <memory>
+#include <libevmasm/GasMeter.h>
+
+namespace dev
+{
+namespace eth
+{
+
+class KnownState;
+
+struct GasPath
+{
+	size_t index = 0;
+	std::shared_ptr<KnownState> state;
+	u256 largestMemoryAccess;
+	GasMeter::GasConsumption gas;
+	std::set<size_t> visitedJumpdests;
+};
+
+/**
+ * Computes an upper bound on the gas usage of a computation starting at a certain position in
+ * a list of AssemblyItems in a given state until the computation stops.
+ * Can be used to estimate the gas usage of functions on any given input.
+ */
+class PathGasMeter
+{
+public:
+	PathGasMeter(AssemblyItems const& _items);
+
+	GasMeter::GasConsumption estimateMax(size_t _startIndex, std::shared_ptr<KnownState> const& _state);
+
+private:
+	GasMeter::GasConsumption handleQueueItem();
+
+	std::vector<std::unique_ptr<GasPath>> m_queue;
+	std::map<u256, size_t> m_tagPositions;
+	AssemblyItems const& m_items;
+};
+
+}
+}
diff --git a/SemanticInformation.cpp b/SemanticInformation.cpp
index 056162b5..91f93e7e 100644
--- a/SemanticInformation.cpp
+++ b/SemanticInformation.cpp
@@ -111,7 +111,7 @@ bool SemanticInformation::altersControlFlow(AssemblyItem const& _item)
 	switch (_item.instruction())
 	{
 	// note that CALL, CALLCODE and CREATE do not really alter the control flow, because we
-	// continue on the next instruction (unless an exception happens which can always happen)
+	// continue on the next instruction
 	case Instruction::JUMP:
 	case Instruction::JUMPI:
 	case Instruction::RETURN: