/src/solidity/libevmasm/Inliner.cpp

Source (jump to first uncovered line)
/*
  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/>.
*/
// SPDX-License-Identifier: GPL-3.0
/**
 * @file Inliner.cpp
 * Inlines small code snippets by replacing JUMP with a copy of the code jumped to.
 */

#include <libevmasm/Inliner.h>

#include <libevmasm/AssemblyItem.h>
#include <libevmasm/GasMeter.h>
#include <libevmasm/KnownState.h>
#include <libevmasm/SemanticInformation.h>

#include <libsolutil/CommonData.h>

#include <range/v3/numeric/accumulate.hpp>
#include <range/v3/view/drop_last.hpp>
#include <range/v3/view/enumerate.hpp>
#include <range/v3/view/slice.hpp>
#include <range/v3/view/transform.hpp>

#include <optional>
#include <limits>

using namespace std;
using namespace solidity;
using namespace solidity::evmasm;


namespace
{
/// @returns an estimation of the runtime gas cost of the AsssemblyItems in @a _itemRange.
template<typename RangeType>
u256 executionCost(RangeType const& _itemRange, langutil::EVMVersion _evmVersion)
{
  GasMeter gasMeter{std::make_shared<KnownState>(), _evmVersion};
  auto gasConsumption = ranges::accumulate(_itemRange | ranges::views::transform(
    [&gasMeter](auto const& _item) { return gasMeter.estimateMax(_item, false); }
  ), GasMeter::GasConsumption());
  if (gasConsumption.isInfinite)
    return numeric_limits<u256>::max();
  else
    return gasConsumption.value;
}
/// @returns an estimation of the code size in bytes needed for the AssemblyItems in @a _itemRange.
template<typename RangeType>
uint64_t codeSize(RangeType const& _itemRange)
{
  return ranges::accumulate(_itemRange | ranges::views::transform(
    [](auto const& _item) { return _item.bytesRequired(2, Precision::Approximate); }
  ), 0u);
}
/// @returns the tag id, if @a _item is a PushTag or Tag into the current subassembly, nullopt otherwise.
optional<size_t> getLocalTag(AssemblyItem const& _item)
{
  if (_item.type() != PushTag && _item.type() != Tag)
    return nullopt;
  auto [subId, tag] = _item.splitForeignPushTag();
  if (subId != numeric_limits<size_t>::max())
    return nullopt;
  return tag;
}
}

bool Inliner::isInlineCandidate(size_t _tag, ranges::span<AssemblyItem const> _items) const
{
  assertThrow(_items.size() > 0, OptimizerException, "");

  if (_items.back().type() != Operation)
    return false;
  if (
    _items.back() != Instruction::JUMP &&
    !SemanticInformation::terminatesControlFlow(_items.back().instruction())
  )
    return false;

  // Never inline tags that reference themselves.
  for (AssemblyItem const& item: _items)
    if (item.type() == PushTag)
      if (getLocalTag(item) == _tag)
          return false;

  return true;
}

map<size_t, Inliner::InlinableBlock> Inliner::determineInlinableBlocks(AssemblyItems const& _items) const
{
  std::map<size_t, ranges::span<AssemblyItem const>> inlinableBlockItems;
  std::map<size_t, uint64_t> numPushTags;
  std::optional<size_t> lastTag;
  for (auto&& [index, item]: _items | ranges::views::enumerate)
  {
    // The number of PushTags approximates the number of calls to a block.
    if (item.type() == PushTag)
      if (optional<size_t> tag = getLocalTag(item))
        ++numPushTags[*tag];

    // We can only inline blocks with straight control flow that end in a jump.
    // Using breaksCSEAnalysisBlock will hopefully allow the return jump to be optimized after inlining.
    if (lastTag && SemanticInformation::breaksCSEAnalysisBlock(item, false))
    {
      ranges::span<AssemblyItem const> block = _items | ranges::views::slice(*lastTag + 1, index + 1);
      if (optional<size_t> tag = getLocalTag(_items[*lastTag]))
        if (isInlineCandidate(*tag, block))
          inlinableBlockItems[*tag] = block;
      lastTag.reset();
    }

    if (item.type() == Tag)
    {
      assertThrow(getLocalTag(item), OptimizerException, "");
      lastTag = index;
    }
  }

  // Store the number of PushTags alongside the assembly items and discard tags that are never pushed.
  map<size_t, InlinableBlock> result;
  for (auto&& [tag, items]: inlinableBlockItems)
    if (uint64_t const* numPushes = util::valueOrNullptr(numPushTags, tag))
      result.emplace(tag, InlinableBlock{items, *numPushes});
  return result;
}

