From e3dffb611fe1736e3ffa170e6d8dc4dee17366bd Mon Sep 17 00:00:00 2001 From: chriseth Date: Wed, 21 Oct 2015 00:21:52 +0200 Subject: File reorganisation. --- libsolidity/interface/GasEstimator.cpp | 191 +++++++++++++++++++++++++++++++++ 1 file changed, 191 insertions(+) create mode 100644 libsolidity/interface/GasEstimator.cpp (limited to 'libsolidity/interface/GasEstimator.cpp') diff --git a/libsolidity/interface/GasEstimator.cpp b/libsolidity/interface/GasEstimator.cpp new file mode 100644 index 00000000..d460ba76 --- /dev/null +++ b/libsolidity/interface/GasEstimator.cpp @@ -0,0 +1,191 @@ +/* + 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 . +*/ +/** + * @author Christian + * @date 2015 + * Gas consumption estimator working alongside the AST. + */ + +#include "GasEstimator.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; +using namespace dev; +using namespace dev::eth; +using namespace dev::solidity; + +GasEstimator::ASTGasConsumptionSelfAccumulated GasEstimator::structuralEstimation( + AssemblyItems const& _items, + vector const& _ast +) +{ + solAssert(std::count(_ast.begin(), _ast.end(), nullptr) == 0, ""); + map particularCosts; + + ControlFlowGraph cfg(_items); + for (BasicBlock const& block: cfg.optimisedBlocks()) + { + assertThrow(!!block.startState, OptimizerException, ""); + GasMeter meter(block.startState->copy()); + auto const end = _items.begin() + block.end; + for (auto iter = _items.begin() + block.begin; iter != end; ++iter) + particularCosts[iter->location()] += meter.estimateMax(*iter); + } + + set finestNodes = finestNodesAtLocation(_ast); + ASTGasConsumptionSelfAccumulated gasCosts; + auto onNode = [&](ASTNode const& _node) + { + if (!finestNodes.count(&_node)) + return true; + gasCosts[&_node][0] = gasCosts[&_node][1] = particularCosts[_node.location()]; + return true; + }; + auto onEdge = [&](ASTNode const& _parent, ASTNode const& _child) + { + gasCosts[&_parent][1] += gasCosts[&_child][1]; + }; + ASTReduce folder(onNode, onEdge); + for (ASTNode const* ast: _ast) + ast->accept(folder); + + return gasCosts; +} + +map GasEstimator::breakToStatementLevel( + ASTGasConsumptionSelfAccumulated const& _gasCosts, + vector const& _roots +) +{ + solAssert(std::count(_roots.begin(), _roots.end(), nullptr) == 0, ""); + // first pass: statementDepth[node] is the distance from the deepend statement to node + // in direction of the tree root (or undefined if not possible) + map statementDepth; + auto onNodeFirstPass = [&](ASTNode const& _node) + { + if (dynamic_cast(&_node)) + statementDepth[&_node] = 0; + return true; + }; + auto onEdgeFirstPass = [&](ASTNode const& _parent, ASTNode const& _child) + { + if (statementDepth.count(&_child)) + statementDepth[&_parent] = max(statementDepth[&_parent], statementDepth[&_child] + 1); + }; + ASTReduce firstPass(onNodeFirstPass, onEdgeFirstPass); + for (ASTNode const* node: _roots) + node->accept(firstPass); + + // 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 gasCosts; + auto onNodeSecondPass = [&](ASTNode const& _node) + { + return statementDepth.count(&_node); + }; + auto onEdgeSecondPass = [&](ASTNode const& _parent, ASTNode const& _child) + { + bool useNode = false; + if (statementDepth.count(&_child)) + useNode = statementDepth[&_child] == 0; + else + useNode = statementDepth.count(&_parent) && statementDepth.at(&_parent) > 0; + if (useNode) + gasCosts[&_child] = _gasCosts.at(&_child)[1]; + }; + ASTReduce secondPass(onNodeSecondPass, onEdgeSecondPass); + for (ASTNode const* node: _roots) + node->accept(secondPass); + // gasCosts should only contain non-overlapping locations + return gasCosts; +} + +GasEstimator::GasConsumption GasEstimator::functionalEstimation( + AssemblyItems const& _items, + string const& _signature +) +{ + auto state = make_shared(); + + if (!_signature.empty()) + { + ExpressionClasses& classes = state->expressionClasses(); + using Id = ExpressionClasses::Id; + using Ids = vector; + 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(); + + unsigned parametersSize = CompilerUtils::sizeOnStack(_function.parameters()); + 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 GasEstimator::finestNodesAtLocation( + vector const& _roots +) +{ + map locations; + set nodes; + SimpleASTVisitor visitor(function(), [&](ASTNode const& _n) + { + if (!locations.count(_n.location())) + { + locations[_n.location()] = &_n; + nodes.insert(&_n); + } + }); + + for (ASTNode const* root: _roots) + root->accept(visitor); + return nodes; +} -- cgit v1.2.3