Home | History | Annotate | Download | only in CodeGen
      1 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file declares the SelectionDAG class, and transitively defines the
     11 // SDNode class and subclasses.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
     16 #define LLVM_CODEGEN_SELECTIONDAG_H
     17 
     18 #include "llvm/ADT/ilist.h"
     19 #include "llvm/ADT/DenseSet.h"
     20 #include "llvm/ADT/StringMap.h"
     21 #include "llvm/CodeGen/SelectionDAGNodes.h"
     22 #include "llvm/Support/RecyclingAllocator.h"
     23 #include "llvm/Target/TargetMachine.h"
     24 #include <cassert>
     25 #include <vector>
     26 #include <map>
     27 #include <string>
     28 
     29 namespace llvm {
     30 
     31 class AliasAnalysis;
     32 class MachineConstantPoolValue;
     33 class MachineFunction;
     34 class MDNode;
     35 class SDNodeOrdering;
     36 class SDDbgValue;
     37 class TargetLowering;
     38 class TargetSelectionDAGInfo;
     39 
     40 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
     41 private:
     42   mutable ilist_half_node<SDNode> Sentinel;
     43 public:
     44   SDNode *createSentinel() const {
     45     return static_cast<SDNode*>(&Sentinel);
     46   }
     47   static void destroySentinel(SDNode *) {}
     48 
     49   SDNode *provideInitialHead() const { return createSentinel(); }
     50   SDNode *ensureHead(SDNode*) const { return createSentinel(); }
     51   static void noteHead(SDNode*, SDNode*) {}
     52 
     53   static void deleteNode(SDNode *) {
     54     llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
     55   }
     56 private:
     57   static void createNode(const SDNode &);
     58 };
     59 
     60 /// SDDbgInfo - Keeps track of dbg_value information through SDISel.  We do
     61 /// not build SDNodes for these so as not to perturb the generated code;
     62 /// instead the info is kept off to the side in this structure. Each SDNode may
     63 /// have one or more associated dbg_value entries. This information is kept in
     64 /// DbgValMap.
     65 /// Byval parameters are handled separately because they don't use alloca's,
     66 /// which busts the normal mechanism.  There is good reason for handling all
     67 /// parameters separately:  they may not have code generated for them, they
     68 /// should always go at the beginning of the function regardless of other code
     69 /// motion, and debug info for them is potentially useful even if the parameter
     70 /// is unused.  Right now only byval parameters are handled separately.
     71 class SDDbgInfo {
     72   SmallVector<SDDbgValue*, 32> DbgValues;
     73   SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
     74   DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMap;
     75 
     76   void operator=(const SDDbgInfo&);   // Do not implement.
     77   SDDbgInfo(const SDDbgInfo&);   // Do not implement.
     78 public:
     79   SDDbgInfo() {}
     80 
     81   void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
     82     if (isParameter) {
     83       ByvalParmDbgValues.push_back(V);
     84     } else     DbgValues.push_back(V);
     85     if (Node)
     86       DbgValMap[Node].push_back(V);
     87   }
     88 
     89   void clear() {
     90     DbgValMap.clear();
     91     DbgValues.clear();
     92     ByvalParmDbgValues.clear();
     93   }
     94 
     95   bool empty() const {
     96     return DbgValues.empty() && ByvalParmDbgValues.empty();
     97   }
     98 
     99   ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
    100     DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> >::iterator I =
    101       DbgValMap.find(Node);
    102     if (I != DbgValMap.end())
    103       return I->second;
    104     return ArrayRef<SDDbgValue*>();
    105   }
    106 
    107   typedef SmallVector<SDDbgValue*,32>::iterator DbgIterator;
    108   DbgIterator DbgBegin() { return DbgValues.begin(); }
    109   DbgIterator DbgEnd()   { return DbgValues.end(); }
    110   DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
    111   DbgIterator ByvalParmDbgEnd()   { return ByvalParmDbgValues.end(); }
    112 };
    113 
    114 enum CombineLevel {
    115   BeforeLegalizeTypes,
    116   AfterLegalizeTypes,
    117   AfterLegalizeVectorOps,
    118   AfterLegalizeDAG
    119 };
    120 
    121 class SelectionDAG;
    122 void checkForCycles(const SDNode *N);
    123 void checkForCycles(const SelectionDAG *DAG);
    124 
    125 /// SelectionDAG class - This is used to represent a portion of an LLVM function
    126 /// in a low-level Data Dependence DAG representation suitable for instruction
    127 /// selection.  This DAG is constructed as the first step of instruction
    128 /// selection in order to allow implementation of machine specific optimizations
    129 /// and code simplifications.
    130 ///
    131 /// The representation used by the SelectionDAG is a target-independent
    132 /// representation, which has some similarities to the GCC RTL representation,
    133 /// but is significantly more simple, powerful, and is a graph form instead of a
    134 /// linear form.
    135 ///
    136 class SelectionDAG {
    137   const TargetMachine &TM;
    138   const TargetLowering &TLI;
    139   const TargetSelectionDAGInfo &TSI;
    140   MachineFunction *MF;
    141   LLVMContext *Context;
    142   CodeGenOpt::Level OptLevel;
    143 
    144   /// EntryNode - The starting token.
    145   SDNode EntryNode;
    146 
    147   /// Root - The root of the entire DAG.
    148   SDValue Root;
    149 
    150   /// AllNodes - A linked list of nodes in the current DAG.
    151   ilist<SDNode> AllNodes;
    152 
    153   /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
    154   /// pool allocation with recycling.
    155   typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
    156                              AlignOf<MostAlignedSDNode>::Alignment>
    157     NodeAllocatorType;
    158 
    159   /// NodeAllocator - Pool allocation for nodes.
    160   NodeAllocatorType NodeAllocator;
    161 
    162   /// CSEMap - This structure is used to memoize nodes, automatically performing
    163   /// CSE with existing nodes when a duplicate is requested.
    164   FoldingSet<SDNode> CSEMap;
    165 
    166   /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
    167   BumpPtrAllocator OperandAllocator;
    168 
    169   /// Allocator - Pool allocation for misc. objects that are created once per
    170   /// SelectionDAG.
    171   BumpPtrAllocator Allocator;
    172 
    173   /// SDNodeOrdering - The ordering of the SDNodes. It roughly corresponds to
    174   /// the ordering of the original LLVM instructions.
    175   SDNodeOrdering *Ordering;
    176 
    177   /// DbgInfo - Tracks dbg_value information through SDISel.
    178   SDDbgInfo *DbgInfo;
    179 
    180   /// setGraphColorHelper - Implementation of setSubgraphColor.
    181   /// Return whether we had to truncate the search.
    182   ///
    183   bool setSubgraphColorHelper(SDNode *N, const char *Color,
    184                               DenseSet<SDNode *> &visited,
    185                               int level, bool &printed);
    186 
    187   void operator=(const SelectionDAG&); // Do not implement.
    188   SelectionDAG(const SelectionDAG&);   // Do not implement.
    189 
    190 public:
    191   explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
    192   ~SelectionDAG();
    193 
    194   /// init - Prepare this SelectionDAG to process code in the given
    195   /// MachineFunction.
    196   ///
    197   void init(MachineFunction &mf);
    198 
    199   /// clear - Clear state and free memory necessary to make this
    200   /// SelectionDAG ready to process a new block.
    201   ///
    202   void clear();
    203 
    204   MachineFunction &getMachineFunction() const { return *MF; }
    205   const TargetMachine &getTarget() const { return TM; }
    206   const TargetLowering &getTargetLoweringInfo() const { return TLI; }
    207   const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
    208   LLVMContext *getContext() const {return Context; }
    209 
    210   /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
    211   ///
    212   void viewGraph(const std::string &Title);
    213   void viewGraph();
    214 
    215 #ifndef NDEBUG
    216   std::map<const SDNode *, std::string> NodeGraphAttrs;
    217 #endif
    218 
    219   /// clearGraphAttrs - Clear all previously defined node graph attributes.
    220   /// Intended to be used from a debugging tool (eg. gdb).
    221   void clearGraphAttrs();
    222 
    223   /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
    224   ///
    225   void setGraphAttrs(const SDNode *N, const char *Attrs);
    226 
    227   /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
    228   /// Used from getNodeAttributes.
    229   const std::string getGraphAttrs(const SDNode *N) const;
    230 
    231   /// setGraphColor - Convenience for setting node color attribute.
    232   ///
    233   void setGraphColor(const SDNode *N, const char *Color);
    234 
    235   /// setGraphColor - Convenience for setting subgraph color attribute.
    236   ///
    237   void setSubgraphColor(SDNode *N, const char *Color);
    238 
    239   typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
    240   allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
    241   allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
    242   typedef ilist<SDNode>::iterator allnodes_iterator;
    243   allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
    244   allnodes_iterator allnodes_end() { return AllNodes.end(); }
    245   ilist<SDNode>::size_type allnodes_size() const {
    246     return AllNodes.size();
    247   }
    248 
    249   /// getRoot - Return the root tag of the SelectionDAG.
    250   ///
    251   const SDValue &getRoot() const { return Root; }
    252 
    253   /// getEntryNode - Return the token chain corresponding to the entry of the
    254   /// function.
    255   SDValue getEntryNode() const {
    256     return SDValue(const_cast<SDNode *>(&EntryNode), 0);
    257   }
    258 
    259   /// setRoot - Set the current root tag of the SelectionDAG.
    260   ///
    261   const SDValue &setRoot(SDValue N) {
    262     assert((!N.getNode() || N.getValueType() == MVT::Other) &&
    263            "DAG root value is not a chain!");
    264     if (N.getNode())
    265       checkForCycles(N.getNode());
    266     Root = N;
    267     if (N.getNode())
    268       checkForCycles(this);
    269     return Root;
    270   }
    271 
    272   /// Combine - This iterates over the nodes in the SelectionDAG, folding
    273   /// certain types of nodes together, or eliminating superfluous nodes.  The
    274   /// Level argument controls whether Combine is allowed to produce nodes and
    275   /// types that are illegal on the target.
    276   void Combine(CombineLevel Level, AliasAnalysis &AA,
    277                CodeGenOpt::Level OptLevel);
    278 
    279   /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
    280   /// only uses types natively supported by the target.  Returns "true" if it
    281   /// made any changes.
    282   ///
    283   /// Note that this is an involved process that may invalidate pointers into
    284   /// the graph.
    285   bool LegalizeTypes();
    286 
    287   /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
    288   /// compatible with the target instruction selector, as indicated by the
    289   /// TargetLowering object.
    290   ///
    291   /// Note that this is an involved process that may invalidate pointers into
    292   /// the graph.
    293   void Legalize();
    294 
    295   /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
    296   /// that only uses vector math operations supported by the target.  This is
    297   /// necessary as a separate step from Legalize because unrolling a vector
    298   /// operation can introduce illegal types, which requires running
    299   /// LegalizeTypes again.
    300   ///
    301   /// This returns true if it made any changes; in that case, LegalizeTypes
    302   /// is called again before Legalize.
    303   ///
    304   /// Note that this is an involved process that may invalidate pointers into
    305   /// the graph.
    306   bool LegalizeVectors();
    307 
    308   /// RemoveDeadNodes - This method deletes all unreachable nodes in the
    309   /// SelectionDAG.
    310   void RemoveDeadNodes();
    311 
    312   /// DeleteNode - Remove the specified node from the system.  This node must
    313   /// have no referrers.
    314   void DeleteNode(SDNode *N);
    315 
    316   /// getVTList - Return an SDVTList that represents the list of values
    317   /// specified.
    318   SDVTList getVTList(EVT VT);
    319   SDVTList getVTList(EVT VT1, EVT VT2);
    320   SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
    321   SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
    322   SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
    323 
    324   //===--------------------------------------------------------------------===//
    325   // Node creation methods.
    326   //
    327   SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
    328   SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
    329   SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
    330   SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
    331   SDValue getTargetConstant(uint64_t Val, EVT VT) {
    332     return getConstant(Val, VT, true);
    333   }
    334   SDValue getTargetConstant(const APInt &Val, EVT VT) {
    335     return getConstant(Val, VT, true);
    336   }
    337   SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
    338     return getConstant(Val, VT, true);
    339   }
    340   // The forms below that take a double should only be used for simple
    341   // constants that can be exactly represented in VT.  No checks are made.
    342   SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
    343   SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
    344   SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
    345   SDValue getTargetConstantFP(double Val, EVT VT) {
    346     return getConstantFP(Val, VT, true);
    347   }
    348   SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
    349     return getConstantFP(Val, VT, true);
    350   }
    351   SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
    352     return getConstantFP(Val, VT, true);
    353   }
    354   SDValue getGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
    355                            int64_t offset = 0, bool isTargetGA = false,
    356                            unsigned char TargetFlags = 0);
    357   SDValue getTargetGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
    358                                  int64_t offset = 0,
    359                                  unsigned char TargetFlags = 0) {
    360     return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
    361   }
    362   SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
    363   SDValue getTargetFrameIndex(int FI, EVT VT) {
    364     return getFrameIndex(FI, VT, true);
    365   }
    366   SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
    367                        unsigned char TargetFlags = 0);
    368   SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
    369     return getJumpTable(JTI, VT, true, TargetFlags);
    370   }
    371   SDValue getConstantPool(const Constant *C, EVT VT,
    372                           unsigned Align = 0, int Offs = 0, bool isT=false,
    373                           unsigned char TargetFlags = 0);
    374   SDValue getTargetConstantPool(const Constant *C, EVT VT,
    375                                 unsigned Align = 0, int Offset = 0,
    376                                 unsigned char TargetFlags = 0) {
    377     return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
    378   }
    379   SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
    380                           unsigned Align = 0, int Offs = 0, bool isT=false,
    381                           unsigned char TargetFlags = 0);
    382   SDValue getTargetConstantPool(MachineConstantPoolValue *C,
    383                                   EVT VT, unsigned Align = 0,
    384                                   int Offset = 0, unsigned char TargetFlags=0) {
    385     return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
    386   }
    387   // When generating a branch to a BB, we don't in general know enough
    388   // to provide debug info for the BB at that time, so keep this one around.
    389   SDValue getBasicBlock(MachineBasicBlock *MBB);
    390   SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl);
    391   SDValue getExternalSymbol(const char *Sym, EVT VT);
    392   SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT);
    393   SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
    394                                   unsigned char TargetFlags = 0);
    395   SDValue getValueType(EVT);
    396   SDValue getRegister(unsigned Reg, EVT VT);
    397   SDValue getRegisterMask(const uint32_t *RegMask);
    398   SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label);
    399   SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
    400                           bool isTarget = false, unsigned char TargetFlags = 0);
    401 
    402   SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) {
    403     return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
    404                    getRegister(Reg, N.getValueType()), N);
    405   }
    406 
    407   // This version of the getCopyToReg method takes an extra operand, which
    408   // indicates that there is potentially an incoming glue value (if Glue is not
    409   // null) and that there should be a glue result.
    410   SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N,
    411                        SDValue Glue) {
    412     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
    413     SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
    414     return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
    415   }
    416 
    417   // Similar to last getCopyToReg() except parameter Reg is a SDValue
    418   SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N,
    419                          SDValue Glue) {
    420     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
    421     SDValue Ops[] = { Chain, Reg, N, Glue };
    422     return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
    423   }
    424 
    425   SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) {
    426     SDVTList VTs = getVTList(VT, MVT::Other);
    427     SDValue Ops[] = { Chain, getRegister(Reg, VT) };
    428     return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
    429   }
    430 
    431   // This version of the getCopyFromReg method takes an extra operand, which
    432   // indicates that there is potentially an incoming glue value (if Glue is not
    433   // null) and that there should be a glue result.
    434   SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT,
    435                            SDValue Glue) {
    436     SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
    437     SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
    438     return getNode(ISD::CopyFromReg, dl, VTs, Ops, Glue.getNode() ? 3 : 2);
    439   }
    440 
    441   SDValue getCondCode(ISD::CondCode Cond);
    442 
    443   /// Returns the ConvertRndSat Note: Avoid using this node because it may
    444   /// disappear in the future and most targets don't support it.
    445   SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy,
    446                            SDValue STy,
    447                            SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
    448 
    449   /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node.  The number of
    450   /// elements in VT, which must be a vector type, must match the number of
    451   /// mask elements NumElts.  A integer mask element equal to -1 is treated as
    452   /// undefined.
    453   SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2,
    454                            const int *MaskElts);
    455 
    456   /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
    457   /// integer type VT, by either any-extending or truncating it.
    458   SDValue getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
    459 
    460   /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
    461   /// integer type VT, by either sign-extending or truncating it.
    462   SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
    463 
    464   /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
    465   /// integer type VT, by either zero-extending or truncating it.
    466   SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
    467 
    468   /// getZeroExtendInReg - Return the expression required to zero extend the Op
    469   /// value assuming it was the smaller SrcTy value.
    470   SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy);
    471 
    472   /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
    473   SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT);
    474 
    475   /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
    476   /// a glue result (to ensure it's not CSE'd).  CALLSEQ_START does not have a
    477   /// useful DebugLoc.
    478   SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) {
    479     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
    480     SDValue Ops[] = { Chain,  Op };
    481     return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2);
    482   }
    483 
    484   /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
    485   /// glue result (to ensure it's not CSE'd).  CALLSEQ_END does not have
    486   /// a useful DebugLoc.
    487   SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
    488                            SDValue InGlue) {
    489     SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
    490     SmallVector<SDValue, 4> Ops;
    491     Ops.push_back(Chain);
    492     Ops.push_back(Op1);
    493     Ops.push_back(Op2);
    494     Ops.push_back(InGlue);
    495     return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0],
    496                    (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0));
    497   }
    498 
    499   /// getUNDEF - Return an UNDEF node.  UNDEF does not have a useful DebugLoc.
    500   SDValue getUNDEF(EVT VT) {
    501     return getNode(ISD::UNDEF, DebugLoc(), VT);
    502   }
    503 
    504   /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node.  This does
    505   /// not have a useful DebugLoc.
    506   SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
    507     return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc(), VT);
    508   }
    509 
    510   /// getNode - Gets or creates the specified node.
    511   ///
    512   SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT);
    513   SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N);
    514   SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2);
    515   SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
    516                   SDValue N1, SDValue N2, SDValue N3);
    517   SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
    518                   SDValue N1, SDValue N2, SDValue N3, SDValue N4);
    519   SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
    520                   SDValue N1, SDValue N2, SDValue N3, SDValue N4,
    521                   SDValue N5);
    522   SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
    523                   const SDUse *Ops, unsigned NumOps);
    524   SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
    525                   const SDValue *Ops, unsigned NumOps);
    526   SDValue getNode(unsigned Opcode, DebugLoc DL,
    527                   const std::vector<EVT> &ResultTys,
    528                   const SDValue *Ops, unsigned NumOps);
    529   SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs,
    530                   const SDValue *Ops, unsigned NumOps);
    531   SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
    532                   const SDValue *Ops, unsigned NumOps);
    533   SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs);
    534   SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N);
    535   SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
    536                   SDValue N1, SDValue N2);
    537   SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
    538                   SDValue N1, SDValue N2, SDValue N3);
    539   SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
    540                   SDValue N1, SDValue N2, SDValue N3, SDValue N4);
    541   SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
    542                   SDValue N1, SDValue N2, SDValue N3, SDValue N4,
    543                   SDValue N5);
    544 
    545   /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
    546   /// the incoming stack arguments to be loaded from the stack. This is
    547   /// used in tail call lowering to protect stack arguments from being
    548   /// clobbered.
    549   SDValue getStackArgumentTokenFactor(SDValue Chain);
    550 
    551   SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
    552                     SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
    553                     MachinePointerInfo DstPtrInfo,
    554                     MachinePointerInfo SrcPtrInfo);
    555 
    556   SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
    557                      SDValue Size, unsigned Align, bool isVol,
    558                      MachinePointerInfo DstPtrInfo,
    559                      MachinePointerInfo SrcPtrInfo);
    560 
    561   SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
    562                     SDValue Size, unsigned Align, bool isVol,
    563                     MachinePointerInfo DstPtrInfo);
    564 
    565   /// getSetCC - Helper function to make it easier to build SetCC's if you just
    566   /// have an ISD::CondCode instead of an SDValue.
    567   ///
    568   SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
    569                    ISD::CondCode Cond) {
    570     assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
    571       "Cannot compare scalars to vectors");
    572     assert(LHS.getValueType().isVector() == VT.isVector() &&
    573       "Cannot compare scalars to vectors");
    574     return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
    575   }
    576 
    577   /// getSelectCC - Helper function to make it easier to build SelectCC's if you
    578   /// just have an ISD::CondCode instead of an SDValue.
    579   ///
    580   SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS,
    581                       SDValue True, SDValue False, ISD::CondCode Cond) {
    582     return getNode(ISD::SELECT_CC, DL, True.getValueType(),
    583                    LHS, RHS, True, False, getCondCode(Cond));
    584   }
    585 
    586   /// getVAArg - VAArg produces a result and token chain, and takes a pointer
    587   /// and a source value as input.
    588   SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
    589                    SDValue SV, unsigned Align);
    590 
    591   /// getAtomic - Gets a node for an atomic op, produces result and chain and
    592   /// takes 3 operands
    593   SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
    594                     SDValue Ptr, SDValue Cmp, SDValue Swp,
    595                     MachinePointerInfo PtrInfo, unsigned Alignment,
    596                     AtomicOrdering Ordering,
    597                     SynchronizationScope SynchScope);
    598   SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
    599                     SDValue Ptr, SDValue Cmp, SDValue Swp,
    600                     MachineMemOperand *MMO,
    601                     AtomicOrdering Ordering,
    602                     SynchronizationScope SynchScope);
    603 
    604   /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
    605   /// and chain and takes 2 operands.
    606   SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
    607                     SDValue Ptr, SDValue Val, const Value* PtrVal,
    608                     unsigned Alignment, AtomicOrdering Ordering,
    609                     SynchronizationScope SynchScope);
    610   SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
    611                     SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
    612                     AtomicOrdering Ordering,
    613                     SynchronizationScope SynchScope);
    614 
    615   /// getAtomic - Gets a node for an atomic op, produces result and chain and
    616   /// takes 1 operand.
    617   SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
    618                     SDValue Chain, SDValue Ptr, const Value* PtrVal,
    619                     unsigned Alignment,
    620                     AtomicOrdering Ordering,
    621                     SynchronizationScope SynchScope);
    622   SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
    623                     SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
    624                     AtomicOrdering Ordering,
    625                     SynchronizationScope SynchScope);
    626 
    627   /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
    628   /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
    629   /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
    630   /// less than FIRST_TARGET_MEMORY_OPCODE.
    631   SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
    632                               const EVT *VTs, unsigned NumVTs,
    633                               const SDValue *Ops, unsigned NumOps,
    634                               EVT MemVT, MachinePointerInfo PtrInfo,
    635                               unsigned Align = 0, bool Vol = false,
    636                               bool ReadMem = true, bool WriteMem = true);
    637 
    638   SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
    639                               const SDValue *Ops, unsigned NumOps,
    640                               EVT MemVT, MachinePointerInfo PtrInfo,
    641                               unsigned Align = 0, bool Vol = false,
    642                               bool ReadMem = true, bool WriteMem = true);
    643 
    644   SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
    645                               const SDValue *Ops, unsigned NumOps,
    646                               EVT MemVT, MachineMemOperand *MMO);
    647 
    648   /// getMergeValues - Create a MERGE_VALUES node from the given operands.
    649   SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl);
    650 
    651   /// getLoad - Loads are not normal binary operators: their result type is not
    652   /// determined by their operands, and they produce a value AND a token chain.
    653   ///
    654   SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
    655                   MachinePointerInfo PtrInfo, bool isVolatile,
    656                   bool isNonTemporal, bool isInvariant, unsigned Alignment,
    657                   const MDNode *TBAAInfo = 0, const MDNode *Ranges = 0);
    658   SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
    659                      SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
    660                      EVT MemVT, bool isVolatile,
    661                      bool isNonTemporal, unsigned Alignment,
    662                      const MDNode *TBAAInfo = 0);
    663   SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
    664                          SDValue Offset, ISD::MemIndexedMode AM);
    665   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
    666                   EVT VT, DebugLoc dl,
    667                   SDValue Chain, SDValue Ptr, SDValue Offset,
    668                   MachinePointerInfo PtrInfo, EVT MemVT,
    669                   bool isVolatile, bool isNonTemporal, bool isInvariant,
    670                   unsigned Alignment, const MDNode *TBAAInfo = 0,
    671                   const MDNode *Ranges = 0);
    672   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
    673                   EVT VT, DebugLoc dl,
    674                   SDValue Chain, SDValue Ptr, SDValue Offset,
    675                   EVT MemVT, MachineMemOperand *MMO);
    676 
    677   /// getStore - Helper function to build ISD::STORE nodes.
    678   ///
    679   SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
    680                    MachinePointerInfo PtrInfo, bool isVolatile,
    681                    bool isNonTemporal, unsigned Alignment,
    682                    const MDNode *TBAAInfo = 0);
    683   SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
    684                    MachineMemOperand *MMO);
    685   SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
    686                         MachinePointerInfo PtrInfo, EVT TVT,
    687                         bool isNonTemporal, bool isVolatile,
    688                         unsigned Alignment,
    689                         const MDNode *TBAAInfo = 0);
    690   SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
    691                         EVT TVT, MachineMemOperand *MMO);
    692   SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base,
    693                            SDValue Offset, ISD::MemIndexedMode AM);
    694 
    695   /// getSrcValue - Construct a node to track a Value* through the backend.
    696   SDValue getSrcValue(const Value *v);
    697 
    698   /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
    699   SDValue getMDNode(const MDNode *MD);
    700 
    701   /// getShiftAmountOperand - Return the specified value casted to
    702   /// the target's desired shift amount type.
    703   SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
    704 
    705   /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
    706   /// specified operands.  If the resultant node already exists in the DAG,
    707   /// this does not modify the specified node, instead it returns the node that
    708   /// already exists.  If the resultant node does not exist in the DAG, the
    709   /// input node is returned.  As a degenerate case, if you specify the same
    710   /// input operands as the node already has, the input node is returned.
    711   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
    712   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
    713   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
    714                                SDValue Op3);
    715   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
    716                                SDValue Op3, SDValue Op4);
    717   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
    718                                SDValue Op3, SDValue Op4, SDValue Op5);
    719   SDNode *UpdateNodeOperands(SDNode *N,
    720                                const SDValue *Ops, unsigned NumOps);
    721 
    722   /// SelectNodeTo - These are used for target selectors to *mutate* the
    723   /// specified node to have the specified return type, Target opcode, and
    724   /// operands.  Note that target opcodes are stored as
    725   /// ~TargetOpcode in the node opcode field.  The resultant node is returned.
    726   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
    727   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
    728   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
    729                        SDValue Op1, SDValue Op2);
    730   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
    731                        SDValue Op1, SDValue Op2, SDValue Op3);
    732   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
    733                        const SDValue *Ops, unsigned NumOps);
    734   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
    735   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    736                        EVT VT2, const SDValue *Ops, unsigned NumOps);
    737   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    738                        EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
    739   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
    740                        EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
    741                        unsigned NumOps);
    742   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    743                        EVT VT2, SDValue Op1);
    744   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    745                        EVT VT2, SDValue Op1, SDValue Op2);
    746   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    747                        EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
    748   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    749                        EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
    750   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
    751                        const SDValue *Ops, unsigned NumOps);
    752 
    753   /// MorphNodeTo - This *mutates* the specified node to have the specified
    754   /// return type, opcode, and operands.
    755   SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
    756                       const SDValue *Ops, unsigned NumOps);
    757 
    758   /// getMachineNode - These are used for target selectors to create a new node
    759   /// with specified return type(s), MachineInstr opcode, and operands.
    760   ///
    761   /// Note that getMachineNode returns the resultant node.  If there is already
    762   /// a node of the specified opcode and operands, it returns that node instead
    763   /// of the current one.
    764   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
    765   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
    766                                 SDValue Op1);
    767   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
    768                                 SDValue Op1, SDValue Op2);
    769   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
    770                          SDValue Op1, SDValue Op2, SDValue Op3);
    771   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
    772                          const SDValue *Ops, unsigned NumOps);
    773   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2);
    774   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
    775                          SDValue Op1);
    776   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
    777                          EVT VT2, SDValue Op1, SDValue Op2);
    778   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
    779                          EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
    780   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
    781                          const SDValue *Ops, unsigned NumOps);
    782   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
    783                          EVT VT3, SDValue Op1, SDValue Op2);
    784   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
    785                          EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
    786   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
    787                          EVT VT3, const SDValue *Ops, unsigned NumOps);
    788   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
    789                          EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
    790   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
    791                          const std::vector<EVT> &ResultTys, const SDValue *Ops,
    792                          unsigned NumOps);
    793   MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
    794                          const SDValue *Ops, unsigned NumOps);
    795 
    796   /// getTargetExtractSubreg - A convenience function for creating
    797   /// TargetInstrInfo::EXTRACT_SUBREG nodes.
    798   SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
    799                                  SDValue Operand);
    800 
    801   /// getTargetInsertSubreg - A convenience function for creating
    802   /// TargetInstrInfo::INSERT_SUBREG nodes.
    803   SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
    804                                 SDValue Operand, SDValue Subreg);
    805 
    806   /// getNodeIfExists - Get the specified node if it's already available, or
    807   /// else return NULL.
    808   SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
    809                           const SDValue *Ops, unsigned NumOps);
    810 
    811   /// getDbgValue - Creates a SDDbgValue node.
    812   ///
    813   SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
    814                           DebugLoc DL, unsigned O);
    815   SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
    816                           DebugLoc DL, unsigned O);
    817   SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
    818                           DebugLoc DL, unsigned O);
    819 
    820   /// DAGUpdateListener - Clients of various APIs that cause global effects on
    821   /// the DAG can optionally implement this interface.  This allows the clients
    822   /// to handle the various sorts of updates that happen.
    823   class DAGUpdateListener {
    824   public:
    825     virtual ~DAGUpdateListener();
    826 
    827     /// NodeDeleted - The node N that was deleted and, if E is not null, an
    828     /// equivalent node E that replaced it.
    829     virtual void NodeDeleted(SDNode *N, SDNode *E) = 0;
    830 
    831     /// NodeUpdated - The node N that was updated.
    832     virtual void NodeUpdated(SDNode *N) = 0;
    833   };
    834 
    835   /// RemoveDeadNode - Remove the specified node from the system. If any of its
    836   /// operands then becomes dead, remove them as well. Inform UpdateListener
    837   /// for each node deleted.
    838   void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0);
    839 
    840   /// RemoveDeadNodes - This method deletes the unreachable nodes in the
    841   /// given list, and any nodes that become unreachable as a result.
    842   void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
    843                        DAGUpdateListener *UpdateListener = 0);
    844 
    845   /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
    846   /// This can cause recursive merging of nodes in the DAG.  Use the first
    847   /// version if 'From' is known to have a single result, use the second
    848   /// if you have two nodes with identical results (or if 'To' has a superset
    849   /// of the results of 'From'), use the third otherwise.
    850   ///
    851   /// These methods all take an optional UpdateListener, which (if not null) is
    852   /// informed about nodes that are deleted and modified due to recursive
    853   /// changes in the dag.
    854   ///
    855   /// These functions only replace all existing uses. It's possible that as
    856   /// these replacements are being performed, CSE may cause the From node
    857   /// to be given new uses. These new uses of From are left in place, and
    858   /// not automatically transferred to To.
    859   ///
    860   void ReplaceAllUsesWith(SDValue From, SDValue Op,
    861                           DAGUpdateListener *UpdateListener = 0);
    862   void ReplaceAllUsesWith(SDNode *From, SDNode *To,
    863                           DAGUpdateListener *UpdateListener = 0);
    864   void ReplaceAllUsesWith(SDNode *From, const SDValue *To,
    865                           DAGUpdateListener *UpdateListener = 0);
    866 
    867   /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
    868   /// uses of other values produced by From.Val alone.
    869   void ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
    870                                  DAGUpdateListener *UpdateListener = 0);
    871 
    872   /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
    873   /// for multiple values at once. This correctly handles the case where
    874   /// there is an overlap between the From values and the To values.
    875   void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
    876                                   unsigned Num,
    877                                   DAGUpdateListener *UpdateListener = 0);
    878 
    879   /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
    880   /// assign a unique node id for each node in the DAG based on their
    881   /// topological order. Returns the number of nodes.
    882   unsigned AssignTopologicalOrder();
    883 
    884   /// RepositionNode - Move node N in the AllNodes list to be immediately
    885   /// before the given iterator Position. This may be used to update the
    886   /// topological ordering when the list of nodes is modified.
    887   void RepositionNode(allnodes_iterator Position, SDNode *N) {
    888     AllNodes.insert(Position, AllNodes.remove(N));
    889   }
    890 
    891   /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
    892   /// operation.
    893   static bool isCommutativeBinOp(unsigned Opcode) {
    894     // FIXME: This should get its info from the td file, so that we can include
    895     // target info.
    896     switch (Opcode) {
    897     case ISD::ADD:
    898     case ISD::MUL:
    899     case ISD::MULHU:
    900     case ISD::MULHS:
    901     case ISD::SMUL_LOHI:
    902     case ISD::UMUL_LOHI:
    903     case ISD::FADD:
    904     case ISD::FMUL:
    905     case ISD::AND:
    906     case ISD::OR:
    907     case ISD::XOR:
    908     case ISD::SADDO:
    909     case ISD::UADDO:
    910     case ISD::ADDC:
    911     case ISD::ADDE: return true;
    912     default: return false;
    913     }
    914   }
    915 
    916   /// AssignOrdering - Assign an order to the SDNode.
    917   void AssignOrdering(const SDNode *SD, unsigned Order);
    918 
    919   /// GetOrdering - Get the order for the SDNode.
    920   unsigned GetOrdering(const SDNode *SD) const;
    921 
    922   /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
    923   /// value is produced by SD.
    924   void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
    925 
    926   /// GetDbgValues - Get the debug values which reference the given SDNode.
    927   ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
    928     return DbgInfo->getSDDbgValues(SD);
    929   }
    930 
    931   /// TransferDbgValues - Transfer SDDbgValues.
    932   void TransferDbgValues(SDValue From, SDValue To);
    933 
    934   /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
    935   /// with this SelectionDAG.
    936   bool hasDebugValues() const { return !DbgInfo->empty(); }
    937 
    938   SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
    939   SDDbgInfo::DbgIterator DbgEnd()   { return DbgInfo->DbgEnd(); }
    940   SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
    941     return DbgInfo->ByvalParmDbgBegin();
    942   }
    943   SDDbgInfo::DbgIterator ByvalParmDbgEnd()   {
    944     return DbgInfo->ByvalParmDbgEnd();
    945   }
    946 
    947   void dump() const;
    948 
    949   /// CreateStackTemporary - Create a stack temporary, suitable for holding the
    950   /// specified value type.  If minAlign is specified, the slot size will have
    951   /// at least that alignment.
    952   SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
    953 
    954   /// CreateStackTemporary - Create a stack temporary suitable for holding
    955   /// either of the specified value types.
    956   SDValue CreateStackTemporary(EVT VT1, EVT VT2);
    957 
    958   /// FoldConstantArithmetic -
    959   SDValue FoldConstantArithmetic(unsigned Opcode,
    960                                  EVT VT,
    961                                  ConstantSDNode *Cst1,
    962                                  ConstantSDNode *Cst2);
    963 
    964   /// FoldSetCC - Constant fold a setcc to true or false.
    965   SDValue FoldSetCC(EVT VT, SDValue N1,
    966                     SDValue N2, ISD::CondCode Cond, DebugLoc dl);
    967 
    968   /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
    969   /// use this predicate to simplify operations downstream.
    970   bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
    971 
    972   /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero.  We
    973   /// use this predicate to simplify operations downstream.  Op and Mask are
    974   /// known to be the same type.
    975   bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
    976     const;
    977 
    978   /// ComputeMaskedBits - Determine which of the bits specified in Mask are
    979   /// known to be either zero or one and return them in the KnownZero/KnownOne
    980   /// bitsets.  This code only analyzes bits in Mask, in order to short-circuit
    981   /// processing.  Targets can implement the computeMaskedBitsForTargetNode
    982   /// method in the TargetLowering class to allow target nodes to be understood.
    983   void ComputeMaskedBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
    984                          unsigned Depth = 0) const;
    985 
    986   /// ComputeNumSignBits - Return the number of times the sign bit of the
    987   /// register is replicated into the other bits.  We know that at least 1 bit
    988   /// is always equal to the sign bit (itself), but other cases can give us
    989   /// information.  For example, immediately after an "SRA X, 2", we know that
    990   /// the top 3 bits are all equal to each other, so we return 3.  Targets can
    991   /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
    992   /// class to allow target nodes to be understood.
    993   unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
    994 
    995   /// isBaseWithConstantOffset - Return true if the specified operand is an
    996   /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
    997   /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
    998   /// semantics as an ADD.  This handles the equivalence:
    999   ///     X|Cst == X+Cst iff X&Cst = 0.
   1000   bool isBaseWithConstantOffset(SDValue Op) const;
   1001 
   1002   /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
   1003   bool isKnownNeverNaN(SDValue Op) const;
   1004 
   1005   /// isKnownNeverZero - Test whether the given SDValue is known to never be
   1006   /// positive or negative Zero.
   1007   bool isKnownNeverZero(SDValue Op) const;
   1008 
   1009   /// isEqualTo - Test whether two SDValues are known to compare equal. This
   1010   /// is true if they are the same value, or if one is negative zero and the
   1011   /// other positive zero.
   1012   bool isEqualTo(SDValue A, SDValue B) const;
   1013 
   1014   /// UnrollVectorOp - Utility function used by legalize and lowering to
   1015   /// "unroll" a vector operation by splitting out the scalars and operating
   1016   /// on each element individually.  If the ResNE is 0, fully unroll the vector
   1017   /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
   1018   /// If the  ResNE is greater than the width of the vector op, unroll the
   1019   /// vector op and fill the end of the resulting vector with UNDEFS.
   1020   SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
   1021 
   1022   /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
   1023   /// location that is 'Dist' units away from the location that the 'Base' load
   1024   /// is loading from.
   1025   bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
   1026                          unsigned Bytes, int Dist) const;
   1027 
   1028   /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
   1029   /// it cannot be inferred.
   1030   unsigned InferPtrAlignment(SDValue Ptr) const;
   1031 
   1032 private:
   1033   bool RemoveNodeFromCSEMaps(SDNode *N);
   1034   void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener);
   1035   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
   1036   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
   1037                                void *&InsertPos);
   1038   SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
   1039                                void *&InsertPos);
   1040   SDNode *UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc loc);
   1041 
   1042   void DeleteNodeNotInCSEMaps(SDNode *N);
   1043   void DeallocateNode(SDNode *N);
   1044 
   1045   unsigned getEVTAlignment(EVT MemoryVT) const;
   1046 
   1047   void allnodes_clear();
   1048 
   1049   /// VTList - List of non-single value types.
   1050   std::vector<SDVTList> VTList;
   1051 
   1052   /// CondCodeNodes - Maps to auto-CSE operations.
   1053   std::vector<CondCodeSDNode*> CondCodeNodes;
   1054 
   1055   std::vector<SDNode*> ValueTypeNodes;
   1056   std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
   1057   StringMap<SDNode*> ExternalSymbols;
   1058 
   1059   std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
   1060 };
   1061 
   1062 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
   1063   typedef SelectionDAG::allnodes_iterator nodes_iterator;
   1064   static nodes_iterator nodes_begin(SelectionDAG *G) {
   1065     return G->allnodes_begin();
   1066   }
   1067   static nodes_iterator nodes_end(SelectionDAG *G) {
   1068     return G->allnodes_end();
   1069   }
   1070 };
   1071 
   1072 }  // end namespace llvm
   1073 
   1074 #endif
   1075