LLVM API Documentation
00001 //==-llvm/CodeGen/DAGISelHeader.h - Common DAG ISel definitions -*- C++ -*-==// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file provides definitions of the common, target-independent methods and 00011 // data, which is used by SelectionDAG-based instruction selectors. 00012 // 00013 // *** NOTE: This file is #included into the middle of the target 00014 // instruction selector class. These functions are really methods. 00015 // This is a little awkward, but it allows this code to be shared 00016 // by all the targets while still being able to call into 00017 // target-specific code without using a virtual function call. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #ifndef LLVM_CODEGEN_DAGISEL_HEADER_H 00022 #define LLVM_CODEGEN_DAGISEL_HEADER_H 00023 00024 /// ISelPosition - Node iterator marking the current position of 00025 /// instruction selection as it procedes through the topologically-sorted 00026 /// node list. 00027 SelectionDAG::allnodes_iterator ISelPosition; 00028 00029 /// IsChainCompatible - Returns true if Chain is Op or Chain does 00030 /// not reach Op. 00031 static bool IsChainCompatible(SDNode *Chain, SDNode *Op) { 00032 if (Chain->getOpcode() == ISD::EntryToken) 00033 return true; 00034 if (Chain->getOpcode() == ISD::TokenFactor) 00035 return false; 00036 if (Chain->getNumOperands() > 0) { 00037 SDValue C0 = Chain->getOperand(0); 00038 if (C0.getValueType() == MVT::Other) 00039 return C0.getNode() != Op && IsChainCompatible(C0.getNode(), Op); 00040 } 00041 return true; 00042 } 00043 00044 /// ISelUpdater - helper class to handle updates of the 00045 /// instruciton selection graph. 00046 class VISIBILITY_HIDDEN ISelUpdater : public SelectionDAG::DAGUpdateListener { 00047 SelectionDAG::allnodes_iterator &ISelPosition; 00048 public: 00049 explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp) 00050 : ISelPosition(isp) {} 00051 00052 /// NodeDeleted - Handle nodes deleted from the graph. If the 00053 /// node being deleted is the current ISelPosition node, update 00054 /// ISelPosition. 00055 /// 00056 virtual void NodeDeleted(SDNode *N, SDNode *E) { 00057 if (ISelPosition == SelectionDAG::allnodes_iterator(N)) 00058 ++ISelPosition; 00059 } 00060 00061 /// NodeUpdated - Ignore updates for now. 00062 virtual void NodeUpdated(SDNode *N) {} 00063 }; 00064 00065 /// ReplaceUses - replace all uses of the old node F with the use 00066 /// of the new node T. 00067 void ReplaceUses(SDValue F, SDValue T) DISABLE_INLINE { 00068 ISelUpdater ISU(ISelPosition); 00069 CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU); 00070 } 00071 00072 /// ReplaceUses - replace all uses of the old nodes F with the use 00073 /// of the new nodes T. 00074 void ReplaceUses(const SDValue *F, const SDValue *T, 00075 unsigned Num) DISABLE_INLINE { 00076 ISelUpdater ISU(ISelPosition); 00077 CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU); 00078 } 00079 00080 /// ReplaceUses - replace all uses of the old node F with the use 00081 /// of the new node T. 00082 void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE { 00083 ISelUpdater ISU(ISelPosition); 00084 CurDAG->ReplaceAllUsesWith(F, T, &ISU); 00085 } 00086 00087 /// SelectRoot - Top level entry to DAG instruction selector. 00088 /// Selects instructions starting at the root of the current DAG. 00089 void SelectRoot(SelectionDAG &DAG) { 00090 SelectRootInit(); 00091 00092 // Create a dummy node (which is not added to allnodes), that adds 00093 // a reference to the root node, preventing it from being deleted, 00094 // and tracking any changes of the root. 00095 HandleSDNode Dummy(CurDAG->getRoot()); 00096 ISelPosition = next(SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode())); 00097 00098 // The AllNodes list is now topological-sorted. Visit the 00099 // nodes by starting at the end of the list (the root of the 00100 // graph) and preceding back toward the beginning (the entry 00101 // node). 00102 while (ISelPosition != CurDAG->allnodes_begin()) { 00103 SDNode *Node = --ISelPosition; 00104 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes, 00105 // but there are currently some corner cases that it misses. Also, this 00106 // makes it theoretically possible to disable the DAGCombiner. 00107 if (Node->use_empty()) 00108 continue; 00109 #if 0 00110 DAG.setSubgraphColor(Node, "red"); 00111 #endif 00112 SDNode *ResNode = Select(SDValue(Node, 0)); 00113 // If node should not be replaced, 00114 // continue with the next one. 00115 if (ResNode == Node) 00116 continue; 00117 // Replace node. 00118 if (ResNode) { 00119 #if 0 00120 DAG.setSubgraphColor(ResNode, "yellow"); 00121 DAG.setSubgraphColor(ResNode, "black"); 00122 #endif 00123 ReplaceUses(Node, ResNode); 00124 } 00125 // If after the replacement this node is not used any more, 00126 // remove this dead node. 00127 if (Node->use_empty()) { // Don't delete EntryToken, etc. 00128 ISelUpdater ISU(ISelPosition); 00129 CurDAG->RemoveDeadNode(Node, &ISU); 00130 } 00131 } 00132 00133 CurDAG->setRoot(Dummy.getValue()); 00134 } 00135 00136 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */