compiler/optimizer/ExpressionsSimplification.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 "optimizer/ExpressionsSimplification.hpp"

#include <stddef.h>
#include <stdint.h>
#include "compile/Compilation.hpp"
#include "env/StackMemoryRegion.hpp"
#include "env/TRMemory.hpp"
#include "env/jittypes.h"
#include "il/AliasSetInterface.hpp"
#include "il/Block.hpp"
#include "il/ILOpCodes.hpp"
#include "il/ILOps.hpp"
#include "il/Node.hpp"
#include "il/Node_inlines.hpp"
#include "il/Symbol.hpp"
#include "il/SymbolReference.hpp"
#include "il/TreeTop.hpp"
#include "il/TreeTop_inlines.hpp"
#include "infra/Assert.hpp"
#include "infra/BitVector.hpp"
#include "infra/Cfg.hpp"
#include "infra/List.hpp"
#include "infra/CfgEdge.hpp"
#include "infra/CfgNode.hpp"
#include "optimizer/Dominators.hpp"
#include "optimizer/LocalAnalysis.hpp"
#include "optimizer/Optimization.hpp"
#include "optimizer/Optimization_inlines.hpp"
#include "optimizer/Structure.hpp"
#include "optimizer/TransformUtil.hpp"
#include "optimizer/VPConstraint.hpp"
#include "ras/Debug.hpp"

#define OPT_DETAILS "O^O EXPRESSION SIMPLIFICATION: "

TR_ExpressionsSimplification::TR_ExpressionsSimplification(TR::OptimizationManager *manager)
   : TR::Optimization(manager)
   {}

int32_t
TR_ExpressionsSimplification::perform()
   {
   TR::StackMemoryRegion stackMemoryRegion(*trMemory());

   int32_t cost = 0;
   _supportedExpressions = NULL;

   if (trace())
      {
      comp()->dumpMethodTrees("Trees Before Performing Expression Simplification");
      }
   cost = perform(comp()->getFlowGraph()->getStructure());

   return cost;
   }


// Process the structure recursively
//
int32_t
TR_ExpressionsSimplification::perform(TR_Structure * str)
   {
   if (trace())
      traceMsg(comp(), "Analyzing root Structure : %p\n", str);

   TR_RegionStructure *region;

   // Only regions can be simplified
   //
   if (!(region = str->asRegion()))
      return 0;

   TR_RegionStructure::Cursor it(*region);

   for (TR_StructureSubGraphNode *node = it.getCurrent();
        node != 0;
        node = it.getNext())
      {
      // Too strict
      /*
      if ((node->getPredecessors().size() == 1))
         {
         TR::CFGEdge *edge = node->getPredecessors().front();
         TR_StructureSubGraphNode *pred = toStructureSubGraphNode(edge->getFrom());
         TR_BlockStructure *b = pred->getStructure()->asBlock();
         if (b && pred->getSuccessors().size() == 1))
            perform(node->getStructure());
         }
      */
      perform(node->getStructure());
      }

   // debug only
   //
   /*
   if (region->isNaturalLoop() &&
          (region->getParent()  &&
            !region->getParent()->asRegion()->isCanonicalizedLoop()))
      {
      traceMsg(comp(), "Loop not canonicalized %x\n", region);
      }
   */

   TR::Block *entryBlock = region->getEntryBlock();
   if (region->isNaturalLoop() && !entryBlock->isCold() &&
          (region->getParent() /* &&
            region->getParent()->asRegion()->isCanonicalizedLoop() */))
         {
         if (trace())
           traceMsg(comp(), "Found candidate non cold loop %p for expression elimination\n", region);

         findAndSimplifyInvariantLoopExpressions(region);
         }

   return 1;  // Need to specify the cost
   }


void
TR_ExpressionsSimplification::findAndSimplifyInvariantLoopExpressions(TR_RegionStructure * region)
   {
   _currentRegion = region;
   TR::Block *entryBlock = _currentRegion->getEntryBlock();
   if (trace())
      traceMsg(comp(), "Entry block: %p in loop region %p\n", entryBlock, region);


   // Generate a list of blocks that can be processed
   // Criteria: the block must be excucted exactly once
   //
   TR_ScratchList<TR::Block> candidateBlocksList(trMemory());
   _currentRegion->getBlocks(&candidateBlocksList);

   if (candidateBlocksList.getSize() > 1)
      {
      if (trace())
         traceMsg(comp(), "More than 1 blocks in the natural loop, need to remove uncertain blocks\n");

      removeUncertainBlocks(_currentRegion, &candidateBlocksList);

      if (candidateBlocksList.getSize() < 1)
         return;
      }

   _currentRegion->resetInvariance();
   _currentRegion->computeInvariantExpressions();

   // The rest is the transformation
   //
   // For each block that is definitely executed once
   // analyze its nodes
   //
   ListIterator<TR::Block> candidateBlocks;
   candidateBlocks.set(&candidateBlocksList);
   simplifyInvariantLoopExpressions(candidateBlocks);
   }

void TR_ExpressionsSimplification::simplifyInvariantLoopExpressions(ListIterator<TR::Block> &blocks)
   {
   // Need to locate the induction variable of the loop
   //
   LoopInfo *loopInfo = findLoopInfo(_currentRegion);

   bool canReduceSummations = false;
   if (!loopInfo)
      {
      if (trace())
         traceMsg(comp(), "Accurate loop info is not found, cannot carry out summation reduction\n");
      }
   else
      {
      if (trace())
         traceMsg(comp(), "Accurate loop info has been found, will try to carry out summation reduction\n");

      int32_t iters = loopInfo->getNumIterations();
      if (loopInfo->getBoundaryNode())
         {
         if (trace())
            traceMsg(comp(), "Variable iterations from node %p has not been handled\n",loopInfo->getBoundaryNode());
         }
      else if (iters <= 0)
         {
         if (trace())
            traceMsg(comp(), "Failed to determine iteration count\n");
         }
      else
         {
         canReduceSummations = true;
         if (trace())
            traceMsg(comp(), "Natural Loop %p will run %d times\n", _currentRegion, iters);
         }
      }

   // Initialize the list of candidates
   //
   _candidates = new (trStackMemory()) TR_ScratchList<SimplificationCandidateTuple>(trMemory());

   for (TR::Block *currentBlock = blocks.getFirst(); currentBlock; currentBlock  = blocks.getNext())
      {
      if (trace())
         traceMsg(comp(), "Analyzing block #%d, which must be executed once per iteration\n", currentBlock->getNumber());


      // Scan through each node in the block
      //
      TR::TreeTop *tt = currentBlock->getEntry();
      TR::TreeTop *exitTreeTop = currentBlock->getExit();
      while (tt != exitTreeTop)
         {
         TR::Node *currentNode = tt->getNode();
         if (trace())
            traceMsg(comp(), "Analyzing tree top node %p\n", currentNode);

         if (canReduceSummations)
            {
            // requires loop info for the number of iterations
            setSummationReductionCandidates(currentNode, tt);
            }
         setStoreMotionCandidates(currentNode, tt);

         tt = tt->getNextTreeTop();
         }
      }

   // New code: without using any UDI
   // walk through the trees in the loop
   // to invalidate the candidates
   //
   if (!_supportedExpressions)
      {
      _supportedExpressions = new (trStackMemory()) TR_BitVector(comp()->getNodeCount(), trMemory(), stackAlloc, growable);
      }

   invalidateCandidates();

   ListIterator<SimplificationCandidateTuple> candidates(_candidates);
   for (SimplificationCandidateTuple *nextCandidate = candidates.getFirst(); nextCandidate; nextCandidate = candidates.getNext())
      {
      TR::TreeTop *treeTop = nextCandidate->getTreeTop();
      if (trace())
         {
         nextCandidate->print(comp());
         }

      bool usedCandidate = false;
      bool isPreheaderBlockInvalid = false;

      if (canReduceSummations && nextCandidate->isSummationReductionCandidate())
         {
         usedCandidate = tranformSummationReductionCandidate(treeTop, loopInfo, &isPreheaderBlockInvalid);
         }

      if (isPreheaderBlockInvalid)
         {
         break;
         }

      if (!usedCandidate && nextCandidate->isInvariantExpressionCandidate())
         {
         tranformStoreMotionCandidate(treeTop, &isPreheaderBlockInvalid);
         }
      if (isPreheaderBlockInvalid)
         {
         break;
         }
      }
   }

void TR_ExpressionsSimplification::setSummationReductionCandidates(TR::Node *node, TR::TreeTop *tt)
   {
   // Must be a store node
   //
   if (node->getOpCodeValue() != TR::istore
   /* || node->getOpCodeValue() != TR::astore */)
      {
      if (trace())
         traceMsg(comp(), "Node %p: The opcode is not istore so not a summation reduction candidate\n",node);
      return;
      }

   TR::Node *opNode = node->getFirstChild();

   if (opNode->getOpCodeValue() == TR::iadd ||
       opNode->getOpCodeValue() == TR::isub)
      {
      TR::Node *firstNode = opNode->getFirstChild();
      TR::Node *secondNode = opNode->getSecondChild();

      if (firstNode->getOpCode().hasSymbolReference() &&
            node->getSymbolReference() == firstNode->getSymbolReference() &&
            opNode->getReferenceCount() == 1 && firstNode->getReferenceCount() == 1)
         {
         // The second node must be loop invariant
         //
         if (!_currentRegion->isExprInvariant(secondNode))
            {
            if (trace())
               {
               traceMsg(comp(), "The node %p is not loop invariant\n",secondNode);

               // This can be the arithmetic series case
               // only when the node is an induction variable
               if (secondNode->getNumChildren() == 1 && secondNode->getOpCode().hasSymbolReference())
                  {
                  TR_InductionVariable *indVar = _currentRegion->findMatchingIV(secondNode->getSymbolReference());
                  if (indVar)
                     {
                     //printf("Found Candidate of arithmetic series\n" );
                     }
                  }
               }
            return;
            }

         _candidates->add(new (trStackMemory()) SimplificationCandidateTuple(tt,
                                                   flags32_t(SimplificationCandidateTuple::SummationReductionCandidate)));
         }
      else if (secondNode->getOpCode().hasSymbolReference() &&
            node->getSymbolReference() == secondNode->getSymbolReference() &&
            opNode->getReferenceCount() == 1 && secondNode->getReferenceCount() == 1 &&
            _currentRegion->isExprInvariant(firstNode))
         {
         _candidates->add(new (trStackMemory()) SimplificationCandidateTuple(tt,
                                                   flags32_t(SimplificationCandidateTuple::SummationReductionCandidate)));
         }
      }
   else if (opNode->getOpCodeValue() == TR::ixor ||
            opNode->getOpCodeValue() == TR::ineg)
      {
      if (opNode->getFirstChild()->getOpCode().hasSymbolReference() &&
            node->getSymbolReference() == opNode->getFirstChild()->getSymbolReference() &&
            opNode->getReferenceCount() == 1 && opNode->getFirstChild()->getReferenceCount() == 1 &&
            (opNode->getOpCodeValue() == TR::ineg || _currentRegion->isExprInvariant(opNode->getSecondChild())))
         {
         _candidates->add(new (trStackMemory()) SimplificationCandidateTuple(tt,
                                                   flags32_t(SimplificationCandidateTuple::SummationReductionCandidate)));
         }
      else if (opNode->getOpCodeValue() == TR::ixor && opNode->getSecondChild()->getOpCode().hasSymbolReference() &&
            node->getSymbolReference() == opNode->getSecondChild()->getSymbolReference() &&
            opNode->getReferenceCount() == 1 && opNode->getSecondChild()->getReferenceCount() == 1 &&
            _currentRegion->isExprInvariant(opNode->getFirstChild()))
         {
         _candidates->add(new (trStackMemory()) SimplificationCandidateTuple(tt,
                                                   flags32_t(SimplificationCandidateTuple::SummationReductionCandidate)));
         }
      }
   }

void TR_ExpressionsSimplification::setStoreMotionCandidates(TR::Node *node, TR::TreeTop *tt)
   {
   // Must be a store node, of any type but not holding a monitor object
   //
   if (node->getOpCode().isStore() &&
       !node->getSymbol()->isStatic() &&
       !node->getSymbol()->holdsMonitoredObject())
      {
      if (trace())
         traceMsg(comp(), "Node %p: The opcode is a non-static, non-monitor object store\n", node);

      for (int32_t i = 0; i < node->getNumChildren(); i++)
         {
         if (!_currentRegion->isExprInvariant(node->getChild(i)))
            {
            if (trace())
               traceMsg(comp(), "Node %p: The store is not loop-invariant due to child %p\n", node, node->getChild(i));
            return;
            }
         }
      // If store's operands are loop-invariant
      if (trace())
         {
         traceMsg(comp(), "Node %p: The store's operands are all loop-invariant, adding candidate\n", node);
         traceMsg(comp(), "Node %p:   - value of isExprInvariant for the store itself is %s\n", node, _currentRegion->isExprInvariant(node) ? "true" : "false");
         }
      _candidates->add(new (trStackMemory()) SimplificationCandidateTuple(tt,
                                                SimplificationCandidateTuple::InvariantExpressionCandidate));
      }
   }

