Gas estimation taking known state into account.

6 files changed, 167 insertions, 16 deletions

diff --git a/Assembly.cpp b/Assembly.cpp
index 6f38b0f4..5cf3b787 100644
--- a/Assembly.cpp
+++ b/Assembly.cpp
@@ -431,6 +431,7 @@ bytes Assembly::assemble() const
 		case PushSubSize:
 		{
 			auto s = m_data[i.data()].size();
+			i.setPushedValue(u256(s));
 			byte b = max<unsigned>(1, dev::bytesRequired(s));
 			ret.push_back((byte)Instruction::PUSH1 - 1 + b);
 			ret.resize(ret.size() + b);
diff --git a/AssemblyItem.h b/AssemblyItem.h
index b3012a7e..7d8f3d9a 100644
--- a/AssemblyItem.h
+++ b/AssemblyItem.h
@@ -84,11 +84,17 @@ public:
 	JumpType getJumpType() const { return m_jumpType; }
 	std::string getJumpTypeAsString() const;
 
+	void setPushedValue(u256 const& _value) const { m_pushedValue = std::make_shared<u256>(_value); }
+	u256 const* pushedValue() const { return m_pushedValue.get(); }
+
 private:
 	AssemblyItemType m_type;
 	u256 m_data;
 	SourceLocation m_location;
 	JumpType m_jumpType = JumpType::Ordinary;
+	/// Pushed value for operations with data to be determined during assembly stage,
+	/// e.g. PushSubSize, PushTag, PushSub, etc.
+	mutable std::shared_ptr<u256> m_pushedValue;
 };
 
 using AssemblyItems = std::vector<AssemblyItem>;
diff --git a/GasMeter.cpp b/GasMeter.cpp
index e5fb0e09..a8dc4dd5 100644
--- a/GasMeter.cpp
+++ b/GasMeter.cpp
@@ -20,6 +20,7 @@
  */
 
 #include "GasMeter.h"
+#include <libevmasm/KnownState.h>
 #include <libevmcore/Params.h>
 
 using namespace std;
