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