bool TR_ExpressionsSimplification::tranformSummationReductionCandidate(TR::TreeTop *treeTop, LoopInfo *loopInfo, bool *isPreheaderBlockInvalid)
   {
   TR::Node *node = treeTop->getNode();
   TR::Node *opNode = node->getFirstChild();
   TR::Node *expNode = NULL;
   int32_t expChildNumber = 0;
   bool removeOnly = false;
   bool replaceWithNewNode = false;

   if (opNode->getOpCodeValue() == TR::iadd || opNode->getOpCodeValue() == TR::isub)
      {
      if (opNode->getSecondChild()->getOpCode().hasSymbolReference() &&
            node->getSymbolReference() == opNode->getSecondChild()->getSymbolReference())
         {
         expChildNumber = 0;
         expNode = opNode->getFirstChild();
         }
      else
         {
         expChildNumber = 1;
         expNode = opNode->getSecondChild();
         }
      expNode = iaddisubSimplifier(expNode, loopInfo);
      replaceWithNewNode = true;
      }
   else if (opNode->getOpCodeValue() == TR::ixor || opNode->getOpCodeValue() == TR::ineg)
      {
      expNode = ixorinegSimplifier(opNode, loopInfo, &removeOnly);
      }

   if (expNode)
      {
      if (trace())
         comp()->getDebug()->print(comp()->getOutFile(), expNode, 0, true);

      TR::Block *entryBlock = _currentRegion->getEntryBlock();
      TR::Block *preheaderBlock = findPredecessorBlock(entryBlock);

      if (!preheaderBlock)
         {
         if (trace())
            traceMsg(comp(), "Fail to find a place to put the hoist code in\n");
         *isPreheaderBlockInvalid = true;
         return true;
         }

      if (loopInfo->getNumIterations() > 0 ||     // make sure that the loop is going to be executed at least once
            _currentRegion->isCanonicalizedLoop())  // or that the loop is canonicalized, in which case the preheader is
         {                                        // executed in its first iteration and is protected.
         if (performTransformation(comp(), "%sMove out reduction node [%p] to block_%d\n", OPT_DETAILS, node, preheaderBlock->getNumber()))
            {
            if (!(removeOnly))
               {
               TR::Node *newNode = node->duplicateTree();
               if (replaceWithNewNode)
                  newNode->getFirstChild()->setAndIncChild(expChildNumber, expNode);
               transformNode(newNode, preheaderBlock);
               }
            TR::TransformUtil::removeTree(comp(), treeTop);
            }
         }
      }
      return (expNode != NULL);
   }

void TR_ExpressionsSimplification::tranformStoreMotionCandidate(TR::TreeTop *treeTop, bool *isPreheaderBlockInvalid)
   {
   TR::Node *node = treeTop->getNode();

   TR_ASSERT(node->getOpCode().isStore() && !node->getSymbol()->isStatic() && !node->getSymbol()->holdsMonitoredObject(),
      "node %p was expected to be a non-static non-monitored object store and was not.", node);

   // this candidate should be valid, either direct or indirect

   if (trace())
      comp()->getDebug()->print(comp()->getOutFile(), node, 0, true);

   TR::Block *entryBlock = _currentRegion->getEntryBlock();
   TR::Block *preheaderBlock = findPredecessorBlock(entryBlock);

   if (!preheaderBlock)
      {
      if (trace())
         traceMsg(comp(), "Fail to find a place to put the hoist code in\n");
      *isPreheaderBlockInvalid = true;
      return;
      }

   // Earlier post-dominance test ensures that the loop is executed as least once, or is canonicalized.
   // but to be safe we still perform on canonicalized loops only.
   if (_currentRegion->isCanonicalizedLoop())  // make sure that the loop is canonicalized, in which case the preheader is
      {                                        // executed in its first iteration and is protected.
      if (performTransformation(comp(), "%sMove out loop-invariant store [%p] to block_%d\n", OPT_DETAILS, node, preheaderBlock->getNumber()))
         {
         TR::Node *newNode = node->duplicateTree();
         transformNode(newNode, preheaderBlock);
         TR::TransformUtil::removeTree(comp(), treeTop);
         }
      }
   else
      {
      if (trace())
         traceMsg(comp(), "No canonicalized loop for this candidate\n");
      }
   }

