include/llvm/CodeGen/DAGISelHeader.h

   1 //==-llvm/CodeGen/DAGISelHeader.h - Common DAG ISel definitions  -*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file provides definitions of the common, target-independent methods and
  11 // data, which is used by SelectionDAG-based instruction selectors.
  12 //
  13 // *** NOTE: This file is #included into the middle of the target
  14 // instruction selector class.  These functions are really methods.
  15 // This is a little awkward, but it allows this code to be shared
  16 // by all the targets while still being able to call into
  17 // target-specific code without using a virtual function call.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_CODEGEN_DAGISEL_HEADER_H
  22 #define LLVM_CODEGEN_DAGISEL_HEADER_H
  23
  24 /// ISelQueue - Instruction selector priority queue sorted
  25 /// in the order of decreasing NodeId() values.
  26 std::vector<SDNode*> ISelQueue;
  27
  28 /// Keep track of nodes which have already been added to queue.
  29 unsigned char *ISelQueued;
  30
  31 /// Keep track of nodes which have already been selected.
  32 unsigned char *ISelSelected;
  33
  34 /// IsChainCompatible - Returns true if Chain is Op or Chain does
  35 /// not reach Op.
  36 static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
  37   if (Chain->getOpcode() == ISD::EntryToken)
  38     return true;
  39   else if (Chain->getOpcode() == ISD::TokenFactor)
  40     return false;
  41   else if (Chain->getNumOperands() > 0) {
  42     SDValue C0 = Chain->getOperand(0);
  43     if (C0.getValueType() == MVT::Other)
  44       return C0.getNode() != Op && IsChainCompatible(C0.getNode(), Op);
  45   }
  46   return true;
  47 }
  48
  49 /// isel_sort - Sorting functions for the selection queue in the
  50 /// decreasing NodeId order.
  51 struct isel_sort : public std::binary_function<SDNode*, SDNode*, bool> {
  52   bool operator()(const SDNode* left, const SDNode* right) const {
  53     return left->getNodeId() < right->getNodeId();
  54   }
  55 };
  56
  57 /// setQueued - marks the node with a given NodeId() as element of the
  58 /// instruction selection queue.
  59 inline void setQueued(int Id) {
  60   ISelQueued[Id / 8] |= 1 << (Id % 8);
  61 }
  62
  63 /// isSelected - checks if the node with a given NodeId() is
  64 /// in the instruction selection queue already.
  65 inline bool isQueued(int Id) {
  66   return ISelQueued[Id / 8] & (1 << (Id % 8));
  67 }
  68
  69 /// setSelected - marks the node with a given NodeId() as selected.
  70 inline void setSelected(int Id) {
  71   ISelSelected[Id / 8] |= 1 << (Id % 8);
  72 }
  73
  74 /// isSelected - checks if the node with a given NodeId() is
  75 /// selected already.
  76 inline bool isSelected(int Id) {
  77   return ISelSelected[Id / 8] & (1 << (Id % 8));
  78 }
  79
  80 /// AddToISelQueue - adds a node to the instruction
  81 /// selection queue.
  82 void AddToISelQueue(SDValue N) DISABLE_INLINE {
  83   int Id = N.getNode()->getNodeId();
  84   if (Id != -1 && !isQueued(Id)) {
  85     ISelQueue.push_back(N.getNode());
  86     std::push_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());
  87     setQueued(Id);
  88   }
  89 }
  90
  91 /// ISelQueueUpdater - helper class to handle updates of the
  92 /// instruciton selection queue.
  93 class VISIBILITY_HIDDEN ISelQueueUpdater :
  94   public SelectionDAG::DAGUpdateListener {
  95     std::vector<SDNode*> &ISelQueue;
  96     bool HadDelete; // Indicate if any deletions were done.
  97   public:
  98     explicit ISelQueueUpdater(std::vector<SDNode*> &isq)
  99       : ISelQueue(isq), HadDelete(false) {}
 100
 101     bool hadDelete() const { return HadDelete; }
 102
 103     /// NodeDeleted - remove node from the selection queue.
 104     virtual void NodeDeleted(SDNode *N, SDNode *E) {
 105       ISelQueue.erase(std::remove(ISelQueue.begin(), ISelQueue.end(), N),
 106                       ISelQueue.end());
 107       HadDelete = true;
 108     }
 109
 110     /// NodeUpdated - Ignore updates for now.
 111     virtual void NodeUpdated(SDNode *N) {}
 112   };
 113
 114 /// UpdateQueue - update the instruction selction queue to maintain
 115 /// the decreasing NodeId() ordering property.
 116 inline void UpdateQueue(const ISelQueueUpdater &ISQU) {
 117   if (ISQU.hadDelete())
 118     std::make_heap(ISelQueue.begin(), ISelQueue.end(),isel_sort());
 119 }
 120
 121
 122 /// ReplaceUses - replace all uses of the old node F with the use
 123 /// of the new node T.
 124 void ReplaceUses(SDValue F, SDValue T) DISABLE_INLINE {
 125   ISelQueueUpdater ISQU(ISelQueue);
 126   CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISQU);
 127   setSelected(F.getNode()->getNodeId());
 128   UpdateQueue(ISQU);
 129 }
 130
 131 /// ReplaceUses - replace all uses of the old nodes F with the use
 132 /// of the new nodes T.
 133 void ReplaceUses(const SDValue *F, const SDValue *T,
 134                  unsigned Num) DISABLE_INLINE {
 135   ISelQueueUpdater ISQU(ISelQueue);
 136   CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISQU);
 137   for (unsigned i = 0; i != Num; ++i)
 138     setSelected(F[i].getNode()->getNodeId());
 139   UpdateQueue(ISQU);
 140 }
 141
 142 /// ReplaceUses - replace all uses of the old node F with the use
 143 /// of the new node T.
 144 void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE {
 145   unsigned FNumVals = F->getNumValues();
 146   unsigned TNumVals = T->getNumValues();
 147   ISelQueueUpdater ISQU(ISelQueue);
 148   if (FNumVals != TNumVals) {
 149     for (unsigned i = 0, e = std::min(FNumVals, TNumVals); i < e; ++i)
 150      CurDAG->ReplaceAllUsesOfValueWith(SDValue(F, i), SDValue(T, i), &ISQU);
 151   } else {
 152     CurDAG->ReplaceAllUsesWith(F, T, &ISQU);
 153   }
 154   setSelected(F->getNodeId());
 155   UpdateQueue(ISQU);
 156 }
 157
 158 /// SelectRoot - Top level entry to DAG instruction selector.
 159 /// Selects instructions starting at the root of the current DAG.
 160 void SelectRoot(SelectionDAG &DAG) {
 161   SelectRootInit();
 162   unsigned NumBytes = (DAGSize + 7) / 8;
 163   ISelQueued   = new unsigned char[NumBytes];
 164   ISelSelected = new unsigned char[NumBytes];
 165   memset(ISelQueued,   0, NumBytes);
 166   memset(ISelSelected, 0, NumBytes);
 167
 168   // Create a dummy node (which is not added to allnodes), that adds
 169   // a reference to the root node, preventing it from being deleted,
 170   // and tracking any changes of the root.
 171   HandleSDNode Dummy(CurDAG->getRoot());
 172   ISelQueue.push_back(CurDAG->getRoot().getNode());
 173
 174   // Select pending nodes from the instruction selection queue
 175   // until no more nodes are left for selection.
 176   while (!ISelQueue.empty()) {
 177     SDNode *Node = ISelQueue.front();
 178     std::pop_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());
 179     ISelQueue.pop_back();
 180     // Skip already selected nodes.
 181     if (isSelected(Node->getNodeId()))
 182       continue;
 183 #ifndef NDEBUG
 184     DAG.setSubgraphColor(Node, "red");
 185 #endif
 186     SDNode *ResNode = Select(SDValue(Node, 0));
 187     // If node should not be replaced,
 188     // continue with the next one.
 189     if (ResNode == Node)
 190       continue;
 191     // Replace node.
 192     if (ResNode) {
 193 #ifndef NDEBUG
 194       DAG.setSubgraphColor(ResNode, "yellow");
 195       DAG.setSubgraphColor(ResNode, "black");
 196 #endif
 197       ReplaceUses(Node, ResNode);
 198     }
 199     // If after the replacement this node is not used any more,
 200     // remove this dead node.
 201     if (Node->use_empty()) { // Don't delete EntryToken, etc.
 202       ISelQueueUpdater ISQU(ISelQueue);
 203       CurDAG->RemoveDeadNode(Node, &ISQU);
 204       UpdateQueue(ISQU);
 205     }
 206   }
 207
 208   delete[] ISelQueued;
 209   ISelQueued = NULL;
 210   delete[] ISelSelected;
 211   ISelSelected = NULL;
 212   CurDAG->setRoot(Dummy.getValue());
 213 }
 214
 215 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */