compiler/infra/ILWalk.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 "infra/ILWalk.hpp"

#include "compile/Compilation.hpp"
#include "il/Block.hpp"
#include "il/Node_inlines.hpp"
#include "il/TreeTop.hpp"
#include "infra/Cfg.hpp"
#include "optimizer/Optimization.hpp"
#include "optimizer/Optimization_inlines.hpp"

#include <stdarg.h>

//
// Hack markers
//

// If it weren't for the fact that an already-visited block could be removed
// and re-inserted into the block list, our algorithms would be more elegant.
//
#define REMOVED_BLOCKS_CAN_BE_REINSERTED (1)


//
// TreeTopIterator and TreeTopIteratorImpl
//

TR::TreeTopIteratorImpl::TreeTopIteratorImpl(TR::TreeTop *start, TR::Compilation * comp, const char *name)
   :_current(start),_comp(comp),_name(name)
   {
   }

TR::Node *TR::TreeTopIteratorImpl::currentNode()
   {
   return currentTree()->getNode();
   }

bool TR::TreeTopIteratorImpl::isAt(PreorderNodeIterator &other)
   {
   return other.isAt(currentTree());
   }

void TR::TreeTopIteratorImpl::logCurrentLocation()
   {
   if (_name && _comp && _comp->getOption(TR_TraceILWalks))
      {
      if (currentTree())
         {
         TR::Node *node = currentTree()->getNode();
         traceMsg(_comp, "TREE  %s @ %s n%dn [%p]\n", _name, node->getOpCode().getName(), node->getGlobalIndex(), node);
         }
      else
         {
         traceMsg(_comp, "TREE  %s finished\n", _name);
         }
      }
   }

void TR::TreeTopIteratorImpl::stepForward()
   {
   TR_ASSERT(_current, "Cannot stepForward a TreeTopIterator that has already moved beyond the first or last tree of the method");
   _current = _current->getNextTreeTop();
   }

void TR::TreeTopIteratorImpl::stepBackward()
   {
   TR_ASSERT(_current, "Cannot stepBackward a TreeTopIterator that has already moved beyond the first or last tree of the method");
   _current = _current->getPrevTreeTop();
   }

//
// Node iterators
//

TR::NodeIterator::NodeIterator(TR::TreeTop *start, TR::Compilation *comp, const char *name)
   :TreeTopIteratorImpl(start, comp, name)
   ,_checklist(comp)
   ,_stack(comp->trMemory(), 5, false, stackAlloc)
   {}

bool TR::NodeIterator::isAt(PreorderNodeIterator &other)
   {
   // One PreorderNodeIterator "is at" another if both follow the same node
   // child path from the same treetop.  Note that the checklist is explicitly
   // NOT compared.  This means that a.isAt(b) is no guarantee that a and b
   // will subsequently return the same sequence of nodes.  This is
   // intentional--isAt is not an equality test--and it could occur if the
   // iterations started at differnet points, or if there were differences in
   // timing between advancement of the iterator versus mutations in the IL.
   // This function explicitly disregards such differences.
   //
   if (currentTree() != other.currentTree())
      return false;
   if (stackDepth() != other.stackDepth())
      return false;
   for (int32_t i = 0; i < stackDepth(); i++)
      if (_stack[i] != other._stack[i])
         return false;
   return true;
   }

void TR::NodeIterator::logCurrentLocation()
   {
   if (_name && comp() && comp()->getOption(TR_TraceILWalks))
      {
      if (currentTree())
         {
         TR::Node *node = currentNode();
         traceMsg(comp(), "NODE  %s  ", _name);
         if (stackDepth() >= 2)
            {
            traceMsg(comp(), " ");
            for (int32_t i = 0; i < stackDepth()-2; i++)
               {
               if (_stack[i]._isBetweenChildren)
                  traceMsg(comp(), " |");
               else
                  traceMsg(comp(), "  ");
               }
            traceMsg(comp(), " %d: ", _stack[_stack.topIndex()-1]._child);
            }
         traceMsg(comp(), "%s n%dn [%p]\n", node->getOpCode().getName(), node->getGlobalIndex(), node);
         }
      else
         {
         // Usualy this one doesn't print, because when the iterator finishes
         // naturally, logCurrentLocation is not even called.
         //
         traceMsg(comp(), "NODE  %s finished\n", _name );
         }
      }
   }

