// data, which is used by SelectionDAG-based instruction selectors.
//
// *** NOTE: This file is #included into the middle of the target
-// *** instruction selector class. These functions are really methods.
+// instruction selector class. These functions are really methods.
+// This is a little awkward, but it allows this code to be shared
+// by all the targets while still being able to call into
+// target-specific code without using a virtual function call.
+//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_DAGISEL_HEADER_H
#define LLVM_CODEGEN_DAGISEL_HEADER_H
-/// ISelQueue - Instruction selector priority queue sorted
-/// in the order of increasing NodeId() values.
-std::vector<SDNode*> ISelQueue;
-
-/// Keep track of nodes which have already been added to queue.
-unsigned char *ISelQueued;
-
-/// Keep track of nodes which have already been selected.
-unsigned char *ISelSelected;
+/// ISelPosition - Node iterator marking the current position of
+/// instruction selection as it procedes through the topologically-sorted
+/// node list.
+SelectionDAG::allnodes_iterator ISelPosition;
/// IsChainCompatible - Returns true if Chain is Op or Chain does
/// not reach Op.
static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
if (Chain->getOpcode() == ISD::EntryToken)
return true;
- else if (Chain->getOpcode() == ISD::TokenFactor)
+ if (Chain->getOpcode() == ISD::TokenFactor)
return false;
- else if (Chain->getNumOperands() > 0) {
- SDOperand C0 = Chain->getOperand(0);
+ if (Chain->getNumOperands() > 0) {
+ SDValue C0 = Chain->getOperand(0);
if (C0.getValueType() == MVT::Other)
- return C0.Val != Op && IsChainCompatible(C0.Val, Op);
+ return C0.getNode() != Op && IsChainCompatible(C0.getNode(), Op);
}
return true;
}
-/// isel_sort - Sorting functions for the selection queue in the
-/// increasing NodeId order.
-struct isel_sort : public std::binary_function<SDNode*, SDNode*, bool> {
- bool operator()(const SDNode* left, const SDNode* right) const {
- return (left->getNodeId() > right->getNodeId());
+/// ISelUpdater - helper class to handle updates of the
+/// instruciton selection graph.
+class VISIBILITY_HIDDEN ISelUpdater : public SelectionDAG::DAGUpdateListener {
+ SelectionDAG::allnodes_iterator &ISelPosition;
+public:
+ explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
+ : ISelPosition(isp) {}
+
+ /// NodeDeleted - Handle nodes deleted from the graph. If the
+ /// node being deleted is the current ISelPosition node, update
+ /// ISelPosition.
+ ///
+ virtual void NodeDeleted(SDNode *N, SDNode *E) {
+ if (ISelPosition == SelectionDAG::allnodes_iterator(N))
+ ++ISelPosition;
}
-};
-
-/// setQueued - marks the node with a given NodeId() as element of the
-/// instruction selection queue.
-inline void setQueued(int Id) {
- ISelQueued[Id / 8] |= 1 << (Id % 8);
-}
-
-/// isSelected - checks if the node with a given NodeId() is
-/// in the instruction selection queue already.
-inline bool isQueued(int Id) {
- return ISelQueued[Id / 8] & (1 << (Id % 8));
-}
-
-/// setSelected - marks the node with a given NodeId() as selected.
-inline void setSelected(int Id) {
- ISelSelected[Id / 8] |= 1 << (Id % 8);
-}
-
-/// isSelected - checks if the node with a given NodeId() is
-/// selected already.
-inline bool isSelected(int Id) {
- return ISelSelected[Id / 8] & (1 << (Id % 8));
-}
-
-/// AddToISelQueue - adds a node to the instruction
-/// selection queue.
-void AddToISelQueue(SDOperand N) DISABLE_INLINE {
- int Id = N.Val->getNodeId();
- if (Id != -1 && !isQueued(Id)) {
- ISelQueue.push_back(N.Val);
- std::push_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());
- setQueued(Id);
- }
-}
-
-/// ISelQueueUpdater - helper class to handle updates of the
-/// instruciton selection queue.
-class VISIBILITY_HIDDEN ISelQueueUpdater :
- public SelectionDAG::DAGUpdateListener {
- std::vector<SDNode*> &ISelQueue;
- bool HadDelete; // Indicate if any deletions were done.
- public:
- explicit ISelQueueUpdater(std::vector<SDNode*> &isq)
- : ISelQueue(isq), HadDelete(false) {}
-
- bool hadDelete() const { return HadDelete; }
-
- /// NodeDeleted - remove node from the selection queue.
- virtual void NodeDeleted(SDNode *N, SDNode *E) {
- ISelQueue.erase(std::remove(ISelQueue.begin(), ISelQueue.end(), N),
- ISelQueue.end());
- HadDelete = true;
- }
-
- /// NodeUpdated - Ignore updates for now.
- virtual void NodeUpdated(SDNode *N) {}
- };
-
-/// UpdateQueue - update the instruction selction queue to maintain
-/// the increasing NodeId() ordering property.
-inline void UpdateQueue(const ISelQueueUpdater &ISQU) {
- if (ISQU.hadDelete())
- std::make_heap(ISelQueue.begin(), ISelQueue.end(),isel_sort());
-}
+ /// NodeUpdated - Ignore updates for now.
+ virtual void NodeUpdated(SDNode *N) {}
+};
/// ReplaceUses - replace all uses of the old node F with the use
/// of the new node T.
-void ReplaceUses(SDOperand F, SDOperand T) DISABLE_INLINE {
- ISelQueueUpdater ISQU(ISelQueue);
- CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISQU);
- setSelected(F.Val->getNodeId());
- UpdateQueue(ISQU);
+void ReplaceUses(SDValue F, SDValue T) DISABLE_INLINE {
+ ISelUpdater ISU(ISelPosition);
+ CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
+}
+
+/// ReplaceUses - replace all uses of the old nodes F with the use
+/// of the new nodes T.
+void ReplaceUses(const SDValue *F, const SDValue *T,
+ unsigned Num) DISABLE_INLINE {
+ ISelUpdater ISU(ISelPosition);
+ CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
}
/// ReplaceUses - replace all uses of the old node F with the use
/// of the new node T.
void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE {
- unsigned FNumVals = F->getNumValues();
- unsigned TNumVals = T->getNumValues();
- ISelQueueUpdater ISQU(ISelQueue);
- if (FNumVals != TNumVals) {
- for (unsigned i = 0, e = std::min(FNumVals, TNumVals); i < e; ++i)
- CurDAG->ReplaceAllUsesOfValueWith(SDOperand(F, i), SDOperand(T, i), &ISQU);
- } else {
- CurDAG->ReplaceAllUsesWith(F, T, &ISQU);
- }
- setSelected(F->getNodeId());
- UpdateQueue(ISQU);
+ ISelUpdater ISU(ISelPosition);
+ CurDAG->ReplaceAllUsesWith(F, T, &ISU);
}
/// SelectRoot - Top level entry to DAG instruction selector.
/// Selects instructions starting at the root of the current DAG.
-SDOperand SelectRoot(SDOperand Root) {
+void SelectRoot(SelectionDAG &DAG) {
SelectRootInit();
- unsigned NumBytes = (DAGSize + 7) / 8;
- ISelQueued = new unsigned char[NumBytes];
- ISelSelected = new unsigned char[NumBytes];
- memset(ISelQueued, 0, NumBytes);
- memset(ISelSelected, 0, NumBytes);
// Create a dummy node (which is not added to allnodes), that adds
// a reference to the root node, preventing it from being deleted,
// and tracking any changes of the root.
HandleSDNode Dummy(CurDAG->getRoot());
- ISelQueue.push_back(CurDAG->getRoot().Val);
-
- // Select pending nodes from the instruction selection queue
- // until no more nodes are left for selection.
- while (!ISelQueue.empty()) {
- SDNode *Node = ISelQueue.front();
- std::pop_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());
- ISelQueue.pop_back();
- // Skip already selected nodes.
- if (isSelected(Node->getNodeId()))
+ ISelPosition = next(SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode()));
+
+ // The AllNodes list is now topological-sorted. Visit the
+ // nodes by starting at the end of the list (the root of the
+ // graph) and preceding back toward the beginning (the entry
+ // node).
+ while (ISelPosition != CurDAG->allnodes_begin()) {
+ SDNode *Node = --ISelPosition;
+ // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
+ // but there are currently some corner cases that it misses. Also, this
+ // makes it theoretically possible to disable the DAGCombiner.
+ if (Node->use_empty())
continue;
- SDNode *ResNode = Select(SDOperand(Node, 0));
+#if 0
+ DAG.setSubgraphColor(Node, "red");
+#endif
+ SDNode *ResNode = Select(SDValue(Node, 0));
// If node should not be replaced,
// continue with the next one.
if (ResNode == Node)
continue;
// Replace node.
- if (ResNode)
+ if (ResNode) {
+#if 0
+ DAG.setSubgraphColor(ResNode, "yellow");
+ DAG.setSubgraphColor(ResNode, "black");
+#endif
ReplaceUses(Node, ResNode);
+ }
// If after the replacement this node is not used any more,
// remove this dead node.
if (Node->use_empty()) { // Don't delete EntryToken, etc.
- ISelQueueUpdater ISQU(ISelQueue);
- CurDAG->RemoveDeadNode(Node, &ISQU);
- UpdateQueue(ISQU);
+ ISelUpdater ISU(ISelPosition);
+ CurDAG->RemoveDeadNode(Node, &ISU);
}
}
- delete[] ISelQueued;
- ISelQueued = NULL;
- delete[] ISelSelected;
- ISelSelected = NULL;
- return Dummy.getValue();
+ CurDAG->setRoot(Dummy.getValue());
}
#endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */
projects / oota-llvm.git / blobdiff