void
TR_ExpressionsSimplification::invalidateCandidates()
   {
   _visitCount = comp()->incVisitCount();

   if (trace())
      {
      traceMsg(comp(), "Checking which candidates may be invalidated\n");

      ListIterator<SimplificationCandidateTuple> candidates(_candidates);
      for (SimplificationCandidateTuple *nextCandidate = candidates.getFirst(); nextCandidate; nextCandidate = candidates.getNext())
         {
         nextCandidate->print(comp());
         }
      }

   TR_ScratchList<TR::Block> blocksInLoop(trMemory());
   _currentRegion->getBlocks(&blocksInLoop);
   ListIterator<TR::Block> blocks(&blocksInLoop);

   for (TR::Block *currentBlock = blocks.getFirst(); currentBlock; currentBlock  = blocks.getNext())
      {
      TR::TreeTop *tt = currentBlock->getEntry();
      TR::TreeTop *exitTreeTop = currentBlock->getExit();
      while (tt != exitTreeTop)
         {
         TR::Node *currentNode = tt->getNode();

         if (trace())
            traceMsg(comp(), "Looking at treeTop [%p]\n", currentNode);

         removeCandidate(currentNode, tt);

         tt = tt->getNextTreeTop();
         }
      }
   removeUnsupportedCandidates();
   }

void
TR_ExpressionsSimplification::removeUnsupportedCandidates()
   {
   ListIterator<SimplificationCandidateTuple> candidates(_candidates);
   for (SimplificationCandidateTuple *nextCandidate = candidates.getFirst(); nextCandidate; nextCandidate = candidates.getNext())
      {
      TR::TreeTop *candidateTT = nextCandidate->getTreeTop();
      TR::Node *candidateNode = candidateTT->getNode();
      if (!_supportedExpressions->get(candidateNode->getGlobalIndex()))
         {
         if (trace())
            traceMsg(comp(), "Removing candidate %p which is unsupported or has unsupported subexpressions\n", candidateNode);

         _candidates->remove(nextCandidate);
         }
      }
   }

void
TR_ExpressionsSimplification::removeCandidate(TR::Node *node, TR::TreeTop* tt)
   {
   if (node->getVisitCount() == _visitCount)
      return;

   node->setVisitCount(_visitCount);

   if (trace())
      traceMsg(comp(), "Looking at Node [%p]\n", node);

   ListIterator<SimplificationCandidateTuple> candidates(_candidates);
   for (SimplificationCandidateTuple *nextCandidate = candidates.getFirst(); nextCandidate; nextCandidate = candidates.getNext())
      {
      TR::TreeTop *candidateTT = nextCandidate->getTreeTop();
      if (tt != candidateTT &&
          node->getOpCode().hasSymbolReference() &&
          candidateTT->getNode()->mayKill(true).contains(node->getSymbolReference(), comp()))
         {
         if (trace())
            traceMsg(comp(), "Removing candidate %p which has aliases in the loop\n", candidateTT->getNode());

         _candidates->remove(nextCandidate);
         continue;
         }
      }

   bool hasSupportedChildren = true;

   // Process the children as well
   //
   for (int32_t i = 0; i < node->getNumChildren(); i++)
      {
      removeCandidate(node->getChild(i), tt);
      // candidates child expressions must be invariant and supported. Here we determine if they are supported.
      if (!_supportedExpressions->get(node->getChild(i)->getGlobalIndex()))
         {
         hasSupportedChildren = false;
         }
      }

   if (hasSupportedChildren && isSupportedNodeForExpressionSimplification(node))
      {
       _supportedExpressions->set(node->getGlobalIndex());
      }
   else
      {
      if (trace())
         traceMsg(comp(), "  Node %p is unsupported expression because %s\n", node,
               !hasSupportedChildren ? "it has unsupported children" : "it is itself unsupported");
      }
   }

bool
TR_ExpressionsSimplification::isSupportedNodeForExpressionSimplification(TR::Node *node)
   {
   // types of stores that may be supported by loop invariant store motion
   bool isSupportedStoreNode = node->getOpCode().isStore();
   return TR_LocalAnalysis::isSupportedNodeForFunctionality(node, comp(), NULL, isSupportedStoreNode);
   }


static bool examineNode(TR::Node *node, intptr_t visitCount)
   {
   if (node->getVisitCount() == visitCount)
      return false;

   node->setVisitCount(static_cast<vcount_t>(visitCount));

   if (node->getOpCode().isCall())
      return true;

   bool hasCalls = false;
   for (int32_t i = 0; !hasCalls && i < node->getNumChildren(); i++)
      {
      hasCalls = examineNode(node->getChild(i), visitCount);
      }

   return hasCalls;
   }

