Merge pull request #2006 from chriseth/sol_functionalGasEstimator

Functional gas estimator

10 files changed, 127 insertions, 17 deletions

diff --git a/ASTPrinter.cpp b/ASTPrinter.cpp
index 0a170f8e..d29ace17 100644
--- a/ASTPrinter.cpp
+++ b/ASTPrinter.cpp
@@ -33,7 +33,7 @@ namespace solidity
 ASTPrinter::ASTPrinter(
 	ASTNode const& _ast,
 	string const& _source,
-	StructuralGasEstimator::ASTGasConsumption const& _gasCosts
+	GasEstimator::ASTGasConsumption const& _gasCosts
 ): m_indentation(0), m_source(_source), m_ast(&_ast), m_gasCosts(_gasCosts)
 {
 }
diff --git a/ASTPrinter.h b/ASTPrinter.h
index 25678c17..cdf651f3 100644
--- a/ASTPrinter.h
+++ b/ASTPrinter.h
@@ -24,7 +24,7 @@
 
 #include <ostream>
 #include <libsolidity/ASTVisitor.h>
-#include <libsolidity/StructuralGasEstimator.h>
+#include <libsolidity/GasEstimator.h>
 
 namespace dev
 {
@@ -42,7 +42,7 @@ public:
 	ASTPrinter(
 		ASTNode const& _ast,
 		std::string const& _source = std::string(),
-		StructuralGasEstimator::ASTGasConsumption const& _gasCosts = StructuralGasEstimator::ASTGasConsumption()
+		GasEstimator::ASTGasConsumption const& _gasCosts = GasEstimator::ASTGasConsumption()
 	);
 	/// Output the string representation of the AST to _stream.
 	void print(std::ostream& _stream);
@@ -133,7 +133,7 @@ private:
 	int m_indentation;
 	std::string m_source;
 	ASTNode const* m_ast;
-	StructuralGasEstimator::ASTGasConsumption m_gasCosts;
+	GasEstimator::ASTGasConsumption m_gasCosts;
 	std::ostream* m_ostream;
 };
 
diff --git a/Compiler.cpp b/Compiler.cpp
index 66c50317..5e24aaaa 100644
--- a/Compiler.cpp
+++ b/Compiler.cpp
@@ -71,6 +71,11 @@ void Compiler::compileContract(ContractDefinition const& _contract,
 	packIntoContractCreator(_contract, m_runtimeContext);
 }
 
+eth::AssemblyItem Compiler::getFunctionEntryLabel(FunctionDefinition const& _function) const
+{
+	return m_runtimeContext.getFunctionEntryLabelIfExists(_function);
+}
+
 void Compiler::initializeContext(ContractDefinition const& _contract,
 								 map<ContractDefinition const*, bytes const*> const& _contracts)
 {
diff --git a/Compiler.h b/Compiler.h
index 106038d1..13b8639d 100644
--- a/Compiler.h
+++ b/Compiler.h
@@ -52,6 +52,10 @@ public:
 	/// @returns Assembly items of the runtime compiler context
 	eth::AssemblyItems const& getRuntimeAssemblyItems() const { return m_runtimeContext.getAssembly().getItems(); }
 
+	/// @returns the entry label of the given function. Might return an AssemblyItem of type
+	/// UndefinedItem if it does not exist yet.
+	eth::AssemblyItem getFunctionEntryLabel(FunctionDefinition const& _function) const;
+
 private:
 	/// Registers the non-function objects inside the contract with the context.
 	void initializeContext(ContractDefinition const& _contract,
diff --git a/CompilerContext.cpp b/CompilerContext.cpp
index f373fdfb..2edff82e 100644
--- a/CompilerContext.cpp
+++ b/CompilerContext.cpp
@@ -99,6 +99,12 @@ eth::AssemblyItem CompilerContext::getFunctionEntryLabel(Declaration const& _dec
 		return res->second.tag();
 }
 
+eth::AssemblyItem CompilerContext::getFunctionEntryLabelIfExists(Declaration const& _declaration) const
+{
+	auto res = m_functionEntryLabels.find(&_declaration);
+	return res == m_functionEntryLabels.end() ? eth::AssemblyItem(eth::UndefinedItem) : res->second.tag();
+}
+
 eth::AssemblyItem CompilerContext::getVirtualFunctionEntryLabel(FunctionDefinition const& _function)
 {
 	solAssert(!m_inheritanceHierarchy.empty(), "No inheritance hierarchy set.");
diff --git a/CompilerContext.h b/CompilerContext.h
index 93391245..7bc29de1 100644
--- a/CompilerContext.h
+++ b/CompilerContext.h
@@ -59,7 +59,11 @@ public:
 	bool isLocalVariable(Declaration const* _declaration) const;
 	bool isStateVariable(Declaration const* _declaration) const { return m_stateVariables.count(_declaration) != 0; }
 
+	/// @returns the entry label of the given function and creates it if it does not exist yet.
 	eth::AssemblyItem getFunctionEntryLabel(Declaration const& _declaration);
+	/// @returns the entry label of the given function. Might return an AssemblyItem of type
+	/// UndefinedItem if it does not exist yet.
+	eth::AssemblyItem getFunctionEntryLabelIfExists(Declaration const& _declaration) const;
 	void setInheritanceHierarchy(std::vector<ContractDefinition const*> const& _hierarchy) { m_inheritanceHierarchy = _hierarchy; }
 	/// @returns the entry label of the given function and takes overrides into account.
 	eth::AssemblyItem getVirtualFunctionEntryLabel(FunctionDefinition const& _function);
diff --git a/CompilerStack.cpp b/CompilerStack.cpp
index 4f976407..ebb98876 100644
--- a/CompilerStack.cpp
+++ b/CompilerStack.cpp
@@ -268,6 +268,24 @@ ContractDefinition const& CompilerStack::getContractDefinition(string const& _co
 	return *getContract(_contractName).contract;
 }
 
+size_t CompilerStack::getFunctionEntryPoint(
+	std::string const& _contractName,
+	FunctionDefinition const& _function
+) const
+{
+	shared_ptr<Compiler> const& compiler = getContract(_contractName).compiler;
+	if (!compiler)
+		return 0;
+	eth::AssemblyItem tag = compiler->getFunctionEntryLabel(_function);
+	if (tag.type() == eth::UndefinedItem)
+		return 0;
+	eth::AssemblyItems const& items = compiler->getRuntimeAssemblyItems();
+	for (size_t i = 0; i < items.size(); ++i)
+		if (items.at(i).type() == eth::Tag && items.at(i).data() == tag.data())
+			return i;
+	return 0;
+}
+
 bytes CompilerStack::staticCompile(std::string const& _sourceCode, bool _optimize)
 {
 	CompilerStack stack;
diff --git a/CompilerStack.h b/CompilerStack.h
index 0bc109a2..6be45aec 100644
--- a/CompilerStack.h
+++ b/CompilerStack.h
@@ -48,6 +48,7 @@ namespace solidity
 // forward declarations
 class Scanner;
 class ContractDefinition;
+class FunctionDefinition;
 class SourceUnit;
 class Compiler;
 class GlobalContext;
@@ -131,6 +132,13 @@ public:
 	/// does not exist.
 	ContractDefinition const& getContractDefinition(std::string const& _contractName) const;
 
+	/// @returns the offset of the entry point of the given function into the list of assembly items
+	/// or zero if it is not found or does not exist.
+	size_t getFunctionEntryPoint(
+		std::string const& _contractName,
+		FunctionDefinition const& _function
+	) const;
+
 	/// Compile the given @a _sourceCode to bytecode. If a scanner is provided, it is used for
 	/// scanning the source code - this is useful for printing exception information.
 	static bytes staticCompile(std::string const& _sourceCode, bool _optimize = false);
diff --git a/StructuralGasEstimator.cpp b/GasEstimator.cpp
index 9ce32ca5..01219a65 100644
--- a/StructuralGasEstimator.cpp
+++ b/GasEstimator.cpp
@@ -20,27 +20,30 @@
  * Gas consumption estimator working alongside the AST.
  */
 
-#include "StructuralGasEstimator.h"
+#include "GasEstimator.h"
 #include <map>
 #include <functional>
 #include <memory>
+#include <libdevcore/SHA3.h>
 #include <libevmasm/ControlFlowGraph.h>
 #include <libevmasm/KnownState.h>
+#include <libevmasm/PathGasMeter.h>
 #include <libsolidity/AST.h>
 #include <libsolidity/ASTVisitor.h>
+#include <libsolidity/CompilerUtils.h>
 
 using namespace std;
 using namespace dev;
 using namespace dev::eth;
 using namespace dev::solidity;
 
-StructuralGasEstimator::ASTGasConsumptionSelfAccumulated StructuralGasEstimator::performEstimation(
+GasEstimator::ASTGasConsumptionSelfAccumulated GasEstimator::structuralEstimation(
 	AssemblyItems const& _items,
 	vector<ASTNode const*> const& _ast
 )
 {
 	solAssert(std::count(_ast.begin(), _ast.end(), nullptr) == 0, "");
-	map<SourceLocation, GasMeter::GasConsumption> particularCosts;
+	map<SourceLocation, GasConsumption> particularCosts;
 
 	ControlFlowGraph cfg(_items);
 	for (BasicBlock const& block: cfg.optimisedBlocks())
@@ -72,7 +75,7 @@ StructuralGasEstimator::ASTGasConsumptionSelfAccumulated StructuralGasEstimator:
 	return gasCosts;
 }
 
-map<ASTNode const*, GasMeter::GasConsumption> StructuralGasEstimator::breakToStatementLevel(
+map<ASTNode const*, GasMeter::GasConsumption> GasEstimator::breakToStatementLevel(
 	ASTGasConsumptionSelfAccumulated const& _gasCosts,
 	vector<ASTNode const*> const& _roots
 )
@@ -99,7 +102,7 @@ map<ASTNode const*, GasMeter::GasConsumption> StructuralGasEstimator::breakToSta
 	// we use the location of a node if
 	//  - its statement depth is 0 or
 	//  - its statement depth is undefined but the parent's statement depth is at least 1
-	map<ASTNode const*, GasMeter::GasConsumption> gasCosts;
+	map<ASTNode const*, GasConsumption> gasCosts;
 	auto onNodeSecondPass = [&](ASTNode const& _node)
 	{
 		return statementDepth.count(&_node);
@@ -121,7 +124,53 @@ map<ASTNode const*, GasMeter::GasConsumption> StructuralGasEstimator::breakToSta
 	return gasCosts;
 }
 
-set<ASTNode const*> StructuralGasEstimator::finestNodesAtLocation(
+GasEstimator::GasConsumption GasEstimator::functionalEstimation(
+	AssemblyItems const& _items,
+	string const& _signature
+)
+{
+	auto state = make_shared<KnownState>();
+
+	if (!_signature.empty())
+	{
+		ExpressionClasses& classes = state->expressionClasses();
+		using Id = ExpressionClasses::Id;
+		using Ids = vector<Id>;
+		Id hashValue = classes.find(u256(FixedHash<4>::Arith(FixedHash<4>(dev::sha3(_signature)))));
+		Id calldata = classes.find(eth::Instruction::CALLDATALOAD, Ids{classes.find(u256(0))});
+		classes.forceEqual(hashValue, eth::Instruction::DIV, Ids{
+			calldata,
+			classes.find(u256(1) << (8 * 28))
+		});
+	}
+
+	PathGasMeter meter(_items);
+	return meter.estimateMax(0, state);
+}
+
+GasEstimator::GasConsumption GasEstimator::functionalEstimation(
+	AssemblyItems const& _items,
+	size_t const& _offset,
+	FunctionDefinition const& _function
+)
+{
+	auto state = make_shared<KnownState>();
+
+	unsigned parametersSize = CompilerUtils::getSizeOnStack(_function.getParameters());
+	if (parametersSize > 16)
+		return GasConsumption::infinite();
+
+	// Store an invalid return value on the stack, so that the path estimator breaks upon reaching
+	// the return jump.
+	AssemblyItem invalidTag(PushTag, u256(-0x10));
+	state->feedItem(invalidTag, true);
+	if (parametersSize > 0)
+		state->feedItem(eth::swapInstruction(parametersSize));
+
+	return PathGasMeter(_items).estimateMax(_offset, state);
+}
+
+set<ASTNode const*> GasEstimator::finestNodesAtLocation(
 	vector<ASTNode const*> const& _roots
 )
 {
@@ -140,4 +189,3 @@ set<ASTNode const*> StructuralGasEstimator::finestNodesAtLocation(
 		root->accept(visitor);
 	return nodes;
 }
-
diff --git a/StructuralGasEstimator.h b/GasEstimator.h
index ddc7c186..4020d60b 100644
--- a/StructuralGasEstimator.h
+++ b/GasEstimator.h
@@ -34,17 +34,18 @@ namespace dev
 namespace solidity
 {
 
-class StructuralGasEstimator
+struct GasEstimator
 {
 public:
-	using ASTGasConsumption = std::map<ASTNode const*, eth::GasMeter::GasConsumption>;
+	using GasConsumption = eth::GasMeter::GasConsumption;
+	using ASTGasConsumption = std::map<ASTNode const*, GasConsumption>;
 	using ASTGasConsumptionSelfAccumulated =
-		std::map<ASTNode const*, std::array<eth::GasMeter::GasConsumption, 2>>;
+		std::map<ASTNode const*, std::array<GasConsumption, 2>>;
 
 	/// Estimates the gas consumption for every assembly item in the given assembly and stores
 	/// it by source location.
 	/// @returns a mapping from each AST node to a pair of its particular and syntactically accumulated gas costs.
-	ASTGasConsumptionSelfAccumulated performEstimation(
+	static ASTGasConsumptionSelfAccumulated structuralEstimation(
 		eth::AssemblyItems const& _items,
 		std::vector<ASTNode const*> const& _ast
 	);
@@ -52,14 +53,30 @@ public:
 	/// the following source locations are part of the mapping:
 	/// 1. source locations of statements that do not contain other statements
 	/// 2. maximal source locations that do not overlap locations coming from the first rule
-	ASTGasConsumption breakToStatementLevel(
+	static ASTGasConsumption breakToStatementLevel(
 		ASTGasConsumptionSelfAccumulated const& _gasCosts,
 		std::vector<ASTNode const*> const& _roots
 	);
 
+	/// @returns the estimated gas consumption by the (public or external) function with the
+	/// given signature. If no signature is given, estimates the maximum gas usage.
+	static GasConsumption functionalEstimation(
+		eth::AssemblyItems const& _items,
+		std::string const& _signature = ""
+	);
+
+	/// @returns the estimated gas consumption by the given function which starts at the given
+	/// offset into the list of assembly items.
+	/// @note this does not work correctly for recursive functions.
+	static GasConsumption functionalEstimation(
+		eth::AssemblyItems const& _items,
+		size_t const& _offset,
+		FunctionDefinition const& _function
+	);
+
 private:
 	/// @returns the set of AST nodes which are the finest nodes at their location.
-	std::set<ASTNode const*> finestNodesAtLocation(std::vector<ASTNode const*> const& _roots);
+	static std::set<ASTNode const*> finestNodesAtLocation(std::vector<ASTNode const*> const& _roots);
 };
 
 }