SelectionDAG.h revision c23b8719ef9d6b1220e854b37d40e9e1c48a82bc
1e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===// 2e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// 3e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// The LLVM Compiler Infrastructure 4e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// 5e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// This file is distributed under the University of Illinois Open Source 6e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// License. See LICENSE.TXT for details. 7e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// 8e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich//===----------------------------------------------------------------------===// 9e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// 10e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// This file declares the SelectionDAG class, and transitively defines the 11e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// SDNode class and subclasses. 12e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich// 13e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich//===----------------------------------------------------------------------===// 14e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 15e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#ifndef LLVM_CODEGEN_SELECTIONDAG_H 16e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#define LLVM_CODEGEN_SELECTIONDAG_H 17e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 18e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#include "llvm/ADT/ilist.h" 19e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#include "llvm/ADT/DenseSet.h" 20e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#include "llvm/ADT/FoldingSet.h" 21e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#include "llvm/ADT/StringMap.h" 22e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#include "llvm/CodeGen/SelectionDAGNodes.h" 23e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 24e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#include <cassert> 25e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#include <vector> 26e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#include <map> 27e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich#include <string> 28e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 29e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichnamespace llvm { 30e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 31e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichclass AliasAnalysis; 32e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichclass TargetLowering; 33e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichclass TargetMachine; 34e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichclass MachineModuleInfo; 35e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichclass DwarfWriter; 36e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichclass MachineFunction; 37e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichclass MachineConstantPoolValue; 38e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichclass FunctionLoweringInfo; 39e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 40e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichtemplate<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> { 41e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichprivate: 42e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich mutable ilist_node<SDNode> Sentinel; 43e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichpublic: 44e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich SDNode *createSentinel() const { 45e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich return static_cast<SDNode*>(&Sentinel); 46e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich } 47e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich static void destroySentinel(SDNode *) {} 48e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 49e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich SDNode *provideInitialHead() const { return createSentinel(); } 50e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich SDNode *ensureHead(SDNode*) const { return createSentinel(); } 51e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 52e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich static void deleteNode(SDNode *) { 53e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich assert(0 && "ilist_traits<SDNode> shouldn't see a deleteNode call!"); 54e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich } 55e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichprivate: 56e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich static void createNode(const SDNode &); 57e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich}; 58e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 59e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevichenum CombineLevel { 60e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich Unrestricted, // Combine may create illegal operations and illegal types. 61e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich NoIllegalTypes, // Combine may create illegal operations but no illegal types. 62e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich NoIllegalOperations // Combine may only create legal operations and types. 63e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich}; 64e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich 65e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich/// SelectionDAG class - This is used to represent a portion of an LLVM function 66e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich/// in a low-level Data Dependence DAG representation suitable for instruction 67e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich/// selection. This DAG is constructed as the first step of instruction 68e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich/// selection in order to allow implementation of machine specific optimizations 69e4e83f8147f92141cd02cc46cccca088c527ea2aNick Kralevich/// and code simplifications. 70/// 71/// The representation used by the SelectionDAG is a target-independent 72/// representation, which has some similarities to the GCC RTL representation, 73/// but is significantly more simple, powerful, and is a graph form instead of a 74/// linear form. 75/// 76class SelectionDAG { 77 TargetLowering &TLI; 78 MachineFunction *MF; 79 FunctionLoweringInfo &FLI; 80 MachineModuleInfo *MMI; 81 DwarfWriter *DW; 82 83 /// EntryNode - The starting token. 84 SDNode EntryNode; 85 86 /// Root - The root of the entire DAG. 87 SDValue Root; 88 89 /// AllNodes - A linked list of nodes in the current DAG. 90 ilist<SDNode> AllNodes; 91 92 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use 93 /// pool allocation with recycling. 94 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode), 95 AlignOf<MostAlignedSDNode>::Alignment> 96 NodeAllocatorType; 97 98 /// NodeAllocator - Pool allocation for nodes. 99 NodeAllocatorType NodeAllocator; 100 101 /// CSEMap - This structure is used to memoize nodes, automatically performing 102 /// CSE with existing nodes with a duplicate is requested. 103 FoldingSet<SDNode> CSEMap; 104 105 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands. 106 BumpPtrAllocator OperandAllocator; 107 108 /// Allocator - Pool allocation for misc. objects that are created once per 109 /// SelectionDAG. 110 BumpPtrAllocator Allocator; 111 112 /// VerifyNode - Sanity check the given node. Aborts if it is invalid. 113 void VerifyNode(SDNode *N); 114 115 /// setGraphColorHelper - Implementation of setSubgraphColor. 116 /// Return whether we had to truncate the search. 117 /// 118 bool setSubgraphColorHelper(SDNode *N, const char *Color, 119 DenseSet<SDNode *> &visited, 120 int level, bool &printed); 121 122public: 123 SelectionDAG(TargetLowering &tli, FunctionLoweringInfo &fli); 124 ~SelectionDAG(); 125 126 /// init - Prepare this SelectionDAG to process code in the given 127 /// MachineFunction. 128 /// 129 void init(MachineFunction &mf, MachineModuleInfo *mmi, DwarfWriter *dw); 130 131 /// clear - Clear state and free memory necessary to make this 132 /// SelectionDAG ready to process a new block. 133 /// 134 void clear(); 135 136 MachineFunction &getMachineFunction() const { return *MF; } 137 const TargetMachine &getTarget() const; 138 TargetLowering &getTargetLoweringInfo() const { return TLI; } 139 FunctionLoweringInfo &getFunctionLoweringInfo() const { return FLI; } 140 MachineModuleInfo *getMachineModuleInfo() const { return MMI; } 141 DwarfWriter *getDwarfWriter() const { return DW; } 142 143 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 144 /// 145 void viewGraph(const std::string &Title); 146 void viewGraph(); 147 148#ifndef NDEBUG 149 std::map<const SDNode *, std::string> NodeGraphAttrs; 150#endif 151 152 /// clearGraphAttrs - Clear all previously defined node graph attributes. 153 /// Intended to be used from a debugging tool (eg. gdb). 154 void clearGraphAttrs(); 155 156 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".) 157 /// 158 void setGraphAttrs(const SDNode *N, const char *Attrs); 159 160 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".) 161 /// Used from getNodeAttributes. 162 const std::string getGraphAttrs(const SDNode *N) const; 163 164 /// setGraphColor - Convenience for setting node color attribute. 165 /// 166 void setGraphColor(const SDNode *N, const char *Color); 167 168 /// setGraphColor - Convenience for setting subgraph color attribute. 169 /// 170 void setSubgraphColor(SDNode *N, const char *Color); 171 172 typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 173 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 174 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 175 typedef ilist<SDNode>::iterator allnodes_iterator; 176 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 177 allnodes_iterator allnodes_end() { return AllNodes.end(); } 178 ilist<SDNode>::size_type allnodes_size() const { 179 return AllNodes.size(); 180 } 181 182 /// getRoot - Return the root tag of the SelectionDAG. 183 /// 184 const SDValue &getRoot() const { return Root; } 185 186 /// getEntryNode - Return the token chain corresponding to the entry of the 187 /// function. 188 SDValue getEntryNode() const { 189 return SDValue(const_cast<SDNode *>(&EntryNode), 0); 190 } 191 192 /// setRoot - Set the current root tag of the SelectionDAG. 193 /// 194 const SDValue &setRoot(SDValue N) { 195 assert((!N.getNode() || N.getValueType() == MVT::Other) && 196 "DAG root value is not a chain!"); 197 return Root = N; 198 } 199 200 /// Combine - This iterates over the nodes in the SelectionDAG, folding 201 /// certain types of nodes together, or eliminating superfluous nodes. The 202 /// Level argument controls whether Combine is allowed to produce nodes and 203 /// types that are illegal on the target. 204 void Combine(CombineLevel Level, AliasAnalysis &AA, bool Fast); 205 206 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 207 /// only uses types natively supported by the target. Returns "true" if it 208 /// made any changes. 209 /// 210 /// Note that this is an involved process that may invalidate pointers into 211 /// the graph. 212 bool LegalizeTypes(); 213 214 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 215 /// compatible with the target instruction selector, as indicated by the 216 /// TargetLowering object. 217 /// 218 /// Note that this is an involved process that may invalidate pointers into 219 /// the graph. 220 void Legalize(bool TypesNeedLegalizing, bool Fast); 221 222 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 223 /// SelectionDAG. 224 void RemoveDeadNodes(); 225 226 /// DeleteNode - Remove the specified node from the system. This node must 227 /// have no referrers. 228 void DeleteNode(SDNode *N); 229 230 /// getVTList - Return an SDVTList that represents the list of values 231 /// specified. 232 SDVTList getVTList(MVT VT); 233 SDVTList getVTList(MVT VT1, MVT VT2); 234 SDVTList getVTList(MVT VT1, MVT VT2, MVT VT3); 235 SDVTList getVTList(MVT VT1, MVT VT2, MVT VT3, MVT VT4); 236 SDVTList getVTList(const MVT *VTs, unsigned NumVTs); 237 238 /// getNodeValueTypes - These are obsolete, use getVTList instead. 239 const MVT *getNodeValueTypes(MVT VT) { 240 return getVTList(VT).VTs; 241 } 242 const MVT *getNodeValueTypes(MVT VT1, MVT VT2) { 243 return getVTList(VT1, VT2).VTs; 244 } 245 const MVT *getNodeValueTypes(MVT VT1, MVT VT2, MVT VT3) { 246 return getVTList(VT1, VT2, VT3).VTs; 247 } 248 const MVT *getNodeValueTypes(MVT VT1, MVT VT2, MVT VT3, MVT VT4) { 249 return getVTList(VT1, VT2, VT3, VT4).VTs; 250 } 251 const MVT *getNodeValueTypes(const std::vector<MVT> &vtList) { 252 return getVTList(&vtList[0], (unsigned)vtList.size()).VTs; 253 } 254 255 256 //===--------------------------------------------------------------------===// 257 // Node creation methods. 258 // 259 SDValue getConstant(uint64_t Val, MVT VT, bool isTarget = false); 260 SDValue getConstant(const APInt &Val, MVT VT, bool isTarget = false); 261 SDValue getConstant(const ConstantInt &Val, MVT VT, bool isTarget = false); 262 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false); 263 SDValue getTargetConstant(uint64_t Val, MVT VT) { 264 return getConstant(Val, VT, true); 265 } 266 SDValue getTargetConstant(const APInt &Val, MVT VT) { 267 return getConstant(Val, VT, true); 268 } 269 SDValue getTargetConstant(const ConstantInt &Val, MVT VT) { 270 return getConstant(Val, VT, true); 271 } 272 SDValue getConstantFP(double Val, MVT VT, bool isTarget = false); 273 SDValue getConstantFP(const APFloat& Val, MVT VT, bool isTarget = false); 274 SDValue getConstantFP(const ConstantFP &CF, MVT VT, bool isTarget = false); 275 SDValue getTargetConstantFP(double Val, MVT VT) { 276 return getConstantFP(Val, VT, true); 277 } 278 SDValue getTargetConstantFP(const APFloat& Val, MVT VT) { 279 return getConstantFP(Val, VT, true); 280 } 281 SDValue getTargetConstantFP(const ConstantFP &Val, MVT VT) { 282 return getConstantFP(Val, VT, true); 283 } 284 SDValue getGlobalAddress(const GlobalValue *GV, MVT VT, 285 int64_t offset = 0, bool isTargetGA = false); 286 SDValue getTargetGlobalAddress(const GlobalValue *GV, MVT VT, 287 int64_t offset = 0) { 288 return getGlobalAddress(GV, VT, offset, true); 289 } 290 SDValue getFrameIndex(int FI, MVT VT, bool isTarget = false); 291 SDValue getTargetFrameIndex(int FI, MVT VT) { 292 return getFrameIndex(FI, VT, true); 293 } 294 SDValue getJumpTable(int JTI, MVT VT, bool isTarget = false); 295 SDValue getTargetJumpTable(int JTI, MVT VT) { 296 return getJumpTable(JTI, VT, true); 297 } 298 SDValue getConstantPool(Constant *C, MVT VT, 299 unsigned Align = 0, int Offs = 0, bool isT=false); 300 SDValue getTargetConstantPool(Constant *C, MVT VT, 301 unsigned Align = 0, int Offset = 0) { 302 return getConstantPool(C, VT, Align, Offset, true); 303 } 304 SDValue getConstantPool(MachineConstantPoolValue *C, MVT VT, 305 unsigned Align = 0, int Offs = 0, bool isT=false); 306 SDValue getTargetConstantPool(MachineConstantPoolValue *C, 307 MVT VT, unsigned Align = 0, 308 int Offset = 0) { 309 return getConstantPool(C, VT, Align, Offset, true); 310 } 311 // When generating a branch to a BB, we don't in general know enough 312 // to provide debug info for the BB at that time, so keep this one around. 313 SDValue getBasicBlock(MachineBasicBlock *MBB); 314 SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl); 315 SDValue getExternalSymbol(const char *Sym, MVT VT); 316 SDValue getExternalSymbol(const char *Sym, DebugLoc dl, MVT VT); 317 SDValue getTargetExternalSymbol(const char *Sym, MVT VT); 318 SDValue getTargetExternalSymbol(const char *Sym, DebugLoc dl, MVT VT); 319 SDValue getArgFlags(ISD::ArgFlagsTy Flags); 320 SDValue getValueType(MVT); 321 SDValue getRegister(unsigned Reg, MVT VT); 322 SDValue getDbgStopPoint(SDValue Root, unsigned Line, unsigned Col, 323 Value *CU); 324 SDValue getLabel(unsigned Opcode, DebugLoc dl, SDValue Root, 325 unsigned LabelID); 326 327 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) { 328 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, 329 getRegister(Reg, N.getValueType()), N); 330 } 331 332 // This version of the getCopyToReg method takes an extra operand, which 333 // indicates that there is potentially an incoming flag value (if Flag is not 334 // null) and that there should be a flag result. 335 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N, 336 SDValue Flag) { 337 const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 338 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; 339 return getNode(ISD::CopyToReg, dl, VTs, 2, Ops, Flag.getNode() ? 4 : 3); 340 } 341 342 // Similar to last getCopyToReg() except parameter Reg is a SDValue 343 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N, 344 SDValue Flag) { 345 const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 346 SDValue Ops[] = { Chain, Reg, N, Flag }; 347 return getNode(ISD::CopyToReg, dl, VTs, 2, Ops, Flag.getNode() ? 4 : 3); 348 } 349 350 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, MVT VT) { 351 const MVT *VTs = getNodeValueTypes(VT, MVT::Other); 352 SDValue Ops[] = { Chain, getRegister(Reg, VT) }; 353 return getNode(ISD::CopyFromReg, dl, VTs, 2, Ops, 2); 354 } 355 356 // This version of the getCopyFromReg method takes an extra operand, which 357 // indicates that there is potentially an incoming flag value (if Flag is not 358 // null) and that there should be a flag result. 359 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, MVT VT, 360 SDValue Flag) { 361 const MVT *VTs = getNodeValueTypes(VT, MVT::Other, MVT::Flag); 362 SDValue Ops[] = { Chain, getRegister(Reg, VT), Flag }; 363 return getNode(ISD::CopyFromReg, dl, VTs, 3, Ops, Flag.getNode() ? 3 : 2); 364 } 365 366 SDValue getCondCode(ISD::CondCode Cond); 367 368 /// Returns the ConvertRndSat Note: Avoid using this node because it may 369 /// disappear in the future and most targets don't support it. 370 SDValue getConvertRndSat(MVT VT, DebugLoc dl, SDValue Val, SDValue DTy, 371 SDValue STy, 372 SDValue Rnd, SDValue Sat, ISD::CvtCode Code); 373 374 /// getZeroExtendInReg - Return the expression required to zero extend the Op 375 /// value assuming it was the smaller SrcTy value. 376 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, MVT SrcTy); 377 378 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). 379 SDValue getNOT(DebugLoc DL, SDValue Val, MVT VT); 380 381 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 382 /// a flag result (to ensure it's not CSE'd). CALLSEQ_START does not have a 383 /// useful DebugLoc. 384 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) { 385 const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 386 SDValue Ops[] = { Chain, Op }; 387 return getNode(ISD::CALLSEQ_START, DebugLoc::getUnknownLoc(), 388 VTs, 2, Ops, 2); 389 } 390 391 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a 392 /// flag result (to ensure it's not CSE'd). CALLSEQ_END does not have 393 /// a useful DebugLoc. 394 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, 395 SDValue InFlag) { 396 SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag); 397 SmallVector<SDValue, 4> Ops; 398 Ops.push_back(Chain); 399 Ops.push_back(Op1); 400 Ops.push_back(Op2); 401 Ops.push_back(InFlag); 402 return getNode(ISD::CALLSEQ_END, DebugLoc::getUnknownLoc(), NodeTys, 403 &Ops[0], 404 (unsigned)Ops.size() - (InFlag.getNode() == 0 ? 1 : 0)); 405 } 406 407 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc. 408 SDValue getUNDEF(MVT VT) { 409 return getNode(ISD::UNDEF, DebugLoc::getUnknownLoc(), VT); 410 } 411 412 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does 413 /// not have a useful DebugLoc. 414 SDValue getGLOBAL_OFFSET_TABLE(MVT VT) { 415 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc::getUnknownLoc(), VT); 416 } 417 418 /// getNode - Gets or creates the specified node. 419 /// 420 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT); 421 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, SDValue N); 422 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, SDValue N1, SDValue N2); 423 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 424 SDValue N1, SDValue N2, SDValue N3); 425 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 426 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 427 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 428 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 429 SDValue N5); 430 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 431 const SDUse *Ops, unsigned NumOps); 432 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 433 const SDValue *Ops, unsigned NumOps); 434 SDValue getNode(unsigned Opcode, DebugLoc DL, 435 const std::vector<MVT> &ResultTys, 436 const SDValue *Ops, unsigned NumOps); 437 SDValue getNode(unsigned Opcode, DebugLoc DL, const MVT *VTs, unsigned NumVTs, 438 const SDValue *Ops, unsigned NumOps); 439 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 440 const SDValue *Ops, unsigned NumOps); 441 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs); 442 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N); 443 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 444 SDValue N1, SDValue N2); 445 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 446 SDValue N1, SDValue N2, SDValue N3); 447 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 448 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 449 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 450 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 451 SDValue N5); 452 453 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 454 SDValue Size, unsigned Align, bool AlwaysInline, 455 const Value *DstSV, uint64_t DstSVOff, 456 const Value *SrcSV, uint64_t SrcSVOff); 457 458 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 459 SDValue Size, unsigned Align, 460 const Value *DstSV, uint64_t DstOSVff, 461 const Value *SrcSV, uint64_t SrcSVOff); 462 463 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 464 SDValue Size, unsigned Align, 465 const Value *DstSV, uint64_t DstSVOff); 466 467 /// getSetCC - Helper function to make it easier to build SetCC's if you just 468 /// have an ISD::CondCode instead of an SDValue. 469 /// 470 SDValue getSetCC(DebugLoc DL, MVT VT, SDValue LHS, SDValue RHS, 471 ISD::CondCode Cond) { 472 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 473 } 474 475 /// getVSetCC - Helper function to make it easier to build VSetCC's nodes 476 /// if you just have an ISD::CondCode instead of an SDValue. 477 /// 478 SDValue getVSetCC(DebugLoc DL, MVT VT, SDValue LHS, SDValue RHS, 479 ISD::CondCode Cond) { 480 return getNode(ISD::VSETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 481 } 482 483 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 484 /// just have an ISD::CondCode instead of an SDValue. 485 /// 486 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS, 487 SDValue True, SDValue False, ISD::CondCode Cond) { 488 return getNode(ISD::SELECT_CC, DL, True.getValueType(), 489 LHS, RHS, True, False, getCondCode(Cond)); 490 } 491 492 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 493 /// and a source value as input. 494 SDValue getVAArg(MVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, 495 SDValue SV); 496 497 /// getAtomic - Gets a node for an atomic op, produces result and chain and 498 /// takes 3 operands 499 SDValue getAtomic(unsigned Opcode, DebugLoc dl, MVT MemVT, SDValue Chain, 500 SDValue Ptr, SDValue Cmp, SDValue Swp, const Value* PtrVal, 501 unsigned Alignment=0); 502 503 /// getAtomic - Gets a node for an atomic op, produces result and chain and 504 /// takes 2 operands. 505 SDValue getAtomic(unsigned Opcode, DebugLoc dl, MVT MemVT, SDValue Chain, 506 SDValue Ptr, SDValue Val, const Value* PtrVal, 507 unsigned Alignment = 0); 508 509 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a 510 /// result and takes a list of operands. 511 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, 512 const MVT *VTs, unsigned NumVTs, 513 const SDValue *Ops, unsigned NumOps, 514 MVT MemVT, const Value *srcValue, int SVOff, 515 unsigned Align = 0, bool Vol = false, 516 bool ReadMem = true, bool WriteMem = true); 517 518 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 519 const SDValue *Ops, unsigned NumOps, 520 MVT MemVT, const Value *srcValue, int SVOff, 521 unsigned Align = 0, bool Vol = false, 522 bool ReadMem = true, bool WriteMem = true); 523 524 /// getMergeValues - Create a MERGE_VALUES node from the given operands. 525 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl); 526 527 /// getCall - Create a CALL node from the given information. 528 /// 529 SDValue getCall(unsigned CallingConv, DebugLoc dl, bool IsVarArgs, 530 bool IsTailCall, bool isInreg, SDVTList VTs, 531 const SDValue *Operands, unsigned NumOperands); 532 533 /// getLoad - Loads are not normal binary operators: their result type is not 534 /// determined by their operands, and they produce a value AND a token chain. 535 /// 536 SDValue getLoad(MVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, 537 const Value *SV, int SVOffset, bool isVolatile=false, 538 unsigned Alignment=0); 539 SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, MVT VT, 540 SDValue Chain, SDValue Ptr, const Value *SV, 541 int SVOffset, MVT EVT, bool isVolatile=false, 542 unsigned Alignment=0); 543 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, 544 SDValue Offset, ISD::MemIndexedMode AM); 545 SDValue getLoad(ISD::MemIndexedMode AM, DebugLoc dl, ISD::LoadExtType ExtType, 546 MVT VT, SDValue Chain, 547 SDValue Ptr, SDValue Offset, 548 const Value *SV, int SVOffset, MVT EVT, 549 bool isVolatile=false, unsigned Alignment=0); 550 551 /// getStore - Helper function to build ISD::STORE nodes. 552 /// 553 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 554 const Value *SV, int SVOffset, bool isVolatile=false, 555 unsigned Alignment=0); 556 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 557 const Value *SV, int SVOffset, MVT TVT, 558 bool isVolatile=false, unsigned Alignment=0); 559 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base, 560 SDValue Offset, ISD::MemIndexedMode AM); 561 562 /// getSrcValue - Construct a node to track a Value* through the backend. 563 SDValue getSrcValue(const Value *v); 564 565 /// getMemOperand - Construct a node to track a memory reference 566 /// through the backend. 567 SDValue getMemOperand(const MachineMemOperand &MO); 568 569 /// getShiftAmountOperand - Return the specified value casted to 570 /// the target's desired shift amount type. 571 SDValue getShiftAmountOperand(SDValue Op); 572 573 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 574 /// specified operands. If the resultant node already exists in the DAG, 575 /// this does not modify the specified node, instead it returns the node that 576 /// already exists. If the resultant node does not exist in the DAG, the 577 /// input node is returned. As a degenerate case, if you specify the same 578 /// input operands as the node already has, the input node is returned. 579 SDValue UpdateNodeOperands(SDValue N, SDValue Op); 580 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2); 581 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 582 SDValue Op3); 583 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 584 SDValue Op3, SDValue Op4); 585 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 586 SDValue Op3, SDValue Op4, SDValue Op5); 587 SDValue UpdateNodeOperands(SDValue N, 588 const SDValue *Ops, unsigned NumOps); 589 590 /// SelectNodeTo - These are used for target selectors to *mutate* the 591 /// specified node to have the specified return type, Target opcode, and 592 /// operands. Note that target opcodes are stored as 593 /// ~TargetOpcode in the node opcode field. The resultant node is returned. 594 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT); 595 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, SDValue Op1); 596 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 597 SDValue Op1, SDValue Op2); 598 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 599 SDValue Op1, SDValue Op2, SDValue Op3); 600 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 601 const SDValue *Ops, unsigned NumOps); 602 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, MVT VT2); 603 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 604 MVT VT2, const SDValue *Ops, unsigned NumOps); 605 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 606 MVT VT2, MVT VT3, const SDValue *Ops, unsigned NumOps); 607 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, MVT VT1, 608 MVT VT2, MVT VT3, MVT VT4, const SDValue *Ops, 609 unsigned NumOps); 610 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 611 MVT VT2, SDValue Op1); 612 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 613 MVT VT2, SDValue Op1, SDValue Op2); 614 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 615 MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 616 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 617 MVT VT2, MVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); 618 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs, 619 const SDValue *Ops, unsigned NumOps); 620 621 /// MorphNodeTo - These *mutate* the specified node to have the specified 622 /// return type, opcode, and operands. 623 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT); 624 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, SDValue Op1); 625 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, 626 SDValue Op1, SDValue Op2); 627 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, 628 SDValue Op1, SDValue Op2, SDValue Op3); 629 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, 630 const SDValue *Ops, unsigned NumOps); 631 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, MVT VT2); 632 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 633 MVT VT2, const SDValue *Ops, unsigned NumOps); 634 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 635 MVT VT2, MVT VT3, const SDValue *Ops, unsigned NumOps); 636 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 637 MVT VT2, SDValue Op1); 638 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 639 MVT VT2, SDValue Op1, SDValue Op2); 640 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 641 MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 642 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, 643 const SDValue *Ops, unsigned NumOps); 644 645 /// getTargetNode - These are used for target selectors to create a new node 646 /// with specified return type(s), target opcode, and operands. 647 /// 648 /// Note that getTargetNode returns the resultant node. If there is already a 649 /// node of the specified opcode and operands, it returns that node instead of 650 /// the current one. 651 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT); 652 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, SDValue Op1); 653 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, SDValue Op1, 654 SDValue Op2); 655 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, 656 SDValue Op1, SDValue Op2, SDValue Op3); 657 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, 658 const SDValue *Ops, unsigned NumOps); 659 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2); 660 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, 661 SDValue Op1); 662 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, 663 MVT VT2, SDValue Op1, SDValue Op2); 664 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, 665 MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 666 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, 667 const SDValue *Ops, unsigned NumOps); 668 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 669 SDValue Op1, SDValue Op2); 670 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 671 SDValue Op1, SDValue Op2, SDValue Op3); 672 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 673 const SDValue *Ops, unsigned NumOps); 674 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 675 MVT VT4, const SDValue *Ops, unsigned NumOps); 676 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, 677 const std::vector<MVT> &ResultTys, const SDValue *Ops, 678 unsigned NumOps); 679 680 /// getNodeIfExists - Get the specified node if it's already available, or 681 /// else return NULL. 682 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, 683 const SDValue *Ops, unsigned NumOps); 684 685 /// DAGUpdateListener - Clients of various APIs that cause global effects on 686 /// the DAG can optionally implement this interface. This allows the clients 687 /// to handle the various sorts of updates that happen. 688 class DAGUpdateListener { 689 public: 690 virtual ~DAGUpdateListener(); 691 692 /// NodeDeleted - The node N that was deleted and, if E is not null, an 693 /// equivalent node E that replaced it. 694 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0; 695 696 /// NodeUpdated - The node N that was updated. 697 virtual void NodeUpdated(SDNode *N) = 0; 698 }; 699 700 /// RemoveDeadNode - Remove the specified node from the system. If any of its 701 /// operands then becomes dead, remove them as well. Inform UpdateListener 702 /// for each node deleted. 703 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0); 704 705 /// RemoveDeadNodes - This method deletes the unreachable nodes in the 706 /// given list, and any nodes that become unreachable as a result. 707 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes, 708 DAGUpdateListener *UpdateListener = 0); 709 710 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 711 /// This can cause recursive merging of nodes in the DAG. Use the first 712 /// version if 'From' is known to have a single result, use the second 713 /// if you have two nodes with identical results, use the third otherwise. 714 /// 715 /// These methods all take an optional UpdateListener, which (if not null) is 716 /// informed about nodes that are deleted and modified due to recursive 717 /// changes in the dag. 718 /// 719 /// These functions only replace all existing uses. It's possible that as 720 /// these replacements are being performed, CSE may cause the From node 721 /// to be given new uses. These new uses of From are left in place, and 722 /// not automatically transfered to To. 723 /// 724 void ReplaceAllUsesWith(SDValue From, SDValue Op, 725 DAGUpdateListener *UpdateListener = 0); 726 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 727 DAGUpdateListener *UpdateListener = 0); 728 void ReplaceAllUsesWith(SDNode *From, const SDValue *To, 729 DAGUpdateListener *UpdateListener = 0); 730 731 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 732 /// uses of other values produced by From.Val alone. 733 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To, 734 DAGUpdateListener *UpdateListener = 0); 735 736 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but 737 /// for multiple values at once. This correctly handles the case where 738 /// there is an overlap between the From values and the To values. 739 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, 740 unsigned Num, 741 DAGUpdateListener *UpdateListener = 0); 742 743 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a 744 /// assign a unique node id for each node in the DAG based on their 745 /// topological order. Returns the number of nodes. 746 unsigned AssignTopologicalOrder(); 747 748 /// RepositionNode - Move node N in the AllNodes list to be immediately 749 /// before the given iterator Position. This may be used to update the 750 /// topological ordering when the list of nodes is modified. 751 void RepositionNode(allnodes_iterator Position, SDNode *N) { 752 AllNodes.insert(Position, AllNodes.remove(N)); 753 } 754 755 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 756 /// operation. 757 static bool isCommutativeBinOp(unsigned Opcode) { 758 // FIXME: This should get its info from the td file, so that we can include 759 // target info. 760 switch (Opcode) { 761 case ISD::ADD: 762 case ISD::MUL: 763 case ISD::MULHU: 764 case ISD::MULHS: 765 case ISD::SMUL_LOHI: 766 case ISD::UMUL_LOHI: 767 case ISD::FADD: 768 case ISD::FMUL: 769 case ISD::AND: 770 case ISD::OR: 771 case ISD::XOR: 772 case ISD::ADDC: 773 case ISD::ADDE: return true; 774 default: return false; 775 } 776 } 777 778 void dump() const; 779 780 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 781 /// specified value type. If minAlign is specified, the slot size will have 782 /// at least that alignment. 783 SDValue CreateStackTemporary(MVT VT, unsigned minAlign = 1); 784 785 /// CreateStackTemporary - Create a stack temporary suitable for holding 786 /// either of the specified value types. 787 SDValue CreateStackTemporary(MVT VT1, MVT VT2); 788 789 /// FoldConstantArithmetic - 790 SDValue FoldConstantArithmetic(unsigned Opcode, 791 MVT VT, 792 ConstantSDNode *Cst1, 793 ConstantSDNode *Cst2); 794 795 /// FoldSetCC - Constant fold a setcc to true or false. 796 SDValue FoldSetCC(MVT VT, SDValue N1, 797 SDValue N2, ISD::CondCode Cond, DebugLoc dl); 798 799 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 800 /// use this predicate to simplify operations downstream. 801 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const; 802 803 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 804 /// use this predicate to simplify operations downstream. Op and Mask are 805 /// known to be the same type. 806 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0) 807 const; 808 809 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 810 /// known to be either zero or one and return them in the KnownZero/KnownOne 811 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 812 /// processing. Targets can implement the computeMaskedBitsForTargetNode 813 /// method in the TargetLowering class to allow target nodes to be understood. 814 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero, 815 APInt &KnownOne, unsigned Depth = 0) const; 816 817 /// ComputeNumSignBits - Return the number of times the sign bit of the 818 /// register is replicated into the other bits. We know that at least 1 bit 819 /// is always equal to the sign bit (itself), but other cases can give us 820 /// information. For example, immediately after an "SRA X, 2", we know that 821 /// the top 3 bits are all equal to each other, so we return 3. Targets can 822 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 823 /// class to allow target nodes to be understood. 824 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; 825 826 /// isVerifiedDebugInfoDesc - Returns true if the specified SDValue has 827 /// been verified as a debug information descriptor. 828 bool isVerifiedDebugInfoDesc(SDValue Op) const; 829 830 /// getShuffleScalarElt - Returns the scalar element that will make up the ith 831 /// element of the result of the vector shuffle. 832 SDValue getShuffleScalarElt(const SDNode *N, unsigned Idx); 833 834private: 835 bool RemoveNodeFromCSEMaps(SDNode *N); 836 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener); 837 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); 838 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, 839 void *&InsertPos); 840 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps, 841 void *&InsertPos); 842 843 void DeleteNodeNotInCSEMaps(SDNode *N); 844 void DeallocateNode(SDNode *N); 845 846 unsigned getMVTAlignment(MVT MemoryVT) const; 847 848 void allnodes_clear(); 849 850 /// VTList - List of non-single value types. 851 std::vector<SDVTList> VTList; 852 853 /// CondCodeNodes - Maps to auto-CSE operations. 854 std::vector<CondCodeSDNode*> CondCodeNodes; 855 856 std::vector<SDNode*> ValueTypeNodes; 857 std::map<MVT, SDNode*, MVT::compareRawBits> ExtendedValueTypeNodes; 858 StringMap<SDNode*> ExternalSymbols; 859 StringMap<SDNode*> TargetExternalSymbols; 860}; 861 862template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 863 typedef SelectionDAG::allnodes_iterator nodes_iterator; 864 static nodes_iterator nodes_begin(SelectionDAG *G) { 865 return G->allnodes_begin(); 866 } 867 static nodes_iterator nodes_end(SelectionDAG *G) { 868 return G->allnodes_end(); 869 } 870}; 871 872} // end namespace llvm 873 874#endif 875