int32_t TR_AsyncCheckInsertion::insertReturnAsyncChecks(TR::Optimization *opt, const char *counterPrefix)
   {
   TR::Compilation * const comp = opt->comp();
   if (opt->trace())
      traceMsg(comp, "Inserting return asyncchecks (%s)\n", counterPrefix);

   int numAsyncChecksInserted = 0;
   for (TR::TreeTop *treeTop = comp->getStartTree();
        treeTop;
        /* nothing */ )
      {
      TR::Block *block = treeTop->getNode()->getBlock();
      if (block->getLastRealTreeTop()->getNode()->getOpCode().isReturn()
          && performTransformation(comp,
               "%sInserting return asynccheck (%s) in block_%d\n",
               opt->optDetailString(),
               counterPrefix,
               block->getNumber()))
         {
         insertAsyncCheck(block, comp, counterPrefix);
         numAsyncChecksInserted++;
         }

      treeTop = block->getExit()->getNextRealTreeTop();
      }
   return numAsyncChecksInserted;
   }

void TR_ReachingDefinitions::initializeGenAndKillSetInfo()
   {
   // For each block in the CFG build the gen and kill set for this analysis.
   // Go in treetop order, which guarantees that we see the correct (i.e. first)
   // evaluation point for each node.
   //
   TR::Block *block;
   int32_t   blockNum = 0;
   bool      seenException = false;
   TR_BitVector defsKilled(getNumberOfBits(), trMemory()->currentStackRegion());

   comp()->incVisitCount();
   for (TR::TreeTop *treeTop = comp()->getStartTree(); treeTop; treeTop = treeTop->getNextTreeTop())
      {
      TR::Node *node = treeTop->getNode();

      if (node->getOpCodeValue() == TR::BBStart)
         {
         block = node->getBlock();
         blockNum = block->getNumber();
         seenException  = false;
         if (traceRD())
            traceMsg(comp(), "\nNow generating gen and kill information for block_%d\n", blockNum);
         continue;
         }

#if DEBUG
      if (node->getOpCodeValue() == TR::BBEnd && traceRD())
         {
         traceMsg(comp(), "  Block %d:\n", blockNum);
         traceMsg(comp(), "     Gen set ");
         if (_regularGenSetInfo[blockNum])
            _regularGenSetInfo[blockNum]->print(comp());
         else
            traceMsg(comp(), "{}");
         traceMsg(comp(), "\n     Kill set ");
         if (_regularKillSetInfo[blockNum])
            _regularKillSetInfo[blockNum]->print(comp());
         else
            traceMsg(comp(), "{}");
         traceMsg(comp(), "\n     Exception Gen set ");
         if (_exceptionGenSetInfo[blockNum])
            _exceptionGenSetInfo[blockNum]->print(comp());
         else
            traceMsg(comp(), "{}");
         traceMsg(comp(), "\n     Exception Kill set ");
         if (_exceptionKillSetInfo[blockNum])
            _exceptionKillSetInfo[blockNum]->print(comp());
         else
            traceMsg(comp(), "{}");
         continue;
         }
#endif

      initializeGenAndKillSetInfoForNode(node, defsKilled, seenException, blockNum, NULL);

      if (!seenException && treeHasChecks(treeTop))
         seenException = true;
      }
   }

