1 //==-llvm/CodeGen/DAGISelHeader.h - Common DAG ISel definitions -*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides definitions of the common, target-independent methods and
11 // data, which is used by SelectionDAG-based instruction selectors.
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.
19 //===----------------------------------------------------------------------===//
21 #ifndef LLVM_CODEGEN_DAGISEL_HEADER_H
22 #define LLVM_CODEGEN_DAGISEL_HEADER_H
24 /// ISelPosition - Node iterator marking the current position of
25 /// instruction selection as it procedes through the topologically-sorted
27 SelectionDAG::allnodes_iterator ISelPosition;
29 /// IsChainCompatible - Returns true if Chain is Op or Chain does
31 static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
32 if (Chain->getOpcode() == ISD::EntryToken)
34 else if (Chain->getOpcode() == ISD::TokenFactor)
36 else 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);
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 bool HadDelete; // Indicate if any deletions were done.
50 explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
51 : ISelPosition(isp) {}
53 /// NodeDeleted - Handle nodes deleted from the graph. If the
54 /// node being deleted is the current ISelPosition node, update
57 virtual void NodeDeleted(SDNode *N, SDNode *E) {
58 if (ISelPosition == SelectionDAG::allnodes_iterator(N))
62 /// NodeUpdated - Ignore updates for now.
63 virtual void NodeUpdated(SDNode *N) {}
66 /// ReplaceUses - replace all uses of the old node F with the use
67 /// of the new node T.
68 void ReplaceUses(SDValue F, SDValue T) DISABLE_INLINE {
69 ISelUpdater ISU(ISelPosition);
70 CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
73 /// ReplaceUses - replace all uses of the old nodes F with the use
74 /// of the new nodes T.
75 void ReplaceUses(const SDValue *F, const SDValue *T,
76 unsigned Num) DISABLE_INLINE {
77 ISelUpdater ISU(ISelPosition);
78 CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
81 /// ReplaceUses - replace all uses of the old node F with the use
82 /// of the new node T.
83 void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE {
84 unsigned FNumVals = F->getNumValues();
85 unsigned TNumVals = T->getNumValues();
86 ISelUpdater ISU(ISelPosition);
87 if (FNumVals != TNumVals) {
88 for (unsigned i = 0, e = std::min(FNumVals, TNumVals); i < e; ++i)
89 CurDAG->ReplaceAllUsesOfValueWith(SDValue(F, i), SDValue(T, i), &ISU);
91 CurDAG->ReplaceAllUsesWith(F, T, &ISU);
95 /// SelectRoot - Top level entry to DAG instruction selector.
96 /// Selects instructions starting at the root of the current DAG.
97 void SelectRoot(SelectionDAG &DAG) {
100 // Create a dummy node (which is not added to allnodes), that adds
101 // a reference to the root node, preventing it from being deleted,
102 // and tracking any changes of the root.
103 HandleSDNode Dummy(CurDAG->getRoot());
104 ISelPosition = next(SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode()));
106 // The AllNodes list is now topological-sorted. Visit the
107 // nodes by starting at the end of the list (the root of the
108 // graph) and preceding back toward the beginning (the entry
110 while (ISelPosition != CurDAG->allnodes_begin()) {
111 SDNode *Node = --ISelPosition;
113 DAG.setSubgraphColor(Node, "red");
115 SDNode *ResNode = Select(SDValue(Node, 0));
116 // If node should not be replaced,
117 // continue with the next one.
123 DAG.setSubgraphColor(ResNode, "yellow");
124 DAG.setSubgraphColor(ResNode, "black");
126 ReplaceUses(Node, ResNode);
128 // If after the replacement this node is not used any more,
129 // remove this dead node.
130 if (Node->use_empty()) { // Don't delete EntryToken, etc.
131 ISelUpdater ISU(ISelPosition);
132 CurDAG->RemoveDeadNode(Node, &ISU);
136 CurDAG->setRoot(Dummy.getValue());
139 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */