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