From 393ad0f5d2f3d0091d49be0822e432ef19323ba2 Mon Sep 17 00:00:00 2001 From: Roman Levenstein Date: Wed, 14 May 2008 10:17:11 +0000 Subject: Do not generate by TableGen the hard-coded standard, target-independent part of DAG instruction selectors. Introudce a dedicated header file for this part: include/llvm/CodeGen/DAGISelHeader.h TableGen now only generates the include preprocessor directive to include this new header. This is a preparation for supporting multiple implementations of instruction selectors in the future. Reviewed and approved by Evan and Dan. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51102 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/DAGISelHeader.h | 192 +++++++++++++++++++++++++++++++++++ utils/TableGen/DAGISelEmitter.cpp | 143 +------------------------- 2 files changed, 195 insertions(+), 140 deletions(-) create mode 100644 include/llvm/CodeGen/DAGISelHeader.h diff --git a/include/llvm/CodeGen/DAGISelHeader.h b/include/llvm/CodeGen/DAGISelHeader.h new file mode 100644 index 0000000..3188cc2 --- /dev/null +++ b/include/llvm/CodeGen/DAGISelHeader.h @@ -0,0 +1,192 @@ +//==-llvm/CodeGen/DAGISelHeader.h - Common DAG ISel definitions -*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides definitions of the common, target-independent methods and +// 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. +//===----------------------------------------------------------------------===// + +#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 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; + +/// 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) + return false; + else if (Chain->getNumOperands() > 0) { + SDOperand C0 = Chain->getOperand(0); + if (C0.getValueType() == MVT::Other) + return C0.Val != Op && IsChainCompatible(C0.Val, Op); + } + return true; +} + +/// isel_sort - Sorting functions for the selection queue in the +/// increasing NodeId order. +struct isel_sort : public std::binary_function { + bool operator()(const SDNode* left, const SDNode* right) const { + return (left->getNodeId() > right->getNodeId()); + } +}; + +/// 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 &ISelQueue; + bool HadDelete; // Indicate if any deletions were done. + public: + explicit ISelQueueUpdater(std::vector &isq) + : ISelQueue(isq), HadDelete(false) {} + + bool hadDelete() const { return HadDelete; } + + /// NodeDeleted - remove node from the selection queue. + virtual void NodeDeleted(SDNode *N) { + 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()); +} + + +/// 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); +} + +/// 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); +} + +/// SelectRoot - Top level entry to DAG instruction selector. +/// Selects instructions starting at the root of the current DAG. +SDOperand SelectRoot(SDOperand Root) { + 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())) + continue; + SDNode *ResNode = Select(SDOperand(Node, 0)); + // If node should not be replaced, + // continue with the next one. + if (ResNode == Node) + continue; + // Replace node. + if (ResNode) + 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); + } + } + + delete[] ISelQueued; + ISelQueued = NULL; + delete[] ISelSelected; + ISelSelected = NULL; + return Dummy.getValue(); +} + +#endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */ diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index 70d88ce..72bd5bd 100644 --- a/utils/TableGen/DAGISelEmitter.cpp +++ b/utils/TableGen/DAGISelEmitter.cpp @@ -2011,147 +2011,10 @@ void DAGISelEmitter::run(std::ostream &OS) { OS << "// *** NOTE: This file is #included into the middle of the target\n" << "// *** instruction selector class. These functions are really " << "methods.\n\n"; - - OS << "// Instruction selector priority queue:\n" - << "std::vector ISelQueue;\n"; - OS << "/// Keep track of nodes which have already been added to queue.\n" - << "unsigned char *ISelQueued;\n"; - OS << "/// Keep track of nodes which have already been selected.\n" - << "unsigned char *ISelSelected;\n"; - - - OS << "/// IsChainCompatible - Returns true if Chain is Op or Chain does\n"; - OS << "/// not reach Op.\n"; - OS << "static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {\n"; - OS << " if (Chain->getOpcode() == ISD::EntryToken)\n"; - OS << " return true;\n"; - OS << " else if (Chain->getOpcode() == ISD::TokenFactor)\n"; - OS << " return false;\n"; - OS << " else if (Chain->getNumOperands() > 0) {\n"; - OS << " SDOperand C0 = Chain->getOperand(0);\n"; - OS << " if (C0.getValueType() == MVT::Other)\n"; - OS << " return C0.Val != Op && IsChainCompatible(C0.Val, Op);\n"; - OS << " }\n"; - OS << " return true;\n"; - OS << "}\n"; - - OS << "/// Sorting functions for the selection queue.\n" - << "struct isel_sort : public std::binary_function" - << " {\n" - << " bool operator()(const SDNode* left, const SDNode* right) " - << "const {\n" - << " return (left->getNodeId() > right->getNodeId());\n" - << " }\n" - << "};\n\n"; - - OS << "inline void setQueued(int Id) {\n"; - OS << " ISelQueued[Id / 8] |= 1 << (Id % 8);\n"; - OS << "}\n"; - OS << "inline bool isQueued(int Id) {\n"; - OS << " return ISelQueued[Id / 8] & (1 << (Id % 8));\n"; - OS << "}\n"; - OS << "inline void setSelected(int Id) {\n"; - OS << " ISelSelected[Id / 8] |= 1 << (Id % 8);\n"; - OS << "}\n"; - OS << "inline bool isSelected(int Id) {\n"; - OS << " return ISelSelected[Id / 8] & (1 << (Id % 8));\n"; - OS << "}\n\n"; - - OS << "void AddToISelQueue(SDOperand N) DISABLE_INLINE {\n"; - OS << " int Id = N.Val->getNodeId();\n"; - OS << " if (Id != -1 && !isQueued(Id)) {\n"; - OS << " ISelQueue.push_back(N.Val);\n"; - OS << " std::push_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());\n"; - OS << " setQueued(Id);\n"; - OS << " }\n"; - OS << "}\n\n"; - - OS << "class VISIBILITY_HIDDEN ISelQueueUpdater :\n"; - OS << " public SelectionDAG::DAGUpdateListener {\n"; - OS << " std::vector &ISelQueue;\n"; - OS << " bool HadDelete;\n"; - OS << " public:\n"; - OS << " explicit ISelQueueUpdater(std::vector &isq)\n"; - OS << " : ISelQueue(isq), HadDelete(false) {}\n"; - OS << " \n"; - OS << " bool hadDelete() const { return HadDelete; }\n"; - OS << " \n"; - OS << " virtual void NodeDeleted(SDNode *N) {\n"; - OS << " ISelQueue.erase(std::remove(ISelQueue.begin(), ISelQueue.end(),"; - OS << " N),\n ISelQueue.end());\n"; - OS << " HadDelete = true;\n"; - OS << " }\n"; - OS << " \n"; - OS << " // Ignore updates.\n"; - OS << " virtual void NodeUpdated(SDNode *N) {}\n"; - OS << " };\n"; - - OS << "inline void UpdateQueue(const ISelQueueUpdater &ISQU) {\n"; - OS << " if (ISQU.hadDelete())\n"; - OS << " std::make_heap(ISelQueue.begin(), ISelQueue.end(),isel_sort());\n"; - OS << "}\n\n"; - - OS << "void ReplaceUses(SDOperand F, SDOperand T) DISABLE_INLINE {\n"; - OS << " ISelQueueUpdater ISQU(ISelQueue);\n"; - OS << " CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISQU);\n"; - OS << " setSelected(F.Val->getNodeId());\n"; - OS << " UpdateQueue(ISQU);\n"; - OS << "}\n"; - OS << "void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE {\n"; - OS << " unsigned FNumVals = F->getNumValues();\n"; - OS << " unsigned TNumVals = T->getNumValues();\n"; - OS << " ISelQueueUpdater ISQU(ISelQueue);\n"; - OS << " if (FNumVals != TNumVals) {\n"; - OS << " for (unsigned i = 0, e = std::min(FNumVals, TNumVals); " - << "i < e; ++i)\n"; - OS << " CurDAG->ReplaceAllUsesOfValueWith(SDOperand(F, i), " - << "SDOperand(T, i), &ISQU);\n"; - OS << " } else {\n"; - OS << " CurDAG->ReplaceAllUsesWith(F, T, &ISQU);\n"; - OS << " }\n"; - OS << " setSelected(F->getNodeId());\n"; - OS << " UpdateQueue(ISQU);\n"; - OS << "}\n\n"; - - OS << "// SelectRoot - Top level entry to DAG isel.\n"; - OS << "SDOperand SelectRoot(SDOperand Root) {\n"; - OS << " SelectRootInit();\n"; - OS << " unsigned NumBytes = (DAGSize + 7) / 8;\n"; - OS << " ISelQueued = new unsigned char[NumBytes];\n"; - OS << " ISelSelected = new unsigned char[NumBytes];\n"; - OS << " memset(ISelQueued, 0, NumBytes);\n"; - OS << " memset(ISelSelected, 0, NumBytes);\n"; - OS << "\n"; - OS << " // Create a dummy node (which is not added to allnodes), that adds\n" - << " // a reference to the root node, preventing it from being deleted,\n" - << " // and tracking any changes of the root.\n" - << " HandleSDNode Dummy(CurDAG->getRoot());\n" - << " ISelQueue.push_back(CurDAG->getRoot().Val);\n"; - OS << " while (!ISelQueue.empty()) {\n"; - OS << " SDNode *Node = ISelQueue.front();\n"; - OS << " std::pop_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());\n"; - OS << " ISelQueue.pop_back();\n"; - OS << " if (!isSelected(Node->getNodeId())) {\n"; - OS << " SDNode *ResNode = Select(SDOperand(Node, 0));\n"; - OS << " if (ResNode != Node) {\n"; - OS << " if (ResNode)\n"; - OS << " ReplaceUses(Node, ResNode);\n"; - OS << " if (Node->use_empty()) { // Don't delete EntryToken, etc.\n"; - OS << " ISelQueueUpdater ISQU(ISelQueue);\n"; - OS << " CurDAG->RemoveDeadNode(Node, &ISQU);\n"; - OS << " UpdateQueue(ISQU);\n"; - OS << " }\n"; - OS << " }\n"; - OS << " }\n"; - OS << " }\n"; - OS << "\n"; - OS << " delete[] ISelQueued;\n"; - OS << " ISelQueued = NULL;\n"; - OS << " delete[] ISelSelected;\n"; - OS << " ISelSelected = NULL;\n"; - OS << " return Dummy.getValue();\n"; - OS << "}\n"; + OS << "// Include standard, target-independent definitions and methods used\n" + << "// by the instruction selector.\n"; + OS << "#include \n\n"; EmitNodeTransforms(OS); EmitPredicateFunctions(OS); -- cgit v1.1