TR::PreorderNodeIterator::PreorderNodeIterator(TR::TreeTop *start, TR::Compilation * comp, const char *name)
   :NodeIterator(start, comp, name)
   {
   push(start->getNode());
   }

bool TR::PreorderNodeIterator::alreadyBeenPushed(TR::Node *node)
   {
   return _checklist.contains(node);
   }

void TR::PreorderNodeIterator::push(TR::Node *node)
   {
   TR_ASSERT(!alreadyBeenPushed(node), "Cannot push node n%dn that was already pushed", node->getGlobalIndex());
   _stack.push(WalkState(node));
   _stack.top()._isBetweenChildren = (node->getNumChildren() >= 2);
   _checklist.add(node);
   logCurrentLocation();
   }

void TR::PreorderNodeIterator::stepForward()
   {
   // Move down into the next un-visited child
   //
   for (int32_t i = _stack.top()._child; i < _stack.top()._node->getNumChildren(); i++)
      {
      TR::Node *child = _stack.top()._node->getChild(i);
      if (!alreadyBeenPushed(child))
         {
         _stack.top()._child = i;
         if (i == _stack.top()._node->getNumChildren()-1)
            _stack.top()._isBetweenChildren = false;
         push(child);
         return;
         }
      }

   // No more un-visited children; we're done with this node
   //
   _stack.pop();
   if (_stack.isEmpty())
      {
      // Step to the next tree, if any
      //
      while (_stack.isEmpty())
         {
         TreeTopIteratorImpl::stepForward();
         if (!currentTree())
            return;
         else if (!alreadyBeenPushed(currentTree()->getNode()))
            push(currentTree()->getNode());
         }
      }
   else
      {
      _stack.top()._child++;
      stepForward();
      }
   }

TR::PostorderNodeIterator::PostorderNodeIterator(TR::TreeTop *start, TR::Compilation * comp, const char *name)
   :NodeIterator(start, comp, name)
   {
   push(start->getNode());
   descend();
   }

bool TR::PostorderNodeIterator::alreadyBeenPushed(TR::Node *node)
   {
   return _checklist.contains(node);
   }

void TR::PostorderNodeIterator::push(TR::Node *node)
   {
   TR_ASSERT(!alreadyBeenPushed(node), "Cannot push node n%dn that was already pushed", node->getGlobalIndex());
   _stack.push(WalkState(node));
   _checklist.add(node);
   }

void TR::PostorderNodeIterator::descend()
   {
   // Push frames until we find the innermost, leftmost unvisited descendant.
   TR::Node *node = _stack.top()._node;
   for (;;)
      {
      int32_t i = _stack.top()._child;
      while (i < node->getNumChildren() && alreadyBeenPushed(node->getChild(i)))
         i++;

      _stack.top()._child = i;
      if (i == node->getNumChildren())
         break;

      node = node->getChild(i);
      push(node);
      }

   logCurrentLocation();
   }

void TR::PostorderNodeIterator::stepForward()
   {
   // We're done with the current node and all its descendants. Move back up
   // to the parent and attempt to descend into later subtrees.
   _stack.pop();
   if (!_stack.isEmpty())
      {
      _stack.top()._child++;
      _stack.top()._isBetweenChildren = true;
      descend();
      return;
      }

   // Step to the next tree, if any
   do
      TreeTopIteratorImpl::stepForward();
   while (currentTree() && alreadyBeenPushed(currentTree()->getNode()));

   if (!currentTree())
     return;

   push(currentTree()->getNode());
   descend();
   }

//
// Node occurrence iterators
//

TR::Node *TR::NodeOccurrenceIterator::currentNode()
   {
   if (stackDepth() == 0)
      return currentTree()->getNode();
   else
      return _stack.top()._node->getChild(_stack.top()._child);
   }

void TR::NodeOccurrenceIterator::logCurrentLocation()
   {
   if (_name && comp() && comp()->getOption(TR_TraceILWalks))
      {
      if (currentTree())
         {
         TR::Node *node = currentNode();
         traceMsg(comp(), "WALK  %s  ", _name);
         if (stackDepth() >= 1)
            {
            traceMsg(comp(), " ");
            for (int32_t i = 0; i < stackDepth()-1; i++)
               {
               if (_stack[i]._isBetweenChildren)
                  traceMsg(comp(), " |");
               else
                  traceMsg(comp(), "  ");
               }
            traceMsg(comp(), " %d: ", _stack[_stack.topIndex()]._child);
            }
         traceMsg(comp(), "%s n%dn [%p]\n", node->getOpCode().getName(), node->getGlobalIndex(), node);
         }
      else
         {
         // Usually this one doesn't print, because when the iterator finishes
         // naturally, logCurrentLocation is not even called.
         //
         traceMsg(comp(), "WALK  %s finished\n", _name );
         }
      }
   }

TR::PreorderNodeOccurrenceIterator::PreorderNodeOccurrenceIterator(TR::TreeTop *start, TR::Compilation * comp, const char *name)
   :NodeOccurrenceIterator(start, comp, name)
   {
   logCurrentLocation();
   }

bool TR::PreorderNodeOccurrenceIterator::alreadyPushedChildren(TR::Node *node)
   {
   return _checklist.contains(node);
   }

void TR::PreorderNodeOccurrenceIterator::push(TR::Node *node)
   {
   _stack.push(WalkState(node));
   _stack.top()._isBetweenChildren = (node->getNumChildren() >= 2);
   _checklist.add(node);
   logCurrentLocation();
   }

void TR::PreorderNodeOccurrenceIterator::stepForward()
   {
   if (currentNode()->getNumChildren() >= 1 && !alreadyPushedChildren(currentNode()))
      {
      // Pushing currentNode has the effect of moving down into its children
      //
      push(currentNode());
      }
   else if (_stack.isEmpty())
      {
      // Nullary treetop node; move on to the next treetop
      //
      TreeTopIteratorImpl::stepForward();
      logCurrentLocation();
      }
   else if (++_stack.top()._child < _stack.top()._node->getNumChildren())
      {
      // Our attempt to move to the next sibling was successful
      //
      if (_stack.top()._child == _stack.top()._node->getNumChildren()-1)
         _stack.top()._isBetweenChildren = false;
      logCurrentLocation();
      }
   else
      {
      // No more siblings; try moving to parent's siblings
      //
      _stack.pop();
      stepForward();
      }
   }

TR::PostorderNodeOccurrenceIterator::PostorderNodeOccurrenceIterator(TR::TreeTop *start, TR::Compilation * comp, const char *name)
   :NodeOccurrenceIterator(start, comp, name)
   {
   pushLeftmost(currentTree()->getNode());
   }

bool TR::PostorderNodeOccurrenceIterator::alreadyPushedChildren(TR::Node *node)
   {
   return _checklist.contains(node);
   }

void TR::PostorderNodeOccurrenceIterator::pushLeftmost(TR::Node *nodeArg)
   {
   for (TR::Node *node = nodeArg; node->getNumChildren() >= 1 && !alreadyPushedChildren(node); node = node->getFirstChild())
      {
      _stack.push(WalkState(node));
      _checklist.add(node);
      }
   logCurrentLocation();
   }

void TR::PostorderNodeOccurrenceIterator::stepForward()
   {
   if (_stack.isEmpty())
      {
      // Nullary treetop node; move on to the next treetop
      //
      TreeTopIteratorImpl::stepForward();
      if (currentTree())
         pushLeftmost(currentTree()->getNode());
      }
   else if (++_stack.top()._child < _stack.top()._node->getNumChildren())
      {
      // Our attempt to move to the next sibling was successful
      //
      _stack.top()._isBetweenChildren = true;
      pushLeftmost(currentNode());
      }
   else
      {
      // No more siblings; move to parent
      //
      _stack.pop();
      logCurrentLocation();
      }
   }

//
// Block iterators
//

TR::BlockIterator::BlockIterator(TR::Compilation * comp, const char *name)
   :_comp(comp),_name(name)
   {
   }

bool TR::BlockIterator::isLoggingEnabled()
   {
   return (_name && _comp && _comp->getOption(TR_TraceILWalks));
   }

TR::ReversePostorderSnapshotBlockIterator::ReversePostorderSnapshotBlockIterator(TR::Block *start, TR::Compilation * comp, const char *name)
   :BlockIterator(comp, name),
   _postorder(comp->trMemory(), 5, false, stackAlloc)
   {
   takeSnapshot(start);
   logCurrentLocation();
   }

TR::ReversePostorderSnapshotBlockIterator::ReversePostorderSnapshotBlockIterator(TR::CFG *cfg, TR::Compilation *comp, const char *name)
   :BlockIterator(comp, name),
   _postorder(comp->trMemory(), cfg->getNumberOfNodes(), false, stackAlloc)
   {
   takeSnapshot(cfg->getStart()->asBlock());
   if (isLoggingEnabled())
      {
      traceMsg(comp, "BLOCK  %s Snapshot:", _name);
      for (int32_t i = _postorder.lastIndex(); i >= 0; --i)
         traceMsg(comp, " %d", _postorder[i]->getNumber());
      traceMsg(comp, "\n");
      }
   logCurrentLocation();
   }

void TR::ReversePostorderSnapshotBlockIterator::takeSnapshot(TR::Block *start)
   {
   // TODO: This should use an iterative algorithm with a worklist, but the recursive algo is so much easier to write...
   TR::BlockChecklist alreadyVisited(comp());
   visit(start, alreadyVisited);
   _currentIndex = _postorder.lastIndex();
   }

void TR::ReversePostorderSnapshotBlockIterator::visit(TR::Block *block, TR::BlockChecklist &alreadyVisited)
   {
   if (alreadyVisited.contains(block))
      return;
   alreadyVisited.add(block);

   TR_SuccessorIterator bi(block);
   for (TR::CFGEdge *edge = bi.getFirst(); edge != NULL; edge = bi.getNext())
      visit(edge->getTo()->asBlock(), alreadyVisited);
   if (block->getEntry()) // Don't add the special blocks with no trees to the snapshot
      _postorder.add(block);
   }

TR::Block *TR::ReversePostorderSnapshotBlockIterator::currentBlock()
   {
   if (0 <= _currentIndex && _currentIndex <= _postorder.lastIndex())
      return _postorder[_currentIndex];
   else
      return NULL;
   }

void TR::ReversePostorderSnapshotBlockIterator::stepForward()
   {
   TR_ASSERT(currentBlock(), "cannot stepForward a ReversePostorderSnapshotBlockIterator that has already finished its walk");
   do
      --_currentIndex;
   while (!isStepOperationFinished());
   logCurrentLocation();
   }

void TR::ReversePostorderSnapshotBlockIterator::stepBackward()
   {
   TR_ASSERT(currentBlock(), "cannot stepForward a ReversePostorderSnapshotBlockIterator that has already finished its walk");
   do
      ++_currentIndex;
   while (!isStepOperationFinished());
   logCurrentLocation();
   }

bool TR::ReversePostorderSnapshotBlockIterator::isStepOperationFinished()
   {
   if (!currentBlock())
      return true; // Reached the end
   else if (currentBlock()->isValid())
      return true; // Reached the next block in the walk

   if (isLoggingEnabled())
      traceMsg(comp(), "BLOCK  %s Skip block_%d removed during walk\n", _name, currentBlock()->getNumber());
   return false;
   }

void TR::ReversePostorderSnapshotBlockIterator::logCurrentLocation()
   {
   if (isLoggingEnabled())
      {
      if (currentBlock())
         traceMsg(comp(), "BLOCK  %s @ block_%d\n", _name, currentBlock()->getNumber());
      else
         traceMsg(comp(), "BLOCK  %s finished\n", _name);
      }
   }

TR::AllBlockIterator::AllBlockIterator(TR::CFG *cfg, TR::Compilation * comp, const char *name)
   :BlockIterator(comp, name),_cfg(cfg),_currentBlock(cfg->getFirstNode()->asBlock()),_nextBlock(_currentBlock->getNext()->asBlock()),_alreadyVisited(cfg->comp())
   {
   _alreadyVisited.add(_currentBlock);
   logCurrentLocation();
   }

TR::Block *TR::AllBlockIterator::currentBlock()
   {
   return _currentBlock;
   }