@@ -41,55 +42,162 @@ GasMeter::GasConsumption& GasMeter::GasConsumption::operator+=(GasConsumption co
 
 GasMeter::GasConsumption GasMeter::estimateMax(AssemblyItem const& _item)
 {
-	switch (_item.type()) {
+	GasConsumption gas;
+	switch (_item.type())
+	{
 	case Push:
 	case PushTag:
-		return runGas(Instruction::PUSH1);
+	case PushData:
+	case PushString:
+	case PushSub:
+	case PushSubSize:
+	case PushProgramSize:
+		gas = runGas(Instruction::PUSH1);
+		break;
 	case Tag:
-		return runGas(Instruction::JUMPDEST);
+		gas = runGas(Instruction::JUMPDEST);
+		break;
 	case Operation:
 	{
-		GasConsumption gas = runGas(_item.instruction());
+		ExpressionClasses& classes = m_state->expressionClasses();
+		gas = runGas(_item.instruction());
 		switch (_item.instruction())
 		{
 		case Instruction::SSTORE:
-			// @todo logic can be improved
-			gas += c_sstoreSetGas;
+		{
+			ExpressionClasses::Id slot = m_state->relativeStackElement(0);
+			ExpressionClasses::Id value = m_state->relativeStackElement(-1);
+			if (classes.knownZero(value) || (
+				m_state->storageContent().count(slot) &&
+				classes.knownNonZero(m_state->storageContent().at(slot))
+			))
+				gas += c_sstoreResetGas; //@todo take refunds into account
+			else
+				gas += c_sstoreSetGas;
 			break;
+		}
 		case Instruction::SLOAD:
 			gas += c_sloadGas;
 			break;
+		case Instruction::RETURN:
+			gas += memoryGas(0, -1);
+			break;
+		case Instruction::MLOAD:
 		case Instruction::MSTORE:
+			gas += memoryGas(classes.find(eth::Instruction::ADD, {
+				m_state->relativeStackElement(0),
+				classes.find(AssemblyItem(32))
+			}));
+			break;
 		case Instruction::MSTORE8:
-		case Instruction::MLOAD:
-		case Instruction::RETURN:
+			gas += memoryGas(classes.find(eth::Instruction::ADD, {
+				m_state->relativeStackElement(0),
+				classes.find(AssemblyItem(1))
+			}));
+			break;
 		case Instruction::SHA3:
+			gas = c_sha3Gas;
+			gas += wordGas(c_sha3WordGas, m_state->relativeStackElement(-1));
+			gas += memoryGas(0, -1);
+			break;
 		case Instruction::CALLDATACOPY:
 		case Instruction::CODECOPY:
+			gas += memoryGas(0, -2);
+			gas += wordGas(c_copyGas, m_state->relativeStackElement(-2));
+			break;
 		case Instruction::EXTCODECOPY:
+			gas += memoryGas(-1, -3);
+			gas += wordGas(c_copyGas, m_state->relativeStackElement(-3));
+			break;
 		case Instruction::LOG0:
 		case Instruction::LOG1:
 		case Instruction::LOG2:
 		case Instruction::LOG3:
 		case Instruction::LOG4:
+		{
+			unsigned n = unsigned(_item.instruction()) - unsigned(Instruction::LOG0);
+			gas = c_logGas + c_logTopicGas * n;
+			gas += memoryGas(0, -1);
+			if (u256 const* value = classes.knownConstant(m_state->relativeStackElement(-1)))
+				gas += c_logDataGas * (*value);
+			else
+				gas = GasConsumption::infinite();
+			break;
+		}
 		case Instruction::CALL:
 		case Instruction::CALLCODE:
+			gas = c_callGas;
+			if (u256 const* value = classes.knownConstant(m_state->relativeStackElement(0)))
+				gas += (*value);
+			else
+				gas = GasConsumption::infinite();
+			if (_item.instruction() != Instruction::CALLCODE)
+				gas += c_callNewAccountGas; // We very rarely know whether the address exists.
+			if (!classes.knownZero(m_state->relativeStackElement(-2)))
+				gas += c_callValueTransferGas;
+			gas += memoryGas(-3, -4);
+			gas += memoryGas(-5, -6);
+			break;
 		case Instruction::CREATE:
+			gas = c_createGas;
+			gas += memoryGas(-1, -2);
+			break;
 		case Instruction::EXP:
-			// @todo logic can be improved
-			gas = GasConsumption::infinite();
+			gas = c_expGas;
+			if (u256 const* value = classes.knownConstant(m_state->relativeStackElement(-1)))
+				gas += c_expByteGas * (32 - (h256(*value).firstBitSet() / 8));
+			else
+				gas = GasConsumption::infinite();
 			break;
 		default:
 			break;
 		}
-		return gas;
 		break;
 	}
 	default:
+		gas = GasConsumption::infinite();
 		break;
 	}
 
-	return GasConsumption::infinite();
+	m_state->feedItem(_item);
+	return gas;
+}
+
+GasMeter::GasConsumption GasMeter::wordGas(u256 const& _multiplier, ExpressionClasses::Id _position)
+{
+	u256 const* value = m_state->expressionClasses().knownConstant(_position);
+	if (!value)
+		return GasConsumption::infinite();
+	return GasConsumption(_multiplier * ((*value + 31) / 32));
+}
+
+GasMeter::GasConsumption GasMeter::memoryGas(ExpressionClasses::Id _position)
+{
+	u256 const* value = m_state->expressionClasses().knownConstant(_position);
+	if (!value)
+		return GasConsumption::infinite();
+	if (*value < m_largestMemoryAccess)
+		return GasConsumption(u256(0));
+	u256 previous = m_largestMemoryAccess;
+	m_largestMemoryAccess = *value;
+	auto memGas = [](u256 const& pos) -> u256
+	{
+		u256 size = (pos + 31) / 32;
+		return c_memoryGas * size + size * size / c_quadCoeffDiv;
+	};
+	return memGas(*value) - memGas(previous);
+}
+
+GasMeter::GasConsumption GasMeter::memoryGas(int _stackPosOffset, int _stackPosSize)
+{
+	ExpressionClasses& classes = m_state->expressionClasses();
+	if (classes.knownZero(m_state->relativeStackElement(_stackPosSize)))
+		return GasConsumption(0);
+	else
+		return memoryGas(classes.find(eth::Instruction::ADD, {
+			m_state->relativeStackElement(_stackPosOffset),
+			m_state->relativeStackElement(_stackPosSize)
+		}));
 }
 
 GasMeter::GasConsumption GasMeter::runGas(Instruction _instruction)
diff --git a/GasMeter.h b/GasMeter.h
index 63dbc138..ab6d5613 100644
--- a/GasMeter.h
+++ b/GasMeter.h
@@ -22,6 +22,7 @@
 #pragma once
 
 #include <ostream>
+#include <libevmasm/ExpressionClasses.h>
 #include <libevmasm/AssemblyItem.h>
 
 namespace dev
@@ -29,8 +30,13 @@ namespace dev
 namespace eth
 {
 
+class KnownState;
+
 /**
  * Class that helps computing the maximum gas consumption for instructions.
+ * Has to be initialized with a certain known state that will be automatically updated for
+ * each call to estimateMax. These calls have to supply strictly subsequent AssemblyItems.
+ * A new gas meter has to be constructed (with a new state) for control flow changes.
  */
 class GasMeter
 {
@@ -47,11 +53,28 @@ public:
 		bool isInfinite;
 	};
 
-	/// Returns an upper bound on the gas consumed by the given instruction.
+	/// Constructs a new gas meter given the current state.
+	GasMeter(std::shared_ptr<KnownState> const& _state): m_state(_state) {}
+
+	/// @returns an upper bound on the gas consumed by the given instruction and updates
+	/// the state.
 	GasConsumption estimateMax(AssemblyItem const& _item);
 
 private:
+	/// @returns _multiplier * (_value + 31) / 32, if _value is a known constant and infinite otherwise.
+	GasConsumption wordGas(u256 const& _multiplier, ExpressionClasses::Id _value);
+	/// @returns the gas needed to access the given memory position.
+	/// @todo this assumes that memory was never accessed before and thus over-estimates gas usage.
+	GasConsumption memoryGas(ExpressionClasses::Id _position);
+	/// @returns the memory gas for accessing the memory at a specific offset for a number of bytes
+	/// given as values on the stack at the given relative positions.
+	GasConsumption memoryGas(int _stackPosOffset, int _stackPosSize);
+
 	static GasConsumption runGas(Instruction _instruction);
+
+	std::shared_ptr<KnownState> m_state;
+	/// Largest point where memory was accessed since the creation of this object.
+	u256 m_largestMemoryAccess;
 };
 
 inline std::ostream& operator<<(std::ostream& _str, GasMeter::GasConsumption const& _consumption)
@@ -59,7 +82,7 @@ inline std::ostream& operator<<(std::ostream& _str, GasMeter::GasConsumption con
 	if (_consumption.isInfinite)
 		return _str << "inf";
 	else
-		return _str << _consumption.value;
+		return _str << std::dec << _consumption.value;
 }
 
 
diff --git a/KnownState.cpp b/KnownState.cpp
index 895778ed..d62dbf17 100644
--- a/KnownState.cpp
+++ b/KnownState.cpp
@@ -92,7 +92,11 @@ KnownState::StoreOperation KnownState::feedItem(AssemblyItem const& _item, bool
 	else if (_item.type() != Operation)
 	{
 		assertThrow(_item.deposit() == 1, InvalidDeposit, "");
-		setStackElement(++m_stackHeight, m_expressionClasses->find(_item, {}, _copyItem));
+		if (_item.pushedValue())
+			// only available after assembly stage, should not be used for optimisation
+			setStackElement(++m_stackHeight, m_expressionClasses->find(*_item.pushedValue()));
+		else
+			setStackElement(++m_stackHeight, m_expressionClasses->find(_item, {}, _copyItem));
 	}
 	else
 	{
@@ -230,7 +234,12 @@ ExpressionClasses::Id KnownState::stackElement(int _stackHeight, SourceLocation
 		return m_stackElements.at(_stackHeight);
 	// Stack element not found (not assigned yet), create new unknown equivalence class.
 	return m_stackElements[_stackHeight] =
-		m_expressionClasses->find(AssemblyItem(UndefinedItem, _stackHeight, _location));
+			m_expressionClasses->find(AssemblyItem(UndefinedItem, _stackHeight, _location));
+}
+
+KnownState::Id KnownState::relativeStackElement(int _stackOffset, SourceLocation const& _location)
+{
+	return stackElement(m_stackHeight + _stackOffset, _location);
 }
 
 void KnownState::clearTagUnions()
diff --git a/KnownState.h b/KnownState.h
index 3505df74..9d28ef21 100644
--- a/KnownState.h
+++ b/KnownState.h
@@ -111,6 +111,8 @@ public:
 	/// Retrieves the current equivalence class fo the given stack element (or generates a new
 	/// one if it does not exist yet).
 	Id stackElement(int _stackHeight, SourceLocation const& _location);
+	/// @returns the stackElement relative to the current stack height.
+	Id relativeStackElement(int _stackOffset, SourceLocation const& _location = SourceLocation());
 
 	/// @returns its set of tags if the given expression class is a known tag union; returns a set
 	/// containing the tag if it is a PushTag expression and the empty set otherwise.
@@ -123,6 +125,8 @@ public:
 	std::map<int, Id> const& stackElements() const { return m_stackElements; }
 	ExpressionClasses& expressionClasses() const { return *m_expressionClasses; }
 
+	std::map<Id, Id> const& storageContent() const { return m_storageContent; }
+
 private:
 	/// Assigns a new equivalence class to the next sequence number of the given stack element.
 	void setStackElement(int _stackHeight, Id _class);