// Add an async check into a block - MUST be at block entry
//
void TR_AsyncCheckInsertion::insertAsyncCheck(TR::Block *block, TR::Compilation *comp, const char *counterPrefix)
   {
   TR::TreeTop *lastTree = block->getLastRealTreeTop();
   TR::TreeTop *asyncTree =
      TR::TreeTop::create(comp,
         TR::Node::createWithSymRef(lastTree->getNode(), TR::asynccheck, 0,
            comp->getSymRefTab()->findOrCreateAsyncCheckSymbolRef(comp->getMethodSymbol())));


   if (lastTree->getNode()->getOpCode().isReturn())
      {
      TR::TreeTop *prevTree = lastTree->getPrevTreeTop();
      prevTree->join(asyncTree);
      asyncTree->join(lastTree);
      }
   else
      {
      TR::TreeTop *nextTree = block->getEntry()->getNextTreeTop();
      block->getEntry()->join(asyncTree);
      asyncTree->join(nextTree);
      }

   const char * const name = TR::DebugCounter::debugCounterName(comp,
      "asynccheck.insert/%s/(%s)/%s/block_%d",
      counterPrefix,
      comp->signature(),
      comp->getHotnessName(),
      block->getNumber());
   TR::DebugCounter::prependDebugCounter(comp, name, asyncTree->getNextTreeTop());
   }

void
OMR::IlValue::storeToAuto()
   {
   if (_symRefThatCanBeUsedInOtherBlocks == NULL)
      {
      TR::Compilation *comp = TR::comp();

      // first use from another block, need to create symref and insert store tree where node  was computed
      TR::SymbolReference *symRef = comp->getSymRefTab()->createTemporary(_methodBuilder->methodSymbol(), _nodeThatComputesValue->getDataType());
      symRef->getSymbol()->setNotCollected();
      char *name = (char *) comp->trMemory()->allocateHeapMemory((2+10+1) * sizeof(char)); // 2 ("_T") + max 10 digits + trailing zero
      sprintf(name, "_T%u", symRef->getCPIndex());
      symRef->getSymbol()->getAutoSymbol()->setName(name);
      _methodBuilder->defineSymbol(name, symRef);

      // create store and its treetop
      TR::Node *storeNode = TR::Node::createStore(symRef, _nodeThatComputesValue);
      TR::TreeTop *prevTreeTop = _treeTopThatAnchorsValue->getPrevTreeTop();
      TR::TreeTop *newTree = TR::TreeTop::create(comp, storeNode);
      newTree->insertNewTreeTop(prevTreeTop, _treeTopThatAnchorsValue);

      _treeTopThatAnchorsValue->unlink(true);

      _treeTopThatAnchorsValue = newTree;
      _symRefThatCanBeUsedInOtherBlocks = symRef;
      }
   }

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();
      }

   }

int32_t
OMR::Simplifier::perform()
   {

   vcount_t visitCount = comp()->incOrResetVisitCount();
   TR::TreeTop * tt;
   for (tt = comp()->getStartTree(); tt; tt = tt->getNextTreeTop())
      tt->getNode()->initializeFutureUseCounts(visitCount);

   comp()->incVisitCount();
   for (tt = comp()->getStartTree(); tt; tt = tt->getNextTreeTop())
      cleanupFlags(tt->getNode());

   visitCount = comp()->incVisitCount();
   tt = comp()->getStartTree();
   while (tt)
      tt = simplifyExtendedBlock(tt);

   comp()->getFlowGraph()->removeUnreachableBlocks();

   if (manager()->numPassesCompleted() == 0)
      manager()->incNumPassesCompleted();

   return 1;
   }

void TR::ILValidator::checkSoundness(TR::TreeTop *start, TR::TreeTop *stop)
   {
   soundnessRule(start, start != NULL, "Start tree must exist");
   soundnessRule(stop, !stop || stop->getNode() != NULL, "Stop tree must have a node");

   TR::NodeChecklist treetopNodes(comp()), ancestorNodes(comp()), visitedNodes(comp());

   // Can't use iterators here, because those presuppose the IL is sound.  Walk trees the old-fashioned way.
   //
   for (TR::TreeTop *currentTree = start; currentTree != stop; currentTree = currentTree->getNextTreeTop())
      {
      soundnessRule(currentTree, currentTree->getNode() != NULL, "Tree must have a node");
      soundnessRule(currentTree, !treetopNodes.contains(currentTree->getNode()), "Treetop node n%dn encountered twice", currentTree->getNode()->getGlobalIndex());

      treetopNodes.add(currentTree->getNode());

      TR::TreeTop *next = currentTree->getNextTreeTop();
      if (next)
         {
         soundnessRule(currentTree, next->getNode() != NULL, "Tree after n%dn must have a node", currentTree->getNode()->getGlobalIndex());
         soundnessRule(currentTree, next->getPrevTreeTop() == currentTree, "Doubly-linked treetop list must be consistent: n%dn->n%dn<-n%dn", currentTree->getNode()->getGlobalIndex(), next->getNode()->getGlobalIndex(), next->getPrevTreeTop()->getNode()->getGlobalIndex());
         }
      else
         {
         soundnessRule(currentTree, stop == NULL, "Reached the end of the trees after n%dn without encountering the stop tree n%dn", currentTree->getNode()->getGlobalIndex(), stop? stop->getNode()->getGlobalIndex() : 0);
         checkNodeSoundness(currentTree, currentTree->getNode(), ancestorNodes, visitedNodes);
         }
      }
   }

TR_DominatorVerifier::TR_DominatorVerifier(TR_Dominators &findDominators)
   : _compilation(findDominators.comp())
   {
   TR::StackMemoryRegion stackMemoryRegion(*trMemory());

   _dominators = &findDominators;

   TR::CFG *cfg = comp()->getFlowGraph();
   _visitCount = comp()->incVisitCount();
   _numBlocks = cfg->getNumberOfNodes()+1;

   if (debug("traceVER"))
      {
      dumpOptDetails(comp(), "Printing out the TreeTops from DominatorVerifier\n");

      TR::TreeTop *currentTree = comp()->getStartTree();

      while (!(currentTree == NULL))
         {
         comp()->getDebug()->print(comp()->getOutFile(), currentTree);
         currentTree = currentTree->getNextTreeTop();
         }

      dumpOptDetails(comp(), "Printing out the CFG from DominatorVerifier\n");
      if (cfg != NULL)
         comp()->getDebug()->print(comp()->getOutFile(), cfg);
      }

   TR_DominatorsChk expensiveAlgorithm(comp());
   expensiveAlgorithmCorrect = isExpensiveAlgorithmCorrect(expensiveAlgorithm);

   if (expensiveAlgorithmCorrect)
      {
      if (debug("traceVER"))
         dumpOptDetails(comp(), "Dominators computed by the expensive algorithm are correct\n");
      }
   else
      {
      if (debug("traceVER"))
         dumpOptDetails(comp(), "Dominators computed by the expensive algorithm are NOT correct\n");
      TR_ASSERT(0, "Dominators computed by the expensive algorithm are NOT correct\n");
      }


   bothImplementationsConsistent = areBothImplementationsConsistent(expensiveAlgorithm, findDominators);

   if (bothImplementationsConsistent)
      {
      if (debug("traceVER"))
         dumpOptDetails(comp(), "Dominators computed by the two implementations are consistent\n");
      }
   else
      {
      if (debug("traceVER"))
         dumpOptDetails(comp(), "Dominators computed by the two implementations are NOT consistent\n");
      TR_ASSERT(0, "Dominators computed by the two implementations are NOT consistent\n");
      }
   }

TR::TreeTop *
OMR::TreeTop::getExtendedBlockExitTreeTop()
   {
   TR_ASSERT(self()->getNode()->getOpCodeValue() == TR::BBStart, "getExitTreeTop, is only valid for a bbStart");
   TR::Block * b;
   TR::TreeTop * exitTT = self()->getNode()->getBlock()->getExit(), * nextTT;
   while ((nextTT = exitTT->getNextTreeTop()) && (b = nextTT->getNode()->getBlock(), b->isExtensionOfPreviousBlock()))
      exitTT = b->getExit();
   return exitTT;
   }

inline TR::TreeTop *
OMR::TreeTop::getPrevRealTreeTop()
   {
   TR::TreeTop *treeTop;
   for (treeTop = self()->getPrevTreeTop();
        treeTop && treeTop->getNode()->getOpCode().isExceptionRangeFence();
        treeTop = treeTop->getPrevTreeTop())
      {}
   return treeTop;
   }

void
OMR::CodeGenPhase::performCleanUpFlagsPhase(TR::CodeGenerator * cg, TR::CodeGenPhase * phase)
   {
   TR::TreeTop * tt;
   vcount_t visitCount = cg->comp()->incVisitCount();

   for (tt = cg->comp()->getStartTree(); tt; tt = tt->getNextTreeTop())
      {
      cg->cleanupFlags(tt->getNode());
      }
   }

inline void
OMR::TreeTop::unlink(bool decRefCountRecursively)
   {
   TR::TreeTop *prevTT = self()->getPrevTreeTop();
   TR::TreeTop *nextTT = self()->getNextTreeTop();

   prevTT->setNextTreeTop(nextTT);
   nextTT->setPrevTreeTop(prevTT);
   if (decRefCountRecursively)
      self()->getNode()->recursivelyDecReferenceCount();
   }

int32_t
TR::RegDepCopyRemoval::perform()
   {
   if (!cg()->supportsPassThroughCopyToNewVirtualRegister())
      return 0;

   discardAllNodeChoices();
   TR::TreeTop *tt;
   for (tt = comp()->getStartTree(); tt != NULL; tt = tt->getNextTreeTop())
      {
      TR::Node *node = tt->getNode();
      switch (node->getOpCodeValue())
         {
         case TR::BBStart:
            if (!node->getBlock()->isExtensionOfPreviousBlock())
               {
               if (trace())
                  traceMsg(comp(), "clearing remembered node choices at start of extended block at block_%d\n", node->getBlock()->getNumber());
               discardAllNodeChoices();
               }
            if (node->getNumChildren() > 0)
               processRegDeps(node->getFirstChild(), tt);
            break;
         case TR::BBEnd:
            if (node->getNumChildren() > 0)
               processRegDeps(node->getFirstChild(), tt);
            break;
         default:
            if (node->getOpCode().isSwitch())
               {
               TR::Node *defaultDest = node->getSecondChild();
               if (defaultDest->getNumChildren() > 0)
                  processRegDeps(defaultDest->getFirstChild(), tt);
               }
            else if (node->getOpCode().isBranch())
               {
               int nChildren = node->getNumChildren();
               // only the last child may be GlRegDeps
               for (int i = 0; i < nChildren - 1; i++)
                  TR_ASSERT(node->getChild(i)->getOpCodeValue() != TR::GlRegDeps, "GlRegDeps for branch is not the last child\n");
               if (nChildren > 0)
                  {
                  TR::Node *lastChild = node->getChild(nChildren - 1);
                  if (lastChild->getOpCodeValue() == TR::GlRegDeps)
                     processRegDeps(lastChild, tt);
                  }
               }
            break;
         }
      }
   return 1; // a bit arbitrary...
   }

static TR::TreeTop *findNextLegalTreeTop(TR::Compilation *comp, TR::Block *block)
   {
   vcount_t startVisitCount = comp->getStartTree()->getNode()->getVisitCount();
   TR::TreeTop * tt = NULL;
   for (tt = comp->getStartTree(); tt; tt = tt->getNextTreeTop())
      {
      if (tt->getNode()->getVisitCount() < startVisitCount)
         break;
      if (tt->getNode()->getOpCodeValue() == TR::BBStart)
         tt = tt->getNode()->getBlock()->getExit();
      }
   return tt;
   }

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<TR::TreeTop> candidateTTs(_candidateTTs);
   for (TR::TreeTop *candidateTT = candidateTTs.getFirst(); candidateTT; candidateTT = candidateTTs.getNext())
      {
      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());

         _candidateTTs->remove(candidateTT);
         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");
      }
   }

