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