static bool blockHasCalls(TR::Block *block, TR::Compilation *comp)
   {
   intptr_t visitCount = comp->incVisitCount();

   TR::TreeTop *currentTree = block->getEntry();
   TR::TreeTop *exitTree = block->getExit();
   bool hasCalls = false;

   while (!hasCalls && currentTree != exitTree)
      {
      hasCalls = examineNode(currentTree->getNode(), visitCount);
      currentTree = currentTree->getNextTreeTop();
      }

   return hasCalls;
   }

void
TR_ExpressionsSimplification::removeUncertainBlocks(TR_RegionStructure* region, List<TR::Block> *candidateBlocksList)
   {
   // Examine the top region block first
   //
   TR::Block *entryBlock = region->getEntryBlock();
   ListIterator<TR::Block> blocks;
   blocks.set(candidateBlocksList);

   if (trace())
      traceMsg(comp(), "Number of blocks %d, entry block number %d\n", candidateBlocksList->getSize(), entryBlock->getNumber());

   for (TR::Block *block = blocks.getFirst(); block; block = blocks.getNext())
      {
      TR::CFGNode *cfgNode = block;
      if (!(cfgNode->getExceptionSuccessors().empty()) || blockHasCalls(block, comp()))
         {
         if (trace())
            traceMsg(comp(), "An exception can be thrown from block_%d. Removing all the blocks, since we cannot know the number of iterations.\n", block->getNumber());
         candidateBlocksList->deleteAll();
         break;
         }
      }

   TR_PostDominators postDominators(comp());
   if (postDominators.isValid())
      {
      postDominators.findControlDependents();
      for (TR::Block *block = blocks.getFirst(); block; block = blocks.getNext())
         {
         if (postDominators.dominates(block, entryBlock) == 0)
            {
            candidateBlocksList->remove(block);
            if (trace())
               traceMsg(comp(), "Block_%d is not guaranteed to be executed at least once. Removing it from the list.\n", block->getNumber());
            }
         else
            {
            // If the block is within another loop that's nested in
            // the current region, remove it from consideration - blocks
            // must be executed exactly once in the loop to be considered
            TR_BlockStructure *blockStructure = block->getStructureOf();
            TR_Structure *parent = blockStructure->getParent();

            while (parent != NULL)
               {
               TR_RegionStructure *parentRegion = parent->asRegion();

               if (parentRegion == region)
                  {
                  break;
                  }
               if (parentRegion->isNaturalLoop() || parentRegion->containsInternalCycles())
                  {
                  candidateBlocksList->remove(block);

                  if (trace())
                     {
                     traceMsg(comp(), "Block_%d is nested within another loop in the current loop. Removing it from the list.\n", block->getNumber());
                     }
                  break;
                  }

               parent = parent->getParent();
               }
            }
         }
      }
   else
      {
      if (trace())
         traceMsg(comp(), "There is no post dominators information. Removing all the blocks.\n");
      for (TR::Block *block = blocks.getFirst(); block; block = blocks.getNext())
         {
         candidateBlocksList->remove(block);
         if (trace())
            traceMsg(comp(), "Block_%d is removed from the list\n", block->getNumber());
         }
      }
   }


TR_ExpressionsSimplification::LoopInfo*
TR_ExpressionsSimplification::findLoopInfo(TR_RegionStructure* region)
   {
   ListIterator<TR::CFGEdge> exitEdges(&region->getExitEdges());

   if (region->getExitEdges().getSize() != 1)
      {
      if (trace())
         traceMsg(comp(), "Region with more than 1 exit edges can't be handled\n");
      return 0;
      }

   TR::CFGEdge *exitEdge = exitEdges.getFirst();
   TR_StructureSubGraphNode* exitNode = toStructureSubGraphNode(exitEdge->getFrom());
   int32_t exitTarget = exitEdge->getTo()->getNumber();

   if (!exitNode->getStructure()->asBlock())
      {
      if (trace())
         traceMsg(comp(), "The exit block can't be found\n");
      return 0;
      }

   TR::Block *exitBlock = exitNode->getStructure()->asBlock()->getBlock();
   TR::Node *lastTreeInExitBlock = exitBlock->getLastRealTreeTop()->getNode();

   if (trace())
      {
      traceMsg(comp(), "The exit block is %d\n", exitBlock->getNumber());
      traceMsg(comp(), "The branch node is %p\n", lastTreeInExitBlock);
      }


   if (!lastTreeInExitBlock->getOpCode().isBranch())
      {
      if (trace())
         traceMsg(comp(), "The branch node couldn't be found\n");
      return 0;
      }

   if (lastTreeInExitBlock->getNumChildren() < 2)
      {
      if (trace())
         traceMsg(comp(), "The branch node has less than 2 children\n");
      return 0;
      }

   TR::Node *firstChildOfLastTree = lastTreeInExitBlock->getFirstChild();
   TR::Node *secondChildOfLastTree = lastTreeInExitBlock->getSecondChild();

   if (!firstChildOfLastTree->getOpCode().hasSymbolReference())
      {
      if (trace())
         traceMsg(comp(), "The branch node's first child node %p - its opcode does not have a symbol reference\n", firstChildOfLastTree);
      return 0;
      }

   TR::SymbolReference *firstChildSymRef = firstChildOfLastTree->getSymbolReference();

   if (trace())
      traceMsg(comp(), "Symbol Reference: %p Symbol: %p\n", firstChildSymRef, firstChildSymRef->getSymbol());

   // Locate the induction variable that matches with the exit node symbol
   //
   TR_InductionVariable *indVar = region->findMatchingIV(firstChildSymRef);
   if (!indVar) return 0;

   if (!indVar->getIncr()->asIntConst())
      {
      if (trace())
         traceMsg(comp(), "Increment is not a constant\n");
      return 0;
      }

   int32_t increment = indVar->getIncr()->getLowInt();

   _visitCount = comp()->incVisitCount();
   bool indVarWrittenAndUsedUnexpectedly = false;
   if (firstChildOfLastTree->getReferenceCount() > 1)
      {
      TR::TreeTop *cursorTreeTopInExitBlock = exitBlock->getEntry();
      TR::TreeTop *exitTreeTopInExitBlock = exitBlock->getExit();

      bool loadSeen = false;
      while (cursorTreeTopInExitBlock != exitTreeTopInExitBlock)
         {
         TR::Node *cursorNode = cursorTreeTopInExitBlock->getNode();
         if (checkForLoad(cursorNode, firstChildOfLastTree))
            loadSeen = true;

         if (!cursorNode->getOpCode().isStore() &&
             (cursorNode->getNumChildren() > 0))
           cursorNode = cursorNode->getFirstChild();

         if (cursorNode->getOpCode().isStore() &&
             (cursorNode->getSymbolReference() == firstChildSymRef))
            {
            indVarWrittenAndUsedUnexpectedly = true;
            if ((cursorNode->getFirstChild() == firstChildOfLastTree) ||
                !loadSeen)
               indVarWrittenAndUsedUnexpectedly = false;
            else
               break;
            }

         cursorTreeTopInExitBlock = cursorTreeTopInExitBlock->getNextTreeTop();
         }
      }

   if (indVarWrittenAndUsedUnexpectedly)
      {
      return 0;
      }

   int32_t lowerBound;
   int32_t upperBound = 0;
   TR::Node *bound = 0;
   bool equals = false;

   switch(lastTreeInExitBlock->getOpCodeValue())
      {
      case TR::ificmplt:
      case TR::ificmpgt:
         equals = true;
      case TR::ificmple:
      case TR::ificmpge:
         {
         TR::TreeTop *branchDestTT = lastTreeInExitBlock->getBranchDestination();
         TR::Block *branchDest = branchDestTT->getNode()->getBlock();
         if (branchDest->getNumber() != exitTarget)
            equals = !equals;

         if (!(indVar->getEntry() && indVar->getEntry()->asIntConst()))
            {
            if (trace())
               traceMsg(comp(), "Entry value is not a constant\n");
            return 0;
            }
         lowerBound = indVar->getEntry()->getLowInt();

         if (secondChildOfLastTree->getOpCode().isLoadConst())
            {
            upperBound = secondChildOfLastTree->getInt();
            }
         else if (secondChildOfLastTree->getOpCode().isLoadVar())
            {
            bound = secondChildOfLastTree;
            }
         else
            {
            if (trace())
               traceMsg(comp(), "Second child is not a const or a load\n");
            return 0;
            }
         return new (trStackMemory()) LoopInfo(bound, lowerBound, upperBound, increment, equals);
         }

      default:
         if (trace())
            traceMsg(comp(), "The condition has not been implemeted\n");
         return 0;
      }

   return 0;
   }