void *
OMR::TreeTop::operator new(size_t s, bool trace, TR_Memory * m)
   {
   if (!trace)
      return m->allocateHeapMemory(s);

   s += sizeof(void *);

   char * p = (char *)m->allocateHeapMemory(s);

   TR::TreeTop * tt = (TR::TreeTop *)(p + sizeof(void *));
   tt->setLastInstruction(0);
   return tt;
   }

static bool blockHasCalls(TR::Block *block, TR::Compilation *comp)
   {
   intptrj_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::removeUnsupportedCandidates()
   {
   ListIterator<TR::TreeTop> candidateTTs(_candidateTTs);
   for (TR::TreeTop *candidateTT = candidateTTs.getFirst(); candidateTT; candidateTT = candidateTTs.getNext())
      {
      TR::Node *candidate = candidateTT->getNode();
      if (!_supportedExpressions->get(candidate->getGlobalIndex()))
         {
         if (trace())
            traceMsg(comp(), "Removing candidate %p which is unsupported or has unsupported subexpressions\n", candidate);

         _candidateTTs->remove(candidateTT);
         }
      }
   }

void TR::ValidateLivenessBoundaries::validate(TR::ResolvedMethodSymbol *methodSymbol)
   {
   /**
    * These must be initialized at the start of every validate call,
    * since the same Rule object can be used multiple times to validate
    * the IL at different stages of the compilation.
    */
   TR::NodeSideTable<TR::NodeState> nodeStates(comp()->trMemory());
   /**
    * Similar to NodeChecklist, but more compact. Rather than track
    * node global indexes, which can be sparse, this tracks local
    * indexes, which are relatively dense.  Furthermore, the _basis field
    * allows us not to waste space on nodes we saw in prior blocks.
    * As the name suggests, used to keep track of live Nodes.
    */
   TR::LiveNodeWindow liveNodes(nodeStates, comp()->trMemory());

   TR::TreeTop *start = methodSymbol->getFirstTreeTop();
   TR::TreeTop *stop = methodSymbol->getLastTreeTop();
   for (TR::PostorderNodeOccurrenceIterator iter(start, comp(), "VALIDATE_LIVENESS_BOUNDARIES");
        iter != stop; ++iter)
      {
      TR::Node *node = iter.currentNode();
      updateNodeState(node, nodeStates, liveNodes);
      if (node->getOpCodeValue() == TR::BBEnd)
         {
         /* Determine whether this is the end of an extended block */
         bool isEndOfExtendedBlock = false;
         TR::TreeTop *nextTree = iter.currentTree()->getNextTreeTop();
         if (nextTree)
            {
            TR::checkILCondition(node, nextTree->getNode()->getOpCodeValue() == TR::BBStart,
                                 comp(), "Expected BBStart after BBEnd");
            isEndOfExtendedBlock = ! nextTree->getNode()->getBlock()->isExtensionOfPreviousBlock();
            }
         else
            {
            isEndOfExtendedBlock = true;
            }
         if (isEndOfExtendedBlock)
            {
            /* Ensure there are no nodes live across the end of a block */
            validateEndOfExtendedBlockBoundary(node, liveNodes);
            }
         }
      }
   }

void TR::ValidateNodeRefCountWithinBlock::validate(TR::TreeTop *firstTreeTop,
                                                      TR::TreeTop *exitTreeTop)
   {
   _nodeChecklist.empty();
   for (TR::TreeTop *tt = firstTreeTop; tt != exitTreeTop->getNextTreeTop();
        tt = tt->getNextTreeTop())
      {
      TR::Node *node = tt->getNode();
      node->setLocalIndex(node->getReferenceCount());
      validateRefCountPass1(node);
      }

   /**
    * We start again from the start of the block, and check the localIndex to
    * make sure it is 0.
    *
    * NOTE: Walking the tree backwards causes huge stack usage in validateRefCountPass2.
    */
   _nodeChecklist.empty();
   for (TR::TreeTop *tt = firstTreeTop; tt != exitTreeTop->getNextTreeTop();
        tt = tt->getNextTreeTop())
      {
      validateRefCountPass2(tt->getNode());
      }
   }