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     SDOperand 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(SDOperand 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) {
 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(SDOperand F, SDOperand 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 node F with the use
 128 /// of the new node T.
 129 void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE {
 130   unsigned FNumVals = F->getNumValues();
 131   unsigned TNumVals = T->getNumValues();
 132   ISelQueueUpdater ISQU(ISelQueue);
 133   if (FNumVals != TNumVals) {
 134     for (unsigned i = 0, e = std::min(FNumVals, TNumVals); i < e; ++i)
 135      CurDAG->ReplaceAllUsesOfValueWith(SDOperand(F, i), SDOperand(T, i), &ISQU);
 136   } else {
 137     CurDAG->ReplaceAllUsesWith(F, T, &ISQU);
 138   }
 139   setSelected(F->getNodeId());
 140   UpdateQueue(ISQU);
 141 }
 142
 143 /// SelectRoot - Top level entry to DAG instruction selector.
 144 /// Selects instructions starting at the root of the current DAG.
 145 SDOperand SelectRoot(SDOperand Root) {
 146   SelectRootInit();
 147   unsigned NumBytes = (DAGSize + 7) / 8;
 148   ISelQueued   = new unsigned char[NumBytes];
 149   ISelSelected = new unsigned char[NumBytes];
 150   memset(ISelQueued,   0, NumBytes);
 151   memset(ISelSelected, 0, NumBytes);
 152
 153   // Create a dummy node (which is not added to allnodes), that adds
 154   // a reference to the root node, preventing it from being deleted,
 155   // and tracking any changes of the root.
 156   HandleSDNode Dummy(CurDAG->getRoot());
 157   ISelQueue.push_back(CurDAG->getRoot().Val);
 158
 159   // Select pending nodes from the instruction selection queue
 160   // until no more nodes are left for selection.
 161   while (!ISelQueue.empty()) {
 162     SDNode *Node = ISelQueue.front();
 163     std::pop_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());
 164     ISelQueue.pop_back();
 165     // Skip already selected nodes.
 166     if (isSelected(Node->getNodeId()))
 167       continue;
 168     SDNode *ResNode = Select(SDOperand(Node, 0));
 169     // If node should not be replaced,
 170     // continue with the next one.
 171     if (ResNode == Node)
 172       continue;
 173     // Replace node.
 174     if (ResNode)
 175       ReplaceUses(Node, ResNode);
 176     // If after the replacement this node is not used any more,
 177     // remove this dead node.
 178     if (Node->use_empty()) { // Don't delete EntryToken, etc.
 179           ISelQueueUpdater ISQU(ISelQueue);
 180           CurDAG->RemoveDeadNode(Node, &ISQU);
 181           UpdateQueue(ISQU);
 182     }
 183   }
 184
 185   delete[] ISelQueued;
 186   ISelQueued = NULL;
 187   delete[] ISelSelected;
 188   ISelSelected = NULL;
 189   return Dummy.getValue();
 190 }
 191
 192 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */