SelectionDAGNodes.h revision fa984b61e42c94ad7e66cf2880ca826dba488d30
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/iterator" 26#include "llvm/Support/DataTypes.h" 27#include <cassert> 28#include <vector> 29 30namespace llvm { 31 32class SelectionDAG; 33class GlobalValue; 34class MachineBasicBlock; 35class SDNode; 36template <typename T> struct simplify_type; 37template <typename T> struct ilist_traits; 38template<typename NodeTy, typename Traits> class iplist; 39template<typename NodeTy> class ilist_iterator; 40 41/// ISD namespace - This namespace contains an enum which represents all of the 42/// SelectionDAG node types and value types. 43/// 44namespace ISD { 45 //===--------------------------------------------------------------------===// 46 /// ISD::NodeType enum - This enum defines all of the operators valid in a 47 /// SelectionDAG. 48 /// 49 enum NodeType { 50 // EntryToken - This is the marker used to indicate the start of the region. 51 EntryToken, 52 53 // Token factor - This node takes multiple tokens as input and produces a 54 // single token result. This is used to represent the fact that the operand 55 // operators are independent of each other. 56 TokenFactor, 57 58 // AssertSext, AssertZext - These nodes record if a register contains a 59 // value that has already been zero or sign extended from a narrower type. 60 // These nodes take two operands. The first is the node that has already 61 // been extended, and the second is a value type node indicating the width 62 // of the extension 63 AssertSext, AssertZext, 64 65 // Various leaf nodes. 66 STRING, BasicBlock, VALUETYPE, CONDCODE, Register, 67 Constant, ConstantFP, 68 GlobalAddress, FrameIndex, ConstantPool, ExternalSymbol, 69 70 // ConstantVec works like Constant or ConstantFP, except that it is not a 71 // leaf node. All operands are either Constant or ConstantFP nodes. 72 ConstantVec, 73 74 // TargetConstant* - Like Constant*, but the DAG does not do any folding or 75 // simplification of the constant. 76 TargetConstant, 77 TargetConstantFP, 78 TargetConstantVec, 79 80 // TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or 81 // anything else with this node, and this is valid in the target-specific 82 // dag, turning into a GlobalAddress operand. 83 TargetGlobalAddress, 84 TargetFrameIndex, 85 TargetConstantPool, 86 TargetExternalSymbol, 87 88 // Abstract version of ConstantVec with abstract Vector type. The first node 89 // is a constant element count, the second is a value type indicating the 90 // type of the elements. 91 VConstant, 92 93 // CopyToReg - This node has three operands: a chain, a register number to 94 // set to this value, and a value. 95 CopyToReg, 96 97 // CopyFromReg - This node indicates that the input value is a virtual or 98 // physical register that is defined outside of the scope of this 99 // SelectionDAG. The register is available from the RegSDNode object. 100 CopyFromReg, 101 102 // UNDEF - An undefined node 103 UNDEF, 104 105 // EXTRACT_ELEMENT - This is used to get the first or second (determined by 106 // a Constant, which is required to be operand #1), element of the aggregate 107 // value specified as operand #0. This is only for use before legalization, 108 // for values that will be broken into multiple registers. 109 EXTRACT_ELEMENT, 110 111 // BUILD_PAIR - This is the opposite of EXTRACT_ELEMENT in some ways. Given 112 // two values of the same integer value type, this produces a value twice as 113 // big. Like EXTRACT_ELEMENT, this can only be used before legalization. 114 BUILD_PAIR, 115 116 // MERGE_VALUES - This node takes multiple discrete operands and returns 117 // them all as its individual results. This nodes has exactly the same 118 // number of inputs and outputs, and is only valid before legalization. 119 // This node is useful for some pieces of the code generator that want to 120 // think about a single node with multiple results, not multiple nodes. 121 MERGE_VALUES, 122 123 // Simple integer binary arithmetic operators. 124 ADD, SUB, MUL, SDIV, UDIV, SREM, UREM, 125 126 // Carry-setting nodes for multiple precision addition and subtraction. 127 // These nodes take two operands of the same value type, and produce two 128 // results. The first result is the normal add or sub result, the second 129 // result is the carry flag result. 130 ADDC, SUBC, 131 132 // Carry-using nodes for multiple precision addition and subtraction. These 133 // nodes take three operands: The first two are the normal lhs and rhs to 134 // the add or sub, and the third is the input carry flag. These nodes 135 // produce two results; the normal result of the add or sub, and the output 136 // carry flag. These nodes both read and write a carry flag to allow them 137 // to them to be chained together for add and sub of arbitrarily large 138 // values. 139 ADDE, SUBE, 140 141 // Simple binary floating point operators. 142 FADD, FSUB, FMUL, FDIV, FREM, 143 144 // FCOPYSIGN(X, Y) - Return the value of X with the sign of Y. NOTE: This 145 // DAG node does not require that X and Y have the same type, just that they 146 // are both floating point. X and the result must have the same type. 147 // FCOPYSIGN(f32, f64) is allowed. 148 FCOPYSIGN, 149 150 /// INSERT_VECTOR_ELT(VECTOR, VAL, IDX) - Returns VECTOR (a legal packed 151 /// type) with the element at IDX replaced with VAL. 152 INSERT_VECTOR_ELT, 153 154 // BINOP(LHS, RHS, COUNT,TYPE) 155 // Simple abstract vector operators. Unlike the integer and floating point 156 // binary operators, these nodes also take two additional operands: 157 // a constant element count, and a value type node indicating the type of 158 // the elements. The order is count, type, op0, op1. All vector opcodes, 159 // including VLOAD and VConstant must currently have count and type as 160 // their 1st and 2nd arguments. 161 VADD, VSUB, VMUL, VSDIV, VUDIV, 162 VAND, VOR, VXOR, 163 164 /// VINSERT_VECTOR_ELT(VECTOR, VAL, IDX, COUNT,TYPE) - Given a vector 165 /// VECTOR, an element ELEMENT, and a (potentially variable) index IDX, 166 /// return an vector with the specified element of VECTOR replaced with VAL. 167 /// COUNT and TYPE specify the type of vector, as is standard for V* nodes. 168 VINSERT_VECTOR_ELT, 169 170 // MULHU/MULHS - Multiply high - Multiply two integers of type iN, producing 171 // an unsigned/signed value of type i[2*n], then return the top part. 172 MULHU, MULHS, 173 174 // Bitwise operators - logical and, logical or, logical xor, shift left, 175 // shift right algebraic (shift in sign bits), shift right logical (shift in 176 // zeroes), rotate left, rotate right, and byteswap. 177 AND, OR, XOR, SHL, SRA, SRL, ROTL, ROTR, BSWAP, 178 179 // Counting operators 180 CTTZ, CTLZ, CTPOP, 181 182 // Select(COND, TRUEVAL, FALSEVAL) 183 SELECT, 184 185 // Select with condition operator - This selects between a true value and 186 // a false value (ops #2 and #3) based on the boolean result of comparing 187 // the lhs and rhs (ops #0 and #1) of a conditional expression with the 188 // condition code in op #4, a CondCodeSDNode. 189 SELECT_CC, 190 191 // SetCC operator - This evaluates to a boolean (i1) true value if the 192 // condition is true. The operands to this are the left and right operands 193 // to compare (ops #0, and #1) and the condition code to compare them with 194 // (op #2) as a CondCodeSDNode. 195 SETCC, 196 197 // SHL_PARTS/SRA_PARTS/SRL_PARTS - These operators are used for expanded 198 // integer shift operations, just like ADD/SUB_PARTS. The operation 199 // ordering is: 200 // [Lo,Hi] = op [LoLHS,HiLHS], Amt 201 SHL_PARTS, SRA_PARTS, SRL_PARTS, 202 203 // Conversion operators. These are all single input single output 204 // operations. For all of these, the result type must be strictly 205 // wider or narrower (depending on the operation) than the source 206 // type. 207 208 // SIGN_EXTEND - Used for integer types, replicating the sign bit 209 // into new bits. 210 SIGN_EXTEND, 211 212 // ZERO_EXTEND - Used for integer types, zeroing the new bits. 213 ZERO_EXTEND, 214 215 // ANY_EXTEND - Used for integer types. The high bits are undefined. 216 ANY_EXTEND, 217 218 // TRUNCATE - Completely drop the high bits. 219 TRUNCATE, 220 221 // [SU]INT_TO_FP - These operators convert integers (whose interpreted sign 222 // depends on the first letter) to floating point. 223 SINT_TO_FP, 224 UINT_TO_FP, 225 226 // SIGN_EXTEND_INREG - This operator atomically performs a SHL/SRA pair to 227 // sign extend a small value in a large integer register (e.g. sign 228 // extending the low 8 bits of a 32-bit register to fill the top 24 bits 229 // with the 7th bit). The size of the smaller type is indicated by the 1th 230 // operand, a ValueType node. 231 SIGN_EXTEND_INREG, 232 233 // FP_TO_[US]INT - Convert a floating point value to a signed or unsigned 234 // integer. 235 FP_TO_SINT, 236 FP_TO_UINT, 237 238 // FP_ROUND - Perform a rounding operation from the current 239 // precision down to the specified precision (currently always 64->32). 240 FP_ROUND, 241 242 // FP_ROUND_INREG - This operator takes a floating point register, and 243 // rounds it to a floating point value. It then promotes it and returns it 244 // in a register of the same size. This operation effectively just discards 245 // excess precision. The type to round down to is specified by the 1th 246 // operation, a VTSDNode (currently always 64->32->64). 247 FP_ROUND_INREG, 248 249 // FP_EXTEND - Extend a smaller FP type into a larger FP type. 250 FP_EXTEND, 251 252 // BIT_CONVERT - Theis operator converts between integer and FP values, as 253 // if one was stored to memory as integer and the other was loaded from the 254 // same address (or equivalently for vector format conversions, etc). The 255 // source and result are required to have the same bit size (e.g. 256 // f32 <-> i32). This can also be used for int-to-int or fp-to-fp 257 // conversions, but that is a noop, deleted by getNode(). 258 BIT_CONVERT, 259 260 // FNEG, FABS, FSQRT, FSIN, FCOS - Perform unary floating point negation, 261 // absolute value, square root, sine and cosine operations. 262 FNEG, FABS, FSQRT, FSIN, FCOS, 263 264 // Other operators. LOAD and STORE have token chains as their first 265 // operand, then the same operands as an LLVM load/store instruction, then a 266 // SRCVALUE node that provides alias analysis information. 267 LOAD, STORE, 268 269 // Abstract vector version of LOAD. VLOAD has a constant element count as 270 // the first operand, followed by a value type node indicating the type of 271 // the elements, a token chain, a pointer operand, and a SRCVALUE node. 272 VLOAD, 273 274 // EXTLOAD, SEXTLOAD, ZEXTLOAD - These three operators all load a value from 275 // memory and extend them to a larger value (e.g. load a byte into a word 276 // register). All three of these have four operands, a token chain, a 277 // pointer to load from, a SRCVALUE for alias analysis, and a VALUETYPE node 278 // indicating the type to load. 279 // 280 // SEXTLOAD loads the integer operand and sign extends it to a larger 281 // integer result type. 282 // ZEXTLOAD loads the integer operand and zero extends it to a larger 283 // integer result type. 284 // EXTLOAD is used for two things: floating point extending loads, and 285 // integer extending loads where it doesn't matter what the high 286 // bits are set to. The code generator is allowed to codegen this 287 // into whichever operation is more efficient. 288 EXTLOAD, SEXTLOAD, ZEXTLOAD, 289 290 // TRUNCSTORE - This operators truncates (for integer) or rounds (for FP) a 291 // value and stores it to memory in one operation. This can be used for 292 // either integer or floating point operands. The first four operands of 293 // this are the same as a standard store. The fifth is the ValueType to 294 // store it as (which will be smaller than the source value). 295 TRUNCSTORE, 296 297 // DYNAMIC_STACKALLOC - Allocate some number of bytes on the stack aligned 298 // to a specified boundary. The first operand is the token chain, the 299 // second is the number of bytes to allocate, and the third is the alignment 300 // boundary. The size is guaranteed to be a multiple of the stack 301 // alignment, and the alignment is guaranteed to be bigger than the stack 302 // alignment (if required) or 0 to get standard stack alignment. 303 DYNAMIC_STACKALLOC, 304 305 // Control flow instructions. These all have token chains. 306 307 // BR - Unconditional branch. The first operand is the chain 308 // operand, the second is the MBB to branch to. 309 BR, 310 311 // BRCOND - Conditional branch. The first operand is the chain, 312 // the second is the condition, the third is the block to branch 313 // to if the condition is true. 314 BRCOND, 315 316 // BR_CC - Conditional branch. The behavior is like that of SELECT_CC, in 317 // that the condition is represented as condition code, and two nodes to 318 // compare, rather than as a combined SetCC node. The operands in order are 319 // chain, cc, lhs, rhs, block to branch to if condition is true. 320 BR_CC, 321 322 // RET - Return from function. The first operand is the chain, 323 // and any subsequent operands are the return values for the 324 // function. This operation can have variable number of operands. 325 RET, 326 327 // INLINEASM - Represents an inline asm block. This node always has two 328 // return values: a chain and a flag result. The inputs are as follows: 329 // Operand #0 : Input chain. 330 // Operand #1 : a ExternalSymbolSDNode with a pointer to the asm string. 331 // Operand #2n+2: A RegisterNode. 332 // Operand #2n+3: A TargetConstant, indicating if the reg is a use/def 333 // Operand #last: Optional, an incoming flag. 334 INLINEASM, 335 336 // STACKSAVE - STACKSAVE has one operand, an input chain. It produces a 337 // value, the same type as the pointer type for the system, and an output 338 // chain. 339 STACKSAVE, 340 341 // STACKRESTORE has two operands, an input chain and a pointer to restore to 342 // it returns an output chain. 343 STACKRESTORE, 344 345 // MEMSET/MEMCPY/MEMMOVE - The first operand is the chain, and the rest 346 // correspond to the operands of the LLVM intrinsic functions. The only 347 // result is a token chain. The alignment argument is guaranteed to be a 348 // Constant node. 349 MEMSET, 350 MEMMOVE, 351 MEMCPY, 352 353 // CALLSEQ_START/CALLSEQ_END - These operators mark the beginning and end of 354 // a call sequence, and carry arbitrary information that target might want 355 // to know. The first operand is a chain, the rest are specified by the 356 // target and not touched by the DAG optimizers. 357 CALLSEQ_START, // Beginning of a call sequence 358 CALLSEQ_END, // End of a call sequence 359 360 // VAARG - VAARG has three operands: an input chain, a pointer, and a 361 // SRCVALUE. It returns a pair of values: the vaarg value and a new chain. 362 VAARG, 363 364 // VACOPY - VACOPY has five operands: an input chain, a destination pointer, 365 // a source pointer, a SRCVALUE for the destination, and a SRCVALUE for the 366 // source. 367 VACOPY, 368 369 // VAEND, VASTART - VAEND and VASTART have three operands: an input chain, a 370 // pointer, and a SRCVALUE. 371 VAEND, VASTART, 372 373 // SRCVALUE - This corresponds to a Value*, and is used to associate memory 374 // locations with their value. This allows one use alias analysis 375 // information in the backend. 376 SRCVALUE, 377 378 // PCMARKER - This corresponds to the pcmarker intrinsic. 379 PCMARKER, 380 381 // READCYCLECOUNTER - This corresponds to the readcyclecounter intrinsic. 382 // The only operand is a chain and a value and a chain are produced. The 383 // value is the contents of the architecture specific cycle counter like 384 // register (or other high accuracy low latency clock source) 385 READCYCLECOUNTER, 386 387 // HANDLENODE node - Used as a handle for various purposes. 388 HANDLENODE, 389 390 // LOCATION - This node is used to represent a source location for debug 391 // info. It takes token chain as input, then a line number, then a column 392 // number, then a filename, then a working dir. It produces a token chain 393 // as output. 394 LOCATION, 395 396 // DEBUG_LOC - This node is used to represent source line information 397 // embedded in the code. It takes a token chain as input, then a line 398 // number, then a column then a file id (provided by MachineDebugInfo.) It 399 // produces a token chain as output. 400 DEBUG_LOC, 401 402 // DEBUG_LABEL - This node is used to mark a location in the code where a 403 // label should be generated for use by the debug information. It takes a 404 // token chain as input and then a unique id (provided by MachineDebugInfo.) 405 // It produces a token chain as output. 406 DEBUG_LABEL, 407 408 // BUILTIN_OP_END - This must be the last enum value in this list. 409 BUILTIN_OP_END 410 }; 411 412 //===--------------------------------------------------------------------===// 413 /// ISD::CondCode enum - These are ordered carefully to make the bitfields 414 /// below work out, when considering SETFALSE (something that never exists 415 /// dynamically) as 0. "U" -> Unsigned (for integer operands) or Unordered 416 /// (for floating point), "L" -> Less than, "G" -> Greater than, "E" -> Equal 417 /// to. If the "N" column is 1, the result of the comparison is undefined if 418 /// the input is a NAN. 419 /// 420 /// All of these (except for the 'always folded ops') should be handled for 421 /// floating point. For integer, only the SETEQ,SETNE,SETLT,SETLE,SETGT, 422 /// SETGE,SETULT,SETULE,SETUGT, and SETUGE opcodes are used. 423 /// 424 /// Note that these are laid out in a specific order to allow bit-twiddling 425 /// to transform conditions. 426 enum CondCode { 427 // Opcode N U L G E Intuitive operation 428 SETFALSE, // 0 0 0 0 Always false (always folded) 429 SETOEQ, // 0 0 0 1 True if ordered and equal 430 SETOGT, // 0 0 1 0 True if ordered and greater than 431 SETOGE, // 0 0 1 1 True if ordered and greater than or equal 432 SETOLT, // 0 1 0 0 True if ordered and less than 433 SETOLE, // 0 1 0 1 True if ordered and less than or equal 434 SETONE, // 0 1 1 0 True if ordered and operands are unequal 435 SETO, // 0 1 1 1 True if ordered (no nans) 436 SETUO, // 1 0 0 0 True if unordered: isnan(X) | isnan(Y) 437 SETUEQ, // 1 0 0 1 True if unordered or equal 438 SETUGT, // 1 0 1 0 True if unordered or greater than 439 SETUGE, // 1 0 1 1 True if unordered, greater than, or equal 440 SETULT, // 1 1 0 0 True if unordered or less than 441 SETULE, // 1 1 0 1 True if unordered, less than, or equal 442 SETUNE, // 1 1 1 0 True if unordered or not equal 443 SETTRUE, // 1 1 1 1 Always true (always folded) 444 // Don't care operations: undefined if the input is a nan. 445 SETFALSE2, // 1 X 0 0 0 Always false (always folded) 446 SETEQ, // 1 X 0 0 1 True if equal 447 SETGT, // 1 X 0 1 0 True if greater than 448 SETGE, // 1 X 0 1 1 True if greater than or equal 449 SETLT, // 1 X 1 0 0 True if less than 450 SETLE, // 1 X 1 0 1 True if less than or equal 451 SETNE, // 1 X 1 1 0 True if not equal 452 SETTRUE2, // 1 X 1 1 1 Always true (always folded) 453 454 SETCC_INVALID // Marker value. 455 }; 456 457 /// isSignedIntSetCC - Return true if this is a setcc instruction that 458 /// performs a signed comparison when used with integer operands. 459 inline bool isSignedIntSetCC(CondCode Code) { 460 return Code == SETGT || Code == SETGE || Code == SETLT || Code == SETLE; 461 } 462 463 /// isUnsignedIntSetCC - Return true if this is a setcc instruction that 464 /// performs an unsigned comparison when used with integer operands. 465 inline bool isUnsignedIntSetCC(CondCode Code) { 466 return Code == SETUGT || Code == SETUGE || Code == SETULT || Code == SETULE; 467 } 468 469 /// isTrueWhenEqual - Return true if the specified condition returns true if 470 /// the two operands to the condition are equal. Note that if one of the two 471 /// operands is a NaN, this value is meaningless. 472 inline bool isTrueWhenEqual(CondCode Cond) { 473 return ((int)Cond & 1) != 0; 474 } 475 476 /// getUnorderedFlavor - This function returns 0 if the condition is always 477 /// false if an operand is a NaN, 1 if the condition is always true if the 478 /// operand is a NaN, and 2 if the condition is undefined if the operand is a 479 /// NaN. 480 inline unsigned getUnorderedFlavor(CondCode Cond) { 481 return ((int)Cond >> 3) & 3; 482 } 483 484 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where 485 /// 'op' is a valid SetCC operation. 486 CondCode getSetCCInverse(CondCode Operation, bool isInteger); 487 488 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 489 /// when given the operation for (X op Y). 490 CondCode getSetCCSwappedOperands(CondCode Operation); 491 492 /// getSetCCOrOperation - Return the result of a logical OR between different 493 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This 494 /// function returns SETCC_INVALID if it is not possible to represent the 495 /// resultant comparison. 496 CondCode getSetCCOrOperation(CondCode Op1, CondCode Op2, bool isInteger); 497 498 /// getSetCCAndOperation - Return the result of a logical AND between 499 /// different comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 500 /// function returns SETCC_INVALID if it is not possible to represent the 501 /// resultant comparison. 502 CondCode getSetCCAndOperation(CondCode Op1, CondCode Op2, bool isInteger); 503} // end llvm::ISD namespace 504 505 506//===----------------------------------------------------------------------===// 507/// SDOperand - Unlike LLVM values, Selection DAG nodes may return multiple 508/// values as the result of a computation. Many nodes return multiple values, 509/// from loads (which define a token and a return value) to ADDC (which returns 510/// a result and a carry value), to calls (which may return an arbitrary number 511/// of values). 512/// 513/// As such, each use of a SelectionDAG computation must indicate the node that 514/// computes it as well as which return value to use from that node. This pair 515/// of information is represented with the SDOperand value type. 516/// 517class SDOperand { 518public: 519 SDNode *Val; // The node defining the value we are using. 520 unsigned ResNo; // Which return value of the node we are using. 521 522 SDOperand() : Val(0) {} 523 SDOperand(SDNode *val, unsigned resno) : Val(val), ResNo(resno) {} 524 525 bool operator==(const SDOperand &O) const { 526 return Val == O.Val && ResNo == O.ResNo; 527 } 528 bool operator!=(const SDOperand &O) const { 529 return !operator==(O); 530 } 531 bool operator<(const SDOperand &O) const { 532 return Val < O.Val || (Val == O.Val && ResNo < O.ResNo); 533 } 534 535 SDOperand getValue(unsigned R) const { 536 return SDOperand(Val, R); 537 } 538 539 // isOperand - Return true if this node is an operand of N. 540 bool isOperand(SDNode *N) const; 541 542 /// getValueType - Return the ValueType of the referenced return value. 543 /// 544 inline MVT::ValueType getValueType() const; 545 546 // Forwarding methods - These forward to the corresponding methods in SDNode. 547 inline unsigned getOpcode() const; 548 inline unsigned getNodeDepth() const; 549 inline unsigned getNumOperands() const; 550 inline const SDOperand &getOperand(unsigned i) const; 551 inline bool isTargetOpcode() const; 552 inline unsigned getTargetOpcode() const; 553 554 /// hasOneUse - Return true if there is exactly one operation using this 555 /// result value of the defining operator. 556 inline bool hasOneUse() const; 557}; 558 559 560/// simplify_type specializations - Allow casting operators to work directly on 561/// SDOperands as if they were SDNode*'s. 562template<> struct simplify_type<SDOperand> { 563 typedef SDNode* SimpleType; 564 static SimpleType getSimplifiedValue(const SDOperand &Val) { 565 return static_cast<SimpleType>(Val.Val); 566 } 567}; 568template<> struct simplify_type<const SDOperand> { 569 typedef SDNode* SimpleType; 570 static SimpleType getSimplifiedValue(const SDOperand &Val) { 571 return static_cast<SimpleType>(Val.Val); 572 } 573}; 574 575 576/// SDNode - Represents one node in the SelectionDAG. 577/// 578class SDNode { 579 /// NodeType - The operation that this node performs. 580 /// 581 unsigned short NodeType; 582 583 /// NodeDepth - Node depth is defined as MAX(Node depth of children)+1. This 584 /// means that leaves have a depth of 1, things that use only leaves have a 585 /// depth of 2, etc. 586 unsigned short NodeDepth; 587 588 /// OperandList - The values that are used by this operation. 589 /// 590 SDOperand *OperandList; 591 592 /// ValueList - The types of the values this node defines. SDNode's may 593 /// define multiple values simultaneously. 594 MVT::ValueType *ValueList; 595 596 /// NumOperands/NumValues - The number of entries in the Operand/Value list. 597 unsigned short NumOperands, NumValues; 598 599 /// Prev/Next pointers - These pointers form the linked list of of the 600 /// AllNodes list in the current DAG. 601 SDNode *Prev, *Next; 602 friend struct ilist_traits<SDNode>; 603 604 /// Uses - These are all of the SDNode's that use a value produced by this 605 /// node. 606 std::vector<SDNode*> Uses; 607public: 608 virtual ~SDNode() { 609 assert(NumOperands == 0 && "Operand list not cleared before deletion"); 610 } 611 612 //===--------------------------------------------------------------------===// 613 // Accessors 614 // 615 unsigned getOpcode() const { return NodeType; } 616 bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; } 617 unsigned getTargetOpcode() const { 618 assert(isTargetOpcode() && "Not a target opcode!"); 619 return NodeType - ISD::BUILTIN_OP_END; 620 } 621 622 size_t use_size() const { return Uses.size(); } 623 bool use_empty() const { return Uses.empty(); } 624 bool hasOneUse() const { return Uses.size() == 1; } 625 626 /// getNodeDepth - Return the distance from this node to the leaves in the 627 /// graph. The leaves have a depth of 1. 628 unsigned getNodeDepth() const { return NodeDepth; } 629 630 typedef std::vector<SDNode*>::const_iterator use_iterator; 631 use_iterator use_begin() const { return Uses.begin(); } 632 use_iterator use_end() const { return Uses.end(); } 633 634 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 635 /// indicated value. This method ignores uses of other values defined by this 636 /// operation. 637 bool hasNUsesOfValue(unsigned NUses, unsigned Value) const; 638 639 // isOnlyUse - Return true if this node is the only use of N. 640 bool isOnlyUse(SDNode *N) const; 641 642 // isOperand - Return true if this node is an operand of N. 643 bool isOperand(SDNode *N) const; 644 645 /// getNumOperands - Return the number of values used by this operation. 646 /// 647 unsigned getNumOperands() const { return NumOperands; } 648 649 const SDOperand &getOperand(unsigned Num) const { 650 assert(Num < NumOperands && "Invalid child # of SDNode!"); 651 return OperandList[Num]; 652 } 653 typedef const SDOperand* op_iterator; 654 op_iterator op_begin() const { return OperandList; } 655 op_iterator op_end() const { return OperandList+NumOperands; } 656 657 658 /// getNumValues - Return the number of values defined/returned by this 659 /// operator. 660 /// 661 unsigned getNumValues() const { return NumValues; } 662 663 /// getValueType - Return the type of a specified result. 664 /// 665 MVT::ValueType getValueType(unsigned ResNo) const { 666 assert(ResNo < NumValues && "Illegal result number!"); 667 return ValueList[ResNo]; 668 } 669 670 typedef const MVT::ValueType* value_iterator; 671 value_iterator value_begin() const { return ValueList; } 672 value_iterator value_end() const { return ValueList+NumValues; } 673 674 /// getOperationName - Return the opcode of this operation for printing. 675 /// 676 const char* getOperationName(const SelectionDAG *G = 0) const; 677 void dump() const; 678 void dump(const SelectionDAG *G) const; 679 680 static bool classof(const SDNode *) { return true; } 681 682protected: 683 friend class SelectionDAG; 684 685 /// getValueTypeList - Return a pointer to the specified value type. 686 /// 687 static MVT::ValueType *getValueTypeList(MVT::ValueType VT); 688 689 SDNode(unsigned NT, MVT::ValueType VT) : NodeType(NT), NodeDepth(1) { 690 OperandList = 0; NumOperands = 0; 691 ValueList = getValueTypeList(VT); 692 NumValues = 1; 693 Prev = 0; Next = 0; 694 } 695 SDNode(unsigned NT, SDOperand Op) 696 : NodeType(NT), NodeDepth(Op.Val->getNodeDepth()+1) { 697 OperandList = new SDOperand[1]; 698 OperandList[0] = Op; 699 NumOperands = 1; 700 Op.Val->Uses.push_back(this); 701 ValueList = 0; 702 NumValues = 0; 703 Prev = 0; Next = 0; 704 } 705 SDNode(unsigned NT, SDOperand N1, SDOperand N2) 706 : NodeType(NT) { 707 if (N1.Val->getNodeDepth() > N2.Val->getNodeDepth()) 708 NodeDepth = N1.Val->getNodeDepth()+1; 709 else 710 NodeDepth = N2.Val->getNodeDepth()+1; 711 OperandList = new SDOperand[2]; 712 OperandList[0] = N1; 713 OperandList[1] = N2; 714 NumOperands = 2; 715 N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); 716 ValueList = 0; 717 NumValues = 0; 718 Prev = 0; Next = 0; 719 } 720 SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3) 721 : NodeType(NT) { 722 unsigned ND = N1.Val->getNodeDepth(); 723 if (ND < N2.Val->getNodeDepth()) 724 ND = N2.Val->getNodeDepth(); 725 if (ND < N3.Val->getNodeDepth()) 726 ND = N3.Val->getNodeDepth(); 727 NodeDepth = ND+1; 728 729 OperandList = new SDOperand[3]; 730 OperandList[0] = N1; 731 OperandList[1] = N2; 732 OperandList[2] = N3; 733 NumOperands = 3; 734 735 N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); 736 N3.Val->Uses.push_back(this); 737 ValueList = 0; 738 NumValues = 0; 739 Prev = 0; Next = 0; 740 } 741 SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4) 742 : NodeType(NT) { 743 unsigned ND = N1.Val->getNodeDepth(); 744 if (ND < N2.Val->getNodeDepth()) 745 ND = N2.Val->getNodeDepth(); 746 if (ND < N3.Val->getNodeDepth()) 747 ND = N3.Val->getNodeDepth(); 748 if (ND < N4.Val->getNodeDepth()) 749 ND = N4.Val->getNodeDepth(); 750 NodeDepth = ND+1; 751 752 OperandList = new SDOperand[4]; 753 OperandList[0] = N1; 754 OperandList[1] = N2; 755 OperandList[2] = N3; 756 OperandList[3] = N4; 757 NumOperands = 4; 758 759 N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); 760 N3.Val->Uses.push_back(this); N4.Val->Uses.push_back(this); 761 ValueList = 0; 762 NumValues = 0; 763 Prev = 0; Next = 0; 764 } 765 SDNode(unsigned Opc, const std::vector<SDOperand> &Nodes) : NodeType(Opc) { 766 NumOperands = Nodes.size(); 767 OperandList = new SDOperand[NumOperands]; 768 769 unsigned ND = 0; 770 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 771 OperandList[i] = Nodes[i]; 772 SDNode *N = OperandList[i].Val; 773 N->Uses.push_back(this); 774 if (ND < N->getNodeDepth()) ND = N->getNodeDepth(); 775 } 776 NodeDepth = ND+1; 777 ValueList = 0; 778 NumValues = 0; 779 Prev = 0; Next = 0; 780 } 781 782 /// MorphNodeTo - This clears the return value and operands list, and sets the 783 /// opcode of the node to the specified value. This should only be used by 784 /// the SelectionDAG class. 785 void MorphNodeTo(unsigned Opc) { 786 NodeType = Opc; 787 ValueList = 0; 788 NumValues = 0; 789 790 // Clear the operands list, updating used nodes to remove this from their 791 // use list. 792 for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) 793 I->Val->removeUser(this); 794 delete [] OperandList; 795 OperandList = 0; 796 NumOperands = 0; 797 } 798 799 void setValueTypes(MVT::ValueType VT) { 800 assert(NumValues == 0 && "Should not have values yet!"); 801 ValueList = getValueTypeList(VT); 802 NumValues = 1; 803 } 804 void setValueTypes(MVT::ValueType *List, unsigned NumVal) { 805 assert(NumValues == 0 && "Should not have values yet!"); 806 ValueList = List; 807 NumValues = NumVal; 808 } 809 810 void setOperands(SDOperand Op0) { 811 assert(NumOperands == 0 && "Should not have operands yet!"); 812 OperandList = new SDOperand[1]; 813 OperandList[0] = Op0; 814 NumOperands = 1; 815 Op0.Val->Uses.push_back(this); 816 } 817 void setOperands(SDOperand Op0, SDOperand Op1) { 818 assert(NumOperands == 0 && "Should not have operands yet!"); 819 OperandList = new SDOperand[2]; 820 OperandList[0] = Op0; 821 OperandList[1] = Op1; 822 NumOperands = 2; 823 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 824 } 825 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2) { 826 assert(NumOperands == 0 && "Should not have operands yet!"); 827 OperandList = new SDOperand[3]; 828 OperandList[0] = Op0; 829 OperandList[1] = Op1; 830 OperandList[2] = Op2; 831 NumOperands = 3; 832 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 833 Op2.Val->Uses.push_back(this); 834 } 835 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3) { 836 assert(NumOperands == 0 && "Should not have operands yet!"); 837 OperandList = new SDOperand[4]; 838 OperandList[0] = Op0; 839 OperandList[1] = Op1; 840 OperandList[2] = Op2; 841 OperandList[3] = Op3; 842 NumOperands = 4; 843 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 844 Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); 845 } 846 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3, 847 SDOperand Op4) { 848 assert(NumOperands == 0 && "Should not have operands yet!"); 849 OperandList = new SDOperand[5]; 850 OperandList[0] = Op0; 851 OperandList[1] = Op1; 852 OperandList[2] = Op2; 853 OperandList[3] = Op3; 854 OperandList[4] = Op4; 855 NumOperands = 5; 856 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 857 Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); 858 Op4.Val->Uses.push_back(this); 859 } 860 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3, 861 SDOperand Op4, SDOperand Op5) { 862 assert(NumOperands == 0 && "Should not have operands yet!"); 863 OperandList = new SDOperand[6]; 864 OperandList[0] = Op0; 865 OperandList[1] = Op1; 866 OperandList[2] = Op2; 867 OperandList[3] = Op3; 868 OperandList[4] = Op4; 869 OperandList[5] = Op5; 870 NumOperands = 6; 871 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 872 Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); 873 Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this); 874 } 875 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3, 876 SDOperand Op4, SDOperand Op5, SDOperand Op6) { 877 assert(NumOperands == 0 && "Should not have operands yet!"); 878 OperandList = new SDOperand[7]; 879 OperandList[0] = Op0; 880 OperandList[1] = Op1; 881 OperandList[2] = Op2; 882 OperandList[3] = Op3; 883 OperandList[4] = Op4; 884 OperandList[5] = Op5; 885 OperandList[6] = Op6; 886 NumOperands = 7; 887 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 888 Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); 889 Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this); 890 Op6.Val->Uses.push_back(this); 891 } 892 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3, 893 SDOperand Op4, SDOperand Op5, SDOperand Op6, SDOperand Op7) { 894 assert(NumOperands == 0 && "Should not have operands yet!"); 895 OperandList = new SDOperand[8]; 896 OperandList[0] = Op0; 897 OperandList[1] = Op1; 898 OperandList[2] = Op2; 899 OperandList[3] = Op3; 900 OperandList[4] = Op4; 901 OperandList[5] = Op5; 902 OperandList[6] = Op6; 903 OperandList[7] = Op7; 904 NumOperands = 8; 905 Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); 906 Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); 907 Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this); 908 Op6.Val->Uses.push_back(this); Op7.Val->Uses.push_back(this); 909 } 910 911 void addUser(SDNode *User) { 912 Uses.push_back(User); 913 } 914 void removeUser(SDNode *User) { 915 // Remove this user from the operand's use list. 916 for (unsigned i = Uses.size(); ; --i) { 917 assert(i != 0 && "Didn't find user!"); 918 if (Uses[i-1] == User) { 919 Uses[i-1] = Uses.back(); 920 Uses.pop_back(); 921 return; 922 } 923 } 924 } 925}; 926 927 928// Define inline functions from the SDOperand class. 929 930inline unsigned SDOperand::getOpcode() const { 931 return Val->getOpcode(); 932} 933inline unsigned SDOperand::getNodeDepth() const { 934 return Val->getNodeDepth(); 935} 936inline MVT::ValueType SDOperand::getValueType() const { 937 return Val->getValueType(ResNo); 938} 939inline unsigned SDOperand::getNumOperands() const { 940 return Val->getNumOperands(); 941} 942inline const SDOperand &SDOperand::getOperand(unsigned i) const { 943 return Val->getOperand(i); 944} 945inline bool SDOperand::isTargetOpcode() const { 946 return Val->isTargetOpcode(); 947} 948inline unsigned SDOperand::getTargetOpcode() const { 949 return Val->getTargetOpcode(); 950} 951inline bool SDOperand::hasOneUse() const { 952 return Val->hasNUsesOfValue(1, ResNo); 953} 954 955/// HandleSDNode - This class is used to form a handle around another node that 956/// is persistant and is updated across invocations of replaceAllUsesWith on its 957/// operand. This node should be directly created by end-users and not added to 958/// the AllNodes list. 959class HandleSDNode : public SDNode { 960public: 961 HandleSDNode(SDOperand X) : SDNode(ISD::HANDLENODE, X) {} 962 ~HandleSDNode() { 963 MorphNodeTo(ISD::HANDLENODE); // Drops operand uses. 964 } 965 966 SDOperand getValue() const { return getOperand(0); } 967}; 968 969class StringSDNode : public SDNode { 970 std::string Value; 971protected: 972 friend class SelectionDAG; 973 StringSDNode(const std::string &val) 974 : SDNode(ISD::STRING, MVT::Other), Value(val) { 975 } 976public: 977 const std::string &getValue() const { return Value; } 978 static bool classof(const StringSDNode *) { return true; } 979 static bool classof(const SDNode *N) { 980 return N->getOpcode() == ISD::STRING; 981 } 982}; 983 984class ConstantSDNode : public SDNode { 985 uint64_t Value; 986protected: 987 friend class SelectionDAG; 988 ConstantSDNode(bool isTarget, uint64_t val, MVT::ValueType VT) 989 : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, VT), Value(val) { 990 } 991public: 992 993 uint64_t getValue() const { return Value; } 994 995 int64_t getSignExtended() const { 996 unsigned Bits = MVT::getSizeInBits(getValueType(0)); 997 return ((int64_t)Value << (64-Bits)) >> (64-Bits); 998 } 999 1000 bool isNullValue() const { return Value == 0; } 1001 bool isAllOnesValue() const { 1002 int NumBits = MVT::getSizeInBits(getValueType(0)); 1003 if (NumBits == 64) return Value+1 == 0; 1004 return Value == (1ULL << NumBits)-1; 1005 } 1006 1007 static bool classof(const ConstantSDNode *) { return true; } 1008 static bool classof(const SDNode *N) { 1009 return N->getOpcode() == ISD::Constant || 1010 N->getOpcode() == ISD::TargetConstant; 1011 } 1012}; 1013 1014class ConstantFPSDNode : public SDNode { 1015 double Value; 1016protected: 1017 friend class SelectionDAG; 1018 ConstantFPSDNode(bool isTarget, double val, MVT::ValueType VT) 1019 : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP, VT), 1020 Value(val) { 1021 } 1022public: 1023 1024 double getValue() const { return Value; } 1025 1026 /// isExactlyValue - We don't rely on operator== working on double values, as 1027 /// it returns true for things that are clearly not equal, like -0.0 and 0.0. 1028 /// As such, this method can be used to do an exact bit-for-bit comparison of 1029 /// two floating point values. 1030 bool isExactlyValue(double V) const; 1031 1032 static bool classof(const ConstantFPSDNode *) { return true; } 1033 static bool classof(const SDNode *N) { 1034 return N->getOpcode() == ISD::ConstantFP || 1035 N->getOpcode() == ISD::TargetConstantFP; 1036 } 1037}; 1038 1039class GlobalAddressSDNode : public SDNode { 1040 GlobalValue *TheGlobal; 1041 int Offset; 1042protected: 1043 friend class SelectionDAG; 1044 GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, MVT::ValueType VT, 1045 int o=0) 1046 : SDNode(isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress, VT), 1047 Offset(o) { 1048 TheGlobal = const_cast<GlobalValue*>(GA); 1049 } 1050public: 1051 1052 GlobalValue *getGlobal() const { return TheGlobal; } 1053 int getOffset() const { return Offset; } 1054 1055 static bool classof(const GlobalAddressSDNode *) { return true; } 1056 static bool classof(const SDNode *N) { 1057 return N->getOpcode() == ISD::GlobalAddress || 1058 N->getOpcode() == ISD::TargetGlobalAddress; 1059 } 1060}; 1061 1062 1063class FrameIndexSDNode : public SDNode { 1064 int FI; 1065protected: 1066 friend class SelectionDAG; 1067 FrameIndexSDNode(int fi, MVT::ValueType VT, bool isTarg) 1068 : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex, VT), FI(fi) {} 1069public: 1070 1071 int getIndex() const { return FI; } 1072 1073 static bool classof(const FrameIndexSDNode *) { return true; } 1074 static bool classof(const SDNode *N) { 1075 return N->getOpcode() == ISD::FrameIndex || 1076 N->getOpcode() == ISD::TargetFrameIndex; 1077 } 1078}; 1079 1080class ConstantPoolSDNode : public SDNode { 1081 Constant *C; 1082 int Offset; 1083 unsigned Alignment; 1084protected: 1085 friend class SelectionDAG; 1086 ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT, 1087 int o=0) 1088 : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT), 1089 C(c), Offset(o), Alignment(0) {} 1090 ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT, int o, 1091 unsigned Align) 1092 : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT), 1093 C(c), Offset(o), Alignment(Align) {} 1094public: 1095 1096 Constant *get() const { return C; } 1097 int getOffset() const { return Offset; } 1098 1099 // Return the alignment of this constant pool object, which is either 0 (for 1100 // default alignment) or log2 of the desired value. 1101 unsigned getAlignment() const { return Alignment; } 1102 1103 static bool classof(const ConstantPoolSDNode *) { return true; } 1104 static bool classof(const SDNode *N) { 1105 return N->getOpcode() == ISD::ConstantPool || 1106 N->getOpcode() == ISD::TargetConstantPool; 1107 } 1108}; 1109 1110class BasicBlockSDNode : public SDNode { 1111 MachineBasicBlock *MBB; 1112protected: 1113 friend class SelectionDAG; 1114 BasicBlockSDNode(MachineBasicBlock *mbb) 1115 : SDNode(ISD::BasicBlock, MVT::Other), MBB(mbb) {} 1116public: 1117 1118 MachineBasicBlock *getBasicBlock() const { return MBB; } 1119 1120 static bool classof(const BasicBlockSDNode *) { return true; } 1121 static bool classof(const SDNode *N) { 1122 return N->getOpcode() == ISD::BasicBlock; 1123 } 1124}; 1125 1126class SrcValueSDNode : public SDNode { 1127 const Value *V; 1128 int offset; 1129protected: 1130 friend class SelectionDAG; 1131 SrcValueSDNode(const Value* v, int o) 1132 : SDNode(ISD::SRCVALUE, MVT::Other), V(v), offset(o) {} 1133 1134public: 1135 const Value *getValue() const { return V; } 1136 int getOffset() const { return offset; } 1137 1138 static bool classof(const SrcValueSDNode *) { return true; } 1139 static bool classof(const SDNode *N) { 1140 return N->getOpcode() == ISD::SRCVALUE; 1141 } 1142}; 1143 1144 1145class RegisterSDNode : public SDNode { 1146 unsigned Reg; 1147protected: 1148 friend class SelectionDAG; 1149 RegisterSDNode(unsigned reg, MVT::ValueType VT) 1150 : SDNode(ISD::Register, VT), Reg(reg) {} 1151public: 1152 1153 unsigned getReg() const { return Reg; } 1154 1155 static bool classof(const RegisterSDNode *) { return true; } 1156 static bool classof(const SDNode *N) { 1157 return N->getOpcode() == ISD::Register; 1158 } 1159}; 1160 1161class ExternalSymbolSDNode : public SDNode { 1162 const char *Symbol; 1163protected: 1164 friend class SelectionDAG; 1165 ExternalSymbolSDNode(bool isTarget, const char *Sym, MVT::ValueType VT) 1166 : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol, VT), 1167 Symbol(Sym) { 1168 } 1169public: 1170 1171 const char *getSymbol() const { return Symbol; } 1172 1173 static bool classof(const ExternalSymbolSDNode *) { return true; } 1174 static bool classof(const SDNode *N) { 1175 return N->getOpcode() == ISD::ExternalSymbol || 1176 N->getOpcode() == ISD::TargetExternalSymbol; 1177 } 1178}; 1179 1180class CondCodeSDNode : public SDNode { 1181 ISD::CondCode Condition; 1182protected: 1183 friend class SelectionDAG; 1184 CondCodeSDNode(ISD::CondCode Cond) 1185 : SDNode(ISD::CONDCODE, MVT::Other), Condition(Cond) { 1186 } 1187public: 1188 1189 ISD::CondCode get() const { return Condition; } 1190 1191 static bool classof(const CondCodeSDNode *) { return true; } 1192 static bool classof(const SDNode *N) { 1193 return N->getOpcode() == ISD::CONDCODE; 1194 } 1195}; 1196 1197/// VTSDNode - This class is used to represent MVT::ValueType's, which are used 1198/// to parameterize some operations. 1199class VTSDNode : public SDNode { 1200 MVT::ValueType ValueType; 1201protected: 1202 friend class SelectionDAG; 1203 VTSDNode(MVT::ValueType VT) 1204 : SDNode(ISD::VALUETYPE, MVT::Other), ValueType(VT) {} 1205public: 1206 1207 MVT::ValueType getVT() const { return ValueType; } 1208 1209 static bool classof(const VTSDNode *) { return true; } 1210 static bool classof(const SDNode *N) { 1211 return N->getOpcode() == ISD::VALUETYPE; 1212 } 1213}; 1214 1215 1216class SDNodeIterator : public forward_iterator<SDNode, ptrdiff_t> { 1217 SDNode *Node; 1218 unsigned Operand; 1219 1220 SDNodeIterator(SDNode *N, unsigned Op) : Node(N), Operand(Op) {} 1221public: 1222 bool operator==(const SDNodeIterator& x) const { 1223 return Operand == x.Operand; 1224 } 1225 bool operator!=(const SDNodeIterator& x) const { return !operator==(x); } 1226 1227 const SDNodeIterator &operator=(const SDNodeIterator &I) { 1228 assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); 1229 Operand = I.Operand; 1230 return *this; 1231 } 1232 1233 pointer operator*() const { 1234 return Node->getOperand(Operand).Val; 1235 } 1236 pointer operator->() const { return operator*(); } 1237 1238 SDNodeIterator& operator++() { // Preincrement 1239 ++Operand; 1240 return *this; 1241 } 1242 SDNodeIterator operator++(int) { // Postincrement 1243 SDNodeIterator tmp = *this; ++*this; return tmp; 1244 } 1245 1246 static SDNodeIterator begin(SDNode *N) { return SDNodeIterator(N, 0); } 1247 static SDNodeIterator end (SDNode *N) { 1248 return SDNodeIterator(N, N->getNumOperands()); 1249 } 1250 1251 unsigned getOperand() const { return Operand; } 1252 const SDNode *getNode() const { return Node; } 1253}; 1254 1255template <> struct GraphTraits<SDNode*> { 1256 typedef SDNode NodeType; 1257 typedef SDNodeIterator ChildIteratorType; 1258 static inline NodeType *getEntryNode(SDNode *N) { return N; } 1259 static inline ChildIteratorType child_begin(NodeType *N) { 1260 return SDNodeIterator::begin(N); 1261 } 1262 static inline ChildIteratorType child_end(NodeType *N) { 1263 return SDNodeIterator::end(N); 1264 } 1265}; 1266 1267template<> 1268struct ilist_traits<SDNode> { 1269 static SDNode *getPrev(const SDNode *N) { return N->Prev; } 1270 static SDNode *getNext(const SDNode *N) { return N->Next; } 1271 1272 static void setPrev(SDNode *N, SDNode *Prev) { N->Prev = Prev; } 1273 static void setNext(SDNode *N, SDNode *Next) { N->Next = Next; } 1274 1275 static SDNode *createSentinel() { 1276 return new SDNode(ISD::EntryToken, MVT::Other); 1277 } 1278 static void destroySentinel(SDNode *N) { delete N; } 1279 //static SDNode *createNode(const SDNode &V) { return new SDNode(V); } 1280 1281 1282 void addNodeToList(SDNode *NTy) {} 1283 void removeNodeFromList(SDNode *NTy) {} 1284 void transferNodesFromList(iplist<SDNode, ilist_traits> &L2, 1285 const ilist_iterator<SDNode> &X, 1286 const ilist_iterator<SDNode> &Y) {} 1287}; 1288 1289} // end llvm namespace 1290 1291#endif 1292