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