DominatorVerifier.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
 *******************************************************************************/

#if DEBUG

#include "optimizer/DominatorVerifier.hpp"

#include <stddef.h>
#include <stdint.h>
#include "env/StackMemoryRegion.hpp"
#include "compile/Compilation.hpp"
#include "env/TRMemory.hpp"
#include "il/Block.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 "optimizer/DominatorsChk.hpp"
#include "optimizer/Dominators.hpp"
#include "ras/Debug.hpp"

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



bool TR_DominatorVerifier::areBothImplementationsConsistent(TR_DominatorsChk &findDominatorsChk, TR_Dominators &findDominators)
   {
   int i;

   _dominatorsChkInfo = findDominatorsChk.getDominatorsChkInfo();

   for (i = 2; i < _numBlocks-1; i++)
      {
      TR::Block *conservativeDominator = _dominatorsChkInfo[i]._idom->_block;
      TR::Block *efficientDominator = findDominators.getDominator(_dominatorsChkInfo[i]._block);

      if (!(efficientDominator == conservativeDominator))
         {
         if (debug("traceVER"))
            {
            dumpOptDetails(comp(), "Inconsistency \n");
            dumpOptDetails(comp(), "   Dominator computed by expensive algorithm for [%p] is [%p]\n", _dominatorsChkInfo[i]._block, _dominatorsChkInfo[i]._idom->_block);
            dumpOptDetails(comp(), "   Dominator computed by efficient algorithm for [%p] is [%p]\n", _dominatorsChkInfo[i]._block, efficientDominator);
            }

         return false;
         }
     }

   return true;
   }



bool TR_DominatorVerifier::isExpensiveAlgorithmCorrect(TR_DominatorsChk &expensiveAlgorithm)
   {
   int32_t i,j;
   _nodesSeenOnEveryPath = new (trStackMemory()) TR_BitVector(_numBlocks,trMemory(), stackAlloc);
   _nodesSeenOnCurrentPath = new (trStackMemory()) TR_BitVector(_numBlocks,trMemory(), stackAlloc);
   _dominatorsChkInfo = expensiveAlgorithm.getDominatorsChkInfo();

   for (i = 2; i < _numBlocks-1; i++)
      {
      TR_BitVector *bucket = _dominatorsChkInfo[i]._tmpbucket;

      for (j = 0; j < _numBlocks-1; j++)
         {
         if (bucket->get(j)) // dominator according to algorithm
            {
            // Initializing these BitVectors before checking
            // dominators for the next block.
            // The last bit is not changed for either bit vector - is that what
            // was intended?
            //
            _nodesSeenOnEveryPath->setAll(_numBlocks-1);
            int32_t lastBit = _nodesSeenOnCurrentPath->get(_numBlocks-1);
            _nodesSeenOnCurrentPath->empty();
            if (lastBit)
               _nodesSeenOnCurrentPath->set(_numBlocks-1);

            if ( ! dominates(_dominatorsChkInfo[j+1]._block,_dominatorsChkInfo[i]._block) )  // dominator according to the CFG
               {
               if (debug("traceVER"))
                  {
                  dumpOptDetails(comp(), "   Dominator info for expensive algorithm is incorrect \n");
                  dumpOptDetails(comp(), "   Dominator of [%p] is [%p] as per the algorithm\n", _dominatorsChkInfo[i]._block, _dominatorsChkInfo[j+1]._block);
                  dumpOptDetails(comp(), "   But [%p] is not an the dominator of [%p] as per the Control Flow Graph", _dominatorsChkInfo[j+1]._block, _dominatorsChkInfo[i]._block);
                  }
               return false;
               }
            }
         }
      }

   return true;
   }


// Returns true if the dominator block dominates the dominated block
// as per the Control Flow Graph. Examines each (backward) control
// flow path from the dominated block to the dominator block. Intersection
// of the nodes seen along each of the backward control flow paths (until
// the dominator block) from the dominated block must be a singleton set,
// containing only the dominator block.
//
bool TR_DominatorVerifier::dominates(TR::Block *dominator, TR::Block *dominated)
   {
   for (auto pred = dominated->getPredecessors().begin(); pred != dominated->getPredecessors().end(); ++pred)
       {
       _visitCount = comp()->incVisitCount();
       compareWithPredsOf(dominator, toBlock((*pred)->getFrom()));
       *_nodesSeenOnEveryPath &= *_nodesSeenOnCurrentPath;

       // Reset all bits except the last - is this what is intended?
       int32_t lastBit = _nodesSeenOnCurrentPath->get(_numBlocks-1);
       _nodesSeenOnCurrentPath->empty();
       if (lastBit)
          _nodesSeenOnCurrentPath->set(_numBlocks-1);
       }

   for (auto pred = dominated->getExceptionPredecessors().begin(); pred != dominated->getExceptionPredecessors().end(); ++pred)
       {
       _visitCount = comp()->incVisitCount();
       compareWithPredsOf(dominator, toBlock((*pred)->getFrom()));
       *_nodesSeenOnEveryPath &= *_nodesSeenOnCurrentPath;
       _nodesSeenOnCurrentPath->empty();
       }

   for (int32_t i=0;i<_numBlocks-1;i++)
      {
      if (i==_dominators->_dfNumbers[dominator->getNumber()])
         {
         if (!_nodesSeenOnEveryPath->get(i))
            return false;
         }
         else
         {
         if (_nodesSeenOnEveryPath->get(i))
            return false;
         }
      }

      return true;
   }



// Visits the Predecessors of the dominated block recursively.
//
void TR_DominatorVerifier::compareWithPredsOf(TR::Block *dominator, TR::Block *dominated)
   {
   dominated->setVisitCount(_visitCount);
   _nodesSeenOnCurrentPath->set(_dominators->_dfNumbers[dominator->getNumber()]);

   if (dominator == dominated)
      return;

   for (auto pred = dominated->getPredecessors().begin(); pred != dominated->getPredecessors().end(); ++pred)
       {
       if (toBlock((*pred)->getFrom())->getVisitCount() != _visitCount)
          compareWithPredsOf(dominator, toBlock((*pred)->getFrom()));
       }

   for (auto pred = dominated->getExceptionPredecessors().begin(); pred != dominated->getExceptionPredecessors().end(); ++pred)
       {
       if (toBlock((*pred)->getFrom())->getVisitCount() != _visitCount)
          compareWithPredsOf(dominator, toBlock((*pred)->getFrom()));
       }

   }

#endif