InterferenceGraph.hpp

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

#ifndef INTERFERENCEGRAPH_INCL
#define INTERFERENCEGRAPH_INCL

#include <stddef.h>
#include <stdint.h>
#include "env/TRMemory.hpp"
#include "env/jittypes.h"
#include "compile/Compilation.hpp"
#include "infra/Array.hpp"
#include "infra/Assert.hpp"
#include "infra/BitVector.hpp"
#include "infra/IGBase.hpp"
#include "infra/IGNode.hpp"

template <class T> class TR_Stack;

class TR_InterferenceGraph : public TR_IGBase
   {
   struct HashTable;
   friend struct HashTable;

   // Ordered table of all allocated nodes.
   //
   TR_Array<TR_IGNode *> * _nodeTable;

   // FILO structure of nodes for simplify/select phases.
   //
   TR_Stack<TR_IGNode *> * _nodeStack;

   // Hash table mapping of entity addresses to IG nodes.
   //
   struct HashTableEntry
      {
      HashTableEntry *_next;
      TR_IGNode      *_igNode;
      };

   struct HashTable
      {
      int32_t          _numBuckets;
      HashTableEntry **_buckets;
      };

   HashTable _entityHash;

   virtual bool simplify();
   virtual bool select();

   protected:

   TR::Compilation * comp() {return _compilation;}

   TR_Memory *               trMemory()                    { return _trMemory; }
   TR_StackMemory            trStackMemory()               { return _trMemory; }
   TR_HeapMemory             trHeapMemory()                { return _trMemory; }

   void partitionNodesIntoDegreeSets(TR_BitVector *workingSet,
                                     TR_BitVector *colourableDegreeSet,
                                     TR_BitVector *notColourableDegreeSet);

   TR::Compilation *_compilation;
   TR_Memory *_trMemory;

   public:

   TR_InterferenceGraph(TR::Compilation *comp) :
      _compilation(comp),
      _nodeTable(NULL),
      _nodeStack(NULL),
      _trMemory(comp->trMemory()),
      TR_IGBase() {}

   TR_InterferenceGraph(TR::Compilation *comp, int32_t estimatedNodes = 32);

   TR_IGNode *getNodeTable(IGNodeIndex i) {return ((*_nodeTable)[i]);}

   TR_Stack<TR_IGNode *> *getNodeStack()  {return _nodeStack;}
   TR_Stack<TR_IGNode *> *setNodeStack(TR_Stack<TR_IGNode *> *ns) {return(_nodeStack = ns);}

   int32_t entityHashBucket(void *entity) {return (int32_t)(((uintptr_t)entity >> 2) % _entityHash._numBuckets);}
   void addIGNodeToEntityHash(TR_IGNode *igNode);

   TR_IGNode *add(void *entity, bool ignoreDuplicates = false);
   void addInterferenceBetween(void *entity1, void *entity2)
       {
       TR_IGNode *igNode1 = getIGNodeForEntity(entity1);
       TR_IGNode *igNode2 = getIGNodeForEntity(entity2);
       TR_ASSERT(igNode1,"addInterferenceBetween: entity1 %p does not exist in this interference graph\n", entity1);
       TR_ASSERT(igNode2,"addInterferenceBetween: entity2 %p does not exist in this interference graph\n", entity2);

       addInterferenceBetween(igNode1,igNode2);
       }

   void addInterferenceBetween(TR_IGNode *igNode1, TR_IGNode *igNode2);
   void removeAllInterferences(void *entity);

   TR_IGNode *getIGNodeForEntity(void *entity);
   bool hasInterference(void *entity1, void *entity2);
   bool hasInterference(TR_IGNode *node1, TR_IGNode *node2)
       {
       IMIndex bit = getNodePairToBVIndex(node1->getIndex(), node2->getIndex());
       return getInterferenceMatrix()->isSet(bit);
       }

   void removeInterferenceBetween(void *entity1, void *entity2)
       {
       TR_IGNode *igNode1 = getIGNodeForEntity(entity1);
       TR_IGNode *igNode2 = getIGNodeForEntity(entity2);

       TR_ASSERT(igNode1, "hasInterference: entity1 %p does not exist in this interference graph\n", entity1);
       TR_ASSERT(igNode2, "hasInterference: entity2 %p does not exist in this interference graph\n", entity2);
       removeInterferenceBetween(igNode1,igNode2);
       }
   void removeInterferenceBetween(TR_IGNode *node1, TR_IGNode *node2);

   void virtualRemoveEntityFromIG(void *entity);
   void virtualRemoveNodeFromIG(TR_IGNode *igNode);

   IGNodeDegree findMaxDegree();

   bool doColouring(IGNodeColour numColours);
   IGNodeColour findMinimumChromaticNumber();

#ifdef DEBUG
   void dumpIG(const char *msg = NULL);
#else
   void dumpIG(const char *msg = NULL) {}
#endif
   };
#endif