Compute constants

6 files changed, 398 insertions, 8 deletions

diff --git a/Assembly.cpp b/Assembly.cpp
index a9ee9619..8642824f 100644
--- a/Assembly.cpp
+++ b/Assembly.cpp
@@ -22,9 +22,12 @@
 #include "Assembly.h"
 #include <fstream>
 #include <libdevcore/Log.h>
+#include <libevmcore/Params.h>
 #include <libevmasm/CommonSubexpressionEliminator.h>
 #include <libevmasm/ControlFlowGraph.h>
 #include <libevmasm/BlockDeduplicator.h>
+#include <libevmasm/ConstantOptimiser.h>
+#include <libevmasm/GasMeter.h>
 #include <json/json.h>
 using namespace std;
 using namespace dev;
@@ -302,7 +305,7 @@ inline bool matches(AssemblyItemsConstRef _a, AssemblyItemsConstRef _b)
 struct OptimiserChannel: public LogChannel { static const char* name() { return "OPT"; } static const int verbosity = 12; };
 #define copt dev::LogOutputStream<OptimiserChannel, true>()
 
-Assembly& Assembly::optimise(bool _enable)
+Assembly& Assembly::optimise(bool _enable, bool _isCreation, size_t _runs)
 {
 	if (!_enable)
 		return *this;
@@ -364,10 +367,17 @@ Assembly& Assembly::optimise(bool _enable)
 		}
 	}
 
+	total += ConstantOptimisationMethod::optimiseConstants(
+		_isCreation,
+		_isCreation ? 1 : _runs,
+		*this,
+		m_items
+	);
+
 	copt << total << " optimisations done.";
 
 	for (auto& sub: m_subs)
-	  sub.optimise(true);
+	  sub.optimise(true, false, _runs);
 
 	return *this;
 }
diff --git a/Assembly.h b/Assembly.h
index 3c82125a..1457173b 100644
--- a/Assembly.h
+++ b/Assembly.h
@@ -49,6 +49,7 @@ public:
 	AssemblyItem newPushTag() { return AssemblyItem(PushTag, m_usedTags++); }
 	AssemblyItem newData(bytes const& _data) { h256 h = (u256)std::hash<std::string>()(asString(_data)); m_data[h] = _data; return AssemblyItem(PushData, h); }
 	AssemblyItem newSub(Assembly const& _sub) { m_subs.push_back(_sub); return AssemblyItem(PushSub, m_subs.size() - 1); }
+	Assembly const& getSub(size_t _sub) const { return m_subs.at(_sub); }
 	AssemblyItem newPushString(std::string const& _data) { h256 h = (u256)std::hash<std::string>()(_data); m_strings[h] = _data; return AssemblyItem(PushString, h); }
 	AssemblyItem newPushSubSize(u256 const& _subId) { return AssemblyItem(PushSubSize, _subId); }
 
@@ -92,7 +93,13 @@ public:
 	void setSourceLocation(SourceLocation const& _location) { m_currentSourceLocation = _location; }
 
 	bytes assemble() const;
-	Assembly& optimise(bool _enable);
+	bytes const& data(h256 const& _i) const { return m_data[_i]; }
+
+	/// Modify (if @a _enable is set) and return the current assembly such that creation and
+	/// execution gas usage is optimised. @a _isCreation should be true for the top-level assembly.
+	/// @a _runs specifes an estimate on how often each opcode in this assembly will be executed,
+	/// i.e. use a small value to optimise for size and a large value to optimise for runtime.
+	Assembly& optimise(bool _enable, bool _isCreation = true, size_t _runs = 200);
 	Json::Value stream(
 		std::ostream& _out,
 		std::string const& _prefix = "",
diff --git a/ConstantOptimiser.cpp b/ConstantOptimiser.cpp
new file mode 100644
index 00000000..77d1bdfa
--- /dev/null
+++ b/ConstantOptimiser.cpp
@@ -0,0 +1,225 @@
+/*
+	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 ConstantOptimiser.cpp
+ * @author Christian <c@ethdev.com>
+ * @date 2015
+ */
+
+#include "libevmasm/ConstantOptimiser.h"
+#include <libevmasm/Assembly.h>
+#include <libevmasm/GasMeter.h>
+#include <libevmcore/Params.h>
+using namespace std;
+using namespace dev;
+using namespace dev::eth;
+
+unsigned ConstantOptimisationMethod::optimiseConstants(
+	bool _isCreation,
+	size_t _runs,
+	Assembly& _assembly,
+	AssemblyItems& _items
+)
+{
+	unsigned optimisations = 0;
+	map<AssemblyItem, size_t> pushes;
+	for (AssemblyItem const& item: _items)
+		if (item.type() == Push)
+			pushes[item]++;
+	for (auto it: pushes)
+	{
+		AssemblyItem const& item = it.first;
+		if (item.data() < 0x100)
+			continue;
+		Params params;
+		params.multiplicity = it.second;
+		params.isCreation = _isCreation;
+		params.runs = _runs;
+		LiteralMethod lit(params, item.data());
+		bigint literalGas = lit.gasNeeded();
+		CodeCopyMethod copy(params, item.data());
+		bigint copyGas = copy.gasNeeded();
+		ComputeMethod compute(params, item.data());
+		bigint computeGas = compute.gasNeeded();
+		if (copyGas < literalGas && copyGas < computeGas)
+		{
+			copy.execute(_assembly, _items);
+			optimisations++;
+		}
+		else if (computeGas < literalGas && computeGas < copyGas)
+		{
+			compute.execute(_assembly, _items);
+			optimisations++;
+		}
+	}
+	return optimisations;
+}
+
+bigint ConstantOptimisationMethod::simpleRunGas(AssemblyItems const& _items)
+{
+	bigint gas = 0;
+	for (AssemblyItem const& item: _items)
+		if (item.type() == Push)
+			gas += GasMeter::runGas(eth::Instruction::PUSH1);
+		else if (item.type() == Operation)
+			gas += GasMeter::runGas(item.instruction());
+	return gas;
+}
+
+bigint ConstantOptimisationMethod::dataGas(bytes const& _data) const
+{
+	if (m_params.isCreation)
+	{
+		bigint gas;
+		for (auto b: _data)
+			gas += b ? c_txDataNonZeroGas : c_txDataZeroGas;
+		return gas;
+	}
+	else
+		return c_createDataGas * dataSize();
+}
+
+size_t ConstantOptimisationMethod::bytesRequired(AssemblyItems const& _items)
+{
+	size_t size = 0;
+	for (AssemblyItem const& item: _items)
+		size += item.bytesRequired(3); // assume 3 byte addresses
+	return size;
+}
+
+void ConstantOptimisationMethod::replaceConstants(
+	AssemblyItems& _items,
+	AssemblyItems const& _replacement
+) const
+{
+	assertThrow(_items.size() > 0, OptimizerException, "");
+	for (size_t i = 0; i < _items.size(); ++i)
+	{
+		if (_items.at(i) != AssemblyItem(m_value))
+			continue;
+		_items[i] = _replacement[0];
+		_items.insert(_items.begin() + i + 1, _replacement.begin() + 1, _replacement.end());
+		i += _replacement.size() - 1;
+	}
+}
+
+bigint LiteralMethod::gasNeeded()
+{
+	return combineGas(
+		simpleRunGas({eth::Instruction::PUSH1}),
+		// PUSHX plus data
+		(m_params.isCreation ? c_txDataNonZeroGas : c_createDataGas) + dataGas(),
+		0
+	);
+}
+
+CodeCopyMethod::CodeCopyMethod(Params const& _params, u256 const& _value):
+	ConstantOptimisationMethod(_params, _value),
+	m_copyRoutine{
+		u256(0),
+		eth::Instruction::DUP1,
+		eth::Instruction::MLOAD, // back up memory
+		u256(32),
+		AssemblyItem(PushData, u256(1) << 16), // has to be replaced
+		eth::Instruction::DUP4,
+		eth::Instruction::CODECOPY,
+		eth::Instruction::DUP2,
+		eth::Instruction::MLOAD,
+		eth::Instruction::SWAP2,
+		eth::Instruction::MSTORE
+	}
+{
+}
+
+bigint CodeCopyMethod::gasNeeded()
+{
+	return combineGas(
+		// Run gas: we ignore memory increase costs
+		simpleRunGas(m_copyRoutine) + c_copyGas,
+		// Data gas for copy routines: Some bytes are zero, but we ignore them.
+		bytesRequired(m_copyRoutine) * (m_params.isCreation ? c_txDataNonZeroGas : c_createDataGas),
+		// Data gas for data itself
+		dataGas(toBigEndian(m_value))
+	);
+}
+
+void CodeCopyMethod::execute(Assembly& _assembly, AssemblyItems& _items)
+{
+	bytes data = toBigEndian(m_value);
+	m_copyRoutine[4] = _assembly.newData(data);
+	replaceConstants(_items, m_copyRoutine);
+}
+
+AssemblyItems ComputeMethod::findRepresentation(u256 const& _value)
+{
+	if (_value < 0x10000)
+		// Very small value, not worth computing
+		return AssemblyItems{_value};
+	else if (dev::bytesRequired(~_value) < dev::bytesRequired(_value))
+		// Negated is shorter to represent
+		return findRepresentation(~_value) + AssemblyItems{Instruction::NOT};
+	else
+	{
+		// Decompose value into a * 2**k + b where abs(b) << 2**k
+		// Is not always better, try literal and decomposition method.
+		AssemblyItems routine{u256(_value)};
+		bigint bestGas = gasNeeded(routine);
+		for (unsigned bits = 255; bits > 8; --bits)
+		{
+			unsigned gapDetector = unsigned(_value >> (bits - 8)) & 0x1ff;
+			if (gapDetector != 0xff && gapDetector != 0x100)
+				continue;
+
+			u256 powerOfTwo = u256(1) << bits;
+			u256 upperPart = _value >> bits;
+			bigint lowerPart = _value & (powerOfTwo - 1);
+			if (abs(powerOfTwo - lowerPart) < lowerPart)
+				lowerPart = lowerPart - powerOfTwo; // make it negative
+			if (abs(lowerPart) >= (powerOfTwo >> 8))
+				continue;
+
+			AssemblyItems newRoutine;
+			if (lowerPart != 0)
+				newRoutine += findRepresentation(u256(abs(lowerPart)));
+			newRoutine += AssemblyItems{u256(bits), u256(2), Instruction::EXP};
+			if (upperPart != 1 && upperPart != 0)
+				newRoutine += findRepresentation(upperPart) + AssemblyItems{Instruction::MUL};
+			if (lowerPart > 0)
+				newRoutine += AssemblyItems{Instruction::ADD};
+			else if (lowerPart < 0)
+				newRoutine.push_back(eth::Instruction::SUB);
+
+			bigint newGas = gasNeeded(newRoutine);
+			if (newGas < bestGas)
+			{
+				bestGas = move(newGas);
+				routine = move(newRoutine);
+			}
+		}
+		return routine;
+	}
+}
+
+bigint ComputeMethod::gasNeeded(AssemblyItems const& _routine)
+{
+	size_t numExps = count(_routine.begin(), _routine.end(), eth::Instruction::EXP);
+	return combineGas(
+		simpleRunGas(_routine) + numExps * (c_expGas + c_expByteGas),
+		// Data gas for routine: Some bytes are zero, but we ignore them.
+		bytesRequired(_routine) * (m_params.isCreation ? c_txDataNonZeroGas : c_createDataGas),
+		0
+	);
+}
diff --git a/ConstantOptimiser.h b/ConstantOptimiser.h
new file mode 100644
index 00000000..e75eff38
--- /dev/null
+++ b/ConstantOptimiser.h
@@ -0,0 +1,147 @@
+/*
+	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 ConstantOptimiser.cpp
+ * @author Christian <c@ethdev.com>
+ * @date 2015
+ */
+
+#pragma once
+
+#include <vector>
+#include <libdevcore/CommonData.h>
+#include <libdevcore/CommonIO.h>
+
+namespace dev
+{
+namespace eth
+{
+
+class AssemblyItem;
+using AssemblyItems = std::vector<AssemblyItem>;
+class Assembly;
+
+/**
+ * Abstract base class for one way to change how constants are represented in the code.
+ */
+class ConstantOptimisationMethod
+{
+public:
+	/// Tries to optimised how constants are represented in the source code and modifies
+	/// @a _assembly and its @a _items.
+	/// @returns zero if no optimisations could be performed.
+	static unsigned optimiseConstants(
+		bool _isCreation,
+		size_t _runs,
+		Assembly& _assembly,
+		AssemblyItems& _items
+	);
+
+	struct Params
+	{
+		bool isCreation; ///< Whether this is called during contract creation or runtime.
+		size_t runs; ///< Estimated number of calls per opcode oven the lifetime of the contract.
+		size_t multiplicity; ///< Number of times the constant appears in the code.
+	};
+
+	explicit ConstantOptimisationMethod(Params const& _params, u256 const& _value):
+		m_params(_params), m_value(_value) {}
+	virtual bigint gasNeeded() = 0;
+	virtual void execute(Assembly& _assembly, AssemblyItems& _items) = 0;
+
+protected:
+	size_t dataSize() const { return std::max<size_t>(1, dev::bytesRequired(m_value)); }
+
+	/// @returns the run gas for the given items ignoring special gas costs
+	static bigint simpleRunGas(AssemblyItems const& _items);
+	/// @returns the gas needed to store the given data literally
+	bigint dataGas(bytes const& _data) const;
+	/// @returns the gas needed to store the value literally
+	bigint dataGas() const { return dataGas(toCompactBigEndian(m_value, 1)); }
+	static size_t bytesRequired(AssemblyItems const& _items);
+	/// @returns the combined estimated gas usage taking @a m_params into account.
+	bigint combineGas(
+		bigint const& _runGas,
+		bigint const& _repeatedDataGas,
+		bigint const& _uniqueDataGas
+	)
+	{
+		// _runGas is not multiplied by _multiplicity because the runs are "per opcode"
+		return m_params.runs * _runGas + m_params.multiplicity * _repeatedDataGas + _uniqueDataGas;
+	}
+
+	/// Replaces the constant by the code given in @a _replacement.
+	void replaceConstants(AssemblyItems& _items, AssemblyItems const& _replacement) const;
+
+	Params m_params;
+	u256 const& m_value;
+};
+
+/**
+ * Optimisation method that pushes the constant to the stack literally. This is the default method,
+ * i.e. executing it does not alter the Assembly.
+ */
+class LiteralMethod: public ConstantOptimisationMethod
+{
+public:
+	explicit LiteralMethod(Params const& _params, u256 const& _value):
+		ConstantOptimisationMethod(_params, _value) {}
+	virtual bigint gasNeeded() override;
+	virtual void execute(Assembly&, AssemblyItems&) override {}
+};
+
+/**
+ * Method that stores the data in the .data section of the code and copies it to the stack.
+ */
+class CodeCopyMethod: public ConstantOptimisationMethod
+{
+public:
+	explicit CodeCopyMethod(Params const& _params, u256 const& _value);
+	virtual bigint gasNeeded() override;
+	virtual void execute(Assembly& _assembly, AssemblyItems& _items) override;
+
+protected:
+	AssemblyItems m_copyRoutine;
+};
+
+/**
+ * Method that tries to compute the constant.
+ */
+class ComputeMethod: public ConstantOptimisationMethod
+{
+public:
+	explicit ComputeMethod(Params const& _params, u256 const& _value):
+		ConstantOptimisationMethod(_params, _value)
+	{
+		m_routine = findRepresentation(m_value);
+	}
+
+	virtual bigint gasNeeded() override { return gasNeeded(m_routine); }
+	virtual void execute(Assembly&, AssemblyItems& _items) override
+	{
+		replaceConstants(_items, m_routine);
+	}
+
+protected:
+	/// Tries to recursively find a way to compute @a _value.
+	AssemblyItems findRepresentation(u256 const& _value);
+	bigint gasNeeded(AssemblyItems const& _routine);
+
+	AssemblyItems m_routine;
+};
+
+}
+}
diff --git a/GasMeter.cpp b/GasMeter.cpp
index 4e5289e3..42a5bed2 100644
--- a/GasMeter.cpp
+++ b/GasMeter.cpp
@@ -201,13 +201,14 @@ GasMeter::GasConsumption GasMeter::memoryGas(int _stackPosOffset, int _stackPosS
 		}));
 }
 
-GasMeter::GasConsumption GasMeter::runGas(Instruction _instruction)
+u256 GasMeter::runGas(Instruction _instruction)
 {
 	if (_instruction == Instruction::JUMPDEST)
-		return GasConsumption(1);
+		return 1;
 
 	int tier = instructionInfo(_instruction).gasPriceTier;
-	return tier == InvalidTier ? GasConsumption::infinite() : c_tierStepGas[tier];
+	assertThrow(tier != InvalidTier, OptimizerException, "Invalid gas tier.");
+	return c_tierStepGas[tier];
 }
 
 
diff --git a/GasMeter.h b/GasMeter.h
index 6949c193..90f151fc 100644
--- a/GasMeter.h
+++ b/GasMeter.h
@@ -66,6 +66,8 @@ public:
 
 	u256 const& largestMemoryAccess() const { return m_largestMemoryAccess; }
 
+	static u256 runGas(Instruction _instruction);
+
 private:
 	/// @returns _multiplier * (_value + 31) / 32, if _value is a known constant and infinite otherwise.
 	GasConsumption wordGas(u256 const& _multiplier, ExpressionClasses::Id _value);
@@ -76,8 +78,6 @@ private:
 	/// 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;