BenefitInliner.cpp

/*******************************************************************************
 * Copyright IBM Corp. and others 2020
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at https://www.eclipse.org/legal/epl-2.0/
 * or the Apache License, Version 2.0 which accompanies this distribution
 * and is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the
 * Eclipse Public License, v. 2.0 are satisfied: GNU General Public License,
 * version 2 with the GNU Classpath Exception [1] and GNU General Public
 * License, version 2 with the OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] https://openjdk.org/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0 OR GPL-2.0-only WITH OpenJDK-assembly-exception-1.0
 *******************************************************************************/

#include "optimizer/BenefitInliner.hpp"
#include "optimizer/abstractinterpreter/IDTBuilder.hpp"
#include "il/Node.hpp"
#include "il/Node_inlines.hpp"
#include <algorithm>


static bool isHot(TR::Compilation *comp)
   {
   return comp->getMethodHotness() >= hot;
   }
static bool isScorching(TR::Compilation *comp)
   {
   return ((comp->getMethodHotness() >= scorching) || ((comp->getMethodHotness() >= veryHot) && comp->isProfilingCompilation())) ;
   }


/**
 * Steps of BenefitInliner:
 *
 *
 *1. perform() --> 2. build IDT -->  3. abstract interpretation  -->  5. run inliner packing (nested knapsack) --> 6. perform inlining
 *                  |                                                |
 *                  |--  4. update IDT with inlining summaries --    |
 *
 *
 * Note: Abstract Interpretation is part of the IDT building process. Check the IDTBuilder.
 *
 */
int32_t TR::BenefitInlinerWrapper::perform()
   {
   TR::ResolvedMethodSymbol * sym = comp()->getMethodSymbol();

   if (sym->mayHaveInlineableCall())
      {
      TR::BenefitInliner inliner(optimizer(), this);
      inliner.buildInliningDependencyTree(); // IDT
      inliner.inlinerPacking(); // nested knapsack
      inliner.performInlining(comp()->getMethodSymbol());
      }

   return 1;
   }

void TR::BenefitInliner::buildInliningDependencyTree()
   {
   TR::IDTBuilder builder(comp()->getMethodSymbol(), _budget, region(), comp(), this);
   _inliningDependencyTree = builder.buildIDT();

   if (comp()->getOption(TR_TraceBIIDTGen))
      _inliningDependencyTree->print();

   _nextIDTNodeToInlineInto = _inliningDependencyTree->getRoot();
   }

void TR::BenefitInliner::inlinerPacking()
   {
   // if get enough budget to inline all options
   if (_inliningDependencyTree->getTotalCost() <= _budget)
      {
      _inliningProposal = new (region()) TR::InliningProposal(region(), _inliningDependencyTree);

      TR::deque<TR::IDTNode*, TR::Region&> idtNodeQueue(comp()->trMemory()->currentStackRegion());
      idtNodeQueue.push_back(_inliningDependencyTree->getRoot());

      while (!idtNodeQueue.empty())
         {
         TR::IDTNode* currentNode = idtNodeQueue.front();
         idtNodeQueue.pop_front();

         _inliningProposal->addNode(currentNode);

         for (uint32_t i = 0; i < currentNode->getNumChildren(); i ++)
            {
            idtNodeQueue.push_back(currentNode->getChild(i));
            }
         }

      return;
      }

   /**
    * An implementation of knapsack packing algorithm (a modified dynamic programming algorithm)
    *
    * This algorithm is described in following patent:
    * https://patents.google.com/patent/US10055210B2/en
    * and this is an implementation of the algorithm on the flowchart FIG.9.
    *
    * The following comments label which part they belong to the algorithm on the flowchart FIG.9.
    */
   _inliningDependencyTree->flattenIDT();

   const uint32_t idtSize = _inliningDependencyTree->getNumNodes();
   const uint32_t budget = _budget;

   //initialize InliningProposal Table (idtSize x budget+1)
   TR::InliningProposalTable table(idtSize, budget + 1, comp()->trMemory()->currentStackRegion());

   // prepare preorder of inlining options
   TR::IDTPriorityQueue pQueue(_inliningDependencyTree, comp()->trMemory()->currentStackRegion());
   for (uint32_t row = 0; row < idtSize; row ++)
      {
      for (uint32_t col = 1; col <= budget; col ++)
         {
         TR::InliningProposal currentSet(comp()->trMemory()->currentStackRegion(), _inliningDependencyTree); // []
         TR::IDTNode* currentNode = pQueue.get(row);

         currentSet.addNode(currentNode); //[ currentNode ]

         uint32_t rowOffset = 1;

         // check if proposal is valid
         while (!currentNode->isRoot()
            && !table.getByOffset(row, rowOffset, col, currentSet.getCost())->isNodeInProposal(currentNode->getParent()))
            {
            // if no, add proposal predecessor to proposal
            currentSet.addNode(currentNode->getParent());
            currentNode = currentNode->getParent();
            }

         // check if intersects base or if is invalid solution
         while ( currentSet.intersects(table.getByOffset(row, rowOffset, col, currentSet.getCost()))
            || ( !(currentNode->getParent() && table.getByOffset(row, rowOffset, col, currentSet.getCost())->isNodeInProposal(currentNode->getParent()) )
                  && !table.getByOffset(row, rowOffset, col, currentSet.getCost())->isEmpty()
                  ))
            {
            // if yes, consider prior base at same budget
            rowOffset++;
            }

         TR::InliningProposal* newProposal = new (comp()->trMemory()->currentStackRegion()) TR::InliningProposal(comp()->trMemory()->currentStackRegion(), _inliningDependencyTree);
         newProposal->merge(table.getByOffset(row, rowOffset, col, currentSet.getCost()), &currentSet);

         // check if cost less than budget and if previous proposal is better
         if (newProposal->getCost() <= col && newProposal->getBenefit() > table.getByOffset(row, 1, col, 0)->getBenefit()) //only set the new proposal if it fits the budget and has more benefits
            table.set(row, col, newProposal);
         else
            table.set(row, col, table.getByOffset(row, 1, col, 0));
         }
      }

   // read solution from table at last row and max budget
   TR::InliningProposal* result = new (region()) TR::InliningProposal(region(), _inliningDependencyTree);
   result->merge(result, table.getByOffset(idtSize, 1, budget, 0));

   if (comp()->getOption(TR_TraceBIProposal))
      {
      traceMsg(comp(), "\n#inliner packing:\n");
      result->print(comp());
      }

   _inliningProposal = result;
   }

