1 files changed, 107 insertions, 37 deletions

diff --git a/libevmasm/ConstantOptimiser.cpp b/libevmasm/ConstantOptimiser.cpp
index f4a50c2d..2ecbfa7f 100644
--- a/libevmasm/ConstantOptimiser.cpp
+++ b/libevmasm/ConstantOptimiser.cpp
@@ -38,6 +38,7 @@ unsigned ConstantOptimisationMethod::optimiseConstants(
 	for (AssemblyItem const& item: _items)
 		if (item.type() == Push)
 			pushes[item]++;
+	map<u256, AssemblyItems> pendingReplacements;
 	for (auto it: pushes)
 	{
 		AssemblyItem const& item = it.first;
@@ -53,17 +54,22 @@ unsigned ConstantOptimisationMethod::optimiseConstants(
 		bigint copyGas = copy.gasNeeded();
 		ComputeMethod compute(params, item.data());
 		bigint computeGas = compute.gasNeeded();
+		AssemblyItems replacement;
 		if (copyGas < literalGas && copyGas < computeGas)
 		{
-			copy.execute(_assembly, _items);
+			replacement = copy.execute(_assembly);
 			optimisations++;
 		}
-		else if (computeGas < literalGas && computeGas < copyGas)
+		else if (computeGas < literalGas && computeGas <= copyGas)
 		{
-			compute.execute(_assembly, _items);
+			replacement = compute.execute(_assembly);
 			optimisations++;
 		}
+		if (!replacement.empty())
+			pendingReplacements[item.data()] = replacement;
 	}
+	if (!pendingReplacements.empty())
+		replaceConstants(_items, pendingReplacements);
 	return optimisations;
 }
 
@@ -93,26 +99,29 @@ bigint ConstantOptimisationMethod::dataGas(bytes const& _data) const
 
 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;
+	return eth::bytesRequired(_items, 3); // assume 3 byte addresses
 }
 
 void ConstantOptimisationMethod::replaceConstants(
 	AssemblyItems& _items,
-	AssemblyItems const& _replacement
-) const
+	map<u256, AssemblyItems> const& _replacements
+)
 {
-	assertThrow(_items.size() > 0, OptimizerException, "");
-	for (size_t i = 0; i < _items.size(); ++i)
+	AssemblyItems replaced;
+	for (AssemblyItem const& item: _items)
 	{
-		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;
+		if (item.type() == Push)
+		{
+			auto it = _replacements.find(item.data());
+			if (it != _replacements.end())
+			{
+				replaced += it->second;
+				continue;
+			}
+		}
+		replaced.push_back(item);
 	}
+	_items = std::move(replaced);
 }
 
 bigint LiteralMethod::gasNeeded()
@@ -128,38 +137,44 @@ bigint LiteralMethod::gasNeeded()
 CodeCopyMethod::CodeCopyMethod(Params const& _params, u256 const& _value):
 	ConstantOptimisationMethod(_params, _value)
 {
-	m_copyRoutine = AssemblyItems{
-		u256(0),
-		Instruction::DUP1,
-		Instruction::MLOAD, // back up memory
-		u256(32),
-		AssemblyItem(PushData, u256(1) << 16), // has to be replaced
-		Instruction::DUP4,
-		Instruction::CODECOPY,
-		Instruction::DUP2,
-		Instruction::MLOAD,
-		Instruction::SWAP2,
-		Instruction::MSTORE
-	};
 }
 
 bigint CodeCopyMethod::gasNeeded()
 {
 	return combineGas(
 		// Run gas: we ignore memory increase costs
-		simpleRunGas(m_copyRoutine) + GasCosts::copyGas,
+		simpleRunGas(copyRoutine()) + GasCosts::copyGas,
 		// Data gas for copy routines: Some bytes are zero, but we ignore them.
-		bytesRequired(m_copyRoutine) * (m_params.isCreation ? GasCosts::txDataNonZeroGas : GasCosts::createDataGas),
+		bytesRequired(copyRoutine()) * (m_params.isCreation ? GasCosts::txDataNonZeroGas : GasCosts::createDataGas),
 		// Data gas for data itself
 		dataGas(toBigEndian(m_value))
 	);
 }
 
-void CodeCopyMethod::execute(Assembly& _assembly, AssemblyItems& _items)
+AssemblyItems CodeCopyMethod::execute(Assembly& _assembly)
 {
 	bytes data = toBigEndian(m_value);
-	m_copyRoutine[4] = _assembly.newData(data);
-	replaceConstants(_items, m_copyRoutine);
+	AssemblyItems actualCopyRoutine = copyRoutine();
+	actualCopyRoutine[4] = _assembly.newData(data);
+	return actualCopyRoutine;
+}
+
+AssemblyItems const& CodeCopyMethod::copyRoutine() const
+{
+	AssemblyItems static copyRoutine{
+		u256(0),
+		Instruction::DUP1,
+		Instruction::MLOAD, // back up memory
+		u256(32),
+		AssemblyItem(PushData, u256(1) << 16), // has to be replaced
+		Instruction::DUP4,
+		Instruction::CODECOPY,
+		Instruction::DUP2,
+		Instruction::MLOAD,
+		Instruction::SWAP2,
+		Instruction::MSTORE
+	};
+	return copyRoutine;
 }
 
 AssemblyItems ComputeMethod::findRepresentation(u256 const& _value)
@@ -176,7 +191,7 @@ AssemblyItems ComputeMethod::findRepresentation(u256 const& _value)
 		// Is not always better, try literal and decomposition method.
 		AssemblyItems routine{u256(_value)};
 		bigint bestGas = gasNeeded(routine);
-		for (unsigned bits = 255; bits > 8; --bits)
+		for (unsigned bits = 255; bits > 8 && m_maxSteps > 0; --bits)
 		{
 			unsigned gapDetector = unsigned(_value >> (bits - 8)) & 0x1ff;
 			if (gapDetector != 0xff && gapDetector != 0x100)
@@ -185,8 +200,13 @@ AssemblyItems ComputeMethod::findRepresentation(u256 const& _value)
 			u256 powerOfTwo = u256(1) << bits;
 			u256 upperPart = _value >> bits;
 			bigint lowerPart = _value & (powerOfTwo - 1);
-			if (abs(powerOfTwo - lowerPart) < lowerPart)
+			if ((powerOfTwo - lowerPart) < lowerPart)
+			{
 				lowerPart = lowerPart - powerOfTwo; // make it negative
+				upperPart++;
+			}
+			if (upperPart == 0)
+				continue;
 			if (abs(lowerPart) >= (powerOfTwo >> 8))
 				continue;
 
@@ -194,13 +214,15 @@ AssemblyItems ComputeMethod::findRepresentation(u256 const& _value)
 			if (lowerPart != 0)
 				newRoutine += findRepresentation(u256(abs(lowerPart)));
 			newRoutine += AssemblyItems{u256(bits), u256(2), Instruction::EXP};
-			if (upperPart != 1 && upperPart != 0)
+			if (upperPart != 1)
 				newRoutine += findRepresentation(upperPart) + AssemblyItems{Instruction::MUL};
 			if (lowerPart > 0)
 				newRoutine += AssemblyItems{Instruction::ADD};
 			else if (lowerPart < 0)
 				newRoutine.push_back(Instruction::SUB);
 
+			if (m_maxSteps > 0)
+				m_maxSteps--;
 			bigint newGas = gasNeeded(newRoutine);
 			if (newGas < bestGas)
 			{
@@ -212,6 +234,54 @@ AssemblyItems ComputeMethod::findRepresentation(u256 const& _value)
 	}
 }
 
+bool ComputeMethod::checkRepresentation(u256 const& _value, AssemblyItems const& _routine)
+{
+	// This is a tiny EVM that can only evaluate some instructions.
+	vector<u256> stack;
+	for (AssemblyItem const& item: _routine)
+	{
+		switch (item.type())
+		{
+		case Operation:
+		{
+			if (stack.size() < size_t(item.arguments()))
+				return false;
+			u256* sp = &stack.back();
+			switch (item.instruction())
+			{
+			case Instruction::MUL:
+				sp[-1] = sp[0] * sp[-1];
+				break;
+			case Instruction::EXP:
+				if (sp[-1] > 0xff)
+					return false;
+				sp[-1] = boost::multiprecision::pow(sp[0], unsigned(sp[-1]));
+				break;
+			case Instruction::ADD:
+				sp[-1] = sp[0] + sp[-1];
+				break;
+			case Instruction::SUB:
+				sp[-1] = sp[0] - sp[-1];
+				break;
+			case Instruction::NOT:
+				sp[0] = ~sp[0];
+				break;
+			default:
+				return false;
+			}
+			stack.resize(stack.size() + item.deposit());
+			break;
+		}
+		case Push:
+			stack.push_back(item.data());
+			break;
+		default:
+			return false;
+		}
+	}
+	return stack.size() == 1 && stack.front() == _value;
+}
+
 bigint ComputeMethod::gasNeeded(AssemblyItems const& _routine)
 {
 	size_t numExps = count(_routine.begin(), _routine.end(), Instruction::EXP);