bool Inliner::shouldInlineFullFunctionBody(size_t _tag, ranges::span<AssemblyItem const> _block, uint64_t _pushTagCount) const
{
  // Accumulate size of the inline candidate block in bytes (without the return jump).
  uint64_t functionBodySize = codeSize(ranges::views::drop_last(_block, 1));

  // Use the number of push tags as approximation of the average number of calls to the function per run.
  uint64_t numberOfCalls = _pushTagCount;
  // Also use the number of push tags as approximation of the number of call sites to the function.
  uint64_t numberOfCallSites = _pushTagCount;

  static AssemblyItems const uninlinedCallSitePattern = {
    AssemblyItem{PushTag},
    AssemblyItem{PushTag},
    AssemblyItem{Instruction::JUMP},
    AssemblyItem{Tag}
  };
  static AssemblyItems const uninlinedFunctionPattern = {
    AssemblyItem{Tag},
    // Actual function body of size functionBodySize. Handled separately below.
    AssemblyItem{Instruction::JUMP}
  };

  // Both the call site and jump site pattern is executed for each call.
  // Since the function body has to be executed equally often both with and without inlining,
  // it can be ignored.
  bigint uninlinedExecutionCost = numberOfCalls * (
    executionCost(uninlinedCallSitePattern, m_evmVersion) +
    executionCost(uninlinedFunctionPattern, m_evmVersion)
  );
  // Each call site deposits the call site pattern, whereas the jump site pattern and the function itself are deposited once.
  bigint uninlinedDepositCost = GasMeter::dataGas(
    numberOfCallSites * codeSize(uninlinedCallSitePattern) +
    codeSize(uninlinedFunctionPattern) +
    functionBodySize,
    m_isCreation,
    m_evmVersion
  );
  // When inlining the execution cost beyond the actual function execution is zero,
  // but for each call site a copy of the function is deposited.
  bigint inlinedDepositCost = GasMeter::dataGas(
    numberOfCallSites * functionBodySize,
    m_isCreation,
    m_evmVersion
  );
  // If the block is referenced from outside the current subassembly, the original function cannot be removed.
  // Note that the function also cannot always be removed, if it is not referenced from outside, but in that case
  // the heuristics is optimistic.
  if (m_tagsReferencedFromOutside.count(_tag))
    inlinedDepositCost += GasMeter::dataGas(
      codeSize(uninlinedFunctionPattern) + functionBodySize,
      m_isCreation,
      m_evmVersion
    );

  // If the estimated runtime cost over the lifetime of the contract plus the deposit cost in the uninlined case
  // exceed the inlined deposit costs, it is beneficial to inline.
  if (bigint(m_runs) * uninlinedExecutionCost + uninlinedDepositCost > inlinedDepositCost)
    return true;

  return false;
}

optional<AssemblyItem> Inliner::shouldInline(size_t _tag, AssemblyItem const& _jump, InlinableBlock const& _block) const
{
  assertThrow(_jump == Instruction::JUMP, OptimizerException, "");
  AssemblyItem blockExit = _block.items.back();

  if (
    _jump.getJumpType() == AssemblyItem::JumpType::IntoFunction &&
    blockExit == Instruction::JUMP &&
    blockExit.getJumpType() == AssemblyItem::JumpType::OutOfFunction &&
    shouldInlineFullFunctionBody(_tag, _block.items, _block.pushTagCount)
  )
  {
    blockExit.setJumpType(AssemblyItem::JumpType::Ordinary);
    return blockExit;
  }

  // Inline small blocks, if the jump to it is ordinary or the blockExit is a terminating instruction.
  if (
    _jump.getJumpType() == AssemblyItem::JumpType::Ordinary ||
    SemanticInformation::terminatesControlFlow(blockExit.instruction())
  )
  {
    static AssemblyItems const jumpPattern = {
      AssemblyItem{PushTag},
      AssemblyItem{Instruction::JUMP},
    };
    if (
      GasMeter::dataGas(codeSize(_block.items), m_isCreation, m_evmVersion) <=
      GasMeter::dataGas(codeSize(jumpPattern), m_isCreation, m_evmVersion)
    )
      return blockExit;
  }

  return nullopt;
}


void Inliner::optimise()
{
  std::map<size_t, InlinableBlock> inlinableBlocks = determineInlinableBlocks(m_items);

  if (inlinableBlocks.empty())
    return;

  AssemblyItems newItems;
  for (auto it = m_items.begin(); it != m_items.end(); ++it)
  {
    AssemblyItem const& item = *it;
    if (next(it) != m_items.end())
    {
      AssemblyItem const& nextItem = *next(it);
      if (item.type() == PushTag && nextItem == Instruction::JUMP)
      {
        if (optional<size_t> tag = getLocalTag(item))
          if (auto* inlinableBlock = util::valueOrNullptr(inlinableBlocks, *tag))
            if (auto exitItem = shouldInline(*tag, nextItem, *inlinableBlock))
            {
              newItems += inlinableBlock->items | ranges::views::drop_last(1);
              newItems.emplace_back(move(*exitItem));

              // We are removing one push tag to the block we inline.
              --inlinableBlock->pushTagCount;
              // We might increase the number of push tags to other blocks.
              for (AssemblyItem const& inlinedItem: inlinableBlock->items)
                if (inlinedItem.type() == PushTag)
                  if (optional<size_t> duplicatedTag = getLocalTag(inlinedItem))
                    if (auto* block = util::valueOrNullptr(inlinableBlocks, *duplicatedTag))
                      ++block->pushTagCount;

              // Skip the original jump to the inlined tag and continue.
              ++it;
              continue;
            }
      }
    }
    newItems.emplace_back(item);
  }

  m_items = move(newItems);
}

Coverage Report

Created: 2022-08-24 06:32