lib/Target/SparcV9/RegAlloc/InterferenceGraph.h

   1 /* Title:   InterferenceGraph.h   -*- C++ -*-
   2    Author:  Ruchira Sasanka
   3    Date:    July 20, 01
   4    Purpose: Interference Graph used for register coloring.
   5
   6    Notes:
   7    Adj Info is  stored in the lower trangular matrix (i.e., row > col )
   8
   9    This class must be used in the following way:
  10
  11    * Construct class
  12    * call addLRToIG as many times to add ALL LRs to this IG
  13    * call createGraph to create the actual matrix
  14    * Then setInterference, getInterference, mergeIGNodesOfLRs can be
  15      called as desired to modify the graph.
  16    * Once the modifications to the graph are over, call
  17      setCurDegreeOfIGNodes() before pushing IGNodes on to stack for coloring.
  18 */
  19
  20
  21 #ifndef  INTERFERENCE_GRAPH_H
  22 #define  INTERFERENCE_GRAPH_H
  23
  24
  25 #include "llvm/CodeGen/IGNode.h"
  26
  27 typedef std::vector <IGNode *> IGNodeListType;
  28
  29
  30 class InterferenceGraph
  31 {
  32   char **IG;                            // a poiner to the interference graph
  33   unsigned int Size;                    // size of a side of the IG
  34   RegClass *const RegCl;                // RegCl contains this IG
  35   IGNodeListType IGNodeList;            // a list of all IGNodes in a reg class
  36
  37   // for asserting this IG node is infact in the IGNodeList of this class
  38   inline void assertIGNode(const IGNode *const Node) const {
  39     assert( IGNodeList[ Node->getIndex() ] == Node );
  40   }
  41
  42
  43
  44  public:
  45
  46   // the matrix is not yet created by the constructor. Call createGraph()
  47   // to create it after adding all IGNodes to the IGNodeList
  48
  49   InterferenceGraph(RegClass *const RC);
  50   ~InterferenceGraph();
  51
  52   void createGraph();
  53
  54   void addLRToIG(LiveRange *const LR);
  55
  56   void setInterference(const LiveRange *const LR1,
  57                               const LiveRange *const LR2 );
  58
  59   unsigned getInterference(const LiveRange *const LR1,
  60                                   const LiveRange *const LR2 ) const ;
  61
  62   void mergeIGNodesOfLRs(const LiveRange *const LR1, LiveRange *const LR2);
  63
  64   inline IGNodeListType &getIGNodeList() { return IGNodeList; }
  65
  66   void setCurDegreeOfIGNodes();
  67
  68   void printIG() const;
  69   void printIGNodeList() const;
  70 };
  71
  72 #endif