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