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 /// ISelPosition - Node iterator marking the current position of
  25 /// instruction selection as it procedes through the topologically-sorted
  26 /// node list.
  27 SelectionDAG::allnodes_iterator ISelPosition;
  28
  29 /// IsChainCompatible - Returns true if Chain is Op or Chain does
  30 /// not reach Op.
  31 static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
  32   if (Chain->getOpcode() == ISD::EntryToken)
  33     return true;
  34   if (Chain->getOpcode() == ISD::TokenFactor)
  35     return false;
  36   if (Chain->getNumOperands() > 0) {
  37     SDValue C0 = Chain->getOperand(0);
  38     if (C0.getValueType() == MVT::Other)
  39       return C0.getNode() != Op && IsChainCompatible(C0.getNode(), Op);
  40   }
  41   return true;
  42 }
  43
  44 /// ISelUpdater - helper class to handle updates of the
  45 /// instruciton selection graph.
  46 class VISIBILITY_HIDDEN ISelUpdater : public SelectionDAG::DAGUpdateListener {
  47   SelectionDAG::allnodes_iterator &ISelPosition;
  48 public:
  49   explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
  50     : ISelPosition(isp) {}
  51
  52   /// NodeDeleted - Handle nodes deleted from the graph. If the
  53   /// node being deleted is the current ISelPosition node, update
  54   /// ISelPosition.
  55   ///
  56   virtual void NodeDeleted(SDNode *N, SDNode *E) {
  57     if (ISelPosition == SelectionDAG::allnodes_iterator(N))
  58       ++ISelPosition;
  59   }
  60
  61   /// NodeUpdated - Ignore updates for now.
  62   virtual void NodeUpdated(SDNode *N) {}
  63 };
  64
  65 /// ReplaceUses - replace all uses of the old node F with the use
  66 /// of the new node T.
  67 void ReplaceUses(SDValue F, SDValue T) DISABLE_INLINE {
  68   ISelUpdater ISU(ISelPosition);
  69   CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
  70 }
  71
  72 /// ReplaceUses - replace all uses of the old nodes F with the use
  73 /// of the new nodes T.
  74 void ReplaceUses(const SDValue *F, const SDValue *T,
  75                  unsigned Num) DISABLE_INLINE {
  76   ISelUpdater ISU(ISelPosition);
  77   CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
  78 }
  79
  80 /// ReplaceUses - replace all uses of the old node F with the use
  81 /// of the new node T.
  82 void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE {
  83   unsigned FNumVals = F->getNumValues();
  84   unsigned TNumVals = T->getNumValues();
  85   ISelUpdater ISU(ISelPosition);
  86   if (FNumVals != TNumVals) {
  87     for (unsigned i = 0, e = std::min(FNumVals, TNumVals); i < e; ++i)
  88      CurDAG->ReplaceAllUsesOfValueWith(SDValue(F, i), SDValue(T, i), &ISU);
  89   } else {
  90     CurDAG->ReplaceAllUsesWith(F, T, &ISU);
  91   }
  92 }
  93
  94 /// SelectRoot - Top level entry to DAG instruction selector.
  95 /// Selects instructions starting at the root of the current DAG.
  96 void SelectRoot(SelectionDAG &DAG) {
  97   SelectRootInit();
  98
  99   // Create a dummy node (which is not added to allnodes), that adds
 100   // a reference to the root node, preventing it from being deleted,
 101   // and tracking any changes of the root.
 102   HandleSDNode Dummy(CurDAG->getRoot());
 103   ISelPosition = next(SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode()));
 104
 105   // The AllNodes list is now topological-sorted. Visit the
 106   // nodes by starting at the end of the list (the root of the
 107   // graph) and preceding back toward the beginning (the entry
 108   // node).
 109   while (ISelPosition != CurDAG->allnodes_begin()) {
 110     SDNode *Node = --ISelPosition;
 111     // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
 112     // but there are currently some corner cases that it misses. Also, this
 113     // makes it theoretically possible to disable the DAGCombiner.
 114     if (Node->use_empty())
 115       continue;
 116 #if 0
 117     DAG.setSubgraphColor(Node, "red");
 118 #endif
 119     SDNode *ResNode = Select(SDValue(Node, 0));
 120     // If node should not be replaced,
 121     // continue with the next one.
 122     if (ResNode == Node)
 123       continue;
 124     // Replace node.
 125     if (ResNode) {
 126 #if 0
 127       DAG.setSubgraphColor(ResNode, "yellow");
 128       DAG.setSubgraphColor(ResNode, "black");
 129 #endif
 130       ReplaceUses(Node, ResNode);
 131     }
 132     // If after the replacement this node is not used any more,
 133     // remove this dead node.
 134     if (Node->use_empty()) { // Don't delete EntryToken, etc.
 135       ISelUpdater ISU(ISelPosition);
 136       CurDAG->RemoveDeadNode(Node, &ISU);
 137     }
 138   }
 139
 140   CurDAG->setRoot(Dummy.getValue());
 141 }
 142
 143 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */