Latestness.cpp

/*******************************************************************************
 * Copyright IBM Corp. and others 2000
 *
 * 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 <stddef.h>
#include <stdint.h>
#include "compile/Compilation.hpp"
#include "env/TRMemory.hpp"
#include "il/Block.hpp"
#include "il/Node.hpp"
#include "il/TreeTop.hpp"
#include "il/TreeTop_inlines.hpp"
#include "infra/Assert.hpp"
#include "infra/Cfg.hpp"
#include "infra/List.hpp"
#include "infra/CfgEdge.hpp"
#include "infra/CfgNode.hpp"
#include "optimizer/DataFlowAnalysis.hpp"
#include "optimizer/LocalAnalysis.hpp"
#include "optimizer/Structure.hpp"

namespace TR { class Optimizer; }

// #define MAX_BLOCKS_FOR_STACK_ALLOCATION 16

// This file contains an implementation of Latestness which
// is the fourth global bit vector analyses used by PRE. Latestness
// attempts to discover for each expression, all those points in the
// CFG that are as both optimal and as late as possible. The objective
// of Latestness is to return a placement scheme that minimizes register
// pressure while maintaining optimality. This is done with a backward
// pass over the set of possible optimal points returned by Delayedness
// choosing only those points that are latest.
//
//
TR_DataFlowAnalysis::Kind TR_Latestness::getKind()
   {
   return Latestness;
   }

TR_Latestness *TR_Latestness::asLatestness()
   {
   return this;
   }

int32_t TR_Latestness::getNumberOfBits()
   {
   return _delayedness->_numberOfBits;
   }




TR_Latestness::TR_Latestness(TR::Compilation *comp, TR::Optimizer *optimizer, TR_Structure *rootStructure, bool trace)
   : TR_BackwardIntersectionBitVectorAnalysis(comp, comp->getFlowGraph(), optimizer, trace)
   {
   _delayedness = new (comp->allocator()) TR_Delayedness(comp, optimizer, rootStructure, trace);

   _supportedNodesAsArray = _delayedness->_supportedNodesAsArray;

   if (trace)
      traceMsg(comp, "Starting Latestness\n");

   TR::CFG *cfg = comp->getFlowGraph();
   _numberOfNodes = cfg->getNextNodeNumber();
   TR_ASSERT(_numberOfNodes > 0, "Latestness, node numbers not assigned");

   _numberOfBits = getNumberOfBits();

   _inSetInfo = (ContainerType **)trMemory()->allocateStackMemory(_numberOfNodes*sizeof(ContainerType *));
   for (int32_t i=0;i<_numberOfNodes;i++)
      allocateContainer(_inSetInfo+i);

   // Allocate temp bit vectors from block info, since it is local to this analysis
   ContainerType *intersection, *negation;
   allocateBlockInfoContainer(&intersection);
   allocateBlockInfoContainer(&negation);

   TR::CFGNode *nextNode;
   for (nextNode = cfg->getFirstNode(); nextNode; nextNode = nextNode->getNext())
      {
      TR_BlockStructure *blockStructure = (toBlock(nextNode))->getStructureOf();
      if ((blockStructure == NULL) || (blockStructure->getBlock()->getSuccessors().empty() && blockStructure->getBlock()->getExceptionSuccessors().empty()))
         continue;

      /////analyzeTreeTopsInBlockStructure(blockStructure);
      /////analysisInfo->_containsExceptionTreeTop = _containsExceptionTreeTop;
      initializeInfo(intersection);
      for (auto succ = nextNode->getSuccessors().begin(); succ != nextNode->getSuccessors().end(); ++succ)
         {
         TR::CFGNode *succBlock = (*succ)->getTo();
         compose(intersection, _delayedness->_inSetInfo[succBlock->getNumber()]);
         }

      /////if (getAnalysisInfo(blockStructure)->_containsExceptionTreeTop)
         {
         for (auto succ = nextNode->getExceptionSuccessors().begin(); succ != nextNode->getExceptionSuccessors().end(); ++succ)
            {
            TR::CFGNode *succBlock = (*succ)->getTo();
            compose(intersection, _delayedness->_inSetInfo[succBlock->getNumber()]);
            }
         }

      negation->setAll(_numberOfBits);
      *negation -= *intersection;
      copyFromInto(negation, _inSetInfo[blockStructure->getNumber()]);
      *(_inSetInfo[blockStructure->getNumber()]) |= *(_delayedness->_earliestness->_globalAnticipatability->_localAnticipatability.getDownwardExposedAnalysisInfo(blockStructure->getBlock()->getNumber()));
      *(_inSetInfo[blockStructure->getNumber()]) &= *(_delayedness->_inSetInfo[blockStructure->getNumber()]);

      if (trace)
         {
         traceMsg(comp, "\nIn Set of Block : %d\n", blockStructure->getNumber());
         _inSetInfo[blockStructure->getNumber()]->print(comp);
         }
      }

   if (trace)
      traceMsg(comp, "\nEnding Latestness\n");

   // Null out info that will not be used by callers
   _delayedness->_inSetInfo = NULL;
   _blockAnalysisInfo = NULL;
   }



// Overrides the implementation in the superclass as this analysis
// is slightly different from conventional bit vector analyses.
// It uses the results from local analyses instead of examining
// each tree top for effects on the input bit vector at that tree top.
// This analysis has a trivial analyzeNode(...) method as a result.
//
//
void TR_Latestness::analyzeNode(TR::Node *, vcount_t, TR_BlockStructure *, ContainerType *)
   {
   }

void TR_Latestness::analyzeTreeTopsInBlockStructure(TR_BlockStructure *blockStructure)
   {
   TR::Block *block = blockStructure->getBlock();
   TR::TreeTop *currentTree = block->getExit();
   TR::TreeTop *entryTree = block->getEntry();
   /////copyFromInto(_regularInfo, _outSetInfo[blockStructure->getNumber()]);
   bool notSeenTreeWithChecks = true;
   _containsExceptionTreeTop = false;

   while (!(currentTree == entryTree))
      {
      if (notSeenTreeWithChecks)
         {
         bool currentTreeHasChecks = treeHasChecks(currentTree);
         if (currentTreeHasChecks)
            {
            notSeenTreeWithChecks = false;
            _containsExceptionTreeTop = true;
            /////compose(_regularInfo, _exceptionInfo);
            /////compose(_outSetInfo[blockStructure->getNumber()], _exceptionInfo);
            }
         }
      else
         break;

      if (!(currentTree == entryTree))
         currentTree = currentTree->getPrevTreeTop();
      }

   }