bool
TR_ExpressionsSimplification::checkForLoad(TR::Node *node, TR::Node *load)
   {
   if (node->getVisitCount() == _visitCount)
      return false;

   node->setVisitCount(_visitCount);

   if (node == load)
      return true;

   for (int32_t i = 0; i < node->getNumChildren(); i++)
      {
      if (checkForLoad(node->getChild(i), load))
         return true;
      }

   return false;
   }


TR::Node *
TR_ExpressionsSimplification::iaddisubSimplifier(TR::Node *invariantNode, LoopInfo* loopInfo)
   {
   TR_ASSERT_FATAL(
      loopInfo->getBoundaryNode() == NULL,
      "iteration count must be constant for loop %d",
      _currentRegion->getNumber());

   int32_t iters = loopInfo->getNumIterations();
   TR_ASSERT_FATAL(
     iters > 0,
     "iteration count (%d) must be known and positive for loop %d",
     iters,
     _currentRegion->getNumber());

   return TR::Node::create(
      invariantNode,
      TR::imul,
      2,
      invariantNode->duplicateTree(),
      TR::Node::create(invariantNode, TR::iconst, 0, iters));
   }


TR::Node *
TR_ExpressionsSimplification::ixorinegSimplifier(TR::Node *node, LoopInfo* loopInfo, bool *removeOnly)
   {
   TR::Node *newNode = 0;
   *removeOnly = false;

   if (loopInfo->getBoundaryNode())
      {
      if (trace())
         traceMsg(comp(), "Loop has a non constant boundary, but this case is not taken care of\n");
      }
   else
      {
      if (loopInfo->getNumIterations() > 0)
         {
         newNode = node;
         if (loopInfo->getNumIterations() % 2 == 0)
            {
            *removeOnly = true;
            }
         }
      }

   return newNode;
   }


TR::Block *
TR_ExpressionsSimplification::findPredecessorBlock(TR::CFGNode *entryNode)
   {
   if (!(entryNode->getPredecessors().size() == 2))
       return 0;


   TR::Block *block = 0;

   for (auto edge = entryNode->getPredecessors().begin(); edge != entryNode->getPredecessors().end(); ++edge)
      {
      if ((*edge)->getFrom()->getSuccessors().size() == 1)
         {
         block = toBlock((*edge)->getFrom());
         if (block->getStructureOf()->isLoopInvariantBlock())
            break;
         else
            block = 0;
         }
      }
   //traceMsg(comp(), "Commoned code will be put in block_%d\n", block->getNumber());
   return block;
   }


void
TR_ExpressionsSimplification::transformNode(TR::Node *srcNode, TR::Block *dstBlock)
   {
   TR::TreeTop *lastTree = dstBlock->getLastRealTreeTop();
   TR::TreeTop *prevTree = lastTree->getPrevTreeTop();
   TR::TreeTop *srcNodeTT = TR::TreeTop::create(comp(), srcNode);

   if (trace())
      comp()->getDebug()->print(comp()->getOutFile(),srcNode,0,true);

   if (lastTree->getNode()->getOpCode().isBranch() ||
       (lastTree->getNode()->getOpCode().isJumpWithMultipleTargets() && lastTree->getNode()->getOpCode().hasBranchChildren()))
      {
      srcNodeTT->join(lastTree);
      prevTree->join(srcNodeTT);
      }
   /*
   else if (dstBlock->getEntry()->getNode()->getOpCodeValue() == TR::BBStart)
      {
      srcNodeTT->join(dstBlock->getExit());
      dstBlock->getEntry()->join(srcNodeTT);
      }
   */
   else
      {
      srcNodeTT->join(dstBlock->getExit());
      lastTree->join(srcNodeTT);
      }
   return;
   }

const char *
TR_ExpressionsSimplification::optDetailString() const throw()
   {
   return "O^O EXPRESSION SIMPLIFICATION: ";
   }

void
TR_ExpressionsSimplification::SimplificationCandidateTuple::print(TR::Compilation *comp)
   {
   traceMsg(comp, "   Candidate treetop: %p node: %p  flags={", _treeTop, _treeTop->getNode());

   if (isSummationReductionCandidate())
      {
      traceMsg(comp, "SummationReductionCandidate ");
      }

   if (isInvariantExpressionCandidate())
      {
      traceMsg(comp, "InvariantExpressionCandidate ");
      }

   traceMsg(comp, "}\n");
   }