SelectionDAGNodes.h revision 056f9f61d071c6c583951678f2bf543a1316efcc
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 Operands.clear(); 618 } 619 620 void setValueTypes(MVT::ValueType VT) { 621 Values.reserve(1); 622 Values.push_back(VT); 623 } 624 void setValueTypes(MVT::ValueType VT1, MVT::ValueType VT2) { 625 Values.reserve(2); 626 Values.push_back(VT1); 627 Values.push_back(VT2); 628 } 629 /// Note: this method destroys the vector passed in. 630 void setValueTypes(std::vector<MVT::ValueType> &VTs) { 631 std::swap(Values, VTs); 632 } 633 634 void setOperands(SDOperand Op0) { 635 Operands.reserve(1); 636 Operands.push_back(Op0); 637 } 638 void setOperands(SDOperand Op0, SDOperand Op1) { 639 Operands.reserve(2); 640 Operands.push_back(Op0); 641 Operands.push_back(Op1); 642 } 643 void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2) { 644 Operands.reserve(3); 645 Operands.push_back(Op0); 646 Operands.push_back(Op1); 647 Operands.push_back(Op2); 648 } 649 void removeUser(SDNode *User) { 650 // Remove this user from the operand's use list. 651 for (unsigned i = Uses.size(); ; --i) { 652 assert(i != 0 && "Didn't find user!"); 653 if (Uses[i-1] == User) { 654 Uses.erase(Uses.begin()+i-1); 655 break; 656 } 657 } 658 } 659}; 660 661 662// Define inline functions from the SDOperand class. 663 664inline unsigned SDOperand::getOpcode() const { 665 return Val->getOpcode(); 666} 667inline unsigned SDOperand::getNodeDepth() const { 668 return Val->getNodeDepth(); 669} 670inline MVT::ValueType SDOperand::getValueType() const { 671 return Val->getValueType(ResNo); 672} 673inline unsigned SDOperand::getNumOperands() const { 674 return Val->getNumOperands(); 675} 676inline const SDOperand &SDOperand::getOperand(unsigned i) const { 677 return Val->getOperand(i); 678} 679inline bool SDOperand::hasOneUse() const { 680 return Val->hasNUsesOfValue(1, ResNo); 681} 682 683 684class ConstantSDNode : public SDNode { 685 uint64_t Value; 686protected: 687 friend class SelectionDAG; 688 ConstantSDNode(bool isTarget, uint64_t val, MVT::ValueType VT) 689 : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, VT), Value(val) { 690 } 691public: 692 693 uint64_t getValue() const { return Value; } 694 695 int64_t getSignExtended() const { 696 unsigned Bits = MVT::getSizeInBits(getValueType(0)); 697 return ((int64_t)Value << (64-Bits)) >> (64-Bits); 698 } 699 700 bool isNullValue() const { return Value == 0; } 701 bool isAllOnesValue() const { 702 int NumBits = MVT::getSizeInBits(getValueType(0)); 703 if (NumBits == 64) return Value+1 == 0; 704 return Value == (1ULL << NumBits)-1; 705 } 706 707 static bool classof(const ConstantSDNode *) { return true; } 708 static bool classof(const SDNode *N) { 709 return N->getOpcode() == ISD::Constant || 710 N->getOpcode() == ISD::TargetConstant; 711 } 712}; 713 714class ConstantFPSDNode : public SDNode { 715 double Value; 716protected: 717 friend class SelectionDAG; 718 ConstantFPSDNode(double val, MVT::ValueType VT) 719 : SDNode(ISD::ConstantFP, VT), Value(val) { 720 } 721public: 722 723 double getValue() const { return Value; } 724 725 /// isExactlyValue - We don't rely on operator== working on double values, as 726 /// it returns true for things that are clearly not equal, like -0.0 and 0.0. 727 /// As such, this method can be used to do an exact bit-for-bit comparison of 728 /// two floating point values. 729 bool isExactlyValue(double V) const { 730 union { 731 double V; 732 uint64_t I; 733 } T1; 734 T1.V = Value; 735 union { 736 double V; 737 uint64_t I; 738 } T2; 739 T2.V = V; 740 return T1.I == T2.I; 741 } 742 743 static bool classof(const ConstantFPSDNode *) { return true; } 744 static bool classof(const SDNode *N) { 745 return N->getOpcode() == ISD::ConstantFP; 746 } 747}; 748 749class GlobalAddressSDNode : public SDNode { 750 GlobalValue *TheGlobal; 751protected: 752 friend class SelectionDAG; 753 GlobalAddressSDNode(const GlobalValue *GA, MVT::ValueType VT) 754 : SDNode(ISD::GlobalAddress, VT) { 755 TheGlobal = const_cast<GlobalValue*>(GA); 756 } 757public: 758 759 GlobalValue *getGlobal() const { return TheGlobal; } 760 761 static bool classof(const GlobalAddressSDNode *) { return true; } 762 static bool classof(const SDNode *N) { 763 return N->getOpcode() == ISD::GlobalAddress; 764 } 765}; 766 767 768class FrameIndexSDNode : public SDNode { 769 int FI; 770protected: 771 friend class SelectionDAG; 772 FrameIndexSDNode(int fi, MVT::ValueType VT) 773 : SDNode(ISD::FrameIndex, VT), FI(fi) {} 774public: 775 776 int getIndex() const { return FI; } 777 778 static bool classof(const FrameIndexSDNode *) { return true; } 779 static bool classof(const SDNode *N) { 780 return N->getOpcode() == ISD::FrameIndex; 781 } 782}; 783 784class ConstantPoolSDNode : public SDNode { 785 unsigned CPI; 786protected: 787 friend class SelectionDAG; 788 ConstantPoolSDNode(unsigned cpi, MVT::ValueType VT) 789 : SDNode(ISD::ConstantPool, VT), CPI(cpi) {} 790public: 791 792 unsigned getIndex() const { return CPI; } 793 794 static bool classof(const ConstantPoolSDNode *) { return true; } 795 static bool classof(const SDNode *N) { 796 return N->getOpcode() == ISD::ConstantPool; 797 } 798}; 799 800class BasicBlockSDNode : public SDNode { 801 MachineBasicBlock *MBB; 802protected: 803 friend class SelectionDAG; 804 BasicBlockSDNode(MachineBasicBlock *mbb) 805 : SDNode(ISD::BasicBlock, MVT::Other), MBB(mbb) {} 806public: 807 808 MachineBasicBlock *getBasicBlock() const { return MBB; } 809 810 static bool classof(const BasicBlockSDNode *) { return true; } 811 static bool classof(const SDNode *N) { 812 return N->getOpcode() == ISD::BasicBlock; 813 } 814}; 815 816class SrcValueSDNode : public SDNode { 817 const Value *V; 818 int offset; 819protected: 820 friend class SelectionDAG; 821 SrcValueSDNode(const Value* v, int o) 822 : SDNode(ISD::SRCVALUE, MVT::Other), V(v), offset(o) {} 823 824public: 825 const Value *getValue() const { return V; } 826 int getOffset() const { return offset; } 827 828 static bool classof(const SrcValueSDNode *) { return true; } 829 static bool classof(const SDNode *N) { 830 return N->getOpcode() == ISD::SRCVALUE; 831 } 832}; 833 834 835class RegisterSDNode : public SDNode { 836 unsigned Reg; 837protected: 838 friend class SelectionDAG; 839 RegisterSDNode(unsigned reg, MVT::ValueType VT) 840 : SDNode(ISD::Register, VT), Reg(reg) {} 841public: 842 843 unsigned getReg() const { return Reg; } 844 845 static bool classof(const RegisterSDNode *) { return true; } 846 static bool classof(const SDNode *N) { 847 return N->getOpcode() == ISD::Register; 848 } 849}; 850 851class ExternalSymbolSDNode : public SDNode { 852 const char *Symbol; 853protected: 854 friend class SelectionDAG; 855 ExternalSymbolSDNode(const char *Sym, MVT::ValueType VT) 856 : SDNode(ISD::ExternalSymbol, VT), Symbol(Sym) { 857 } 858public: 859 860 const char *getSymbol() const { return Symbol; } 861 862 static bool classof(const ExternalSymbolSDNode *) { return true; } 863 static bool classof(const SDNode *N) { 864 return N->getOpcode() == ISD::ExternalSymbol; 865 } 866}; 867 868class CondCodeSDNode : public SDNode { 869 ISD::CondCode Condition; 870protected: 871 friend class SelectionDAG; 872 CondCodeSDNode(ISD::CondCode Cond) 873 : SDNode(ISD::CONDCODE, MVT::Other), Condition(Cond) { 874 } 875public: 876 877 ISD::CondCode get() const { return Condition; } 878 879 static bool classof(const CondCodeSDNode *) { return true; } 880 static bool classof(const SDNode *N) { 881 return N->getOpcode() == ISD::CONDCODE; 882 } 883}; 884 885/// VTSDNode - This class is used to represent MVT::ValueType's, which are used 886/// to parameterize some operations. 887class VTSDNode : public SDNode { 888 MVT::ValueType ValueType; 889protected: 890 friend class SelectionDAG; 891 VTSDNode(MVT::ValueType VT) 892 : SDNode(ISD::VALUETYPE, MVT::Other), ValueType(VT) {} 893public: 894 895 MVT::ValueType getVT() const { return ValueType; } 896 897 static bool classof(const VTSDNode *) { return true; } 898 static bool classof(const SDNode *N) { 899 return N->getOpcode() == ISD::VALUETYPE; 900 } 901}; 902 903 904class SDNodeIterator : public forward_iterator<SDNode, ptrdiff_t> { 905 SDNode *Node; 906 unsigned Operand; 907 908 SDNodeIterator(SDNode *N, unsigned Op) : Node(N), Operand(Op) {} 909public: 910 bool operator==(const SDNodeIterator& x) const { 911 return Operand == x.Operand; 912 } 913 bool operator!=(const SDNodeIterator& x) const { return !operator==(x); } 914 915 const SDNodeIterator &operator=(const SDNodeIterator &I) { 916 assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); 917 Operand = I.Operand; 918 return *this; 919 } 920 921 pointer operator*() const { 922 return Node->getOperand(Operand).Val; 923 } 924 pointer operator->() const { return operator*(); } 925 926 SDNodeIterator& operator++() { // Preincrement 927 ++Operand; 928 return *this; 929 } 930 SDNodeIterator operator++(int) { // Postincrement 931 SDNodeIterator tmp = *this; ++*this; return tmp; 932 } 933 934 static SDNodeIterator begin(SDNode *N) { return SDNodeIterator(N, 0); } 935 static SDNodeIterator end (SDNode *N) { 936 return SDNodeIterator(N, N->getNumOperands()); 937 } 938 939 unsigned getOperand() const { return Operand; } 940 const SDNode *getNode() const { return Node; } 941}; 942 943template <> struct GraphTraits<SDNode*> { 944 typedef SDNode NodeType; 945 typedef SDNodeIterator ChildIteratorType; 946 static inline NodeType *getEntryNode(SDNode *N) { return N; } 947 static inline ChildIteratorType child_begin(NodeType *N) { 948 return SDNodeIterator::begin(N); 949 } 950 static inline ChildIteratorType child_end(NodeType *N) { 951 return SDNodeIterator::end(N); 952 } 953}; 954 955} // end llvm namespace 956 957#endif 958