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