void TR::AllBlockIterator::stepForward()
   {
   TR_ASSERT(_currentBlock, "Cannot stepForward an AllBlockIterator that has already finished iterating");

   // INVARIANT: All visited blocks in the linked list of CFG nodes are at
   // the end of the list.  Therefore, when we hit an already-visited block,
   // we can quit scanning the list.

   // Note: it's crucially important that we use _currentBlock->getNext()->asBlock()
   // and definitely NOT _currentBlock->getNextBlock().  The latter returns
   // blocks in treetop order, which will not provide the "all blocks"
   // guarantee if new blocks are inserted physically before the current one.

   // Move forward, stopping when we hit the end of the list, or a block we've already seen
   //
   TR::CFGNode *next = _nextBlock;
   if (next == NULL || _alreadyVisited.contains(next->asBlock()))
      {
      // Start another lap of the list to catch newly added blocks we need to visit
      //
      next = _cfg->getFirstNode();
      TR_ASSERT(next != NULL, "AllBlockIterator not expecting a CFG with no blocks at all");
      if (_alreadyVisited.contains(next->asBlock()))
         {
         // Since newly added blocks always go at the front, and we never
         // insert a previously removed block, we're done as soon as we try
         // to take another lap and find that the first block in the list is
         // already visited.
         //
         next = NULL;
         }
      }

   if (REMOVED_BLOCKS_CAN_BE_REINSERTED && !next)
      {
      // Can't be certain about our "INVARIANT" after all.  Do another
      // pass looking for any blocks we haven't visited.
      //
      // This isn't the most efficient possible algorithm -- it is O(n^2) in the
      // worst case -- but it cleanly separates the cruft from the main algorithm.
      //
      for (next = _cfg->getFirstNode(); next; next = next->getNext())
         {
         if (!_alreadyVisited.contains(next->asBlock()))
            {
            // Found one!
            //
            if (isLoggingEnabled())
               traceMsg(comp(), "BLOCK  %s REMOVED_BLOCKS_CAN_BE_REINSERTED: block_%d found via extra scan\n", _name, next->asBlock()->getNumber());
            break;
            }
         }
      }

   if (next)
      {
      _currentBlock = next->asBlock();
      _nextBlock    = _currentBlock->getNext()? _currentBlock->getNext()->asBlock() : NULL;
      _alreadyVisited.add(_currentBlock);
      if (_currentBlock->getEntry())
         {
         logCurrentLocation();
         }
      else
         {
         // Skip the special blocks that have no trees.
         //
         stepForward();
         }
      }
   else
      {
      _currentBlock = NULL;
      }

   }

void TR::AllBlockIterator::logCurrentLocation()
   {
   if (isLoggingEnabled())
      {
      if (currentBlock())
         traceMsg(comp(), "BLOCK  %s @ block_%d\n", _name, currentBlock()->getNumber());
      else
         traceMsg(comp(), "BLOCK  %s finished\n", _name);
      }
   }

TR::TreeTopOrderExtendedBlockIterator::TreeTopOrderExtendedBlockIterator(TR::Compilation* comp, const char* name)
   :
      BlockIterator(comp, name), _currBlock(comp->getStartBlock()), _nextBlock(_currBlock->getNextExtendedBlock())
   {
   logCurrentLocation();
   }

TR::Block* TR::TreeTopOrderExtendedBlockIterator::getFirst()
   {
   return _currBlock;
   }

TR::Block* TR::TreeTopOrderExtendedBlockIterator::getLast()
   {
   if (_nextBlock != NULL)
      {
      return _nextBlock->getPrevBlock();
      }
   else
      {
      TR::Block* lastBlock = _currBlock;

      for (TR::Block* nextBlock = _currBlock->getNextBlock(); nextBlock != NULL; lastBlock = nextBlock, nextBlock = lastBlock->getNextBlock())
         {
         // Void
         }

      return lastBlock;
      }
   }

void TR::TreeTopOrderExtendedBlockIterator::operator++()
   {
   TR_ASSERT(_currBlock != NULL, "Cannot increment an TreeTopOrderExtendedBlockIterator that has already finished iterating");

   _currBlock = _nextBlock;

   if (_nextBlock != NULL)
      {
      _nextBlock = _nextBlock->getNextExtendedBlock();

      logCurrentLocation();
      }
   }

void TR::TreeTopOrderExtendedBlockIterator::logCurrentLocation()
   {
   if (isLoggingEnabled())
      {
      if (getFirst() != NULL)
         {
         traceMsg(comp(), "BLOCK %s @ block_%d\n", _name, getFirst()->getNumber());
         }
      else
         {
         traceMsg(comp(), "BLOCK %s finished\n", _name);
         }
      }
   }