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/DenseSet.h"
     19 #include "llvm/ADT/SetVector.h"
     20 #include "llvm/ADT/StringMap.h"
     21 #include "llvm/ADT/ilist.h"
     22 #include "llvm/Analysis/AliasAnalysis.h"
     23 #include "llvm/CodeGen/DAGCombine.h"
     24 #include "llvm/CodeGen/MachineFunction.h"
     25 #include "llvm/CodeGen/SelectionDAGNodes.h"
     26 #include "llvm/Support/RecyclingAllocator.h"
     27 #include "llvm/Target/TargetMachine.h"
     28 #include <cassert>
     29 #include <map>
     30 #include <string>
     31 #include <vector>
     32 
     33 namespace llvm {
     34 
     35 class MachineConstantPoolValue;
     36 class MachineFunction;
     37 class MDNode;
     38 class SDDbgValue;
     39 class TargetLowering;
     40 class TargetSelectionDAGInfo;
     41 
     42 class SDVTListNode : public FoldingSetNode {
     43   friend struct FoldingSetTrait<SDVTListNode>;
     44   /// A reference to an Interned FoldingSetNodeID for this node.
     45   /// The Allocator in SelectionDAG holds the data.
     46   /// SDVTList contains all types which are frequently accessed in SelectionDAG.
     47   /// The size of this list is not expected to be big so it won't introduce
     48   /// a memory penalty.
     49   FoldingSetNodeIDRef FastID;
     50   const EVT *VTs;
     51   unsigned int NumVTs;
     52   /// The hash value for SDVTList is fixed, so cache it to avoid
     53   /// hash calculation.
     54   unsigned HashValue;
     55 public:
     56   SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
     57       FastID(ID), VTs(VT), NumVTs(Num) {
     58     HashValue = ID.ComputeHash();
     59   }
     60   SDVTList getSDVTList() {
     61     SDVTList result = {VTs, NumVTs};
     62     return result;
     63   }
     64 };
     65 
     66 /// Specialize FoldingSetTrait for SDVTListNode
     67 /// to avoid computing temp FoldingSetNodeID and hash value.
     68 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
     69   static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
     70     ID = X.FastID;
     71   }
     72   static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
     73                      unsigned IDHash, FoldingSetNodeID &TempID) {
     74     if (X.HashValue != IDHash)
     75       return false;
     76     return ID == X.FastID;
     77   }
     78   static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
     79     return X.HashValue;
     80   }
     81 };
     82 
     83 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
     84 private:
     85   mutable ilist_half_node<SDNode> Sentinel;
     86 public:
     87   SDNode *createSentinel() const {
     88     return static_cast<SDNode*>(&Sentinel);
     89   }
     90   static void destroySentinel(SDNode *) {}
     91 
     92   SDNode *provideInitialHead() const { return createSentinel(); }
     93   SDNode *ensureHead(SDNode*) const { return createSentinel(); }
     94   static void noteHead(SDNode*, SDNode*) {}
     95 
     96   static void deleteNode(SDNode *) {
     97     llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
     98   }
     99 private:
    100   static void createNode(const SDNode &);
    101 };
    102 
    103 /// Keeps track of dbg_value information through SDISel.  We do
    104 /// not build SDNodes for these so as not to perturb the generated code;
    105 /// instead the info is kept off to the side in this structure. Each SDNode may
    106 /// have one or more associated dbg_value entries. This information is kept in
    107 /// DbgValMap.
    108 /// Byval parameters are handled separately because they don't use alloca's,
    109 /// which busts the normal mechanism.  There is good reason for handling all
    110 /// parameters separately:  they may not have code generated for them, they
    111 /// should always go at the beginning of the function regardless of other code
    112 /// motion, and debug info for them is potentially useful even if the parameter
    113 /// is unused.  Right now only byval parameters are handled separately.
    114 class SDDbgInfo {
    115   BumpPtrAllocator Alloc;
    116   SmallVector<SDDbgValue*, 32> DbgValues;
    117   SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
    118   typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType;
    119   DbgValMapType DbgValMap;
    120 
    121   void operator=(const SDDbgInfo&) = delete;
    122   SDDbgInfo(const SDDbgInfo&) = delete;
    123 public:
    124   SDDbgInfo() {}
    125 
    126   void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
    127     if (isParameter) {
    128       ByvalParmDbgValues.push_back(V);
    129     } else     DbgValues.push_back(V);
    130     if (Node)
    131       DbgValMap[Node].push_back(V);
    132   }
    133 
    134   /// \brief Invalidate all DbgValues attached to the node and remove
    135   /// it from the Node-to-DbgValues map.
    136   void erase(const SDNode *Node);
    137 
    138   void clear() {
    139     DbgValMap.clear();
    140     DbgValues.clear();
    141     ByvalParmDbgValues.clear();
    142     Alloc.Reset();
    143   }
    144 
    145   BumpPtrAllocator &getAlloc() { return Alloc; }
    146 
    147   bool empty() const {
    148     return DbgValues.empty() && ByvalParmDbgValues.empty();
    149   }
    150 
    151   ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
    152     DbgValMapType::iterator I = DbgValMap.find(Node);
    153     if (I != DbgValMap.end())
    154       return I->second;
    155     return ArrayRef<SDDbgValue*>();
    156   }
    157 
    158   typedef SmallVectorImpl<SDDbgValue*>::iterator DbgIterator;
    159   DbgIterator DbgBegin() { return DbgValues.begin(); }
    160   DbgIterator DbgEnd()   { return DbgValues.end(); }
    161   DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
    162   DbgIterator ByvalParmDbgEnd()   { return ByvalParmDbgValues.end(); }
    163 };
    164 
    165 class SelectionDAG;
    166 void checkForCycles(const SelectionDAG *DAG, bool force = false);
    167 
    168 /// This is used to represent a portion of an LLVM function in a low-level
    169 /// Data Dependence DAG representation suitable for instruction selection.
    170 /// This DAG is constructed as the first step of instruction selection in order
    171 /// to allow implementation of machine specific optimizations
    172 /// and code simplifications.
    173 ///
    174 /// The representation used by the SelectionDAG is a target-independent
    175 /// representation, which has some similarities to the GCC RTL representation,
    176 /// but is significantly more simple, powerful, and is a graph form instead of a
    177 /// linear form.
    178 ///
    179 class SelectionDAG {
    180   const TargetMachine &TM;
    181   const TargetSelectionDAGInfo *TSI;
    182   const TargetLowering *TLI;
    183   MachineFunction *MF;
    184   LLVMContext *Context;
    185   CodeGenOpt::Level OptLevel;
    186 
    187   /// The starting token.
    188   SDNode EntryNode;
    189 
    190   /// The root of the entire DAG.
    191   SDValue Root;
    192 
    193   /// A linked list of nodes in the current DAG.
    194   ilist<SDNode> AllNodes;
    195 
    196   /// The AllocatorType for allocating SDNodes. We use
    197   /// pool allocation with recycling.
    198   typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
    199                              AlignOf<MostAlignedSDNode>::Alignment>
    200     NodeAllocatorType;
    201 
    202   /// Pool allocation for nodes.
    203   NodeAllocatorType NodeAllocator;
    204 
    205   /// This structure is used to memoize nodes, automatically performing
    206   /// CSE with existing nodes when a duplicate is requested.
    207   FoldingSet<SDNode> CSEMap;
    208 
    209   /// Pool allocation for machine-opcode SDNode operands.
    210   BumpPtrAllocator OperandAllocator;
    211 
    212   /// Pool allocation for misc. objects that are created once per SelectionDAG.
    213   BumpPtrAllocator Allocator;
    214 
    215   /// Tracks dbg_value information through SDISel.
    216   SDDbgInfo *DbgInfo;
    217 
    218   uint16_t NextPersistentId = 0;
    219 
    220 public:
    221   /// Clients of various APIs that cause global effects on
    222   /// the DAG can optionally implement this interface.  This allows the clients
    223   /// to handle the various sorts of updates that happen.
    224   ///
    225   /// A DAGUpdateListener automatically registers itself with DAG when it is
    226   /// constructed, and removes itself when destroyed in RAII fashion.
    227   struct DAGUpdateListener {
    228     DAGUpdateListener *const Next;
    229     SelectionDAG &DAG;
    230 
    231     explicit DAGUpdateListener(SelectionDAG &D)
    232       : Next(D.UpdateListeners), DAG(D) {
    233       DAG.UpdateListeners = this;
    234     }
    235 
    236     virtual ~DAGUpdateListener() {
    237       assert(DAG.UpdateListeners == this &&
    238              "DAGUpdateListeners must be destroyed in LIFO order");
    239       DAG.UpdateListeners = Next;
    240     }
    241 
    242     /// The node N that was deleted and, if E is not null, an
    243     /// equivalent node E that replaced it.
    244     virtual void NodeDeleted(SDNode *N, SDNode *E);
    245 
    246     /// The node N that was updated.
    247     virtual void NodeUpdated(SDNode *N);
    248   };
    249 
    250   /// When true, additional steps are taken to
    251   /// ensure that getConstant() and similar functions return DAG nodes that
    252   /// have legal types. This is important after type legalization since
    253   /// any illegally typed nodes generated after this point will not experience
    254   /// type legalization.
    255   bool NewNodesMustHaveLegalTypes;
    256 
    257 private:
    258   /// DAGUpdateListener is a friend so it can manipulate the listener stack.
    259   friend struct DAGUpdateListener;
    260 
    261   /// Linked list of registered DAGUpdateListener instances.
    262   /// This stack is maintained by DAGUpdateListener RAII.
    263   DAGUpdateListener *UpdateListeners;
    264 
    265   /// Implementation of setSubgraphColor.
    266   /// Return whether we had to truncate the search.
    267   bool setSubgraphColorHelper(SDNode *N, const char *Color,
    268                               DenseSet<SDNode *> &visited,
    269                               int level, bool &printed);
    270 
    271   void operator=(const SelectionDAG&) = delete;
    272   SelectionDAG(const SelectionDAG&) = delete;
    273 
    274 public:
    275   explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
    276   ~SelectionDAG();
    277 
    278   /// Prepare this SelectionDAG to process code in the given MachineFunction.
    279   void init(MachineFunction &mf);
    280 
    281   /// Clear state and free memory necessary to make this
    282   /// SelectionDAG ready to process a new block.
    283   void clear();
    284 
    285   MachineFunction &getMachineFunction() const { return *MF; }
    286   const DataLayout &getDataLayout() const { return MF->getDataLayout(); }
    287   const TargetMachine &getTarget() const { return TM; }
    288   const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
    289   const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
    290   const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return *TSI; }
    291   LLVMContext *getContext() const {return Context; }
    292 
    293   /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
    294   void viewGraph(const std::string &Title);
    295   void viewGraph();
    296 
    297 #ifndef NDEBUG
    298   std::map<const SDNode *, std::string> NodeGraphAttrs;
    299 #endif
    300 
    301   /// Clear all previously defined node graph attributes.
    302   /// Intended to be used from a debugging tool (eg. gdb).
    303   void clearGraphAttrs();
    304 
    305   /// Set graph attributes for a node. (eg. "color=red".)
    306   void setGraphAttrs(const SDNode *N, const char *Attrs);
    307 
    308   /// Get graph attributes for a node. (eg. "color=red".)
    309   /// Used from getNodeAttributes.
    310   const std::string getGraphAttrs(const SDNode *N) const;
    311 
    312   /// Convenience for setting node color attribute.
    313   void setGraphColor(const SDNode *N, const char *Color);
    314 
    315   /// Convenience for setting subgraph color attribute.
    316   void setSubgraphColor(SDNode *N, const char *Color);
    317 
    318   typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
    319   allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
    320   allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
    321   typedef ilist<SDNode>::iterator allnodes_iterator;
    322   allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
    323   allnodes_iterator allnodes_end() { return AllNodes.end(); }
    324   ilist<SDNode>::size_type allnodes_size() const {
    325     return AllNodes.size();
    326   }
    327 
    328   iterator_range<allnodes_iterator> allnodes() {
    329     return make_range(allnodes_begin(), allnodes_end());
    330   }
    331   iterator_range<allnodes_const_iterator> allnodes() const {
    332     return make_range(allnodes_begin(), allnodes_end());
    333   }
    334 
    335   /// Return the root tag of the SelectionDAG.
    336   const SDValue &getRoot() const { return Root; }
    337 
    338   /// Return the token chain corresponding to the entry of the function.
    339   SDValue getEntryNode() const {
    340     return SDValue(const_cast<SDNode *>(&EntryNode), 0);
    341   }
    342 
    343   /// Set the current root tag of the SelectionDAG.
    344   ///
    345   const SDValue &setRoot(SDValue N) {
    346     assert((!N.getNode() || N.getValueType() == MVT::Other) &&
    347            "DAG root value is not a chain!");
    348     if (N.getNode())
    349       checkForCycles(N.getNode(), this);
    350     Root = N;
    351     if (N.getNode())
    352       checkForCycles(this);
    353     return Root;
    354   }
    355 
    356   /// This iterates over the nodes in the SelectionDAG, folding
    357   /// certain types of nodes together, or eliminating superfluous nodes.  The
    358   /// Level argument controls whether Combine is allowed to produce nodes and
    359   /// types that are illegal on the target.
    360   void Combine(CombineLevel Level, AliasAnalysis &AA,
    361                CodeGenOpt::Level OptLevel);
    362 
    363   /// This transforms the SelectionDAG into a SelectionDAG that
    364   /// only uses types natively supported by the target.
    365   /// Returns "true" if it made any changes.
    366   ///
    367   /// Note that this is an involved process that may invalidate pointers into
    368   /// the graph.
    369   bool LegalizeTypes();
    370 
    371   /// This transforms the SelectionDAG into a SelectionDAG that is
    372   /// compatible with the target instruction selector, as indicated by the
    373   /// TargetLowering object.
    374   ///
    375   /// Note that this is an involved process that may invalidate pointers into
    376   /// the graph.
    377   void Legalize();
    378 
    379   /// \brief Transforms a SelectionDAG node and any operands to it into a node
    380   /// that is compatible with the target instruction selector, as indicated by
    381   /// the TargetLowering object.
    382   ///
    383   /// \returns true if \c N is a valid, legal node after calling this.
    384   ///
    385   /// This essentially runs a single recursive walk of the \c Legalize process
    386   /// over the given node (and its operands). This can be used to incrementally
    387   /// legalize the DAG. All of the nodes which are directly replaced,
    388   /// potentially including N, are added to the output parameter \c
    389   /// UpdatedNodes so that the delta to the DAG can be understood by the
    390   /// caller.
    391   ///
    392   /// When this returns false, N has been legalized in a way that make the
    393   /// pointer passed in no longer valid. It may have even been deleted from the
    394   /// DAG, and so it shouldn't be used further. When this returns true, the
    395   /// N passed in is a legal node, and can be immediately processed as such.
    396   /// This may still have done some work on the DAG, and will still populate
    397   /// UpdatedNodes with any new nodes replacing those originally in the DAG.
    398   bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
    399 
    400   /// This transforms the SelectionDAG into a SelectionDAG
    401   /// that only uses vector math operations supported by the target.  This is
    402   /// necessary as a separate step from Legalize because unrolling a vector
    403   /// operation can introduce illegal types, which requires running
    404   /// LegalizeTypes again.
    405   ///
    406   /// This returns true if it made any changes; in that case, LegalizeTypes
    407   /// is called again before Legalize.
    408   ///
    409   /// Note that this is an involved process that may invalidate pointers into
    410   /// the graph.
    411   bool LegalizeVectors();
    412 
    413   /// This method deletes all unreachable nodes in the SelectionDAG.
    414   void RemoveDeadNodes();
    415 
    416   /// Remove the specified node from the system.  This node must
    417   /// have no referrers.
    418   void DeleteNode(SDNode *N);
    419 
    420   /// Return an SDVTList that represents the list of values specified.
    421   SDVTList getVTList(EVT VT);
    422   SDVTList getVTList(EVT VT1, EVT VT2);
    423   SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
    424   SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
    425   SDVTList getVTList(ArrayRef<EVT> VTs);
    426 
    427   //===--------------------------------------------------------------------===//
    428   // Node creation methods.
    429   //
    430   SDValue getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isTarget = false,
    431                       bool isOpaque = false);
    432   SDValue getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isTarget = false,
    433                       bool isOpaque = false);
    434   SDValue getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
    435                       bool isTarget = false, bool isOpaque = false);
    436   SDValue getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget = false);
    437   SDValue getTargetConstant(uint64_t Val, SDLoc DL, EVT VT,
    438                             bool isOpaque = false) {
    439     return getConstant(Val, DL, VT, true, isOpaque);
    440   }
    441   SDValue getTargetConstant(const APInt &Val, SDLoc DL, EVT VT,
    442                             bool isOpaque = false) {
    443     return getConstant(Val, DL, VT, true, isOpaque);
    444   }
    445   SDValue getTargetConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
    446                             bool isOpaque = false) {
    447     return getConstant(Val, DL, VT, true, isOpaque);
    448   }
    449   // The forms below that take a double should only be used for simple
    450   // constants that can be exactly represented in VT.  No checks are made.
    451   SDValue getConstantFP(double Val, SDLoc DL, EVT VT, bool isTarget = false);
    452   SDValue getConstantFP(const APFloat& Val, SDLoc DL, EVT VT,
    453                         bool isTarget = false);
    454   SDValue getConstantFP(const ConstantFP &CF, SDLoc DL, EVT VT,
    455                         bool isTarget = false);
    456   SDValue getTargetConstantFP(double Val, SDLoc DL, EVT VT) {
    457     return getConstantFP(Val, DL, VT, true);
    458   }
    459   SDValue getTargetConstantFP(const APFloat& Val, SDLoc DL, EVT VT) {
    460     return getConstantFP(Val, DL, VT, true);
    461   }
    462   SDValue getTargetConstantFP(const ConstantFP &Val, SDLoc DL, EVT VT) {
    463     return getConstantFP(Val, DL, VT, true);
    464   }
    465   SDValue getGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
    466                            int64_t offset = 0, bool isTargetGA = false,
    467                            unsigned char TargetFlags = 0);
    468   SDValue getTargetGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
    469                                  int64_t offset = 0,
    470                                  unsigned char TargetFlags = 0) {
    471     return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
    472   }
    473   SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
    474   SDValue getTargetFrameIndex(int FI, EVT VT) {
    475     return getFrameIndex(FI, VT, true);
    476   }
    477   SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
    478                        unsigned char TargetFlags = 0);
    479   SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
    480     return getJumpTable(JTI, VT, true, TargetFlags);
    481   }
    482   SDValue getConstantPool(const Constant *C, EVT VT,
    483                           unsigned Align = 0, int Offs = 0, bool isT=false,
    484                           unsigned char TargetFlags = 0);
    485   SDValue getTargetConstantPool(const Constant *C, EVT VT,
    486                                 unsigned Align = 0, int Offset = 0,
    487                                 unsigned char TargetFlags = 0) {
    488     return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
    489   }
    490   SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
    491                           unsigned Align = 0, int Offs = 0, bool isT=false,
    492                           unsigned char TargetFlags = 0);
    493   SDValue getTargetConstantPool(MachineConstantPoolValue *C,
    494                                   EVT VT, unsigned Align = 0,
    495                                   int Offset = 0, unsigned char TargetFlags=0) {
    496     return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
    497   }
    498   SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
    499                          unsigned char TargetFlags = 0);
    500   // When generating a branch to a BB, we don't in general know enough
    501   // to provide debug info for the BB at that time, so keep this one around.
    502   SDValue getBasicBlock(MachineBasicBlock *MBB);
    503   SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
    504   SDValue getExternalSymbol(const char *Sym, EVT VT);
    505   SDValue getExternalSymbol(const char *Sym, SDLoc dl, EVT VT);
    506   SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
    507                                   unsigned char TargetFlags = 0);
    508   SDValue getMCSymbol(MCSymbol *Sym, EVT VT);
    509 
    510   SDValue getValueType(EVT);
    511   SDValue getRegister(unsigned Reg, EVT VT);
    512   SDValue getRegisterMask(const uint32_t *RegMask);
    513   SDValue getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label);
    514   SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
    515                           int64_t Offset = 0, bool isTarget = false,
    516                           unsigned char TargetFlags = 0);
    517   SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
    518                                 int64_t Offset = 0,
    519                                 unsigned char TargetFlags = 0) {
    520     return getBlockAddress(BA, VT, Offset, true, TargetFlags);
    521   }
    522 
    523   SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N) {
    524     return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
    525                    getRegister(Reg, N.getValueType()), N);
    526   }
    527 
    528   // This version of the getCopyToReg method takes an extra operand, which
    529   // indicates that there is potentially an incoming glue value (if Glue is not
    530   // null) and that there should be a glue result.
    531   SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N,
    532                        SDValue Glue) {
    533     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
    534     SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
    535     return getNode(ISD::CopyToReg, dl, VTs,
    536                    makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
    537   }
    538 
    539   // Similar to last getCopyToReg() except parameter Reg is a SDValue
    540   SDValue getCopyToReg(SDValue Chain, SDLoc dl, SDValue Reg, SDValue N,
    541                          SDValue Glue) {
    542     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
    543     SDValue Ops[] = { Chain, Reg, N, Glue };
    544     return getNode(ISD::CopyToReg, dl, VTs,
    545                    makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
    546   }
    547 
    548   SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT) {
    549     SDVTList VTs = getVTList(VT, MVT::Other);
    550     SDValue Ops[] = { Chain, getRegister(Reg, VT) };
    551     return getNode(ISD::CopyFromReg, dl, VTs, Ops);
    552   }
    553 
    554   // This version of the getCopyFromReg method takes an extra operand, which
    555   // indicates that there is potentially an incoming glue value (if Glue is not
    556   // null) and that there should be a glue result.
    557   SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT,
    558                            SDValue Glue) {
    559     SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
    560     SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
    561     return getNode(ISD::CopyFromReg, dl, VTs,
    562                    makeArrayRef(Ops, Glue.getNode() ? 3 : 2));
    563   }
    564 
    565   SDValue getCondCode(ISD::CondCode Cond);
    566 
    567   /// Returns the ConvertRndSat Note: Avoid using this node because it may
    568   /// disappear in the future and most targets don't support it.
    569   SDValue getConvertRndSat(EVT VT, SDLoc dl, SDValue Val, SDValue DTy,
    570                            SDValue STy,
    571                            SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
    572 
    573   /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT,
    574   /// which must be a vector type, must match the number of mask elements
    575   /// NumElts. An integer mask element equal to -1 is treated as undefined.
    576   SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
    577                            const int *MaskElts);
    578   SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
    579                            ArrayRef<int> MaskElts) {
    580     assert(VT.getVectorNumElements() == MaskElts.size() &&
    581            "Must have the same number of vector elements as mask elements!");
    582     return getVectorShuffle(VT, dl, N1, N2, MaskElts.data());
    583   }
    584 
    585   /// \brief Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
    586   /// the shuffle node in input but with swapped operands.
    587   ///
    588   /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
    589   SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
    590 
    591   /// Convert Op, which must be of integer type, to the
    592   /// integer type VT, by either any-extending or truncating it.
    593   SDValue getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
    594 
    595   /// Convert Op, which must be of integer type, to the
    596   /// integer type VT, by either sign-extending or truncating it.
    597   SDValue getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
    598 
    599   /// Convert Op, which must be of integer type, to the
    600   /// integer type VT, by either zero-extending or truncating it.
    601   SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
    602 
    603   /// Return the expression required to zero extend the Op
    604   /// value assuming it was the smaller SrcTy value.
    605   SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy);
    606 
    607   /// Return an operation which will any-extend the low lanes of the operand
    608   /// into the specified vector type. For example,
    609   /// this can convert a v16i8 into a v4i32 by any-extending the low four
    610   /// lanes of the operand from i8 to i32.
    611   SDValue getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
    612 
    613   /// Return an operation which will sign extend the low lanes of the operand
    614   /// into the specified vector type. For example,
    615   /// this can convert a v16i8 into a v4i32 by sign extending the low four
    616   /// lanes of the operand from i8 to i32.
    617   SDValue getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
    618 
    619   /// Return an operation which will zero extend the low lanes of the operand
    620   /// into the specified vector type. For example,
    621   /// this can convert a v16i8 into a v4i32 by zero extending the low four
    622   /// lanes of the operand from i8 to i32.
    623   SDValue getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
    624 
    625   /// Convert Op, which must be of integer type, to the integer type VT,
    626   /// by using an extension appropriate for the target's
    627   /// BooleanContent for type OpVT or truncating it.
    628   SDValue getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT, EVT OpVT);
    629 
    630   /// Create a bitwise NOT operation as (XOR Val, -1).
    631   SDValue getNOT(SDLoc DL, SDValue Val, EVT VT);
    632 
    633   /// \brief Create a logical NOT operation as (XOR Val, BooleanOne).
    634   SDValue getLogicalNOT(SDLoc DL, SDValue Val, EVT VT);
    635 
    636   /// Return a new CALLSEQ_START node, which always must have a glue result
    637   /// (to ensure it's not CSE'd).  CALLSEQ_START does not have a useful SDLoc.
    638   SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) {
    639     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
    640     SDValue Ops[] = { Chain,  Op };
    641     return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
    642   }
    643 
    644   /// Return a new CALLSEQ_END node, which always must have a
    645   /// glue result (to ensure it's not CSE'd).
    646   /// CALLSEQ_END does not have a useful SDLoc.
    647   SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
    648                            SDValue InGlue, SDLoc DL) {
    649     SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
    650     SmallVector<SDValue, 4> Ops;
    651     Ops.push_back(Chain);
    652     Ops.push_back(Op1);
    653     Ops.push_back(Op2);
    654     if (InGlue.getNode())
    655       Ops.push_back(InGlue);
    656     return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
    657   }
    658 
    659   /// Return an UNDEF node. UNDEF does not have a useful SDLoc.
    660   SDValue getUNDEF(EVT VT) {
    661     return getNode(ISD::UNDEF, SDLoc(), VT);
    662   }
    663 
    664   /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc.
    665   SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
    666     return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
    667   }
    668 
    669   /// Gets or creates the specified node.
    670   ///
    671   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
    672                   ArrayRef<SDUse> Ops);
    673   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
    674                   ArrayRef<SDValue> Ops, const SDNodeFlags *Flags = nullptr);
    675   SDValue getNode(unsigned Opcode, SDLoc DL, ArrayRef<EVT> ResultTys,
    676                   ArrayRef<SDValue> Ops);
    677   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
    678                   ArrayRef<SDValue> Ops);
    679 
    680   // Specialize based on number of operands.
    681   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT);
    682   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N);
    683   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
    684                   const SDNodeFlags *Flags = nullptr);
    685   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
    686                   SDValue N3);
    687   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
    688                   SDValue N3, SDValue N4);
    689   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
    690                   SDValue N3, SDValue N4, SDValue N5);
    691 
    692   // Specialize again based on number of operands for nodes with a VTList
    693   // rather than a single VT.
    694   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs);
    695   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N);
    696   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
    697                   SDValue N2);
    698   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
    699                   SDValue N2, SDValue N3);
    700   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
    701                   SDValue N2, SDValue N3, SDValue N4);
    702   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
    703                   SDValue N2, SDValue N3, SDValue N4, SDValue N5);
    704 
    705   /// Compute a TokenFactor to force all the incoming stack arguments to be
    706   /// loaded from the stack. This is used in tail call lowering to protect
    707   /// stack arguments from being clobbered.
    708   SDValue getStackArgumentTokenFactor(SDValue Chain);
    709 
    710   SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
    711                     SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
    712                     bool isTailCall, MachinePointerInfo DstPtrInfo,
    713                     MachinePointerInfo SrcPtrInfo);
    714 
    715   SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
    716                      SDValue Size, unsigned Align, bool isVol, bool isTailCall,
    717                      MachinePointerInfo DstPtrInfo,
    718                      MachinePointerInfo SrcPtrInfo);
    719 
    720   SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
    721                     SDValue Size, unsigned Align, bool isVol, bool isTailCall,
    722                     MachinePointerInfo DstPtrInfo);
    723 
    724   /// Helper function to make it easier to build SetCC's if you just
    725   /// have an ISD::CondCode instead of an SDValue.
    726   ///
    727   SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS,
    728                    ISD::CondCode Cond) {
    729     assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
    730       "Cannot compare scalars to vectors");
    731     assert(LHS.getValueType().isVector() == VT.isVector() &&
    732       "Cannot compare scalars to vectors");
    733     assert(Cond != ISD::SETCC_INVALID &&
    734         "Cannot create a setCC of an invalid node.");
    735     return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
    736   }
    737 
    738   /// Helper function to make it easier to build Select's if you just
    739   /// have operands and don't want to check for vector.
    740   SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond,
    741                     SDValue LHS, SDValue RHS) {
    742     assert(LHS.getValueType() == RHS.getValueType() &&
    743            "Cannot use select on differing types");
    744     assert(VT.isVector() == LHS.getValueType().isVector() &&
    745            "Cannot mix vectors and scalars");
    746     return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
    747                    Cond, LHS, RHS);
    748   }
    749 
    750   /// Helper function to make it easier to build SelectCC's if you
    751   /// just have an ISD::CondCode instead of an SDValue.
    752   ///
    753   SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS,
    754                       SDValue True, SDValue False, ISD::CondCode Cond) {
    755     return getNode(ISD::SELECT_CC, DL, True.getValueType(),
    756                    LHS, RHS, True, False, getCondCode(Cond));
    757   }
    758 
    759   /// VAArg produces a result and token chain, and takes a pointer
    760   /// and a source value as input.
    761   SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
    762                    SDValue SV, unsigned Align);
    763 
    764   /// Gets a node for an atomic cmpxchg op. There are two
    765   /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
    766   /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
    767   /// a success flag (initially i1), and a chain.
    768   SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
    769                            SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
    770                            MachinePointerInfo PtrInfo, unsigned Alignment,
    771                            AtomicOrdering SuccessOrdering,
    772                            AtomicOrdering FailureOrdering,
    773                            SynchronizationScope SynchScope);
    774   SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
    775                            SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
    776                            MachineMemOperand *MMO,
    777                            AtomicOrdering SuccessOrdering,
    778                            AtomicOrdering FailureOrdering,
    779                            SynchronizationScope SynchScope);
    780 
    781   /// Gets a node for an atomic op, produces result (if relevant)
    782   /// and chain and takes 2 operands.
    783   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
    784                     SDValue Ptr, SDValue Val, const Value *PtrVal,
    785                     unsigned Alignment, AtomicOrdering Ordering,
    786                     SynchronizationScope SynchScope);
    787   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
    788                     SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
    789                     AtomicOrdering Ordering,
    790                     SynchronizationScope SynchScope);
    791 
    792   /// Gets a node for an atomic op, produces result and chain and
    793   /// takes 1 operand.
    794   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
    795                     SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
    796                     AtomicOrdering Ordering,
    797                     SynchronizationScope SynchScope);
    798 
    799   /// Gets a node for an atomic op, produces result and chain and takes N
    800   /// operands.
    801   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
    802                     ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
    803                     AtomicOrdering SuccessOrdering,
    804                     AtomicOrdering FailureOrdering,
    805                     SynchronizationScope SynchScope);
    806   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
    807                     ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
    808                     AtomicOrdering Ordering, SynchronizationScope SynchScope);
    809 
    810   /// Creates a MemIntrinsicNode that may produce a
    811   /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
    812   /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
    813   /// less than FIRST_TARGET_MEMORY_OPCODE.
    814   SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
    815                               ArrayRef<SDValue> Ops,
    816                               EVT MemVT, MachinePointerInfo PtrInfo,
    817                               unsigned Align = 0, bool Vol = false,
    818                               bool ReadMem = true, bool WriteMem = true,
    819                               unsigned Size = 0);
    820 
    821   SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
    822                               ArrayRef<SDValue> Ops,
    823                               EVT MemVT, MachineMemOperand *MMO);
    824 
    825   /// Create a MERGE_VALUES node from the given operands.
    826   SDValue getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl);
    827 
    828   /// Loads are not normal binary operators: their result type is not
    829   /// determined by their operands, and they produce a value AND a token chain.
    830   ///
    831   SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
    832                   MachinePointerInfo PtrInfo, bool isVolatile,
    833                   bool isNonTemporal, bool isInvariant, unsigned Alignment,
    834                   const AAMDNodes &AAInfo = AAMDNodes(),
    835                   const MDNode *Ranges = nullptr);
    836   SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
    837                   MachineMemOperand *MMO);
    838   SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
    839                      SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
    840                      EVT MemVT, bool isVolatile,
    841                      bool isNonTemporal, bool isInvariant, unsigned Alignment,
    842                      const AAMDNodes &AAInfo = AAMDNodes());
    843   SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
    844                      SDValue Chain, SDValue Ptr, EVT MemVT,
    845                      MachineMemOperand *MMO);
    846   SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
    847                          SDValue Offset, ISD::MemIndexedMode AM);
    848   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
    849                   EVT VT, SDLoc dl,
    850                   SDValue Chain, SDValue Ptr, SDValue Offset,
    851                   MachinePointerInfo PtrInfo, EVT MemVT,
    852                   bool isVolatile, bool isNonTemporal, bool isInvariant,
    853                   unsigned Alignment, const AAMDNodes &AAInfo = AAMDNodes(),
    854                   const MDNode *Ranges = nullptr);
    855   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
    856                   EVT VT, SDLoc dl,
    857                   SDValue Chain, SDValue Ptr, SDValue Offset,
    858                   EVT MemVT, MachineMemOperand *MMO);
    859 
    860   /// Helper function to build ISD::STORE nodes.
    861   SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
    862                    MachinePointerInfo PtrInfo, bool isVolatile,
    863                    bool isNonTemporal, unsigned Alignment,
    864                    const AAMDNodes &AAInfo = AAMDNodes());
    865   SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
    866                    MachineMemOperand *MMO);
    867   SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
    868                         MachinePointerInfo PtrInfo, EVT TVT,
    869                         bool isNonTemporal, bool isVolatile,
    870                         unsigned Alignment,
    871                         const AAMDNodes &AAInfo = AAMDNodes());
    872   SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
    873                         EVT TVT, MachineMemOperand *MMO);
    874   SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base,
    875                            SDValue Offset, ISD::MemIndexedMode AM);
    876 
    877   SDValue getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
    878                         SDValue Mask, SDValue Src0, EVT MemVT,
    879                         MachineMemOperand *MMO, ISD::LoadExtType);
    880   SDValue getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
    881                          SDValue Ptr, SDValue Mask, EVT MemVT,
    882                          MachineMemOperand *MMO, bool IsTrunc);
    883   SDValue getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
    884                           ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
    885   SDValue getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
    886                            ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
    887   /// Construct a node to track a Value* through the backend.
    888   SDValue getSrcValue(const Value *v);
    889 
    890   /// Return an MDNodeSDNode which holds an MDNode.
    891   SDValue getMDNode(const MDNode *MD);
    892 
    893   /// Return a bitcast using the SDLoc of the value operand, and casting to the
    894   /// provided type. Use getNode to set a custom SDLoc.
    895   SDValue getBitcast(EVT VT, SDValue V);
    896 
    897   /// Return an AddrSpaceCastSDNode.
    898   SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
    899                            unsigned SrcAS, unsigned DestAS);
    900 
    901   /// Return the specified value casted to
    902   /// the target's desired shift amount type.
    903   SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
    904 
    905   /// Expand the specified \c ISD::VAARG node as the Legalize pass would.
    906   SDValue expandVAArg(SDNode *Node);
    907 
    908   /// Expand the specified \c ISD::VACOPY node as the Legalize pass would.
    909   SDValue expandVACopy(SDNode *Node);
    910 
    911   /// *Mutate* the specified node in-place to have the
    912   /// specified operands.  If the resultant node already exists in the DAG,
    913   /// this does not modify the specified node, instead it returns the node that
    914   /// already exists.  If the resultant node does not exist in the DAG, the
    915   /// input node is returned.  As a degenerate case, if you specify the same
    916   /// input operands as the node already has, the input node is returned.
    917   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
    918   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
    919   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
    920                                SDValue Op3);
    921   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
    922                                SDValue Op3, SDValue Op4);
    923   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
    924                                SDValue Op3, SDValue Op4, SDValue Op5);
    925   SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
    926 
    927   /// These are used for target selectors to *mutate* the
    928   /// specified node to have the specified return type, Target opcode, and
    929   /// operands.  Note that target opcodes are stored as
    930   /// ~TargetOpcode in the node opcode field.  The resultant node is returned.
    931   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
    932   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
    933   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
    934                        SDValue Op1, SDValue Op2);
    935   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
    936                        SDValue Op1, SDValue Op2, SDValue Op3);
    937   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
    938                        ArrayRef<SDValue> Ops);
    939   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
    940   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    941                        EVT VT2, ArrayRef<SDValue> Ops);
    942   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    943                        EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
    944   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
    945                        EVT VT2, EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
    946   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    947                        EVT VT2, SDValue Op1);
    948   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    949                        EVT VT2, SDValue Op1, SDValue Op2);
    950   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    951                        EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
    952   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    953                        EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
    954   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
    955                        ArrayRef<SDValue> Ops);
    956 
    957   /// This *mutates* the specified node to have the specified
    958   /// return type, opcode, and operands.
    959   SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
    960                       ArrayRef<SDValue> Ops);
    961 
    962   /// These are used for target selectors to create a new node
    963   /// with specified return type(s), MachineInstr opcode, and operands.
    964   ///
    965   /// Note that getMachineNode returns the resultant node.  If there is already
    966   /// a node of the specified opcode and operands, it returns that node instead
    967   /// of the current one.
    968   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT);
    969   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
    970                                 SDValue Op1);
    971   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
    972                                 SDValue Op1, SDValue Op2);
    973   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
    974                                 SDValue Op1, SDValue Op2, SDValue Op3);
    975   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
    976                                 ArrayRef<SDValue> Ops);
    977   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2);
    978   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
    979                                 SDValue Op1);
    980   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
    981                                 SDValue Op1, SDValue Op2);
    982   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
    983                                 SDValue Op1, SDValue Op2, SDValue Op3);
    984   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
    985                                 ArrayRef<SDValue> Ops);
    986   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
    987                                 EVT VT3, SDValue Op1, SDValue Op2);
    988   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
    989                                 EVT VT3, SDValue Op1, SDValue Op2,
    990                                 SDValue Op3);
    991   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
    992                                 EVT VT3, ArrayRef<SDValue> Ops);
    993   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
    994                                 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
    995   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl,
    996                                 ArrayRef<EVT> ResultTys,
    997                                 ArrayRef<SDValue> Ops);
    998   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs,
    999                                 ArrayRef<SDValue> Ops);
   1000 
   1001   /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
   1002   SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
   1003                                  SDValue Operand);
   1004 
   1005   /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes.
   1006   SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
   1007                                 SDValue Operand, SDValue Subreg);
   1008 
   1009   /// Get the specified node if it's already available, or else return NULL.
   1010   SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops,
   1011                           const SDNodeFlags *Flags = nullptr);
   1012 
   1013   /// Creates a SDDbgValue node.
   1014   SDDbgValue *getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N, unsigned R,
   1015                           bool IsIndirect, uint64_t Off, DebugLoc DL,
   1016                           unsigned O);
   1017 
   1018   /// Constant
   1019   SDDbgValue *getConstantDbgValue(MDNode *Var, MDNode *Expr, const Value *C,
   1020                                   uint64_t Off, DebugLoc DL, unsigned O);
   1021 
   1022   /// FrameIndex
   1023   SDDbgValue *getFrameIndexDbgValue(MDNode *Var, MDNode *Expr, unsigned FI,
   1024                                     uint64_t Off, DebugLoc DL, unsigned O);
   1025 
   1026   /// Remove the specified node from the system. If any of its
   1027   /// operands then becomes dead, remove them as well. Inform UpdateListener
   1028   /// for each node deleted.
   1029   void RemoveDeadNode(SDNode *N);
   1030 
   1031   /// This method deletes the unreachable nodes in the
   1032   /// given list, and any nodes that become unreachable as a result.
   1033   void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
   1034 
   1035   /// Modify anything using 'From' to use 'To' instead.
   1036   /// This can cause recursive merging of nodes in the DAG.  Use the first
   1037   /// version if 'From' is known to have a single result, use the second
   1038   /// if you have two nodes with identical results (or if 'To' has a superset
   1039   /// of the results of 'From'), use the third otherwise.
   1040   ///
   1041   /// These methods all take an optional UpdateListener, which (if not null) is
   1042   /// informed about nodes that are deleted and modified due to recursive
   1043   /// changes in the dag.
   1044   ///
   1045   /// These functions only replace all existing uses. It's possible that as
   1046   /// these replacements are being performed, CSE may cause the From node
   1047   /// to be given new uses. These new uses of From are left in place, and
   1048   /// not automatically transferred to To.
   1049   ///
   1050   void ReplaceAllUsesWith(SDValue From, SDValue Op);
   1051   void ReplaceAllUsesWith(SDNode *From, SDNode *To);
   1052   void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
   1053 
   1054   /// Replace any uses of From with To, leaving
   1055   /// uses of other values produced by From.Val alone.
   1056   void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
   1057 
   1058   /// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
   1059   /// This correctly handles the case where
   1060   /// there is an overlap between the From values and the To values.
   1061   void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
   1062                                   unsigned Num);
   1063 
   1064   /// Topological-sort the AllNodes list and a
   1065   /// assign a unique node id for each node in the DAG based on their
   1066   /// topological order. Returns the number of nodes.
   1067   unsigned AssignTopologicalOrder();
   1068 
   1069   /// Move node N in the AllNodes list to be immediately
   1070   /// before the given iterator Position. This may be used to update the
   1071   /// topological ordering when the list of nodes is modified.
   1072   void RepositionNode(allnodes_iterator Position, SDNode *N) {
   1073     AllNodes.insert(Position, AllNodes.remove(N));
   1074   }
   1075 
   1076   /// Returns true if the opcode is a commutative binary operation.
   1077   static bool isCommutativeBinOp(unsigned Opcode) {
   1078     // FIXME: This should get its info from the td file, so that we can include
   1079     // target info.
   1080     switch (Opcode) {
   1081     case ISD::ADD:
   1082     case ISD::SMIN:
   1083     case ISD::SMAX:
   1084     case ISD::UMIN:
   1085     case ISD::UMAX:
   1086     case ISD::MUL:
   1087     case ISD::MULHU:
   1088     case ISD::MULHS:
   1089     case ISD::SMUL_LOHI:
   1090     case ISD::UMUL_LOHI:
   1091     case ISD::FADD:
   1092     case ISD::FMUL:
   1093     case ISD::AND:
   1094     case ISD::OR:
   1095     case ISD::XOR:
   1096     case ISD::SADDO:
   1097     case ISD::UADDO:
   1098     case ISD::ADDC:
   1099     case ISD::ADDE:
   1100     case ISD::FMINNUM:
   1101     case ISD::FMAXNUM:
   1102     case ISD::FMINNAN:
   1103     case ISD::FMAXNAN:
   1104       return true;
   1105     default: return false;
   1106     }
   1107   }
   1108 
   1109   /// Returns an APFloat semantics tag appropriate for the given type. If VT is
   1110   /// a vector type, the element semantics are returned.
   1111   static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
   1112     switch (VT.getScalarType().getSimpleVT().SimpleTy) {
   1113     default: llvm_unreachable("Unknown FP format");
   1114     case MVT::f16:     return APFloat::IEEEhalf;
   1115     case MVT::f32:     return APFloat::IEEEsingle;
   1116     case MVT::f64:     return APFloat::IEEEdouble;
   1117     case MVT::f80:     return APFloat::x87DoubleExtended;
   1118     case MVT::f128:    return APFloat::IEEEquad;
   1119     case MVT::ppcf128: return APFloat::PPCDoubleDouble;
   1120     }
   1121   }
   1122 
   1123   /// Add a dbg_value SDNode. If SD is non-null that means the
   1124   /// value is produced by SD.
   1125   void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
   1126 
   1127   /// Get the debug values which reference the given SDNode.
   1128   ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
   1129     return DbgInfo->getSDDbgValues(SD);
   1130   }
   1131 
   1132   /// Transfer SDDbgValues.
   1133   void TransferDbgValues(SDValue From, SDValue To);
   1134 
   1135   /// Return true if there are any SDDbgValue nodes associated
   1136   /// with this SelectionDAG.
   1137   bool hasDebugValues() const { return !DbgInfo->empty(); }
   1138 
   1139   SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
   1140   SDDbgInfo::DbgIterator DbgEnd()   { return DbgInfo->DbgEnd(); }
   1141   SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
   1142     return DbgInfo->ByvalParmDbgBegin();
   1143   }
   1144   SDDbgInfo::DbgIterator ByvalParmDbgEnd()   {
   1145     return DbgInfo->ByvalParmDbgEnd();
   1146   }
   1147 
   1148   void dump() const;
   1149 
   1150   /// Create a stack temporary, suitable for holding the
   1151   /// specified value type.  If minAlign is specified, the slot size will have
   1152   /// at least that alignment.
   1153   SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
   1154 
   1155   /// Create a stack temporary suitable for holding
   1156   /// either of the specified value types.
   1157   SDValue CreateStackTemporary(EVT VT1, EVT VT2);
   1158 
   1159   SDValue FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
   1160                                  SDNode *Cst1, SDNode *Cst2);
   1161 
   1162   SDValue FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
   1163                                  const ConstantSDNode *Cst1,
   1164                                  const ConstantSDNode *Cst2);
   1165 
   1166   SDValue FoldConstantVectorArithmetic(unsigned Opcode, SDLoc DL,
   1167                                        EVT VT, ArrayRef<SDValue> Ops,
   1168                                        const SDNodeFlags *Flags = nullptr);
   1169 
   1170   /// Constant fold a setcc to true or false.
   1171   SDValue FoldSetCC(EVT VT, SDValue N1,
   1172                     SDValue N2, ISD::CondCode Cond, SDLoc dl);
   1173 
   1174   /// Return true if the sign bit of Op is known to be zero.
   1175   /// We use this predicate to simplify operations downstream.
   1176   bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
   1177 
   1178   /// Return true if 'Op & Mask' is known to be zero.  We
   1179   /// use this predicate to simplify operations downstream.  Op and Mask are
   1180   /// known to be the same type.
   1181   bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
   1182     const;
   1183 
   1184   /// Determine which bits of Op are known to be either zero or one and return
   1185   /// them in the KnownZero/KnownOne bitsets.  Targets can implement the
   1186   /// computeKnownBitsForTargetNode method in the TargetLowering class to allow
   1187   /// target nodes to be understood.
   1188   void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
   1189                         unsigned Depth = 0) const;
   1190 
   1191   /// Return the number of times the sign bit of the
   1192   /// register is replicated into the other bits.  We know that at least 1 bit
   1193   /// is always equal to the sign bit (itself), but other cases can give us
   1194   /// information.  For example, immediately after an "SRA X, 2", we know that
   1195   /// the top 3 bits are all equal to each other, so we return 3.  Targets can
   1196   /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
   1197   /// class to allow target nodes to be understood.
   1198   unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
   1199 
   1200   /// Return true if the specified operand is an
   1201   /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
   1202   /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
   1203   /// semantics as an ADD.  This handles the equivalence:
   1204   ///     X|Cst == X+Cst iff X&Cst = 0.
   1205   bool isBaseWithConstantOffset(SDValue Op) const;
   1206 
   1207   /// Test whether the given SDValue is known to never be NaN.
   1208   bool isKnownNeverNaN(SDValue Op) const;
   1209 
   1210   /// Test whether the given SDValue is known to never be
   1211   /// positive or negative Zero.
   1212   bool isKnownNeverZero(SDValue Op) const;
   1213 
   1214   /// Test whether two SDValues are known to compare equal. This
   1215   /// is true if they are the same value, or if one is negative zero and the
   1216   /// other positive zero.
   1217   bool isEqualTo(SDValue A, SDValue B) const;
   1218 
   1219   /// Return true if A and B have no common bits set. As an example, this can
   1220   /// allow an 'add' to be transformed into an 'or'.
   1221   bool haveNoCommonBitsSet(SDValue A, SDValue B) const;
   1222 
   1223   /// Utility function used by legalize and lowering to
   1224   /// "unroll" a vector operation by splitting out the scalars and operating
   1225   /// on each element individually.  If the ResNE is 0, fully unroll the vector
   1226   /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
   1227   /// If the  ResNE is greater than the width of the vector op, unroll the
   1228   /// vector op and fill the end of the resulting vector with UNDEFS.
   1229   SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
   1230 
   1231   /// Return true if LD is loading 'Bytes' bytes from a location that is 'Dist'
   1232   /// units away from the location that the 'Base' load is loading from.
   1233   bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
   1234                          unsigned Bytes, int Dist) const;
   1235 
   1236   /// Infer alignment of a load / store address. Return 0 if
   1237   /// it cannot be inferred.
   1238   unsigned InferPtrAlignment(SDValue Ptr) const;
   1239 
   1240   /// Compute the VTs needed for the low/hi parts of a type
   1241   /// which is split (or expanded) into two not necessarily identical pieces.
   1242   std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
   1243 
   1244   /// Split the vector with EXTRACT_SUBVECTOR using the provides
   1245   /// VTs and return the low/high part.
   1246   std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
   1247                                           const EVT &LoVT, const EVT &HiVT);
   1248 
   1249   /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part.
   1250   std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
   1251     EVT LoVT, HiVT;
   1252     std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
   1253     return SplitVector(N, DL, LoVT, HiVT);
   1254   }
   1255 
   1256   /// Split the node's operand with EXTRACT_SUBVECTOR and
   1257   /// return the low/high part.
   1258   std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
   1259   {
   1260     return SplitVector(N->getOperand(OpNo), SDLoc(N));
   1261   }
   1262 
   1263   /// Append the extracted elements from Start to Count out of the vector Op
   1264   /// in Args. If Count is 0, all of the elements will be extracted.
   1265   void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
   1266                              unsigned Start = 0, unsigned Count = 0);
   1267 
   1268   unsigned getEVTAlignment(EVT MemoryVT) const;
   1269 
   1270 private:
   1271   void InsertNode(SDNode *N);
   1272   bool RemoveNodeFromCSEMaps(SDNode *N);
   1273   void AddModifiedNodeToCSEMaps(SDNode *N);
   1274   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
   1275   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
   1276                                void *&InsertPos);
   1277   SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
   1278                                void *&InsertPos);
   1279   SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
   1280 
   1281   void DeleteNodeNotInCSEMaps(SDNode *N);
   1282   void DeallocateNode(SDNode *N);
   1283 
   1284   void allnodes_clear();
   1285 
   1286   BinarySDNode *GetBinarySDNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
   1287                                 SDValue N1, SDValue N2,
   1288                                 const SDNodeFlags *Flags = nullptr);
   1289 
   1290   /// Look up the node specified by ID in CSEMap.  If it exists, return it.  If
   1291   /// not, return the insertion token that will make insertion faster.  This
   1292   /// overload is for nodes other than Constant or ConstantFP, use the other one
   1293   /// for those.
   1294   SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
   1295 
   1296   /// Look up the node specified by ID in CSEMap.  If it exists, return it.  If
   1297   /// not, return the insertion token that will make insertion faster.  Performs
   1298   /// additional processing for constant nodes.
   1299   SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, DebugLoc DL,
   1300                               void *&InsertPos);
   1301 
   1302   /// List of non-single value types.
   1303   FoldingSet<SDVTListNode> VTListMap;
   1304 
   1305   /// Maps to auto-CSE operations.
   1306   std::vector<CondCodeSDNode*> CondCodeNodes;
   1307 
   1308   std::vector<SDNode*> ValueTypeNodes;
   1309   std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
   1310   StringMap<SDNode*> ExternalSymbols;
   1311 
   1312   std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
   1313   DenseMap<MCSymbol *, SDNode *> MCSymbols;
   1314 };
   1315 
   1316 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
   1317   typedef SelectionDAG::allnodes_iterator nodes_iterator;
   1318   static nodes_iterator nodes_begin(SelectionDAG *G) {
   1319     return G->allnodes_begin();
   1320   }
   1321   static nodes_iterator nodes_end(SelectionDAG *G) {
   1322     return G->allnodes_end();
   1323   }
   1324 };
   1325 
   1326 }  // end namespace llvm
   1327 
   1328 #endif
   1329