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 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_CODEGEN_DAGISEL_HEADER_H
18 #define LLVM_CODEGEN_DAGISEL_HEADER_H
20 /// ISelQueue - Instruction selector priority queue sorted
21 /// in the order of increasing NodeId() values.
22 std::vector<SDNode*> ISelQueue;
24 /// Keep track of nodes which have already been added to queue.
25 unsigned char *ISelQueued;
27 /// Keep track of nodes which have already been selected.
28 unsigned char *ISelSelected;
30 /// IsChainCompatible - Returns true if Chain is Op or Chain does
32 static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
33 if (Chain->getOpcode() == ISD::EntryToken)
35 else if (Chain->getOpcode() == ISD::TokenFactor)
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);
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());
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);
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));
65 /// setSelected - marks the node with a given NodeId() as selected.
66 inline void setSelected(int Id) {
67 ISelSelected[Id / 8] |= 1 << (Id % 8);
70 /// isSelected - checks if the node with a given NodeId() is
72 inline bool isSelected(int Id) {
73 return ISelSelected[Id / 8] & (1 << (Id % 8));
76 /// AddToISelQueue - adds a node to the instruction
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());
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.
94 explicit ISelQueueUpdater(std::vector<SDNode*> &isq)
95 : ISelQueue(isq), HadDelete(false) {}
97 bool hadDelete() const { return HadDelete; }
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),
106 /// NodeUpdated - Ignore updates for now.
107 virtual void NodeUpdated(SDNode *N) {}
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());
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());
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);
137 CurDAG->ReplaceAllUsesWith(F, T, &ISQU);
139 setSelected(F->getNodeId());
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) {
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);
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);
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()))
168 SDNode *ResNode = Select(SDOperand(Node, 0));
169 // If node should not be replaced,
170 // continue with the next one.
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);
187 delete[] ISelSelected;
189 return Dummy.getValue();
192 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */