/*
This file is part of solidity.
solidity 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.
solidity 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 solidity. 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>
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]++;
map<u256, AssemblyItems> pendingReplacements;
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();
AssemblyItems replacement;
if (copyGas < literalGas && copyGas < computeGas)
{
replacement = copy.execute(_assembly);
optimisations++;
}
else if (computeGas < literalGas && computeGas <= copyGas)
{
replacement = compute.execute(_assembly);
optimisations++;
}
if (!replacement.empty())
pendingReplacements[item.data()] = replacement;
}
if (!pendingReplacements.empty())
replaceConstants(_items, pendingReplacements);
return optimisations;
}
bigint ConstantOptimisationMethod::simpleRunGas(AssemblyItems const& _items)
{
bigint gas = 0;
for (AssemblyItem const& item: _items)
if (item.type() == Push)
gas += GasMeter::runGas(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 ? GasCosts::txDataNonZeroGas : GasCosts::txDataZeroGas;
return gas;
}
else
return GasCosts::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,
map<u256, AssemblyItems> const& _replacements
)
{
AssemblyItems replaced;
for (AssemblyItem const& item: _items)
{
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()
{
return combineGas(
simpleRunGas({Instruction::PUSH1}),
// PUSHX plus data
(m_params.isCreation ? GasCosts::txDataNonZeroGas : GasCosts::createDataGas) + dataGas(),
0
);
}
CodeCopyMethod::CodeCopyMethod(Params const& _params, u256 const& _value):
ConstantOptimisationMethod(_params, _value)
{
}
bigint CodeCopyMethod::gasNeeded()
{
return combineGas(
// Run gas: we ignore memory increase costs
simpleRunGas(copyRoutine()) + GasCosts::copyGas,
// Data gas for copy routines: Some bytes are zero, but we ignore them.
bytesRequired(copyRoutine()) * (m_params.isCreation ? GasCosts::txDataNonZeroGas : GasCosts::createDataGas),
// Data gas for data itself
dataGas(toBigEndian(m_value))
);
}
AssemblyItems CodeCopyMethod::execute(Assembly& _assembly)
{
bytes data = toBigEndian(m_value);
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)
{
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 && m_maxSteps > 0; --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(Instruction::SUB);
if (m_maxSteps > 0)
m_maxSteps--;
bigint newGas = gasNeeded(newRoutine);
if (newGas < bestGas)
{
bestGas = move(newGas);
routine = move(newRoutine);
}
}
return routine;
}
}
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);
return combineGas(
simpleRunGas(_routine) + numExps * (GasCosts::expGas + GasCosts::expByteGas),
// Data gas for routine: Some bytes are zero, but we ignore them.
bytesRequired(_routine) * (m_params.isCreation ? GasCosts::txDataNonZeroGas : GasCosts::createDataGas),
0
);
}