int32_t TR::BenefitInlinerBase::getInliningBudget(TR::ResolvedMethodSymbol* callerSymbol)
   {
   const int32_t size = callerSymbol->getResolvedMethod()->maxBytecodeIndex();

   int32_t callerWeightLimit;

   if (isScorching(comp()))     callerWeightLimit = std::max(1500, size * 2);
   else if (isHot(comp()))      callerWeightLimit = std::max(1500, size + (size >> 2));
   else if (size < 125)         callerWeightLimit = 250;
   else if (size < 700)         callerWeightLimit = std::max(700, size + (size >> 2));
   else                         callerWeightLimit = size + (size >> 3);
   return callerWeightLimit - size; //max size we can inline
   }

bool TR::BenefitInlinerBase::inlineCallTargets(TR::ResolvedMethodSymbol *symbol, TR_CallStack *prevCallStack, TR_InnerPreexistenceInfo *info)
   {
   if (!_nextIDTNodeToInlineInto)
      return false;

   if (comp()->getOption(TR_TraceBIProposal))
      traceMsg(comp(), "#BenefitInliner: inlining into %s\n", _nextIDTNodeToInlineInto->getName(comp()->trMemory()));

   TR_CallStack callStack(comp(), symbol, symbol->getResolvedMethod(), prevCallStack, 1500, true);

   if (info)
      callStack._innerPrexInfo = info;

   bool inlined = inlineIntoIDTNode(symbol, &callStack, _nextIDTNodeToInlineInto);

   return inlined;
   }

bool TR::BenefitInlinerBase::inlineIntoIDTNode(TR::ResolvedMethodSymbol *symbol, TR_CallStack *callStack, TR::IDTNode *idtNode)
   {
   uint32_t inlineCount = 0;

   for (TR::TreeTop * tt = symbol->getFirstTreeTop(); tt; tt = tt->getNextTreeTop())
      {
      TR::Node * parent = tt->getNode();
      if (!parent->getNumChildren())
         continue;

      TR::Node * node = parent->getChild(0);
      if (!node->getOpCode().isCall())
         continue;

      if (node->getVisitCount() == _visitCount)
         continue;

      TR_ByteCodeInfo &bcInfo = node->getByteCodeInfo();

      //The actual call target to inline
      TR::IDTNode *childToInline = idtNode->findChildWithBytecodeIndex(bcInfo.getByteCodeIndex());

      if (!childToInline)
         continue;

      //only inline this call target if it is in inlining proposal
      bool shouldInline = _inliningProposal->isNodeInProposal(childToInline);

      if (!shouldInline)
         continue;

      //set _nextIDTNodeToInlineInto because we expect to enter inlineCallTargets() recursively
      _nextIDTNodeToInlineInto = childToInline;

      bool success = analyzeCallSite(callStack, tt, parent, node, childToInline->getCallTarget());

      _nextIDTNodeToInlineInto = idtNode;

      if (success)
         {
         inlineCount++;
         node->setVisitCount(_visitCount);

         }
      }

   callStack->commit();
   return inlineCount > 0;
   }

bool TR::BenefitInlinerBase::analyzeCallSite(TR_CallStack * callStack, TR::TreeTop * callNodeTreeTop, TR::Node * parent, TR::Node * callNode, TR_CallTarget *calltargetToInline)
   {

   TR::SymbolReference *symRef = callNode->getSymbolReference();

   TR_CallSite *callsite = TR_CallSite::create(callNodeTreeTop, parent, callNode,
                                               (TR_OpaqueClassBlock*) 0, symRef, (TR_ResolvedMethod*) 0,
                                               comp(), trMemory() , stackAlloc);

   getSymbolAndFindInlineTargets(callStack, callsite);

   if (!callsite->numTargets())
      return false;

   bool success = false;

   for(uint32_t i = 0; i < unsigned(callsite->numTargets()); i++)
      {
      TR_CallTarget *calltarget = callsite->getTarget(i);

      if (calltarget->_calleeMethod->isSameMethod(calltargetToInline->_calleeMethod) && !calltarget->_alreadyInlined) //we need to inline the exact call target in the IDTNode
         {
         success = inlineCallTarget(callStack, calltarget, false);
         break;
         }
      }

   return success;
   }