include/llvm/CodeGen/SelectionDAGNodes.h

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