SelectionDAGNodes.h revision 7e122db776d9731dfe5acb7faa9da4f3c33ee5a1
1//===-- llvm/CodeGen/SelectionDAGNodes.h - SelectionDAG Nodes ---*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file declares the SDNode class and derived classes, which are used to 11// represent the nodes and operations present in a SelectionDAG. These nodes 12// and operations are machine code level operations, with some similarities to 13// the GCC RTL representation. 14// 15// Clients should include the SelectionDAG.h file instead of this file directly. 16// 17//===----------------------------------------------------------------------===// 18 19#ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H 20#define LLVM_CODEGEN_SELECTIONDAGNODES_H 21 22#include "llvm/CodeGen/ValueTypes.h" 23#include "llvm/Value.h" 24#include "llvm/ADT/GraphTraits.h" 25#include "llvm/ADT/GraphTraits.h" 26#include "llvm/ADT/iterator" 27#include "llvm/Support/DataTypes.h" 28#include <cassert> 29#include <vector> 30 31namespace llvm { 32 33class SelectionDAG; 34class GlobalValue; 35class MachineBasicBlock; 36class SDNode; 37template <typename T> struct simplify_type; 38 39/// ISD namespace - This namespace contains an enum which represents all of the 40/// SelectionDAG node types and value types. 41/// 42namespace ISD { 43 //===--------------------------------------------------------------------===// 44 /// ISD::NodeType enum - This enum defines all of the operators valid in a 45 /// SelectionDAG. 46 /// 47 enum NodeType { 48 // EntryToken - This is the marker used to indicate the start of the region. 49 EntryToken, 50 51 // Token factor - This node takes multiple tokens as input and produces a 52 // single token result. This is used to represent the fact that the operand 53 // operators are independent of each other. 54 TokenFactor, 55 56 // AssertSext, AssertZext - These nodes record if a register contains a 57 // value that has already been zero or sign extended from a narrower type. 58 // These nodes take two operands. The first is the node that has already 59 // been extended, and the second is a value type node indicating the width 60 // of the extension 61 AssertSext, AssertZext, 62 63 // Various leaf nodes. 64 Constant, ConstantFP, GlobalAddress, FrameIndex, ConstantPool, 65 BasicBlock, ExternalSymbol, VALUETYPE, CONDCODE, Register, 66 67 // TargetConstant - Like Constant, but the DAG does not do any folding or 68 // simplification of the constant. This is used by the DAG->DAG selector. 69 TargetConstant, 70 71 // TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or 72 // anything else with this node, and this is valid in the target-specific 73 // dag, turning into a GlobalAddress operand. 74 TargetGlobalAddress, 75 TargetFrameIndex, 76 TargetConstantPool, 77 78 // CopyToReg - This node has three operands: a chain, a register number to 79 // set to this value, and a value. 80 CopyToReg, 81 82 // CopyFromReg - This node indicates that the input value is a virtual or 83 // physical register that is defined outside of the scope of this 84 // SelectionDAG. The register is available from the RegSDNode object. 85 CopyFromReg, 86 87 // ImplicitDef - This node indicates that the specified register is 88 // implicitly defined by some operation (e.g. its a live-in argument). The 89 // two operands to this are the token chain coming in and the register. 90 // The only result is the token chain going out. 91 ImplicitDef, 92 93 // UNDEF - An undefined node 94 UNDEF, 95 96 // EXTRACT_ELEMENT - This is used to get the first or second (determined by 97 // a Constant, which is required to be operand #1), element of the aggregate 98 // value specified as operand #0. This is only for use before legalization, 99 // for values that will be broken into multiple registers. 100 EXTRACT_ELEMENT, 101 102 // BUILD_PAIR - This is the opposite of EXTRACT_ELEMENT in some ways. Given 103 // two values of the same integer value type, this produces a value twice as 104 // big. Like EXTRACT_ELEMENT, this can only be used before legalization. 105 BUILD_PAIR, 106 107 108 // Simple binary arithmetic operators. 109 ADD, SUB, MUL, SDIV, UDIV, SREM, UREM, 110 111 // MULHU/MULHS - Multiply high - Multiply two integers of type iN, producing 112 // an unsigned/signed value of type i[2*n], then return the top part. 113 MULHU, MULHS, 114 115 // Bitwise operators. 116 AND, OR, XOR, SHL, SRA, SRL, 117 118 // Counting operators 119 CTTZ, CTLZ, CTPOP, 120 121 // Select 122 SELECT, 123 124 // Select with condition operator - This selects between a true value and 125 // a false value (ops #2 and #3) based on the boolean result of comparing 126 // the lhs and rhs (ops #0 and #1) of a conditional expression with the 127 // condition code in op #4, a CondCodeSDNode. 128 SELECT_CC, 129 130 // SetCC operator - This evaluates to a boolean (i1) true value if the 131 // condition is true. The operands to this are the left and right operands 132 // to compare (ops #0, and #1) and the condition code to compare them with 133 // (op #2) as a CondCodeSDNode. 134 SETCC, 135 136 // ADD_PARTS/SUB_PARTS - These operators take two logical operands which are 137 // broken into a multiple pieces each, and return the resulting pieces of 138 // doing an atomic add/sub operation. This is used to handle add/sub of 139 // expanded types. The operation ordering is: 140 // [Lo,Hi] = op [LoLHS,HiLHS], [LoRHS,HiRHS] 141 ADD_PARTS, SUB_PARTS, 142 143 // SHL_PARTS/SRA_PARTS/SRL_PARTS - These operators are used for expanded 144 // integer shift operations, just like ADD/SUB_PARTS. The operation 145 // ordering is: 146 // [Lo,Hi] = op [LoLHS,HiLHS], Amt 147 SHL_PARTS, SRA_PARTS, SRL_PARTS, 148 149 // Conversion operators. These are all single input single output 150 // operations. For all of these, the result type must be strictly 151 // wider or narrower (depending on the operation) than the source 152 // type. 153 154 // SIGN_EXTEND - Used for integer types, replicating the sign bit 155 // into new bits. 156 SIGN_EXTEND, 157 158 // ZERO_EXTEND - Used for integer types, zeroing the new bits. 159 ZERO_EXTEND, 160 161 // ANY_EXTEND - Used for integer types. The high bits are undefined. 162 ANY_EXTEND, 163 164 // TRUNCATE - Completely drop the high bits. 165 TRUNCATE, 166 167 // [SU]INT_TO_FP - These operators convert integers (whose interpreted sign 168 // depends on the first letter) to floating point. 169 SINT_TO_FP, 170 UINT_TO_FP, 171 172 // SIGN_EXTEND_INREG - This operator atomically performs a SHL/SRA pair to 173 // sign extend a small value in a large integer register (e.g. sign 174 // extending the low 8 bits of a 32-bit register to fill the top 24 bits 175 // with the 7th bit). The size of the smaller type is indicated by the 1th 176 // operand, a ValueType node. 177 SIGN_EXTEND_INREG, 178 179 // FP_TO_[US]INT - Convert a floating point value to a signed or unsigned 180 // integer. 181 FP_TO_SINT, 182 FP_TO_UINT, 183 184 // FP_ROUND - Perform a rounding operation from the current 185 // precision down to the specified precision (currently always 64->32). 186 FP_ROUND, 187 188 // FP_ROUND_INREG - This operator takes a floating point register, and 189 // rounds it to a floating point value. It then promotes it and returns it 190 // in a register of the same size. This operation effectively just discards 191 // excess precision. The type to round down to is specified by the 1th 192 // operation, a VTSDNode (currently always 64->32->64). 193 FP_ROUND_INREG, 194 195 // FP_EXTEND - Extend a smaller FP type into a larger FP type. 196 FP_EXTEND, 197 198 // FNEG, FABS, FSQRT, FSIN, FCOS - Perform unary floating point negation, 199 // absolute value, square root, sine and cosine operations. 200 FNEG, FABS, FSQRT, FSIN, FCOS, 201 202 // Other operators. LOAD and STORE have token chains as their first 203 // operand, then the same operands as an LLVM load/store instruction, then a 204 // SRCVALUE node that provides alias analysis information. 205 LOAD, STORE, 206 207 // EXTLOAD, SEXTLOAD, ZEXTLOAD - These three operators all load a value from 208 // memory and extend them to a larger value (e.g. load a byte into a word 209 // register). All three of these have four operands, a token chain, a 210 // pointer to load from, a SRCVALUE for alias analysis, and a VALUETYPE node 211 // indicating the type to load. 212 // 213 // SEXTLOAD loads the integer operand and sign extends it to a larger 214 // integer result type. 215 // ZEXTLOAD loads the integer operand and zero extends it to a larger 216 // integer result type. 217 // EXTLOAD is used for two things: floating point extending loads, and 218 // integer extending loads where it doesn't matter what the high 219 // bits are set to. The code generator is allowed to codegen this 220 // into whichever operation is more efficient. 221 EXTLOAD, SEXTLOAD, ZEXTLOAD, 222 223 // TRUNCSTORE - This operators truncates (for integer) or rounds (for FP) a 224 // value and stores it to memory in one operation. This can be used for 225 // either integer or floating point operands. The first four operands of 226 // this are the same as a standard store. The fifth is the ValueType to 227 // store it as (which will be smaller than the source value). 228 TRUNCSTORE, 229 230 // DYNAMIC_STACKALLOC - Allocate some number of bytes on the stack aligned 231 // to a specified boundary. The first operand is the token chain, the 232 // second is the number of bytes to allocate, and the third is the alignment 233 // boundary. The size is guaranteed to be a multiple of the stack 234 // alignment, and the alignment is guaranteed to be bigger than the stack 235 // alignment (if required) or 0 to get standard stack alignment. 236 DYNAMIC_STACKALLOC, 237 238 // Control flow instructions. These all have token chains. 239 240 // BR - Unconditional branch. The first operand is the chain 241 // operand, the second is the MBB to branch to. 242 BR, 243 244 // BRCOND - Conditional branch. The first operand is the chain, 245 // the second is the condition, the third is the block to branch 246 // to if the condition is true. 247 BRCOND, 248 249 // BRCONDTWOWAY - Two-way conditional branch. The first operand is the 250 // chain, the second is the condition, the third is the block to branch to 251 // if true, and the forth is the block to branch to if false. Targets 252 // usually do not implement this, preferring to have legalize demote the 253 // operation to BRCOND/BR pairs when necessary. 254 BRCONDTWOWAY, 255 256 // BR_CC - Conditional branch. The behavior is like that of SELECT_CC, in 257 // that the condition is represented as condition code, and two nodes to 258 // compare, rather than as a combined SetCC node. The operands in order are 259 // chain, cc, lhs, rhs, block to branch to if condition is true. 260 BR_CC, 261 262 // BRTWOWAY_CC - Two-way conditional branch. The operands in order are 263 // chain, cc, lhs, rhs, block to branch to if condition is true, block to 264 // branch to if condition is false. Targets usually do not implement this, 265 // preferring to have legalize demote the operation to BRCOND/BR pairs. 266 BRTWOWAY_CC, 267 268 // RET - Return from function. The first operand is the chain, 269 // and any subsequent operands are the return values for the 270 // function. This operation can have variable number of operands. 271 RET, 272 273 // CALL - Call to a function pointer. The first operand is the chain, the 274 // second is the destination function pointer (a GlobalAddress for a direct 275 // call). Arguments have already been lowered to explicit DAGs according to 276 // the calling convention in effect here. TAILCALL is the same as CALL, but 277 // the callee is known not to access the stack of the caller. 278 CALL, 279 TAILCALL, 280 281 // MEMSET/MEMCPY/MEMMOVE - The first operand is the chain, and the rest 282 // correspond to the operands of the LLVM intrinsic functions. The only 283 // result is a token chain. The alignment argument is guaranteed to be a 284 // Constant node. 285 MEMSET, 286 MEMMOVE, 287 MEMCPY, 288 289 // CALLSEQ_START/CALLSEQ_END - These operators mark the beginning and end of 290 // a call sequence, and carry arbitrary information that target might want 291 // to know. The first operand is a chain, the rest are specified by the 292 // target and not touched by the DAG optimizers. 293 CALLSEQ_START, // Beginning of a call sequence 294 CALLSEQ_END, // End of a call sequence 295 296 // SRCVALUE - This corresponds to a Value*, and is used to associate memory 297 // locations with their value. This allows one use alias analysis 298 // information in the backend. 299 SRCVALUE, 300 301 // PCMARKER - This corresponds to the pcmarker intrinsic. 302 PCMARKER, 303 304 // READPORT, WRITEPORT, READIO, WRITEIO - These correspond to the LLVM 305 // intrinsics of the same name. The first operand is a token chain, the 306 // other operands match the intrinsic. These produce a token chain in 307 // addition to a value (if any). 308 READPORT, WRITEPORT, READIO, WRITEIO, 309 310 // BUILTIN_OP_END - This must be the last enum value in this list. 311 BUILTIN_OP_END, 312 }; 313 314 //===--------------------------------------------------------------------===// 315 /// ISD::CondCode enum - These are ordered carefully to make the bitfields 316 /// below work out, when considering SETFALSE (something that never exists 317 /// dynamically) as 0. "U" -> Unsigned (for integer operands) or Unordered 318 /// (for floating point), "L" -> Less than, "G" -> Greater than, "E" -> Equal 319 /// to. If the "N" column is 1, the result of the comparison is undefined if 320 /// the input is a NAN. 321 /// 322 /// All of these (except for the 'always folded ops') should be handled for 323 /// floating point. For integer, only the SETEQ,SETNE,SETLT,SETLE,SETGT, 324 /// SETGE,SETULT,SETULE,SETUGT, and SETUGE opcodes are used. 325 /// 326 /// Note that these are laid out in a specific order to allow bit-twiddling 327 /// to transform conditions. 328 enum CondCode { 329 // Opcode N U L G E Intuitive operation 330 SETFALSE, // 0 0 0 0 Always false (always folded) 331 SETOEQ, // 0 0 0 1 True if ordered and equal 332 SETOGT, // 0 0 1 0 True if ordered and greater than 333 SETOGE, // 0 0 1 1 True if ordered and greater than or equal 334 SETOLT, // 0 1 0 0 True if ordered and less than 335 SETOLE, // 0 1 0 1 True if ordered and less than or equal 336 SETONE, // 0 1 1 0 True if ordered and operands are unequal 337 SETO, // 0 1 1 1 True if ordered (no nans) 338 SETUO, // 1 0 0 0 True if unordered: isnan(X) | isnan(Y) 339 SETUEQ, // 1 0 0 1 True if unordered or equal 340 SETUGT, // 1 0 1 0 True if unordered or greater than 341 SETUGE, // 1 0 1 1 True if unordered, greater than, or equal 342 SETULT, // 1 1 0 0 True if unordered or less than 343 SETULE, // 1 1 0 1 True if unordered, less than, or equal 344 SETUNE, // 1 1 1 0 True if unordered or not equal 345 SETTRUE, // 1 1 1 1 Always true (always folded) 346 // Don't care operations: undefined if the input is a nan. 347 SETFALSE2, // 1 X 0 0 0 Always false (always folded) 348 SETEQ, // 1 X 0 0 1 True if equal 349 SETGT, // 1 X 0 1 0 True if greater than 350 SETGE, // 1 X 0 1 1 True if greater than or equal 351 SETLT, // 1 X 1 0 0 True if less than 352 SETLE, // 1 X 1 0 1 True if less than or equal 353 SETNE, // 1 X 1 1 0 True if not equal 354 SETTRUE2, // 1 X 1 1 1 Always true (always folded) 355 356 SETCC_INVALID, // Marker value. 357 }; 358 359 /// isSignedIntSetCC - Return true if this is a setcc instruction that 360 /// performs a signed comparison when used with integer operands. 361 inline bool isSignedIntSetCC(CondCode Code) { 362 return Code == SETGT || Code == SETGE || Code == SETLT || Code == SETLE; 363 } 364 365 /// isUnsignedIntSetCC - Return true if this is a setcc instruction that 366 /// performs an unsigned comparison when used with integer operands. 367 inline bool isUnsignedIntSetCC(CondCode Code) { 368 return Code == SETUGT || Code == SETUGE || Code == SETULT || Code == SETULE; 369 } 370 371 /// isTrueWhenEqual - Return true if the specified condition returns true if 372 /// the two operands to the condition are equal. Note that if one of the two 373 /// operands is a NaN, this value is meaningless. 374 inline bool isTrueWhenEqual(CondCode Cond) { 375 return ((int)Cond & 1) != 0; 376 } 377 378 /// getUnorderedFlavor - This function returns 0 if the condition is always 379 /// false if an operand is a NaN, 1 if the condition is always true if the 380 /// operand is a NaN, and 2 if the condition is undefined if the operand is a 381 /// NaN. 382 inline unsigned getUnorderedFlavor(CondCode Cond) { 383 return ((int)Cond >> 3) & 3; 384 } 385 386 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where 387 /// 'op' is a valid SetCC operation. 388 CondCode getSetCCInverse(CondCode Operation, bool isInteger); 389 390 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 391 /// when given the operation for (X op Y). 392 CondCode getSetCCSwappedOperands(CondCode Operation); 393 394 /// getSetCCOrOperation - Return the result of a logical OR between different 395 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This 396 /// function returns SETCC_INVALID if it is not possible to represent the 397 /// resultant comparison. 398 CondCode getSetCCOrOperation(CondCode Op1, CondCode Op2, bool isInteger); 399 400 /// getSetCCAndOperation - Return the result of a logical AND between 401 /// different comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 402 /// function returns SETCC_INVALID if it is not possible to represent the 403 /// resultant comparison. 404 CondCode getSetCCAndOperation(CondCode Op1, CondCode Op2, bool isInteger); 405} // end llvm::ISD namespace 406 407 408//===----------------------------------------------------------------------===// 409/// SDOperand - Unlike LLVM values, Selection DAG nodes may return multiple 410/// values as the result of a computation. Many nodes return multiple values, 411/// from loads (which define a token and a return value) to ADDC (which returns 412/// a result and a carry value), to calls (which may return an arbitrary number 413/// of values). 414/// 415/// As such, each use of a SelectionDAG computation must indicate the node that 416/// computes it as well as which return value to use from that node. This pair 417/// of information is represented with the SDOperand value type. 418/// 419class SDOperand { 420public: 421 SDNode *Val; // The node defining the value we are using. 422 unsigned ResNo; // Which return value of the node we are using. 423 424 SDOperand() : Val(0) {} 425 SDOperand(SDNode *val, unsigned resno) : Val(val), ResNo(resno) {} 426 427 bool operator==(const SDOperand &O) const { 428 return Val == O.Val && ResNo == O.ResNo; 429 } 430 bool operator!=(const SDOperand &O) const { 431 return !operator==(O); 432 } 433 bool operator<(const SDOperand &O) const { 434 return Val < O.Val || (Val == O.Val && ResNo < O.ResNo); 435 } 436 437 SDOperand getValue(unsigned R) const { 438 return SDOperand(Val, R); 439 } 440 441 /// getValueType - Return the ValueType of the referenced return value. 442 /// 443 inline MVT::ValueType getValueType() const; 444 445 // Forwarding methods - These forward to the corresponding methods in SDNode. 446 inline unsigned getOpcode() const; 447 inline unsigned getNodeDepth() const; 448 inline unsigned getNumOperands() const; 449 inline const SDOperand &getOperand(unsigned i) const; 450 inline bool isTargetOpcode() const; 451 inline unsigned getTargetOpcode() const; 452 453 /// hasOneUse - Return true if there is exactly one operation using this 454 /// result value of the defining operator. 455 inline bool hasOneUse() const; 456}; 457 458 459/// simplify_type specializations - Allow casting operators to work directly on 460/// SDOperands as if they were SDNode*'s. 461template<> struct simplify_type<SDOperand> { 462 typedef SDNode* SimpleType; 463 static SimpleType getSimplifiedValue(const SDOperand &Val) { 464 return static_cast<SimpleType>(Val.Val); 465 } 466}; 467template<> struct simplify_type<const SDOperand> { 468 typedef SDNode* SimpleType; 469 static SimpleType getSimplifiedValue(const SDOperand &Val) { 470 return static_cast<SimpleType>(Val.Val); 471 } 472}; 473 474 475/// SDNode - Represents one node in the SelectionDAG. 476/// 477class SDNode { 478 /// NodeType - The operation that this node performs. 479 /// 480 unsigned short NodeType; 481 482 /// NodeDepth - Node depth is defined as MAX(Node depth of children)+1. This 483 /// means that leaves have a depth of 1, things that use only leaves have a 484 /// depth of 2, etc. 485 unsigned short NodeDepth; 486 487 /// Operands - The values that are used by this operation. 488 /// 489 std::vector<SDOperand> Operands; 490 491 /// Values - The types of the values this node defines. SDNode's may define 492 /// multiple values simultaneously. 493 std::vector<MVT::ValueType> Values; 494 495 /// Uses - These are all of the SDNode's that use a value produced by this 496 /// node. 497 std::vector<SDNode*> Uses; 498public: 499 500 //===--------------------------------------------------------------------===// 501 // Accessors 502 // 503 unsigned getOpcode() const { return NodeType; } 504 bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; } 505 unsigned getTargetOpcode() const { 506 assert(isTargetOpcode() && "Not a target opcode!"); 507 return NodeType - ISD::BUILTIN_OP_END; 508 } 509 510 size_t use_size() const { return Uses.size(); } 511 bool use_empty() const { return Uses.empty(); } 512 bool hasOneUse() const { return Uses.size() == 1; } 513 514 /// getNodeDepth - Return the distance from this node to the leaves in the 515 /// graph. The leaves have a depth of 1. 516 unsigned getNodeDepth() const { return NodeDepth; } 517 518 typedef std::vector<SDNode*>::const_iterator use_iterator; 519 use_iterator use_begin() const { return Uses.begin(); } 520 use_iterator use_end() const { return Uses.end(); } 521 522 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 523 /// indicated value. This method ignores uses of other values defined by this 524 /// operation. 525 bool hasNUsesOfValue(unsigned NUses, unsigned Value); 526 527 /// getNumOperands - Return the number of values used by this operation. 528 /// 529 unsigned getNumOperands() const { return Operands.size(); } 530 531 const SDOperand &getOperand(unsigned Num) { 532 assert(Num < Operands.size() && "Invalid child # of SDNode!"); 533 return Operands[Num]; 534 } 535 536 const SDOperand &getOperand(unsigned Num) const { 537 assert(Num < Operands.size() && "Invalid child # of SDNode!"); 538 return Operands[Num]; 539 } 540 typedef std::vector<SDOperand>::const_iterator op_iterator; 541 op_iterator op_begin() const { return Operands.begin(); } 542 op_iterator op_end() const { return Operands.end(); } 543 544 545 /// getNumValues - Return the number of values defined/returned by this 546 /// operator. 547 /// 548 unsigned getNumValues() const { return Values.size(); } 549 550 /// getValueType - Return the type of a specified result. 551 /// 552 MVT::ValueType getValueType(unsigned ResNo) const { 553 assert(ResNo < Values.size() && "Illegal result number!"); 554 return Values[ResNo]; 555 } 556 557 typedef std::vector<MVT::ValueType>::const_iterator value_iterator; 558 value_iterator value_begin() const { return Values.begin(); } 559 value_iterator value_end() const { return Values.end(); } 560 561 /// getOperationName - Return the opcode of this operation for printing. 562 /// 563 const char* getOperationName(const SelectionDAG *G = 0) const; 564 void dump() const; 565 void dump(const SelectionDAG *G) const; 566 567 static bool classof(const SDNode *) { return true; } 568 569 570 /// setAdjCallChain - This method should only be used by the legalizer. 571 void setAdjCallChain(SDOperand N); 572 573protected: 574 friend class SelectionDAG; 575 576 SDNode(unsigned NT, MVT::ValueType VT) : NodeType(NT), NodeDepth(1) { 577 Values.reserve(1); 578 Values.push_back(VT); 579 } 580 SDNode(unsigned NT, SDOperand Op) 581 : NodeType(NT), NodeDepth(Op.Val->getNodeDepth()+1) { 582 Operands.reserve(1); Operands.push_back(Op); 583 Op.Val->Uses.push_back(this); 584 } 585 SDNode(unsigned NT, SDOperand N1, SDOperand N2) 586 : NodeType(NT) { 587 if (N1.Val->getNodeDepth() > N2.Val->getNodeDepth()) 588 NodeDepth = N1.Val->getNodeDepth()+1; 589 else 590 NodeDepth = N2.Val->getNodeDepth()+1; 591 Operands.reserve(2); Operands.push_back(N1); Operands.push_back(N2); 592 N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); 593 } 594 SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3) 595 : NodeType(NT) { 596 unsigned ND = N1.Val->getNodeDepth(); 597 if (ND < N2.Val->getNodeDepth()) 598 ND = N2.Val->getNodeDepth(); 599 if (ND < N3.Val->getNodeDepth()) 600 ND = N3.Val->getNodeDepth(); 601 NodeDepth = ND+1; 602 603 Operands.reserve(3); Operands.push_back(N1); Operands.push_back(N2); 604 Operands.push_back(N3); 605 N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); 606 N3.Val->Uses.push_back(this); 607 } 608 SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4) 609 : NodeType(NT) { 610 unsigned ND = N1.Val->getNodeDepth(); 611 if (ND < N2.Val->getNodeDepth()) 612 ND = N2.Val->getNodeDepth(); 613 if (ND < N3.Val->getNodeDepth()) 614 ND = N3.Val->getNodeDepth(); 615 if (ND < N4.Val->getNodeDepth()) 616 ND = N4.Val->getNodeDepth(); 617 NodeDepth = ND+1; 618 619 Operands.reserve(4); Operands.push_back(N1); Operands.push_back(N2); 620 Operands.push_back(N3); Operands.push_back(N4); 621 N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); 622 N3.Val->Uses.push_back(this); N4.Val->Uses.push_back(this); 623 } 624 SDNode(unsigned NT, std::vector<SDOperand> &Nodes) : NodeType(NT) { 625 Operands.swap(Nodes); 626 unsigned ND = 0; 627 for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 628 Operands[i].Val->Uses.push_back(this); 629 if (ND < Operands[i].Val->getNodeDepth()) 630 ND = Operands[i].Val->getNodeDepth(); 631 } 632 NodeDepth = ND+1; 633 } 634 635 virtual ~SDNode() {} 636 637 /// MorphNodeTo - This clears the return value and operands list, and sets the 638 /// opcode of the node to the specified value. This should only be used by 639 /// the SelectionDAG class. 640 void MorphNodeTo(unsigned Opc) { 641 NodeType = Opc; 642 Values.clear(); 643 644 // Clear the operands list, updating used nodes to remove this from their 645 // use list. 646 while (!Operands.empty()) { 647 SDNode *O = Operands.back().Val; 648 Operands.pop_back(); 649 O->removeUser(this); 650 } 651 } 652 653 void setValueTypes(MVT::ValueType VT) { 654 Values.reserve(1); 655 Values.push_back(VT); 656 } 657 void setValueTypes(MVT::ValueType VT1, MVT::ValueType VT2) { 658 Values.reserve(2); 659 Values.push_back(VT1); 660 Values.push_back(VT2); 661 } 662 /// Note: this method destroys the vector passed in. 663 void setValueTypes(std::vector<MVT::ValueType> &VTs) { 664 std::swap(Values, VTs); 665 } 666 667 void setOperands(SDOperand Op0) { 668 Operands.reserve(1); 669 Operands.push_back(Op0); 670 Op0.Val->Uses.push_back(this); 671 } 672 void setOperands(SDOperand Op0, SDOperand Op1) { 673 Operands.reserve(2); 674 Operands.push_back(Op0); 675 Operands.push_back(Op1); 676 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 677 } 678 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2) { 679 Operands.reserve(3); 680 Operands.push_back(Op0); 681 Operands.push_back(Op1); 682 Operands.push_back(Op2); 683 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 684 Op2.Val->Uses.push_back(this); 685 } 686 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3) { 687 Operands.reserve(4); 688 Operands.push_back(Op0); 689 Operands.push_back(Op1); 690 Operands.push_back(Op2); 691 Operands.push_back(Op3); 692 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 693 Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); 694 } 695 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3, 696 SDOperand Op4) { 697 Operands.reserve(5); 698 Operands.push_back(Op0); 699 Operands.push_back(Op1); 700 Operands.push_back(Op2); 701 Operands.push_back(Op3); 702 Operands.push_back(Op4); 703 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 704 Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); 705 Op4.Val->Uses.push_back(this); 706 } 707 void addUser(SDNode *User) { 708 Uses.push_back(User); 709 } 710 void removeUser(SDNode *User) { 711 // Remove this user from the operand's use list. 712 for (unsigned i = Uses.size(); ; --i) { 713 assert(i != 0 && "Didn't find user!"); 714 if (Uses[i-1] == User) { 715 Uses[i-1] = Uses.back(); 716 Uses.pop_back(); 717 return; 718 } 719 } 720 } 721}; 722 723 724// Define inline functions from the SDOperand class. 725 726inline unsigned SDOperand::getOpcode() const { 727 return Val->getOpcode(); 728} 729inline unsigned SDOperand::getNodeDepth() const { 730 return Val->getNodeDepth(); 731} 732inline MVT::ValueType SDOperand::getValueType() const { 733 return Val->getValueType(ResNo); 734} 735inline unsigned SDOperand::getNumOperands() const { 736 return Val->getNumOperands(); 737} 738inline const SDOperand &SDOperand::getOperand(unsigned i) const { 739 return Val->getOperand(i); 740} 741inline bool SDOperand::isTargetOpcode() const { 742 return Val->isTargetOpcode(); 743} 744inline unsigned SDOperand::getTargetOpcode() const { 745 return Val->getTargetOpcode(); 746} 747inline bool SDOperand::hasOneUse() const { 748 return Val->hasNUsesOfValue(1, ResNo); 749} 750 751 752class ConstantSDNode : public SDNode { 753 uint64_t Value; 754protected: 755 friend class SelectionDAG; 756 ConstantSDNode(bool isTarget, uint64_t val, MVT::ValueType VT) 757 : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, VT), Value(val) { 758 } 759public: 760 761 uint64_t getValue() const { return Value; } 762 763 int64_t getSignExtended() const { 764 unsigned Bits = MVT::getSizeInBits(getValueType(0)); 765 return ((int64_t)Value << (64-Bits)) >> (64-Bits); 766 } 767 768 bool isNullValue() const { return Value == 0; } 769 bool isAllOnesValue() const { 770 int NumBits = MVT::getSizeInBits(getValueType(0)); 771 if (NumBits == 64) return Value+1 == 0; 772 return Value == (1ULL << NumBits)-1; 773 } 774 775 static bool classof(const ConstantSDNode *) { return true; } 776 static bool classof(const SDNode *N) { 777 return N->getOpcode() == ISD::Constant || 778 N->getOpcode() == ISD::TargetConstant; 779 } 780}; 781 782class ConstantFPSDNode : public SDNode { 783 double Value; 784protected: 785 friend class SelectionDAG; 786 ConstantFPSDNode(double val, MVT::ValueType VT) 787 : SDNode(ISD::ConstantFP, VT), Value(val) { 788 } 789public: 790 791 double getValue() const { return Value; } 792 793 /// isExactlyValue - We don't rely on operator== working on double values, as 794 /// it returns true for things that are clearly not equal, like -0.0 and 0.0. 795 /// As such, this method can be used to do an exact bit-for-bit comparison of 796 /// two floating point values. 797 bool isExactlyValue(double V) const; 798 799 static bool classof(const ConstantFPSDNode *) { return true; } 800 static bool classof(const SDNode *N) { 801 return N->getOpcode() == ISD::ConstantFP; 802 } 803}; 804 805class GlobalAddressSDNode : public SDNode { 806 GlobalValue *TheGlobal; 807protected: 808 friend class SelectionDAG; 809 GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, MVT::ValueType VT) 810 : SDNode(isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress, VT) { 811 TheGlobal = const_cast<GlobalValue*>(GA); 812 } 813public: 814 815 GlobalValue *getGlobal() const { return TheGlobal; } 816 817 static bool classof(const GlobalAddressSDNode *) { return true; } 818 static bool classof(const SDNode *N) { 819 return N->getOpcode() == ISD::GlobalAddress || 820 N->getOpcode() == ISD::TargetGlobalAddress; 821 } 822}; 823 824 825class FrameIndexSDNode : public SDNode { 826 int FI; 827protected: 828 friend class SelectionDAG; 829 FrameIndexSDNode(int fi, MVT::ValueType VT, bool isTarg) 830 : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex, VT), FI(fi) {} 831public: 832 833 int getIndex() const { return FI; } 834 835 static bool classof(const FrameIndexSDNode *) { return true; } 836 static bool classof(const SDNode *N) { 837 return N->getOpcode() == ISD::FrameIndex || 838 N->getOpcode() == ISD::TargetFrameIndex; 839 } 840}; 841 842class ConstantPoolSDNode : public SDNode { 843 Constant *C; 844protected: 845 friend class SelectionDAG; 846 ConstantPoolSDNode(Constant *c, MVT::ValueType VT, bool isTarget) 847 : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT), 848 C(c) {} 849public: 850 851 Constant *get() const { return C; } 852 853 static bool classof(const ConstantPoolSDNode *) { return true; } 854 static bool classof(const SDNode *N) { 855 return N->getOpcode() == ISD::ConstantPool || 856 N->getOpcode() == ISD::TargetConstantPool; 857 } 858}; 859 860class BasicBlockSDNode : public SDNode { 861 MachineBasicBlock *MBB; 862protected: 863 friend class SelectionDAG; 864 BasicBlockSDNode(MachineBasicBlock *mbb) 865 : SDNode(ISD::BasicBlock, MVT::Other), MBB(mbb) {} 866public: 867 868 MachineBasicBlock *getBasicBlock() const { return MBB; } 869 870 static bool classof(const BasicBlockSDNode *) { return true; } 871 static bool classof(const SDNode *N) { 872 return N->getOpcode() == ISD::BasicBlock; 873 } 874}; 875 876class SrcValueSDNode : public SDNode { 877 const Value *V; 878 int offset; 879protected: 880 friend class SelectionDAG; 881 SrcValueSDNode(const Value* v, int o) 882 : SDNode(ISD::SRCVALUE, MVT::Other), V(v), offset(o) {} 883 884public: 885 const Value *getValue() const { return V; } 886 int getOffset() const { return offset; } 887 888 static bool classof(const SrcValueSDNode *) { return true; } 889 static bool classof(const SDNode *N) { 890 return N->getOpcode() == ISD::SRCVALUE; 891 } 892}; 893 894 895class RegisterSDNode : public SDNode { 896 unsigned Reg; 897protected: 898 friend class SelectionDAG; 899 RegisterSDNode(unsigned reg, MVT::ValueType VT) 900 : SDNode(ISD::Register, VT), Reg(reg) {} 901public: 902 903 unsigned getReg() const { return Reg; } 904 905 static bool classof(const RegisterSDNode *) { return true; } 906 static bool classof(const SDNode *N) { 907 return N->getOpcode() == ISD::Register; 908 } 909}; 910 911class ExternalSymbolSDNode : public SDNode { 912 const char *Symbol; 913protected: 914 friend class SelectionDAG; 915 ExternalSymbolSDNode(const char *Sym, MVT::ValueType VT) 916 : SDNode(ISD::ExternalSymbol, VT), Symbol(Sym) { 917 } 918public: 919 920 const char *getSymbol() const { return Symbol; } 921 922 static bool classof(const ExternalSymbolSDNode *) { return true; } 923 static bool classof(const SDNode *N) { 924 return N->getOpcode() == ISD::ExternalSymbol; 925 } 926}; 927 928class CondCodeSDNode : public SDNode { 929 ISD::CondCode Condition; 930protected: 931 friend class SelectionDAG; 932 CondCodeSDNode(ISD::CondCode Cond) 933 : SDNode(ISD::CONDCODE, MVT::Other), Condition(Cond) { 934 } 935public: 936 937 ISD::CondCode get() const { return Condition; } 938 939 static bool classof(const CondCodeSDNode *) { return true; } 940 static bool classof(const SDNode *N) { 941 return N->getOpcode() == ISD::CONDCODE; 942 } 943}; 944 945/// VTSDNode - This class is used to represent MVT::ValueType's, which are used 946/// to parameterize some operations. 947class VTSDNode : public SDNode { 948 MVT::ValueType ValueType; 949protected: 950 friend class SelectionDAG; 951 VTSDNode(MVT::ValueType VT) 952 : SDNode(ISD::VALUETYPE, MVT::Other), ValueType(VT) {} 953public: 954 955 MVT::ValueType getVT() const { return ValueType; } 956 957 static bool classof(const VTSDNode *) { return true; } 958 static bool classof(const SDNode *N) { 959 return N->getOpcode() == ISD::VALUETYPE; 960 } 961}; 962 963 964class SDNodeIterator : public forward_iterator<SDNode, ptrdiff_t> { 965 SDNode *Node; 966 unsigned Operand; 967 968 SDNodeIterator(SDNode *N, unsigned Op) : Node(N), Operand(Op) {} 969public: 970 bool operator==(const SDNodeIterator& x) const { 971 return Operand == x.Operand; 972 } 973 bool operator!=(const SDNodeIterator& x) const { return !operator==(x); } 974 975 const SDNodeIterator &operator=(const SDNodeIterator &I) { 976 assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); 977 Operand = I.Operand; 978 return *this; 979 } 980 981 pointer operator*() const { 982 return Node->getOperand(Operand).Val; 983 } 984 pointer operator->() const { return operator*(); } 985 986 SDNodeIterator& operator++() { // Preincrement 987 ++Operand; 988 return *this; 989 } 990 SDNodeIterator operator++(int) { // Postincrement 991 SDNodeIterator tmp = *this; ++*this; return tmp; 992 } 993 994 static SDNodeIterator begin(SDNode *N) { return SDNodeIterator(N, 0); } 995 static SDNodeIterator end (SDNode *N) { 996 return SDNodeIterator(N, N->getNumOperands()); 997 } 998 999 unsigned getOperand() const { return Operand; } 1000 const SDNode *getNode() const { return Node; } 1001}; 1002 1003template <> struct GraphTraits<SDNode*> { 1004 typedef SDNode NodeType; 1005 typedef SDNodeIterator ChildIteratorType; 1006 static inline NodeType *getEntryNode(SDNode *N) { return N; } 1007 static inline ChildIteratorType child_begin(NodeType *N) { 1008 return SDNodeIterator::begin(N); 1009 } 1010 static inline ChildIteratorType child_end(NodeType *N) { 1011 return SDNodeIterator::end(N); 1012 } 1013}; 1014 1015} // end llvm namespace 1016 1017#endif 1018