LLVM API Documentation
00001 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file declares the SelectionDAG class, and transitively defines the 00011 // SDNode class and subclasses. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_CODEGEN_SELECTIONDAG_H 00016 #define LLVM_CODEGEN_SELECTIONDAG_H 00017 00018 #include "llvm/CodeGen/SelectionDAGNodes.h" 00019 #include "llvm/ADT/ilist" 00020 00021 #include <list> 00022 #include <map> 00023 #include <set> 00024 #include <string> 00025 00026 namespace llvm { 00027 class TargetLowering; 00028 class TargetMachine; 00029 class MachineDebugInfo; 00030 class MachineFunction; 00031 00032 /// SelectionDAG class - This is used to represent a portion of an LLVM function 00033 /// in a low-level Data Dependence DAG representation suitable for instruction 00034 /// selection. This DAG is constructed as the first step of instruction 00035 /// selection in order to allow implementation of machine specific optimizations 00036 /// and code simplifications. 00037 /// 00038 /// The representation used by the SelectionDAG is a target-independent 00039 /// representation, which has some similarities to the GCC RTL representation, 00040 /// but is significantly more simple, powerful, and is a graph form instead of a 00041 /// linear form. 00042 /// 00043 class SelectionDAG { 00044 TargetLowering &TLI; 00045 MachineFunction &MF; 00046 MachineDebugInfo *DI; 00047 00048 // Root - The root of the entire DAG. EntryNode - The starting token. 00049 SDOperand Root, EntryNode; 00050 00051 // AllNodes - A linked list of nodes in the current DAG. 00052 ilist<SDNode> AllNodes; 00053 00054 // ValueNodes - track SrcValue nodes 00055 std::map<std::pair<const Value*, int>, SDNode*> ValueNodes; 00056 00057 public: 00058 SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineDebugInfo *di) 00059 : TLI(tli), MF(mf), DI(di) { 00060 EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); 00061 } 00062 ~SelectionDAG(); 00063 00064 MachineFunction &getMachineFunction() const { return MF; } 00065 const TargetMachine &getTarget() const; 00066 TargetLowering &getTargetLoweringInfo() const { return TLI; } 00067 MachineDebugInfo *getMachineDebugInfo() const { return DI; } 00068 00069 /// viewGraph - Pop up a ghostview window with the DAG rendered using 'dot'. 00070 /// 00071 void viewGraph(); 00072 00073 00074 typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 00075 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 00076 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 00077 typedef ilist<SDNode>::iterator allnodes_iterator; 00078 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 00079 allnodes_iterator allnodes_end() { return AllNodes.end(); } 00080 00081 /// getRoot - Return the root tag of the SelectionDAG. 00082 /// 00083 const SDOperand &getRoot() const { return Root; } 00084 00085 /// getEntryNode - Return the token chain corresponding to the entry of the 00086 /// function. 00087 const SDOperand &getEntryNode() const { return EntryNode; } 00088 00089 /// setRoot - Set the current root tag of the SelectionDAG. 00090 /// 00091 const SDOperand &setRoot(SDOperand N) { return Root = N; } 00092 00093 /// Combine - This iterates over the nodes in the SelectionDAG, folding 00094 /// certain types of nodes together, or eliminating superfluous nodes. When 00095 /// the AfterLegalize argument is set to 'true', Combine takes care not to 00096 /// generate any nodes that will be illegal on the target. 00097 void Combine(bool AfterLegalize); 00098 00099 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 00100 /// compatible with the target instruction selector, as indicated by the 00101 /// TargetLowering object. 00102 /// 00103 /// Note that this is an involved process that may invalidate pointers into 00104 /// the graph. 00105 void Legalize(); 00106 00107 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 00108 /// SelectionDAG, including nodes (like loads) that have uses of their token 00109 /// chain but no other uses and no side effect. If a node is passed in as an 00110 /// argument, it is used as the seed for node deletion. 00111 void RemoveDeadNodes(SDNode *N = 0); 00112 00113 SDOperand getString(const std::string &Val); 00114 SDOperand getConstant(uint64_t Val, MVT::ValueType VT); 00115 SDOperand getTargetConstant(uint64_t Val, MVT::ValueType VT); 00116 SDOperand getConstantFP(double Val, MVT::ValueType VT); 00117 SDOperand getTargetConstantFP(double Val, MVT::ValueType VT); 00118 SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 00119 int offset = 0); 00120 SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 00121 int offset = 0); 00122 SDOperand getFrameIndex(int FI, MVT::ValueType VT); 00123 SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT); 00124 SDOperand getJumpTable(int JTI, MVT::ValueType VT); 00125 SDOperand getTargetJumpTable(int JTI, MVT::ValueType VT); 00126 SDOperand getConstantPool(Constant *C, MVT::ValueType VT, 00127 unsigned Alignment=0, int offset = 0); 00128 SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT, 00129 unsigned Alignment=0, int offset = 0); 00130 SDOperand getBasicBlock(MachineBasicBlock *MBB); 00131 SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT); 00132 SDOperand getTargetExternalSymbol(const char *Sym, MVT::ValueType VT); 00133 SDOperand getValueType(MVT::ValueType); 00134 SDOperand getRegister(unsigned Reg, MVT::ValueType VT); 00135 00136 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) { 00137 return getNode(ISD::CopyToReg, MVT::Other, Chain, 00138 getRegister(Reg, N.getValueType()), N); 00139 } 00140 00141 // This version of the getCopyToReg method takes an extra operand, which 00142 // indicates that there is potentially an incoming flag value (if Flag is not 00143 // null) and that there should be a flag result. 00144 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N, 00145 SDOperand Flag) { 00146 std::vector<MVT::ValueType> VTs; 00147 VTs.push_back(MVT::Other); 00148 VTs.push_back(MVT::Flag); 00149 std::vector<SDOperand> Ops; 00150 Ops.push_back(Chain); 00151 Ops.push_back(getRegister(Reg, N.getValueType())); 00152 Ops.push_back(N); 00153 if (Flag.Val) Ops.push_back(Flag); 00154 return getNode(ISD::CopyToReg, VTs, Ops); 00155 } 00156 00157 // Similar to last getCopyToReg() except parameter Reg is a SDOperand 00158 SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N, 00159 SDOperand Flag) { 00160 std::vector<MVT::ValueType> VTs; 00161 VTs.push_back(MVT::Other); 00162 VTs.push_back(MVT::Flag); 00163 std::vector<SDOperand> Ops; 00164 Ops.push_back(Chain); 00165 Ops.push_back(Reg); 00166 Ops.push_back(N); 00167 if (Flag.Val) Ops.push_back(Flag); 00168 return getNode(ISD::CopyToReg, VTs, Ops); 00169 } 00170 00171 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) { 00172 std::vector<MVT::ValueType> ResultTys; 00173 ResultTys.push_back(VT); 00174 ResultTys.push_back(MVT::Other); 00175 std::vector<SDOperand> Ops; 00176 Ops.push_back(Chain); 00177 Ops.push_back(getRegister(Reg, VT)); 00178 return getNode(ISD::CopyFromReg, ResultTys, Ops); 00179 } 00180 00181 // This version of the getCopyFromReg method takes an extra operand, which 00182 // indicates that there is potentially an incoming flag value (if Flag is not 00183 // null) and that there should be a flag result. 00184 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT, 00185 SDOperand Flag) { 00186 std::vector<MVT::ValueType> ResultTys; 00187 ResultTys.push_back(VT); 00188 ResultTys.push_back(MVT::Other); 00189 ResultTys.push_back(MVT::Flag); 00190 std::vector<SDOperand> Ops; 00191 Ops.push_back(Chain); 00192 Ops.push_back(getRegister(Reg, VT)); 00193 if (Flag.Val) Ops.push_back(Flag); 00194 return getNode(ISD::CopyFromReg, ResultTys, Ops); 00195 } 00196 00197 SDOperand getCondCode(ISD::CondCode Cond); 00198 00199 /// getZeroExtendInReg - Return the expression required to zero extend the Op 00200 /// value assuming it was the smaller SrcTy value. 00201 SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy); 00202 00203 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 00204 /// a flag result (to ensure it's not CSE'd). 00205 SDOperand getCALLSEQ_START(SDOperand Chain, SDOperand Op) { 00206 std::vector<MVT::ValueType> ResultTys; 00207 ResultTys.push_back(MVT::Other); 00208 ResultTys.push_back(MVT::Flag); 00209 std::vector<SDOperand> Ops; 00210 Ops.push_back(Chain); 00211 Ops.push_back(Op); 00212 return getNode(ISD::CALLSEQ_START, ResultTys, Ops); 00213 } 00214 00215 /// getNode - Gets or creates the specified node. 00216 /// 00217 SDOperand getNode(unsigned Opcode, MVT::ValueType VT); 00218 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N); 00219 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 00220 SDOperand N1, SDOperand N2); 00221 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 00222 SDOperand N1, SDOperand N2, SDOperand N3); 00223 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 00224 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 00225 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 00226 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 00227 SDOperand N5); 00228 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 00229 std::vector<SDOperand> &Children); 00230 SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 00231 std::vector<SDOperand> &Ops); 00232 00233 /// getSetCC - Helper function to make it easier to build SetCC's if you just 00234 /// have an ISD::CondCode instead of an SDOperand. 00235 /// 00236 SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS, 00237 ISD::CondCode Cond) { 00238 return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond)); 00239 } 00240 00241 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 00242 /// just have an ISD::CondCode instead of an SDOperand. 00243 /// 00244 SDOperand getSelectCC(SDOperand LHS, SDOperand RHS, 00245 SDOperand True, SDOperand False, ISD::CondCode Cond) { 00246 MVT::ValueType VT = True.getValueType(); 00247 return getNode(ISD::SELECT_CC, VT, LHS, RHS, True, False,getCondCode(Cond)); 00248 } 00249 00250 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 00251 /// and a source value as input. 00252 SDOperand getVAArg(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 00253 SDOperand SV); 00254 00255 /// getLoad - Loads are not normal binary operators: their result type is not 00256 /// determined by their operands, and they produce a value AND a token chain. 00257 /// 00258 SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 00259 SDOperand SV); 00260 SDOperand getVecLoad(unsigned Count, MVT::ValueType VT, SDOperand Chain, 00261 SDOperand Ptr, SDOperand SV); 00262 SDOperand getExtLoad(unsigned Opcode, MVT::ValueType VT, SDOperand Chain, 00263 SDOperand Ptr, SDOperand SV, MVT::ValueType EVT); 00264 00265 // getSrcValue - construct a node to track a Value* through the backend 00266 SDOperand getSrcValue(const Value* I, int offset = 0); 00267 00268 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 00269 /// specified operands. If the resultant node already exists in the DAG, 00270 /// this does not modify the specified node, instead it returns the node that 00271 /// already exists. If the resultant node does not exist in the DAG, the 00272 /// input node is returned. As a degenerate case, if you specify the same 00273 /// input operands as the node already has, the input node is returned. 00274 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op); 00275 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2); 00276 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 00277 SDOperand Op3); 00278 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 00279 SDOperand Op3, SDOperand Op4); 00280 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 00281 SDOperand Op3, SDOperand Op4, SDOperand Op5); 00282 SDOperand UpdateNodeOperands(SDOperand N, const std::vector<SDOperand> &Op); 00283 00284 /// SelectNodeTo - These are used for target selectors to *mutate* the 00285 /// specified node to have the specified return type, Target opcode, and 00286 /// operands. Note that target opcodes are stored as 00287 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. The 0th value 00288 /// of the resultant node is returned. 00289 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT); 00290 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 00291 SDOperand Op1); 00292 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 00293 SDOperand Op1, SDOperand Op2); 00294 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 00295 SDOperand Op1, SDOperand Op2, SDOperand Op3); 00296 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 00297 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00298 SDOperand Op4); 00299 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 00300 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00301 SDOperand Op4, SDOperand Op5); 00302 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 00303 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00304 SDOperand Op4, SDOperand Op5, SDOperand Op6); 00305 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 00306 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00307 SDOperand Op4, SDOperand Op5, SDOperand Op6, 00308 SDOperand Op7); 00309 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 00310 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00311 SDOperand Op4, SDOperand Op5, SDOperand Op6, 00312 SDOperand Op7, SDOperand Op8); 00313 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 00314 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 00315 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 00316 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 00317 SDOperand Op3); 00318 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 00319 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 00320 SDOperand Op3, SDOperand Op4); 00321 SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 00322 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 00323 SDOperand Op3, SDOperand Op4, SDOperand Op5); 00324 00325 /// getTargetNode - These are used for target selectors to create a new node 00326 /// with specified return type(s), target opcode, and operands. 00327 /// 00328 /// Note that getTargetNode returns the resultant node. If there is already a 00329 /// node of the specified opcode and operands, it returns that node instead of 00330 /// the current one. 00331 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT); 00332 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 00333 SDOperand Op1); 00334 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 00335 SDOperand Op1, SDOperand Op2); 00336 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 00337 SDOperand Op1, SDOperand Op2, SDOperand Op3); 00338 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 00339 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00340 SDOperand Op4); 00341 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 00342 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00343 SDOperand Op4, SDOperand Op5); 00344 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 00345 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00346 SDOperand Op4, SDOperand Op5, SDOperand Op6); 00347 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 00348 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00349 SDOperand Op4, SDOperand Op5, SDOperand Op6, 00350 SDOperand Op7); 00351 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 00352 SDOperand Op1, SDOperand Op2, SDOperand Op3, 00353 SDOperand Op4, SDOperand Op5, SDOperand Op6, 00354 SDOperand Op7, SDOperand Op8); 00355 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 00356 std::vector<SDOperand> &Ops); 00357 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00358 MVT::ValueType VT2, SDOperand Op1); 00359 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00360 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 00361 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00362 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 00363 SDOperand Op3); 00364 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00365 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 00366 SDOperand Op3, SDOperand Op4); 00367 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00368 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 00369 SDOperand Op3, SDOperand Op4, SDOperand Op5); 00370 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00371 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 00372 SDOperand Op3, SDOperand Op4, SDOperand Op5, 00373 SDOperand Op6); 00374 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00375 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 00376 SDOperand Op3, SDOperand Op4, SDOperand Op5, 00377 SDOperand Op6, SDOperand Op7); 00378 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00379 MVT::ValueType VT2, MVT::ValueType VT3, 00380 SDOperand Op1, SDOperand Op2); 00381 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00382 MVT::ValueType VT2, MVT::ValueType VT3, 00383 SDOperand Op1, SDOperand Op2, 00384 SDOperand Op3, SDOperand Op4, SDOperand Op5); 00385 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00386 MVT::ValueType VT2, MVT::ValueType VT3, 00387 SDOperand Op1, SDOperand Op2, 00388 SDOperand Op3, SDOperand Op4, SDOperand Op5, 00389 SDOperand Op6); 00390 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00391 MVT::ValueType VT2, MVT::ValueType VT3, 00392 SDOperand Op1, SDOperand Op2, 00393 SDOperand Op3, SDOperand Op4, SDOperand Op5, 00394 SDOperand Op6, SDOperand Op7); 00395 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 00396 MVT::ValueType VT2, std::vector<SDOperand> &Ops); 00397 00398 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 00399 /// This can cause recursive merging of nodes in the DAG. Use the first 00400 /// version if 'From' is known to have a single result, use the second 00401 /// if you have two nodes with identical results, use the third otherwise. 00402 /// 00403 /// These methods all take an optional vector, which (if not null) is 00404 /// populated with any nodes that are deleted from the SelectionDAG, due to 00405 /// new equivalences that are discovered. 00406 /// 00407 void ReplaceAllUsesWith(SDOperand From, SDOperand Op, 00408 std::vector<SDNode*> *Deleted = 0); 00409 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 00410 std::vector<SDNode*> *Deleted = 0); 00411 void ReplaceAllUsesWith(SDNode *From, const std::vector<SDOperand> &To, 00412 std::vector<SDNode*> *Deleted = 0); 00413 00414 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 00415 /// uses of other values produced by From.Val alone. The Deleted vector is 00416 /// handled the same was as for ReplaceAllUsesWith, but it is required for 00417 /// this method. 00418 void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 00419 std::vector<SDNode*> &Deleted); 00420 00421 /// DeleteNode - Remove the specified node from the system. This node must 00422 /// have no referrers. 00423 void DeleteNode(SDNode *N); 00424 00425 void dump() const; 00426 00427 /// InsertISelMapEntry - A helper function to insert a key / element pair 00428 /// into a SDOperand to SDOperand map. This is added to avoid the map 00429 /// insertion operator from being inlined. 00430 static void InsertISelMapEntry(std::map<SDOperand, SDOperand> &Map, 00431 SDNode *Key, unsigned KeyResNo, 00432 SDNode *Element, unsigned ElementResNo); 00433 00434 /// InsertInFlightSetEntry - A helper function to insert a SDNode* to a 00435 /// SDNode* set. This is added to avoid the set insertion operator from being 00436 /// inlined. 00437 static void InsertInFlightSetEntry(std::set<SDNode*> &Set, SDNode *N); 00438 00439 /// RemoveInFlightSetEntry - A helper function to remove a SDNode* from a 00440 /// SDNode* set. This is added to avoid the set removal operator from being 00441 /// inlined. 00442 static void RemoveInFlightSetEntry(std::set<SDNode*> &Set, SDNode *N); 00443 00444 private: 00445 void RemoveNodeFromCSEMaps(SDNode *N); 00446 SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); 00447 SDNode **FindModifiedNodeSlot(SDNode *N, SDOperand Op); 00448 SDNode **FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2); 00449 SDNode **FindModifiedNodeSlot(SDNode *N, const std::vector<SDOperand> &Ops); 00450 00451 void DestroyDeadNode(SDNode *N); 00452 void DeleteNodeNotInCSEMaps(SDNode *N); 00453 void setNodeValueTypes(SDNode *N, std::vector<MVT::ValueType> &RetVals); 00454 void setNodeValueTypes(SDNode *N, MVT::ValueType VT1, MVT::ValueType VT2); 00455 00456 00457 /// SimplifySetCC - Try to simplify a setcc built with the specified operands 00458 /// and cc. If unable to simplify it, return a null SDOperand. 00459 SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N1, 00460 SDOperand N2, ISD::CondCode Cond); 00461 00462 // List of non-single value types. 00463 std::list<std::vector<MVT::ValueType> > VTList; 00464 00465 // Maps to auto-CSE operations. 00466 std::map<std::pair<unsigned, MVT::ValueType>, SDNode *> NullaryOps; 00467 std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >, 00468 SDNode *> UnaryOps; 00469 std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >, 00470 SDNode *> BinaryOps; 00471 00472 std::map<std::pair<unsigned, MVT::ValueType>, RegisterSDNode*> RegNodes; 00473 std::vector<CondCodeSDNode*> CondCodeNodes; 00474 00475 std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >, 00476 SDNode *> Loads; 00477 00478 std::map<std::pair<const GlobalValue*, int>, SDNode*> GlobalValues; 00479 std::map<std::pair<const GlobalValue*, int>, SDNode*> TargetGlobalValues; 00480 std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants; 00481 std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> TargetConstants; 00482 std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> ConstantFPs; 00483 std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> TargetConstantFPs; 00484 std::map<int, SDNode*> FrameIndices, TargetFrameIndices, JumpTableIndices, 00485 TargetJumpTableIndices; 00486 std::map<std::pair<Constant *, 00487 std::pair<int, unsigned> >, SDNode*> ConstantPoolIndices; 00488 std::map<std::pair<Constant *, 00489 std::pair<int, unsigned> >, SDNode*> TargetConstantPoolIndices; 00490 std::map<MachineBasicBlock *, SDNode*> BBNodes; 00491 std::vector<SDNode*> ValueTypeNodes; 00492 std::map<std::string, SDNode*> ExternalSymbols; 00493 std::map<std::string, SDNode*> TargetExternalSymbols; 00494 std::map<std::string, StringSDNode*> StringNodes; 00495 std::map<std::pair<unsigned, 00496 std::pair<MVT::ValueType, std::vector<SDOperand> > >, 00497 SDNode*> OneResultNodes; 00498 std::map<std::pair<unsigned, 00499 std::pair<std::vector<MVT::ValueType>, 00500 std::vector<SDOperand> > >, 00501 SDNode*> ArbitraryNodes; 00502 }; 00503 00504 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 00505 typedef SelectionDAG::allnodes_iterator nodes_iterator; 00506 static nodes_iterator nodes_begin(SelectionDAG *G) { 00507 return G->allnodes_begin(); 00508 } 00509 static nodes_iterator nodes_end(SelectionDAG *G) { 00510 return G->allnodes_end(); 00511 } 00512 }; 00513 00514 } // end namespace llvm 00515 00516 #endif