LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - SelectionDAG.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 336 444 75.7 %
Date: 2018-10-20 13:21:21 Functions: 56 108 51.9 %
Legend: Lines: hit not hit

          Line data    Source code
       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/APFloat.h"
      19             : #include "llvm/ADT/APInt.h"
      20             : #include "llvm/ADT/ArrayRef.h"
      21             : #include "llvm/ADT/DenseMap.h"
      22             : #include "llvm/ADT/DenseSet.h"
      23             : #include "llvm/ADT/FoldingSet.h"
      24             : #include "llvm/ADT/SetVector.h"
      25             : #include "llvm/ADT/SmallVector.h"
      26             : #include "llvm/ADT/StringMap.h"
      27             : #include "llvm/ADT/ilist.h"
      28             : #include "llvm/ADT/iterator.h"
      29             : #include "llvm/ADT/iterator_range.h"
      30             : #include "llvm/Analysis/AliasAnalysis.h"
      31             : #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
      32             : #include "llvm/CodeGen/DAGCombine.h"
      33             : #include "llvm/CodeGen/FunctionLoweringInfo.h"
      34             : #include "llvm/CodeGen/ISDOpcodes.h"
      35             : #include "llvm/CodeGen/MachineFunction.h"
      36             : #include "llvm/CodeGen/MachineMemOperand.h"
      37             : #include "llvm/CodeGen/SelectionDAGNodes.h"
      38             : #include "llvm/CodeGen/ValueTypes.h"
      39             : #include "llvm/IR/DebugLoc.h"
      40             : #include "llvm/IR/Instructions.h"
      41             : #include "llvm/IR/Metadata.h"
      42             : #include "llvm/Support/Allocator.h"
      43             : #include "llvm/Support/ArrayRecycler.h"
      44             : #include "llvm/Support/AtomicOrdering.h"
      45             : #include "llvm/Support/Casting.h"
      46             : #include "llvm/Support/CodeGen.h"
      47             : #include "llvm/Support/ErrorHandling.h"
      48             : #include "llvm/Support/MachineValueType.h"
      49             : #include "llvm/Support/RecyclingAllocator.h"
      50             : #include <algorithm>
      51             : #include <cassert>
      52             : #include <cstdint>
      53             : #include <functional>
      54             : #include <map>
      55             : #include <string>
      56             : #include <tuple>
      57             : #include <utility>
      58             : #include <vector>
      59             : 
      60             : namespace llvm {
      61             : 
      62             : class BlockAddress;
      63             : class Constant;
      64             : class ConstantFP;
      65             : class ConstantInt;
      66             : class DataLayout;
      67             : struct fltSemantics;
      68             : class GlobalValue;
      69             : struct KnownBits;
      70             : class LLVMContext;
      71             : class MachineBasicBlock;
      72             : class MachineConstantPoolValue;
      73             : class MCSymbol;
      74             : class OptimizationRemarkEmitter;
      75             : class SDDbgValue;
      76             : class SDDbgLabel;
      77             : class SelectionDAG;
      78             : class SelectionDAGTargetInfo;
      79             : class TargetLibraryInfo;
      80             : class TargetLowering;
      81             : class TargetMachine;
      82             : class TargetSubtargetInfo;
      83             : class Value;
      84             : 
      85             : class SDVTListNode : public FoldingSetNode {
      86             :   friend struct FoldingSetTrait<SDVTListNode>;
      87             : 
      88             :   /// A reference to an Interned FoldingSetNodeID for this node.
      89             :   /// The Allocator in SelectionDAG holds the data.
      90             :   /// SDVTList contains all types which are frequently accessed in SelectionDAG.
      91             :   /// The size of this list is not expected to be big so it won't introduce
      92             :   /// a memory penalty.
      93             :   FoldingSetNodeIDRef FastID;
      94             :   const EVT *VTs;
      95             :   unsigned int NumVTs;
      96             :   /// The hash value for SDVTList is fixed, so cache it to avoid
      97             :   /// hash calculation.
      98             :   unsigned HashValue;
      99             : 
     100             : public:
     101      171614 :   SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
     102      171614 :       FastID(ID), VTs(VT), NumVTs(Num) {
     103      171614 :     HashValue = ID.ComputeHash();
     104             :   }
     105             : 
     106           0 :   SDVTList getSDVTList() {
     107           0 :     SDVTList result = {VTs, NumVTs};
     108           0 :     return result;
     109             :   }
     110             : };
     111             : 
     112             : /// Specialize FoldingSetTrait for SDVTListNode
     113             : /// to avoid computing temp FoldingSetNodeID and hash value.
     114             : template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
     115           0 :   static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
     116           0 :     ID = X.FastID;
     117           0 :   }
     118             : 
     119           0 :   static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
     120             :                      unsigned IDHash, FoldingSetNodeID &TempID) {
     121    23002443 :     if (X.HashValue != IDHash)
     122           0 :       return false;
     123    21780221 :     return ID == X.FastID;
     124             :   }
     125             : 
     126           0 :   static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
     127           0 :     return X.HashValue;
     128             :   }
     129             : };
     130             : 
     131             : template <> struct ilist_alloc_traits<SDNode> {
     132           0 :   static void deleteNode(SDNode *) {
     133           0 :     llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
     134             :   }
     135             : };
     136             : 
     137             : /// Keeps track of dbg_value information through SDISel.  We do
     138             : /// not build SDNodes for these so as not to perturb the generated code;
     139             : /// instead the info is kept off to the side in this structure. Each SDNode may
     140             : /// have one or more associated dbg_value entries. This information is kept in
     141             : /// DbgValMap.
     142             : /// Byval parameters are handled separately because they don't use alloca's,
     143             : /// which busts the normal mechanism.  There is good reason for handling all
     144             : /// parameters separately:  they may not have code generated for them, they
     145             : /// should always go at the beginning of the function regardless of other code
     146             : /// motion, and debug info for them is potentially useful even if the parameter
     147             : /// is unused.  Right now only byval parameters are handled separately.
     148             : class SDDbgInfo {
     149             :   BumpPtrAllocator Alloc;
     150             :   SmallVector<SDDbgValue*, 32> DbgValues;
     151             :   SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
     152             :   SmallVector<SDDbgLabel*, 4> DbgLabels;
     153             :   using DbgValMapType = DenseMap<const SDNode *, SmallVector<SDDbgValue *, 2>>;
     154             :   DbgValMapType DbgValMap;
     155             : 
     156             : public:
     157       58534 :   SDDbgInfo() = default;
     158             :   SDDbgInfo(const SDDbgInfo &) = delete;
     159             :   SDDbgInfo &operator=(const SDDbgInfo &) = delete;
     160             : 
     161      104979 :   void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
     162      104979 :     if (isParameter) {
     163           6 :       ByvalParmDbgValues.push_back(V);
     164      104973 :     } else     DbgValues.push_back(V);
     165      104979 :     if (Node)
     166       68449 :       DbgValMap[Node].push_back(V);
     167      104979 :   }
     168             : 
     169             :   void add(SDDbgLabel *L) {
     170           1 :     DbgLabels.push_back(L);
     171             :   }
     172             : 
     173             :   /// Invalidate all DbgValues attached to the node and remove
     174             :   /// it from the Node-to-DbgValues map.
     175             :   void erase(const SDNode *Node);
     176             : 
     177             :   void clear() {
     178     1269050 :     DbgValMap.clear();
     179             :     DbgValues.clear();
     180             :     ByvalParmDbgValues.clear();
     181             :     DbgLabels.clear();
     182     1269050 :     Alloc.Reset();
     183             :   }
     184             : 
     185      104980 :   BumpPtrAllocator &getAlloc() { return Alloc; }
     186             : 
     187             :   bool empty() const {
     188     1269035 :     return DbgValues.empty() && ByvalParmDbgValues.empty() && DbgLabels.empty();
     189             :   }
     190             : 
     191       27333 :   ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) const {
     192       27333 :     auto I = DbgValMap.find(Node);
     193       27333 :     if (I != DbgValMap.end())
     194       27333 :       return I->second;
     195           0 :     return ArrayRef<SDDbgValue*>();
     196             :   }
     197             : 
     198             :   using DbgIterator = SmallVectorImpl<SDDbgValue*>::iterator;
     199             :   using DbgLabelIterator = SmallVectorImpl<SDDbgLabel*>::iterator;
     200             : 
     201             :   DbgIterator DbgBegin() { return DbgValues.begin(); }
     202             :   DbgIterator DbgEnd()   { return DbgValues.end(); }
     203             :   DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
     204             :   DbgIterator ByvalParmDbgEnd()   { return ByvalParmDbgValues.end(); }
     205             :   DbgLabelIterator DbgLabelBegin() { return DbgLabels.begin(); }
     206             :   DbgLabelIterator DbgLabelEnd()   { return DbgLabels.end(); }
     207             : };
     208             : 
     209             : void checkForCycles(const SelectionDAG *DAG, bool force = false);
     210             : 
     211             : /// This is used to represent a portion of an LLVM function in a low-level
     212             : /// Data Dependence DAG representation suitable for instruction selection.
     213             : /// This DAG is constructed as the first step of instruction selection in order
     214             : /// to allow implementation of machine specific optimizations
     215             : /// and code simplifications.
     216             : ///
     217             : /// The representation used by the SelectionDAG is a target-independent
     218             : /// representation, which has some similarities to the GCC RTL representation,
     219             : /// but is significantly more simple, powerful, and is a graph form instead of a
     220             : /// linear form.
     221             : ///
     222             : class SelectionDAG {
     223             :   const TargetMachine &TM;
     224             :   const SelectionDAGTargetInfo *TSI = nullptr;
     225             :   const TargetLowering *TLI = nullptr;
     226             :   const TargetLibraryInfo *LibInfo = nullptr;
     227             :   MachineFunction *MF;
     228             :   Pass *SDAGISelPass = nullptr;
     229             :   LLVMContext *Context;
     230             :   CodeGenOpt::Level OptLevel;
     231             : 
     232             :   LegacyDivergenceAnalysis * DA = nullptr;
     233             :   FunctionLoweringInfo * FLI = nullptr;
     234             : 
     235             :   /// The function-level optimization remark emitter.  Used to emit remarks
     236             :   /// whenever manipulating the DAG.
     237             :   OptimizationRemarkEmitter *ORE;
     238             : 
     239             :   /// The starting token.
     240             :   SDNode EntryNode;
     241             : 
     242             :   /// The root of the entire DAG.
     243             :   SDValue Root;
     244             : 
     245             :   /// A linked list of nodes in the current DAG.
     246             :   ilist<SDNode> AllNodes;
     247             : 
     248             :   /// The AllocatorType for allocating SDNodes. We use
     249             :   /// pool allocation with recycling.
     250             :   using NodeAllocatorType = RecyclingAllocator<BumpPtrAllocator, SDNode,
     251             :                                                sizeof(LargestSDNode),
     252             :                                                alignof(MostAlignedSDNode)>;
     253             : 
     254             :   /// Pool allocation for nodes.
     255             :   NodeAllocatorType NodeAllocator;
     256             : 
     257             :   /// This structure is used to memoize nodes, automatically performing
     258             :   /// CSE with existing nodes when a duplicate is requested.
     259             :   FoldingSet<SDNode> CSEMap;
     260             : 
     261             :   /// Pool allocation for machine-opcode SDNode operands.
     262             :   BumpPtrAllocator OperandAllocator;
     263             :   ArrayRecycler<SDUse> OperandRecycler;
     264             : 
     265             :   /// Pool allocation for misc. objects that are created once per SelectionDAG.
     266             :   BumpPtrAllocator Allocator;
     267             : 
     268             :   /// Tracks dbg_value and dbg_label information through SDISel.
     269             :   SDDbgInfo *DbgInfo;
     270             : 
     271             :   uint16_t NextPersistentId = 0;
     272             : 
     273             : public:
     274             :   /// Clients of various APIs that cause global effects on
     275             :   /// the DAG can optionally implement this interface.  This allows the clients
     276             :   /// to handle the various sorts of updates that happen.
     277             :   ///
     278             :   /// A DAGUpdateListener automatically registers itself with DAG when it is
     279             :   /// constructed, and removes itself when destroyed in RAII fashion.
     280             :   struct DAGUpdateListener {
     281             :     DAGUpdateListener *const Next;
     282             :     SelectionDAG &DAG;
     283             : 
     284             :     explicit DAGUpdateListener(SelectionDAG &D)
     285   122316792 :       : Next(D.UpdateListeners), DAG(D) {
     286   110702940 :       DAG.UpdateListeners = this;
     287             :     }
     288             : 
     289           0 :     virtual ~DAGUpdateListener() {
     290             :       assert(DAG.UpdateListeners == this &&
     291             :              "DAGUpdateListeners must be destroyed in LIFO order");
     292   117828924 :       DAG.UpdateListeners = Next;
     293           0 :     }
     294           0 : 
     295             :     /// The node N that was deleted and, if E is not null, an
     296             :     /// equivalent node E that replaced it.
     297           0 :     virtual void NodeDeleted(SDNode *N, SDNode *E);
     298           0 : 
     299           0 :     /// The node N that was updated.
     300             :     virtual void NodeUpdated(SDNode *N);
     301             :   };
     302           0 : 
     303           0 :   struct DAGNodeDeletedListener : public DAGUpdateListener {
     304             :     std::function<void(SDNode *, SDNode *)> Callback;
     305             : 
     306             :     DAGNodeDeletedListener(SelectionDAG &DAG,
     307             :                            std::function<void(SDNode *, SDNode *)> Callback)
     308             :         : DAGUpdateListener(DAG), Callback(std::move(Callback)) {}
     309             : 
     310             :     void NodeDeleted(SDNode *N, SDNode *E) override { Callback(N, E); }
     311             :   };
     312             : 
     313    14152073 :   /// When true, additional steps are taken to
     314             :   /// ensure that getConstant() and similar functions return DAG nodes that
     315             :   /// have legal types. This is important after type legalization since
     316             :   /// any illegally typed nodes generated after this point will not experience
     317             :   /// type legalization.
     318    12882968 :   bool NewNodesMustHaveLegalTypes = false;
     319             : 
     320     5739573 : private:
     321             :   /// DAGUpdateListener is a friend so it can manipulate the listener stack.
     322             :   friend struct DAGUpdateListener;
     323             : 
     324             :   /// Linked list of registered DAGUpdateListener instances.
     325             :   /// This stack is maintained by DAGUpdateListener RAII.
     326             :   DAGUpdateListener *UpdateListeners = nullptr;
     327             : 
     328             :   /// Implementation of setSubgraphColor.
     329             :   /// Return whether we had to truncate the search.
     330             :   bool setSubgraphColorHelper(SDNode *N, const char *Color,
     331             :                               DenseSet<SDNode *> &visited,
     332             :                               int level, bool &printed);
     333             : 
     334             :   template <typename SDNodeT, typename... ArgTypes>
     335         642 :   SDNodeT *newSDNode(ArgTypes &&... Args) {
     336             :     return new (NodeAllocator.template Allocate<SDNodeT>())
     337         642 :         SDNodeT(std::forward<ArgTypes>(Args)...);
     338             :   }
     339         355 : 
     340             :   /// Build a synthetic SDNodeT with the given args and extract its subclass
     341         355 :   /// data as an integer (e.g. for use in a folding set).
     342             :   ///
     343         124 :   /// The args to this function are the same as the args to SDNodeT's
     344             :   /// constructor, except the second arg (assumed to be a const DebugLoc&) is
     345    29655357 :   /// omitted.
     346    23001761 :   template <typename SDNodeT, typename... ArgTypes>
     347    58687619 :   static uint16_t getSyntheticNodeSubclassData(unsigned IROrder,
     348             :                                                ArgTypes &&... Args) {
     349          31 :     // The compiler can reduce this expression to a constant iff we pass an
     350           0 :     // empty DebugLoc.  Thankfully, the debug location doesn't have any bearing
     351          31 :     // on the subclass data.
     352             :     return SDNodeT(IROrder, DebugLoc(), std::forward<ArgTypes>(Args)...)
     353          31 :         .getRawSubclassData();
     354           0 :   }
     355          64 : 
     356             :   template <typename SDNodeTy>
     357          64 :   static uint16_t getSyntheticNodeSubclassData(unsigned Opc, unsigned Order,
     358           0 :                                                 SDVTList VTs, EVT MemoryVT,
     359          37 :                                                 MachineMemOperand *MMO) {
     360             :     return SDNodeTy(Opc, Order, DebugLoc(), VTs, MemoryVT, MMO)
     361          37 :          .getRawSubclassData();
     362           0 :   }
     363           0 : 
     364             :   void createOperands(SDNode *Node, ArrayRef<SDValue> Vals);
     365           0 : 
     366           0 :   void removeOperands(SDNode *Node) {
     367           0 :     if (!Node->OperandList)
     368             :       return;
     369           0 :     OperandRecycler.deallocate(
     370           0 :         ArrayRecycler<SDUse>::Capacity::get(Node->NumOperands),
     371         642 :         Node->OperandList);
     372             :     Node->NumOperands = 0;
     373           0 :     Node->OperandList = nullptr;
     374           0 :   }
     375           0 :   void CreateTopologicalOrder(std::vector<SDNode*>& Order);
     376             : public:
     377        1284 :   explicit SelectionDAG(const TargetMachine &TM, CodeGenOpt::Level);
     378           0 :   SelectionDAG(const SelectionDAG &) = delete;
     379         355 :   SelectionDAG &operator=(const SelectionDAG &) = delete;
     380             :   ~SelectionDAG();
     381           0 : 
     382           0 :   /// Prepare this SelectionDAG to process code in the given MachineFunction.
     383           0 :   void init(MachineFunction &NewMF, OptimizationRemarkEmitter &NewORE,
     384             :             Pass *PassPtr, const TargetLibraryInfo *LibraryInfo,
     385         710 :             LegacyDivergenceAnalysis * Divergence);
     386           0 : 
     387         124 :   void setFunctionLoweringInfo(FunctionLoweringInfo * FuncInfo) {
     388             :     FLI = FuncInfo;
     389           0 :   }
     390           0 : 
     391           0 :   /// Clear state and free memory necessary to make this
     392             :   /// SelectionDAG ready to process a new block.
     393         248 :   void clear();
     394           0 : 
     395          31 :   MachineFunction &getMachineFunction() const { return *MF; }
     396           0 :   const Pass *getPass() const { return SDAGISelPass; }
     397           0 : 
     398    44321606 :   const DataLayout &getDataLayout() const { return MF->getDataLayout(); }
     399           0 :   const TargetMachine &getTarget() const { return TM; }
     400       43484 :   const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
     401          62 :   const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
     402           0 :   const TargetLibraryInfo &getLibInfo() const { return *LibInfo; }
     403          31 :   const SelectionDAGTargetInfo &getSelectionDAGInfo() const { return *TSI; }
     404           0 :   LLVMContext *getContext() const {return Context; }
     405           0 :   OptimizationRemarkEmitter &getORE() const { return *ORE; }
     406           0 : 
     407           0 :   /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
     408    98636541 :   void viewGraph(const std::string &Title);
     409          62 :   void viewGraph();
     410       11065 : 
     411          64 : #ifndef NDEBUG
     412           0 :   std::map<const SDNode *, std::string> NodeGraphAttrs;
     413           0 : #endif
     414           0 : 
     415           0 :   /// Clear all previously defined node graph attributes.
     416             :   /// Intended to be used from a debugging tool (eg. gdb).
     417         128 :   void clearGraphAttrs();
     418           0 : 
     419          37 :   /// Set graph attributes for a node. (eg. "color=red".)
     420             :   void setGraphAttrs(const SDNode *N, const char *Attrs);
     421         168 : 
     422             :   /// Get graph attributes for a node. (eg. "color=red".)
     423         168 :   /// Used from getNodeAttributes.
     424             :   const std::string getGraphAttrs(const SDNode *N) const;
     425         537 : 
     426             :   /// Convenience for setting node color attribute.
     427         463 :   void setGraphColor(const SDNode *N, const char *Color);
     428             : 
     429         374 :   /// Convenience for setting subgraph color attribute.
     430             :   void setSubgraphColor(SDNode *N, const char *Color);
     431         374 : 
     432             :   using allnodes_const_iterator = ilist<SDNode>::const_iterator;
     433         612 : 
     434             :   allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
     435         612 :   allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
     436             : 
     437         310 :   using allnodes_iterator = ilist<SDNode>::iterator;
     438             : 
     439         310 :   allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
     440             :   allnodes_iterator allnodes_end() { return AllNodes.end(); }
     441     3493052 : 
     442             :   ilist<SDNode>::size_type allnodes_size() const {
     443     3493052 :     return AllNodes.size();
     444             :   }
     445     3158493 : 
     446             :   iterator_range<allnodes_iterator> allnodes() {
     447     3158493 :     return make_range(allnodes_begin(), allnodes_end());
     448             :   }
     449           0 :   iterator_range<allnodes_const_iterator> allnodes() const {
     450           0 :     return make_range(allnodes_begin(), allnodes_end());
     451           0 :   }
     452             : 
     453           0 :   /// Return the root tag of the SelectionDAG.
     454      215873 :   const SDValue &getRoot() const { return Root; }
     455           0 : 
     456             :   /// Return the token chain corresponding to the entry of the function.
     457    22057289 :   SDValue getEntryNode() const {
     458    24265327 :     return SDValue(const_cast<SDNode *>(&EntryNode), 0);
     459    50125749 :   }
     460             : 
     461      944472 :   /// Set the current root tag of the SelectionDAG.
     462      944472 :   ///
     463    10147336 :   const SDValue &setRoot(SDValue N) {
     464     5325304 :     assert((!N.getNode() || N.getValueType() == MVT::Other) &&
     465           0 :            "DAG root value is not a chain!");
     466     8238969 :     if (N.getNode())
     467     8238969 :       checkForCycles(N.getNode(), this);
     468    10422248 :     Root = N;
     469     8238969 :     if (N.getNode())
     470    10232959 :       checkForCycles(this);
     471     8238969 :     return Root;
     472           6 :   }
     473     7849137 : 
     474           0 : #ifndef NDEBUG
     475           0 :   void VerifyDAGDiverence();
     476     7849137 : #endif
     477     6560936 : 
     478     7849137 :   /// This iterates over the nodes in the SelectionDAG, folding
     479     7849137 :   /// certain types of nodes together, or eliminating superfluous nodes.  The
     480     6560936 :   /// Level argument controls whether Combine is allowed to produce nodes and
     481     7849137 :   /// types that are illegal on the target.
     482           0 :   void Combine(CombineLevel Level, AliasAnalysis *AA,
     483           0 :                CodeGenOpt::Level OptLevel);
     484             : 
     485             :   /// This transforms the SelectionDAG into a SelectionDAG that
     486             :   /// only uses types natively supported by the target.
     487             :   /// Returns "true" if it made any changes.
     488             :   ///
     489             :   /// Note that this is an involved process that may invalidate pointers into
     490             :   /// the graph.
     491             :   bool LegalizeTypes();
     492             : 
     493     6820903 :   /// This transforms the SelectionDAG into a SelectionDAG that is
     494             :   /// compatible with the target instruction selector, as indicated by the
     495             :   /// TargetLowering object.
     496             :   ///
     497             :   /// Note that this is an involved process that may invalidate pointers into
     498             :   /// the graph.
     499    13641806 :   void Legalize();
     500             : 
     501         168 :   /// Transforms a SelectionDAG node and any operands to it into a node
     502             :   /// that is compatible with the target instruction selector, as indicated by
     503             :   /// the TargetLowering object.
     504             :   ///
     505             :   /// \returns true if \c N is a valid, legal node after calling this.
     506             :   ///
     507         336 :   /// This essentially runs a single recursive walk of the \c Legalize process
     508             :   /// over the given node (and its operands). This can be used to incrementally
     509         473 :   /// legalize the DAG. All of the nodes which are directly replaced,
     510             :   /// potentially including N, are added to the output parameter \c
     511             :   /// UpdatedNodes so that the delta to the DAG can be understood by the
     512             :   /// caller.
     513             :   ///
     514             :   /// When this returns false, N has been legalized in a way that make the
     515         946 :   /// pointer passed in no longer valid. It may have even been deleted from the
     516             :   /// DAG, and so it shouldn't be used further. When this returns true, the
     517         374 :   /// N passed in is a legal node, and can be immediately processed as such.
     518             :   /// This may still have done some work on the DAG, and will still populate
     519             :   /// UpdatedNodes with any new nodes replacing those originally in the DAG.
     520             :   bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
     521             : 
     522             :   /// This transforms the SelectionDAG into a SelectionDAG
     523         748 :   /// that only uses vector math operations supported by the target.  This is
     524             :   /// necessary as a separate step from Legalize because unrolling a vector
     525         612 :   /// operation can introduce illegal types, which requires running
     526             :   /// LegalizeTypes again.
     527             :   ///
     528             :   /// This returns true if it made any changes; in that case, LegalizeTypes
     529             :   /// is called again before Legalize.
     530       16985 :   ///
     531        1224 :   /// Note that this is an involved process that may invalidate pointers into
     532             :   /// the graph.
     533     3502420 :   bool LegalizeVectors();
     534             : 
     535             :   /// This method deletes all unreachable nodes in the SelectionDAG.
     536             :   void RemoveDeadNodes();
     537             : 
     538             :   /// Remove the specified node from the system.  This node must
     539     7004840 :   /// have no referrers.
     540             :   void DeleteNode(SDNode *N);
     541     3316856 : 
     542             :   /// Return an SDVTList that represents the list of values specified.
     543             :   SDVTList getVTList(EVT VT);
     544             :   SDVTList getVTList(EVT VT1, EVT VT2);
     545             :   SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
     546             :   SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
     547     6633712 :   SDVTList getVTList(ArrayRef<EVT> VTs);
     548             : 
     549             :   //===--------------------------------------------------------------------===//
     550             :   // Node creation methods.
     551       16718 : 
     552             :   /// Create a ConstantSDNode wrapping a constant value.
     553             :   /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
     554             :   ///
     555       16718 :   /// If only legal types can be produced, this does the necessary
     556             :   /// transformations (e.g., if the vector element type is illegal).
     557             :   /// @{
     558             :   SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT,
     559             :                       bool isTarget = false, bool isOpaque = false);
     560           0 :   SDValue getConstant(const APInt &Val, const SDLoc &DL, EVT VT,
     561           0 :                       bool isTarget = false, bool isOpaque = false);
     562           0 : 
     563          17 :   SDValue getAllOnesConstant(const SDLoc &DL, EVT VT, bool IsTarget = false,
     564           0 :                              bool IsOpaque = false) {
     565          17 :     return getConstant(APInt::getAllOnesValue(VT.getScalarSizeInBits()), DL,
     566          34 :                        VT, IsTarget, IsOpaque);
     567           0 :   }
     568             : 
     569             :   SDValue getConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
     570             :                       bool isTarget = false, bool isOpaque = false);
     571             :   SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL,
     572             :                             bool isTarget = false);
     573        7454 :   SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT,
     574             :                             bool isOpaque = false) {
     575    11199054 :     return getConstant(Val, DL, VT, true, isOpaque);
     576       14908 :   }
     577             :   SDValue getTargetConstant(const APInt &Val, const SDLoc &DL, EVT VT,
     578             :                             bool isOpaque = false) {
     579      210448 :     return getConstant(Val, DL, VT, true, isOpaque);
     580             :   }
     581             :   SDValue getTargetConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
     582             :                             bool isOpaque = false) {
     583         433 :     return getConstant(Val, DL, VT, true, isOpaque);
     584             :   }
     585     2604151 : 
     586             :   /// Create a true or false constant of type \p VT using the target's
     587             :   /// BooleanContent for type \p OpVT.
     588             :   SDValue getBoolConstant(bool V, const SDLoc &DL, EVT VT, EVT OpVT);
     589           0 :   /// @}
     590             : 
     591             :   /// Create a ConstantFPSDNode wrapping a constant value.
     592    15592668 :   /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
     593      673306 :   ///
     594      405299 :   /// If only legal types can be produced, this does the necessary
     595           0 :   /// transformations (e.g., if the vector element type is illegal).
     596             :   /// The forms that take a double should only be used for simple constants
     597             :   /// that can be exactly represented in VT.  No checks are made.
     598           0 :   /// @{
     599             :   SDValue getConstantFP(double Val, const SDLoc &DL, EVT VT,
     600             :                         bool isTarget = false);
     601             :   SDValue getConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT,
     602             :                         bool isTarget = false);
     603             :   SDValue getConstantFP(const ConstantFP &V, const SDLoc &DL, EVT VT,
     604             :                         bool isTarget = false);
     605             :   SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT) {
     606             :     return getConstantFP(Val, DL, VT, true);
     607             :   }
     608             :   SDValue getTargetConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT) {
     609          10 :     return getConstantFP(Val, DL, VT, true);
     610             :   }
     611             :   SDValue getTargetConstantFP(const ConstantFP &Val, const SDLoc &DL, EVT VT) {
     612             :     return getConstantFP(Val, DL, VT, true);
     613             :   }
     614             :   /// @}
     615             : 
     616             :   SDValue getGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
     617             :                            int64_t offset = 0, bool isTargetGA = false,
     618             :                            unsigned char TargetFlags = 0);
     619             :   SDValue getTargetGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
     620             :                                  int64_t offset = 0,
     621             :                                  unsigned char TargetFlags = 0) {
     622      693469 :     return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
     623             :   }
     624             :   SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
     625             :   SDValue getTargetFrameIndex(int FI, EVT VT) {
     626     4020200 :     return getFrameIndex(FI, VT, true);
     627             :   }
     628             :   SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
     629             :                        unsigned char TargetFlags = 0);
     630             :   SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
     631        3261 :     return getJumpTable(JTI, VT, true, TargetFlags);
     632             :   }
     633             :   SDValue getConstantPool(const Constant *C, EVT VT,
     634             :                           unsigned Align = 0, int Offs = 0, bool isT=false,
     635       10230 :                           unsigned char TargetFlags = 0);
     636             :   SDValue getTargetConstantPool(const Constant *C, EVT VT,
     637       10230 :                                 unsigned Align = 0, int Offset = 0,
     638       20460 :                                 unsigned char TargetFlags = 0) {
     639       33314 :     return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
     640             :   }
     641             :   SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
     642             :                           unsigned Align = 0, int Offs = 0, bool isT=false,
     643             :                           unsigned char TargetFlags = 0);
     644             :   SDValue getTargetConstantPool(MachineConstantPoolValue *C,
     645             :                                   EVT VT, unsigned Align = 0,
     646             :                                   int Offset = 0, unsigned char TargetFlags=0) {
     647      107751 :     return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
     648     6279867 :   }
     649             :   SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
     650             :                          unsigned char TargetFlags = 0);
     651             :   // When generating a branch to a BB, we don't in general know enough
     652         155 :   // to provide debug info for the BB at that time, so keep this one around.
     653             :   SDValue getBasicBlock(MachineBasicBlock *MBB);
     654             :   SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
     655             :   SDValue getExternalSymbol(const char *Sym, EVT VT);
     656             :   SDValue getExternalSymbol(const char *Sym, const SDLoc &dl, EVT VT);
     657     5689938 :   SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
     658             :                                   unsigned char TargetFlags = 0);
     659             :   SDValue getMCSymbol(MCSymbol *Sym, EVT VT);
     660     5689938 : 
     661     5689938 :   SDValue getValueType(EVT);
     662     5689938 :   SDValue getRegister(unsigned Reg, EVT VT);
     663     5689938 :   SDValue getRegisterMask(const uint32_t *RegMask);
     664     5689938 :   SDValue getEHLabel(const SDLoc &dl, SDValue Root, MCSymbol *Label);
     665     5689938 :   SDValue getLabelNode(unsigned Opcode, const SDLoc &dl, SDValue Root,
     666             :                        MCSymbol *Label);
     667             :   SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
     668             :                           int64_t Offset = 0, bool isTarget = false,
     669             :                           unsigned char TargetFlags = 0);
     670             :   SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
     671             :                                 int64_t Offset = 0,
     672             :                                 unsigned char TargetFlags = 0) {
     673         157 :     return getBlockAddress(BA, VT, Offset, true, TargetFlags);
     674             :   }
     675             : 
     676     1176437 :   SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg,
     677             :                        SDValue N) {
     678             :     return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
     679     2352874 :                    getRegister(Reg, N.getValueType()), N);
     680             :   }
     681             : 
     682             :   // This version of the getCopyToReg method takes an extra operand, which
     683             :   // indicates that there is potentially an incoming glue value (if Glue is not
     684             :   // null) and that there should be a glue result.
     685      218041 :   SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N,
     686        7175 :                        SDValue Glue) {
     687      218041 :     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
     688      436082 :     SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
     689       14350 :     return getNode(ISD::CopyToReg, dl, VTs,
     690      396379 :                    makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
     691             :   }
     692             : 
     693             :   // Similar to last getCopyToReg() except parameter Reg is a SDValue
     694     1568778 :   SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, SDValue Reg, SDValue N,
     695      127110 :                        SDValue Glue) {
     696        2492 :     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
     697      129602 :     SDValue Ops[] = { Chain, Reg, N, Glue };
     698      254220 :     return getNode(ISD::CopyToReg, dl, VTs,
     699        4832 :                    makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
     700      254124 :   }
     701             : 
     702     1454174 :   SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT) {
     703     1457259 :     SDVTList VTs = getVTList(VT, MVT::Other);
     704     1454174 :     SDValue Ops[] = { Chain, getRegister(Reg, VT) };
     705     1454174 :     return getNode(ISD::CopyFromReg, dl, VTs, Ops);
     706             :   }
     707             : 
     708             :   // This version of the getCopyFromReg method takes an extra operand, which
     709             :   // indicates that there is potentially an incoming glue value (if Glue is not
     710             :   // null) and that there should be a glue result.
     711       62232 :   SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT,
     712      133477 :                          SDValue Glue) {
     713      164759 :     SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
     714      164759 :     SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
     715      133477 :     return getNode(ISD::CopyFromReg, dl, VTs,
     716       31282 :                    makeArrayRef(Ops, Glue.getNode() ? 3 : 2));
     717             :   }
     718             : 
     719             :   SDValue getCondCode(ISD::CondCode Cond);
     720             : 
     721             :   /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT,
     722             :   /// which must be a vector type, must match the number of mask elements
     723             :   /// NumElts. An integer mask element equal to -1 is treated as undefined.
     724             :   SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2,
     725             :                            ArrayRef<int> Mask);
     726             : 
     727             :   /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
     728             :   /// which must be a vector type, must match the number of operands in Ops.
     729             :   /// The operands must have the same type as (or, for integers, a type wider
     730             :   /// than) VT's element type.
     731      116290 :   SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDValue> Ops) {
     732             :     // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
     733      116290 :     return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
     734             :   }
     735             : 
     736             :   /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
     737             :   /// which must be a vector type, must match the number of operands in Ops.
     738             :   /// The operands must have the same type as (or, for integers, a type wider
     739             :   /// than) VT's element type.
     740             :   SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDUse> Ops) {
     741      245839 :     // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
     742             :     return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
     743      245839 :   }
     744             : 
     745         107 :   /// Return a splat ISD::BUILD_VECTOR node, consisting of Op splatted to all
     746             :   /// elements. VT must be a vector type. Op's type must be the same as (or,
     747             :   /// for integers, a type wider than) VT's element type.
     748      405791 :   SDValue getSplatBuildVector(EVT VT, const SDLoc &DL, SDValue Op) {
     749             :     // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
     750      810478 :     if (Op.getOpcode() == ISD::UNDEF) {
     751        1104 :       assert((VT.getVectorElementType() == Op.getValueType() ||
     752        1754 :               (VT.isInteger() &&
     753             :                VT.getVectorElementType().bitsLE(Op.getValueType()))) &&
     754             :              "A splatted value must have a width equal or (for integers) "
     755             :              "greater than the vector element type!");
     756           0 :       return getNode(ISD::UNDEF, SDLoc(), VT);
     757     2131425 :     }
     758             : 
     759     2536664 :     SmallVector<SDValue, 16> Ops(VT.getVectorNumElements(), Op);
     760     4668089 :     return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
     761             :   }
     762     3173443 : 
     763             :   /// Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
     764             :   /// the shuffle node in input but with swapped operands.
     765             :   ///
     766             :   /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
     767             :   SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
     768             : 
     769       44086 :   /// Convert Op, which must be of float type, to the
     770             :   /// float type VT, by either extending or rounding (by truncation).
     771             :   SDValue getFPExtendOrRound(SDValue Op, const SDLoc &DL, EVT VT);
     772             : 
     773             :   /// Convert Op, which must be of integer type, to the
     774      226574 :   /// integer type VT, by either any-extending or truncating it.
     775      226574 :   SDValue getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
     776      226574 : 
     777      226574 :   /// Convert Op, which must be of integer type, to the
     778             :   /// integer type VT, by either sign-extending or truncating it.
     779             :   SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
     780             : 
     781             :   /// Convert Op, which must be of integer type, to the
     782             :   /// integer type VT, by either zero-extending or truncating it.
     783      396792 :   SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
     784             : 
     785      396792 :   /// Return the expression required to zero extend the Op
     786      396792 :   /// value assuming it was the smaller SrcTy value.
     787             :   SDValue getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT VT);
     788      396792 : 
     789             :   /// Return an operation which will any-extend the low lanes of the operand
     790             :   /// into the specified vector type. For example,
     791             :   /// this can convert a v16i8 into a v4i32 by any-extending the low four
     792             :   /// lanes of the operand from i8 to i32.
     793             :   SDValue getAnyExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
     794             : 
     795             :   /// Return an operation which will sign extend the low lanes of the operand
     796             :   /// into the specified vector type. For example,
     797             :   /// this can convert a v16i8 into a v4i32 by sign extending the low four
     798             :   /// lanes of the operand from i8 to i32.
     799             :   SDValue getSignExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
     800             : 
     801             :   /// Return an operation which will zero extend the low lanes of the operand
     802             :   /// into the specified vector type. For example,
     803        8030 :   /// this can convert a v16i8 into a v4i32 by zero extending the low four
     804             :   /// lanes of the operand from i8 to i32.
     805        8030 :   SDValue getZeroExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
     806             : 
     807             :   /// Convert Op, which must be of integer type, to the integer type VT,
     808             :   /// by using an extension appropriate for the target's
     809             :   /// BooleanContent for type OpVT or truncating it.
     810             :   SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT);
     811             : 
     812             :   /// Create a bitwise NOT operation as (XOR Val, -1).
     813             :   SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT);
     814        2426 : 
     815             :   /// Create a logical NOT operation as (XOR Val, BooleanOne).
     816             :   SDValue getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT);
     817             : 
     818             :   /// Create an add instruction with appropriate flags when used for
     819             :   /// addressing some offset of an object. i.e. if a load is split into multiple
     820             :   /// components, create an add nuw from the base pointer to the offset.
     821      203296 :   SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Op, int64_t Offset) {
     822      203296 :     EVT VT = Op.getValueType();
     823      203296 :     return getObjectPtrOffset(SL, Op, getConstant(Offset, SL, VT));
     824             :   }
     825             : 
     826      203384 :   SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Op, SDValue Offset) {
     827      406768 :     EVT VT = Op.getValueType();
     828             : 
     829             :     // The object itself can't wrap around the address space, so it shouldn't be
     830             :     // possible for the adds of the offsets to the split parts to overflow.
     831             :     SDNodeFlags Flags;
     832             :     Flags.setNoUnsignedWrap(true);
     833      203384 :     return getNode(ISD::ADD, SL, VT, Op, Offset, Flags);
     834             :   }
     835             : 
     836             :   /// Return a new CALLSEQ_START node, that starts new call frame, in which
     837             :   /// InSize bytes are set up inside CALLSEQ_START..CALLSEQ_END sequence and
     838             :   /// OutSize specifies part of the frame set up prior to the sequence.
     839       16085 :   SDValue getCALLSEQ_START(SDValue Chain, uint64_t InSize, uint64_t OutSize,
     840             :                            const SDLoc &DL) {
     841       16085 :     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
     842             :     SDValue Ops[] = { Chain,
     843       16085 :                       getIntPtrConstant(InSize, DL, true),
     844       16085 :                       getIntPtrConstant(OutSize, DL, true) };
     845       16085 :     return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
     846             :   }
     847             : 
     848             :   /// Return a new CALLSEQ_END node, which always must have a
     849         158 :   /// glue result (to ensure it's not CSE'd).
     850             :   /// CALLSEQ_END does not have a useful SDLoc.
     851      999537 :   SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
     852             :                          SDValue InGlue, const SDLoc &DL) {
     853      999537 :     SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
     854         158 :     SmallVector<SDValue, 4> Ops;
     855      999537 :     Ops.push_back(Chain);
     856      999379 :     Ops.push_back(Op1);
     857      999379 :     Ops.push_back(Op2);
     858      999379 :     if (InGlue.getNode())
     859      999344 :       Ops.push_back(InGlue);
     860      999379 :     return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
     861         158 :   }
     862             : 
     863         158 :   /// Return true if the result of this operation is always undefined.
     864             :   bool isUndef(unsigned Opcode, ArrayRef<SDValue> Ops);
     865         158 : 
     866         158 :   /// Return an UNDEF node. UNDEF does not have a useful SDLoc.
     867       48259 :   SDValue getUNDEF(EVT VT) {
     868       48259 :     return getNode(ISD::UNDEF, SDLoc(), VT);
     869           0 :   }
     870         158 : 
     871             :   /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc.
     872          28 :   SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
     873          28 :     return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
     874             :   }
     875             : 
     876             :   /// Gets or creates the specified node.
     877      318756 :   ///
     878      318756 :   SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
     879             :                   ArrayRef<SDUse> Ops);
     880             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
     881             :                   ArrayRef<SDValue> Ops, const SDNodeFlags Flags = SDNodeFlags());
     882             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, ArrayRef<EVT> ResultTys,
     883             :                   ArrayRef<SDValue> Ops);
     884             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList,
     885             :                   ArrayRef<SDValue> Ops);
     886             : 
     887             :   // Specialize based on number of operands.
     888             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT);
     889             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue Operand,
     890             :                   const SDNodeFlags Flags = SDNodeFlags());
     891             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
     892             :                   SDValue N2, const SDNodeFlags Flags = SDNodeFlags());
     893             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
     894             :                   SDValue N2, SDValue N3,
     895             :                   const SDNodeFlags Flags = SDNodeFlags());
     896             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
     897             :                   SDValue N2, SDValue N3, SDValue N4);
     898             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
     899             :                   SDValue N2, SDValue N3, SDValue N4, SDValue N5);
     900             : 
     901             :   // Specialize again based on number of operands for nodes with a VTList
     902             :   // rather than a single VT.
     903             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList);
     904             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N);
     905             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
     906             :                   SDValue N2);
     907             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
     908             :                   SDValue N2, SDValue N3);
     909             :   SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
     910             :                   SDValue N2, SDValue N3, SDValue N4);
     911      983678 :   SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
     912             :                   SDValue N2, SDValue N3, SDValue N4, SDValue N5);
     913      983678 : 
     914             :   /// Compute a TokenFactor to force all the incoming stack arguments to be
     915      983678 :   /// loaded from the stack. This is used in tail call lowering to protect
     916      983678 :   /// stack arguments from being clobbered.
     917      983678 :   SDValue getStackArgumentTokenFactor(SDValue Chain);
     918             : 
     919             :   SDValue getMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
     920             :                     SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
     921             :                     bool isTailCall, MachinePointerInfo DstPtrInfo,
     922             :                     MachinePointerInfo SrcPtrInfo);
     923         330 : 
     924             :   SDValue getMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
     925         330 :                      SDValue Size, unsigned Align, bool isVol, bool isTailCall,
     926             :                      MachinePointerInfo DstPtrInfo,
     927         330 :                      MachinePointerInfo SrcPtrInfo);
     928         330 : 
     929         330 :   SDValue getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
     930         330 :                     SDValue Size, unsigned Align, bool isVol, bool isTailCall,
     931           0 :                     MachinePointerInfo DstPtrInfo);
     932         330 : 
     933             :   SDValue getAtomicMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst,
     934             :                           unsigned DstAlign, SDValue Src, unsigned SrcAlign,
     935             :                           SDValue Size, Type *SizeTy, unsigned ElemSz,
     936             :                           bool isTailCall, MachinePointerInfo DstPtrInfo,
     937             :                           MachinePointerInfo SrcPtrInfo);
     938             : 
     939      120145 :   SDValue getAtomicMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst,
     940      120145 :                            unsigned DstAlign, SDValue Src, unsigned SrcAlign,
     941             :                            SDValue Size, Type *SizeTy, unsigned ElemSz,
     942           0 :                            bool isTailCall, MachinePointerInfo DstPtrInfo,
     943             :                            MachinePointerInfo SrcPtrInfo);
     944           0 : 
     945             :   SDValue getAtomicMemset(SDValue Chain, const SDLoc &dl, SDValue Dst,
     946             :                           unsigned DstAlign, SDValue Value, SDValue Size,
     947             :                           Type *SizeTy, unsigned ElemSz, bool isTailCall,
     948             :                           MachinePointerInfo DstPtrInfo);
     949             : 
     950           0 :   /// Helper function to make it easier to build SetCC's if you just
     951             :   /// have an ISD::CondCode instead of an SDValue.
     952             :   ///
     953      112888 :   SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS,
     954           0 :                    ISD::CondCode Cond) {
     955             :     assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
     956             :       "Cannot compare scalars to vectors");
     957             :     assert(LHS.getValueType().isVector() == VT.isVector() &&
     958             :       "Cannot compare scalars to vectors");
     959             :     assert(Cond != ISD::SETCC_INVALID &&
     960             :         "Cannot create a setCC of an invalid node.");
     961      112888 :     return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
     962             :   }
     963      117078 : 
     964             :   /// Helper function to make it easier to build Select's if you just
     965             :   /// have operands and don't want to check for vector.
     966        4705 :   SDValue getSelect(const SDLoc &DL, EVT VT, SDValue Cond, SDValue LHS,
     967             :                     SDValue RHS) {
     968             :     assert(LHS.getValueType() == RHS.getValueType() &&
     969             :            "Cannot use select on differing types");
     970             :     assert(VT.isVector() == LHS.getValueType().isVector() &&
     971      117078 :            "Cannot mix vectors and scalars");
     972        9410 :     return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
     973        9181 :                    Cond, LHS, RHS);
     974             :   }
     975             : 
     976       12438 :   /// Helper function to make it easier to build SelectCC's if you
     977             :   /// just have an ISD::CondCode instead of an SDValue.
     978             :   ///
     979        1932 :   SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True,
     980             :                       SDValue False, ISD::CondCode Cond) {
     981             :     return getNode(ISD::SELECT_CC, DL, True.getValueType(),
     982       26808 :                    LHS, RHS, True, False, getCondCode(Cond));
     983       23741 :   }
     984             : 
     985             :   /// VAArg produces a result and token chain, and takes a pointer
     986             :   /// and a source value as input.
     987             :   SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
     988             :                    SDValue SV, unsigned Align);
     989        1929 : 
     990             :   /// Gets a node for an atomic cmpxchg op. There are two
     991             :   /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
     992        1929 :   /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
     993             :   /// a success flag (initially i1), and a chain.
     994             :   SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
     995             :                            SDVTList VTs, SDValue Chain, SDValue Ptr,
     996             :                            SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
     997             :                            unsigned Alignment, AtomicOrdering SuccessOrdering,
     998             :                            AtomicOrdering FailureOrdering,
     999             :                            SyncScope::ID SSID);
    1000             :   SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
    1001             :                            SDVTList VTs, SDValue Chain, SDValue Ptr,
    1002             :                            SDValue Cmp, SDValue Swp, MachineMemOperand *MMO);
    1003             : 
    1004             :   /// Gets a node for an atomic op, produces result (if relevant)
    1005             :   /// and chain and takes 2 operands.
    1006             :   SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
    1007             :                     SDValue Ptr, SDValue Val, const Value *PtrVal,
    1008             :                     unsigned Alignment, AtomicOrdering Ordering,
    1009             :                     SyncScope::ID SSID);
    1010             :   SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
    1011             :                     SDValue Ptr, SDValue Val, MachineMemOperand *MMO);
    1012             : 
    1013             :   /// Gets a node for an atomic op, produces result and chain and
    1014             :   /// takes 1 operand.
    1015             :   SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, EVT VT,
    1016             :                     SDValue Chain, SDValue Ptr, MachineMemOperand *MMO);
    1017             : 
    1018             :   /// Gets a node for an atomic op, produces result and chain and takes N
    1019             :   /// operands.
    1020             :   SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT,
    1021             :                     SDVTList VTList, ArrayRef<SDValue> Ops,
    1022             :                     MachineMemOperand *MMO);
    1023             : 
    1024             :   /// Creates a MemIntrinsicNode that may produce a
    1025        4352 :   /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
    1026             :   /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
    1027             :   /// less than FIRST_TARGET_MEMORY_OPCODE.
    1028             :   SDValue getMemIntrinsicNode(
    1029             :     unsigned Opcode, const SDLoc &dl, SDVTList VTList,
    1030             :     ArrayRef<SDValue> Ops, EVT MemVT,
    1031             :     MachinePointerInfo PtrInfo,
    1032             :     unsigned Align = 0,
    1033        4352 :     MachineMemOperand::Flags Flags
    1034             :     = MachineMemOperand::MOLoad | MachineMemOperand::MOStore,
    1035             :     unsigned Size = 0);
    1036             : 
    1037             :   SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList,
    1038        2869 :                               ArrayRef<SDValue> Ops, EVT MemVT,
    1039             :                               MachineMemOperand *MMO);
    1040             : 
    1041             :   /// Create a MERGE_VALUES node from the given operands.
    1042             :   SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl);
    1043             : 
    1044        5738 :   /// Loads are not normal binary operators: their result type is not
    1045        2899 :   /// determined by their operands, and they produce a value AND a token chain.
    1046             :   ///
    1047             :   /// This function will set the MOLoad flag on MMOFlags, but you can set it if
    1048             :   /// you want.  The MOStore flag must not be set.
    1049             :   SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
    1050             :                   MachinePointerInfo PtrInfo, unsigned Alignment = 0,
    1051          45 :                   MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
    1052             :                   const AAMDNodes &AAInfo = AAMDNodes(),
    1053             :                   const MDNode *Ranges = nullptr);
    1054          45 :   SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
    1055             :                   MachineMemOperand *MMO);
    1056             :   SDValue
    1057             :   getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain,
    1058             :              SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT,
    1059             :              unsigned Alignment = 0,
    1060             :              MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
    1061     6796354 :              const AAMDNodes &AAInfo = AAMDNodes());
    1062     6796354 :   SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT,
    1063             :                      SDValue Chain, SDValue Ptr, EVT MemVT,
    1064             :                      MachineMemOperand *MMO);
    1065             :   SDValue getIndexedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base,
    1066             :                          SDValue Offset, ISD::MemIndexedMode AM);
    1067             :   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
    1068             :                   const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
    1069             :                   MachinePointerInfo PtrInfo, EVT MemVT, unsigned Alignment = 0,
    1070             :                   MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
    1071             :                   const AAMDNodes &AAInfo = AAMDNodes(),
    1072             :                   const MDNode *Ranges = nullptr);
    1073             :   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
    1074             :                   const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
    1075             :                   EVT MemVT, MachineMemOperand *MMO);
    1076             : 
    1077             :   /// Helper function to build ISD::STORE nodes.
    1078             :   ///
    1079             :   /// This function will set the MOStore flag on MMOFlags, but you can set it if
    1080             :   /// you want.  The MOLoad and MOInvariant flags must not be set.
    1081             :   SDValue
    1082             :   getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
    1083             :            MachinePointerInfo PtrInfo, unsigned Alignment = 0,
    1084             :            MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
    1085             :            const AAMDNodes &AAInfo = AAMDNodes());
    1086             :   SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
    1087             :                    MachineMemOperand *MMO);
    1088             :   SDValue
    1089             :   getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
    1090             :                 MachinePointerInfo PtrInfo, EVT SVT, unsigned Alignment = 0,
    1091             :                 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
    1092             :                 const AAMDNodes &AAInfo = AAMDNodes());
    1093             :   SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val,
    1094             :                         SDValue Ptr, EVT SVT, MachineMemOperand *MMO);
    1095             :   SDValue getIndexedStore(SDValue OrigStore, const SDLoc &dl, SDValue Base,
    1096             :                           SDValue Offset, ISD::MemIndexedMode AM);
    1097             : 
    1098             :   /// Returns sum of the base pointer and offset.
    1099             :   SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, const SDLoc &DL);
    1100             : 
    1101             :   SDValue getMaskedLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
    1102             :                         SDValue Mask, SDValue Src0, EVT MemVT,
    1103             :                         MachineMemOperand *MMO, ISD::LoadExtType,
    1104             :                         bool IsExpanding = false);
    1105             :   SDValue getMaskedStore(SDValue Chain, const SDLoc &dl, SDValue Val,
    1106             :                          SDValue Ptr, SDValue Mask, EVT MemVT,
    1107             :                          MachineMemOperand *MMO, bool IsTruncating = false,
    1108             :                          bool IsCompressing = false);
    1109             :   SDValue getMaskedGather(SDVTList VTs, EVT VT, const SDLoc &dl,
    1110             :                           ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
    1111             :   SDValue getMaskedScatter(SDVTList VTs, EVT VT, const SDLoc &dl,
    1112             :                            ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
    1113             : 
    1114             :   /// Return (create a new or find existing) a target-specific node.
    1115             :   /// TargetMemSDNode should be derived class from MemSDNode.
    1116             :   template <class TargetMemSDNode>
    1117             :   SDValue getTargetMemSDNode(SDVTList VTs, ArrayRef<SDValue> Ops,
    1118             :                              const SDLoc &dl, EVT MemVT,
    1119             :                              MachineMemOperand *MMO);
    1120             : 
    1121             :   /// Construct a node to track a Value* through the backend.
    1122             :   SDValue getSrcValue(const Value *v);
    1123             : 
    1124             :   /// Return an MDNodeSDNode which holds an MDNode.
    1125             :   SDValue getMDNode(const MDNode *MD);
    1126             : 
    1127             :   /// Return a bitcast using the SDLoc of the value operand, and casting to the
    1128             :   /// provided type. Use getNode to set a custom SDLoc.
    1129             :   SDValue getBitcast(EVT VT, SDValue V);
    1130             : 
    1131             :   /// Return an AddrSpaceCastSDNode.
    1132             :   SDValue getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr, unsigned SrcAS,
    1133             :                            unsigned DestAS);
    1134             : 
    1135             :   /// Return the specified value casted to
    1136             :   /// the target's desired shift amount type.
    1137             :   SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
    1138             : 
    1139             :   /// Expand the specified \c ISD::VAARG node as the Legalize pass would.
    1140             :   SDValue expandVAArg(SDNode *Node);
    1141             : 
    1142             :   /// Expand the specified \c ISD::VACOPY node as the Legalize pass would.
    1143             :   SDValue expandVACopy(SDNode *Node);
    1144             : 
    1145             :   /// *Mutate* the specified node in-place to have the
    1146             :   /// specified operands.  If the resultant node already exists in the DAG,
    1147         218 :   /// this does not modify the specified node, instead it returns the node that
    1148             :   /// already exists.  If the resultant node does not exist in the DAG, the
    1149             :   /// input node is returned.  As a degenerate case, if you specify the same
    1150             :   /// input operands as the node already has, the input node is returned.
    1151             :   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
    1152             :   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
    1153             :   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
    1154             :                                SDValue Op3);
    1155         218 :   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
    1156             :                                SDValue Op3, SDValue Op4);
    1157             :   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
    1158             :                                SDValue Op3, SDValue Op4, SDValue Op5);
    1159             :   SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
    1160             : 
    1161             :   /// *Mutate* the specified machine node's memory references to the provided
    1162             :   /// list.
    1163             :   void setNodeMemRefs(MachineSDNode *N,
    1164             :                       ArrayRef<MachineMemOperand *> NewMemRefs);
    1165             : 
    1166             :   // Propagates the change in divergence to users
    1167             :   void updateDivergence(SDNode * N);
    1168             : 
    1169             :   /// These are used for target selectors to *mutate* the
    1170             :   /// specified node to have the specified return type, Target opcode, and
    1171             :   /// operands.  Note that target opcodes are stored as
    1172             :   /// ~TargetOpcode in the node opcode field.  The resultant node is returned.
    1173             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT);
    1174             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, SDValue Op1);
    1175             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
    1176             :                        SDValue Op1, SDValue Op2);
    1177             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
    1178             :                        SDValue Op1, SDValue Op2, SDValue Op3);
    1179             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
    1180             :                        ArrayRef<SDValue> Ops);
    1181             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, EVT VT2);
    1182             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
    1183             :                        EVT VT2, ArrayRef<SDValue> Ops);
    1184             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
    1185             :                        EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
    1186             :   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
    1187             :                        EVT VT2, SDValue Op1);
    1188             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
    1189             :                        EVT VT2, SDValue Op1, SDValue Op2);
    1190             :   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, SDVTList VTs,
    1191             :                        ArrayRef<SDValue> Ops);
    1192             : 
    1193             :   /// This *mutates* the specified node to have the specified
    1194             :   /// return type, opcode, and operands.
    1195             :   SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
    1196             :                       ArrayRef<SDValue> Ops);
    1197             : 
    1198             :   /// Mutate the specified strict FP node to its non-strict equivalent,
    1199             :   /// unlinking the node from its chain and dropping the metadata arguments.
    1200             :   /// The node must be a strict FP node.
    1201             :   SDNode *mutateStrictFPToFP(SDNode *Node);
    1202             : 
    1203             :   /// These are used for target selectors to create a new node
    1204             :   /// with specified return type(s), MachineInstr opcode, and operands.
    1205             :   ///
    1206             :   /// Note that getMachineNode returns the resultant node.  If there is already
    1207             :   /// a node of the specified opcode and operands, it returns that node instead
    1208             :   /// of the current one.
    1209             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT);
    1210             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
    1211             :                                 SDValue Op1);
    1212             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
    1213             :                                 SDValue Op1, SDValue Op2);
    1214             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
    1215             :                                 SDValue Op1, SDValue Op2, SDValue Op3);
    1216             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
    1217             :                                 ArrayRef<SDValue> Ops);
    1218             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
    1219             :                                 EVT VT2, SDValue Op1, SDValue Op2);
    1220             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
    1221             :                                 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
    1222             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
    1223             :                                 EVT VT2, ArrayRef<SDValue> Ops);
    1224             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
    1225             :                                 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2);
    1226             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
    1227             :                                 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2,
    1228             :                                 SDValue Op3);
    1229             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
    1230             :                                 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
    1231             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl,
    1232             :                                 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops);
    1233             :   MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, SDVTList VTs,
    1234             :                                 ArrayRef<SDValue> Ops);
    1235             : 
    1236             :   /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
    1237             :   SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT,
    1238             :                                  SDValue Operand);
    1239             : 
    1240             :   /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes.
    1241             :   SDValue getTargetInsertSubreg(int SRIdx, const SDLoc &DL, EVT VT,
    1242             :                                 SDValue Operand, SDValue Subreg);
    1243             : 
    1244             :   /// Get the specified node if it's already available, or else return NULL.
    1245             :   SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTList, ArrayRef<SDValue> Ops,
    1246             :                           const SDNodeFlags Flags = SDNodeFlags());
    1247             : 
    1248             :   /// Creates a SDDbgValue node.
    1249             :   SDDbgValue *getDbgValue(DIVariable *Var, DIExpression *Expr, SDNode *N,
    1250             :                           unsigned R, bool IsIndirect, const DebugLoc &DL,
    1251             :                           unsigned O);
    1252             : 
    1253             :   /// Creates a constant SDDbgValue node.
    1254             :   SDDbgValue *getConstantDbgValue(DIVariable *Var, DIExpression *Expr,
    1255             :                                   const Value *C, const DebugLoc &DL,
    1256             :                                   unsigned O);
    1257             : 
    1258             :   /// Creates a FrameIndex SDDbgValue node.
    1259             :   SDDbgValue *getFrameIndexDbgValue(DIVariable *Var, DIExpression *Expr,
    1260             :                                     unsigned FI, bool IsIndirect,
    1261             :                                     const DebugLoc &DL, unsigned O);
    1262             : 
    1263             :   /// Creates a VReg SDDbgValue node.
    1264             :   SDDbgValue *getVRegDbgValue(DIVariable *Var, DIExpression *Expr,
    1265             :                               unsigned VReg, bool IsIndirect,
    1266             :                               const DebugLoc &DL, unsigned O);
    1267             : 
    1268             :   /// Creates a SDDbgLabel node.
    1269             :   SDDbgLabel *getDbgLabel(DILabel *Label, const DebugLoc &DL, unsigned O);
    1270             : 
    1271             :   /// Transfer debug values from one node to another, while optionally
    1272             :   /// generating fragment expressions for split-up values. If \p InvalidateDbg
    1273             :   /// is set, debug values are invalidated after they are transferred.
    1274             :   void transferDbgValues(SDValue From, SDValue To, unsigned OffsetInBits = 0,
    1275             :                          unsigned SizeInBits = 0, bool InvalidateDbg = true);
    1276             : 
    1277             :   /// Remove the specified node from the system. If any of its
    1278             :   /// operands then becomes dead, remove them as well. Inform UpdateListener
    1279             :   /// for each node deleted.
    1280             :   void RemoveDeadNode(SDNode *N);
    1281             : 
    1282             :   /// This method deletes the unreachable nodes in the
    1283             :   /// given list, and any nodes that become unreachable as a result.
    1284             :   void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
    1285             : 
    1286             :   /// Modify anything using 'From' to use 'To' instead.
    1287             :   /// This can cause recursive merging of nodes in the DAG.  Use the first
    1288             :   /// version if 'From' is known to have a single result, use the second
    1289             :   /// if you have two nodes with identical results (or if 'To' has a superset
    1290             :   /// of the results of 'From'), use the third otherwise.
    1291             :   ///
    1292             :   /// These methods all take an optional UpdateListener, which (if not null) is
    1293             :   /// informed about nodes that are deleted and modified due to recursive
    1294             :   /// changes in the dag.
    1295             :   ///
    1296             :   /// These functions only replace all existing uses. It's possible that as
    1297             :   /// these replacements are being performed, CSE may cause the From node
    1298             :   /// to be given new uses. These new uses of From are left in place, and
    1299             :   /// not automatically transferred to To.
    1300             :   ///
    1301             :   void ReplaceAllUsesWith(SDValue From, SDValue To);
    1302             :   void ReplaceAllUsesWith(SDNode *From, SDNode *To);
    1303             :   void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
    1304             : 
    1305             :   /// Replace any uses of From with To, leaving
    1306             :   /// uses of other values produced by From.getNode() alone.
    1307             :   void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
    1308             : 
    1309             :   /// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
    1310             :   /// This correctly handles the case where
    1311             :   /// there is an overlap between the From values and the To values.
    1312             :   void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
    1313             :                                   unsigned Num);
    1314             : 
    1315             :   /// If an existing load has uses of its chain, create a token factor node with
    1316             :   /// that chain and the new memory node's chain and update users of the old
    1317             :   /// chain to the token factor. This ensures that the new memory node will have
    1318             :   /// the same relative memory dependency position as the old load. Returns the
    1319             :   /// new merged load chain.
    1320             :   SDValue makeEquivalentMemoryOrdering(LoadSDNode *Old, SDValue New);
    1321             : 
    1322             :   /// Topological-sort the AllNodes list and a
    1323             :   /// assign a unique node id for each node in the DAG based on their
    1324             :   /// topological order. Returns the number of nodes.
    1325             :   unsigned AssignTopologicalOrder();
    1326             : 
    1327             :   /// Move node N in the AllNodes list to be immediately
    1328             :   /// before the given iterator Position. This may be used to update the
    1329             :   /// topological ordering when the list of nodes is modified.
    1330           0 :   void RepositionNode(allnodes_iterator Position, SDNode *N) {
    1331             :     AllNodes.insert(Position, AllNodes.remove(N));
    1332           0 :   }
    1333             : 
    1334             :   /// Returns an APFloat semantics tag appropriate for the given type. If VT is
    1335             :   /// a vector type, the element semantics are returned.
    1336          65 :   static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
    1337          65 :     switch (VT.getScalarType().getSimpleVT().SimpleTy) {
    1338           0 :     default: llvm_unreachable("Unknown FP format");
    1339          12 :     case MVT::f16:     return APFloat::IEEEhalf();
    1340          32 :     case MVT::f32:     return APFloat::IEEEsingle();
    1341          19 :     case MVT::f64:     return APFloat::IEEEdouble();
    1342           0 :     case MVT::f80:     return APFloat::x87DoubleExtended();
    1343           2 :     case MVT::f128:    return APFloat::IEEEquad();
    1344           0 :     case MVT::ppcf128: return APFloat::PPCDoubleDouble();
    1345             :     }
    1346       11760 :   }
    1347       11760 : 
    1348           0 :   /// Add a dbg_value SDNode. If SD is non-null that means the
    1349         199 :   /// value is produced by SD.
    1350        6961 :   void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
    1351        4424 : 
    1352         146 :   /// Add a dbg_label SDNode.
    1353          28 :   void AddDbgLabel(SDDbgLabel *DB);
    1354           2 : 
    1355             :   /// Get the debug values which reference the given SDNode.
    1356           0 :   ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) const {
    1357       16011 :     return DbgInfo->getSDDbgValues(SD);
    1358             :   }
    1359             : 
    1360             : public:
    1361             :   /// Return true if there are any SDDbgValue nodes associated
    1362             :   /// with this SelectionDAG.
    1363     1269035 :   bool hasDebugValues() const { return !DbgInfo->empty(); }
    1364             : 
    1365           0 :   SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
    1366           0 :   SDDbgInfo::DbgIterator DbgEnd()   { return DbgInfo->DbgEnd(); }
    1367             : 
    1368           0 :   SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
    1369           0 :     return DbgInfo->ByvalParmDbgBegin();
    1370             :   }
    1371             : 
    1372           0 :   SDDbgInfo::DbgIterator ByvalParmDbgEnd()   {
    1373           0 :     return DbgInfo->ByvalParmDbgEnd();
    1374             :   }
    1375             : 
    1376           0 :   SDDbgInfo::DbgLabelIterator DbgLabelBegin() {
    1377           0 :     return DbgInfo->DbgLabelBegin();
    1378             :   }
    1379           0 :   SDDbgInfo::DbgLabelIterator DbgLabelEnd() {
    1380           0 :     return DbgInfo->DbgLabelEnd();
    1381             :   }
    1382             : 
    1383             :   /// To be invoked on an SDNode that is slated to be erased. This
    1384             :   /// function mirrors \c llvm::salvageDebugInfo.
    1385             :   void salvageDebugInfo(SDNode &N);
    1386             : 
    1387             :   void dump() const;
    1388             : 
    1389             :   /// Create a stack temporary, suitable for holding the specified value type.
    1390             :   /// If minAlign is specified, the slot size will have at least that alignment.
    1391             :   SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
    1392             : 
    1393             :   /// Create a stack temporary suitable for holding either of the specified
    1394             :   /// value types.
    1395             :   SDValue CreateStackTemporary(EVT VT1, EVT VT2);
    1396             : 
    1397             :   SDValue FoldSymbolOffset(unsigned Opcode, EVT VT,
    1398             :                            const GlobalAddressSDNode *GA,
    1399             :                            const SDNode *N2);
    1400             : 
    1401             :   SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
    1402             :                                  SDNode *Cst1, SDNode *Cst2);
    1403             : 
    1404             :   SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
    1405             :                                  const ConstantSDNode *Cst1,
    1406             :                                  const ConstantSDNode *Cst2);
    1407             : 
    1408             :   SDValue FoldConstantVectorArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
    1409             :                                        ArrayRef<SDValue> Ops,
    1410             :                                        const SDNodeFlags Flags = SDNodeFlags());
    1411             : 
    1412             :   /// Constant fold a setcc to true or false.
    1413             :   SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond,
    1414             :                     const SDLoc &dl);
    1415             : 
    1416             :   /// See if the specified operand can be simplified with the knowledge that only
    1417             :   /// the bits specified by Mask are used.  If so, return the simpler operand,
    1418             :   /// otherwise return a null SDValue.
    1419             :   ///
    1420             :   /// (This exists alongside SimplifyDemandedBits because GetDemandedBits can
    1421             :   /// simplify nodes with multiple uses more aggressively.)
    1422             :   SDValue GetDemandedBits(SDValue V, const APInt &Mask);
    1423             : 
    1424             :   /// Return true if the sign bit of Op is known to be zero.
    1425             :   /// We use this predicate to simplify operations downstream.
    1426             :   bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
    1427             : 
    1428             :   /// Return true if 'Op & Mask' is known to be zero.  We
    1429             :   /// use this predicate to simplify operations downstream.  Op and Mask are
    1430             :   /// known to be the same type.
    1431             :   bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
    1432             :     const;
    1433             : 
    1434             :   /// Determine which bits of Op are known to be either zero or one and return
    1435             :   /// them in Known. For vectors, the known bits are those that are shared by
    1436             :   /// every vector element.
    1437             :   /// Targets can implement the computeKnownBitsForTargetNode method in the
    1438             :   /// TargetLowering class to allow target nodes to be understood.
    1439             :   KnownBits computeKnownBits(SDValue Op, unsigned Depth = 0) const;
    1440             : 
    1441             :   /// Determine which bits of Op are known to be either zero or one and return
    1442             :   /// them in Known. The DemandedElts argument allows us to only collect the
    1443             :   /// known bits that are shared by the requested vector elements.
    1444             :   /// Targets can implement the computeKnownBitsForTargetNode method in the
    1445             :   /// TargetLowering class to allow target nodes to be understood.
    1446             :   KnownBits computeKnownBits(SDValue Op, const APInt &DemandedElts,
    1447             :                              unsigned Depth = 0) const;
    1448             : 
    1449             :   /// \copydoc SelectionDAG::computeKnownBits(SDValue,unsigned)
    1450       21874 :   void computeKnownBits(SDValue Op, KnownBits &Known,
    1451             :                         unsigned Depth = 0) const {
    1452       21874 :     Known = computeKnownBits(Op, Depth);
    1453       21874 :   }
    1454             : 
    1455             :   /// \copydoc SelectionDAG::computeKnownBits(SDValue,const APInt&,unsigned)
    1456        4539 :   void computeKnownBits(SDValue Op, KnownBits &Known, const APInt &DemandedElts,
    1457             :                         unsigned Depth = 0) const {
    1458        4539 :     Known = computeKnownBits(Op, DemandedElts, Depth);
    1459        4539 :   }
    1460     9674898 : 
    1461             :   /// Used to represent the possible overflow behavior of an operation.
    1462     9674898 :   /// Never: the operation cannot overflow.
    1463     9674898 :   /// Always: the operation will always overflow.
    1464             :   /// Sometime: the operation may or may not overflow.
    1465             :   enum OverflowKind {
    1466             :     OFK_Never,
    1467             :     OFK_Sometime,
    1468             :     OFK_Always,
    1469             :   };
    1470             : 
    1471             :   /// Determine if the result of the addition of 2 node can overflow.
    1472             :   OverflowKind computeOverflowKind(SDValue N0, SDValue N1) const;
    1473             : 
    1474             :   /// Test if the given value is known to have exactly one bit set. This differs
    1475             :   /// from computeKnownBits in that it doesn't necessarily determine which bit
    1476             :   /// is set.
    1477             :   bool isKnownToBeAPowerOfTwo(SDValue Val) const;
    1478             : 
    1479             :   /// Return the number of times the sign bit of the register is replicated into
    1480             :   /// the other bits. We know that at least 1 bit is always equal to the sign
    1481             :   /// bit (itself), but other cases can give us information. For example,
    1482             :   /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
    1483             :   /// to each other, so we return 3. Targets can implement the
    1484             :   /// ComputeNumSignBitsForTarget method in the TargetLowering class to allow
    1485             :   /// target nodes to be understood.
    1486             :   unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
    1487             : 
    1488             :   /// Return the number of times the sign bit of the register is replicated into
    1489             :   /// the other bits. We know that at least 1 bit is always equal to the sign
    1490             :   /// bit (itself), but other cases can give us information. For example,
    1491             :   /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
    1492             :   /// to each other, so we return 3. The DemandedElts argument allows
    1493             :   /// us to only collect the minimum sign bits of the requested vector elements.
    1494             :   /// Targets can implement the ComputeNumSignBitsForTarget method in the
    1495             :   /// TargetLowering class to allow target nodes to be understood.
    1496             :   unsigned ComputeNumSignBits(SDValue Op, const APInt &DemandedElts,
    1497             :                               unsigned Depth = 0) const;
    1498             : 
    1499             :   /// Return true if the specified operand is an ISD::ADD with a ConstantSDNode
    1500             :   /// on the right-hand side, or if it is an ISD::OR with a ConstantSDNode that
    1501             :   /// is guaranteed to have the same semantics as an ADD. This handles the
    1502             :   /// equivalence:
    1503             :   ///     X|Cst == X+Cst iff X&Cst = 0.
    1504             :   bool isBaseWithConstantOffset(SDValue Op) const;
    1505             : 
    1506             :   /// Test whether the given SDValue is known to never be NaN. If \p SNaN is
    1507             :   /// true, returns if \p Op is known to never be a signaling NaN (it may still
    1508             :   /// be a qNaN).
    1509             :   bool isKnownNeverNaN(SDValue Op, bool SNaN = false, unsigned Depth = 0) const;
    1510             : 
    1511             :   /// \returns true if \p Op is known to never be a signaling NaN.
    1512             :   bool isKnownNeverSNaN(SDValue Op, unsigned Depth = 0) const {
    1513         463 :     return isKnownNeverNaN(Op, true, Depth);
    1514             :   }
    1515             : 
    1516             :   /// Test whether the given floating point SDValue is known to never be
    1517             :   /// positive or negative zero.
    1518             :   bool isKnownNeverZeroFloat(SDValue Op) const;
    1519             : 
    1520             :   /// Test whether the given SDValue is known to contain non-zero value(s).
    1521             :   bool isKnownNeverZero(SDValue Op) const;
    1522         788 : 
    1523             :   /// Test whether two SDValues are known to compare equal. This
    1524         788 :   /// is true if they are the same value, or if one is negative zero and the
    1525         788 :   /// other positive zero.
    1526             :   bool isEqualTo(SDValue A, SDValue B) const;
    1527             : 
    1528      253551 :   /// Return true if A and B have no common bits set. As an example, this can
    1529             :   /// allow an 'add' to be transformed into an 'or'.
    1530      253551 :   bool haveNoCommonBitsSet(SDValue A, SDValue B) const;
    1531      253551 : 
    1532           0 :   /// Match a binop + shuffle pyramid that represents a horizontal reduction
    1533           0 :   /// over the elements of a vector starting from the EXTRACT_VECTOR_ELT node /p
    1534           0 :   /// Extract. The reduction must use one of the opcodes listed in /p
    1535           0 :   /// CandidateBinOps and on success /p BinOp will contain the matching opcode.
    1536           0 :   /// Returns the vector that is being reduced on, or SDValue() if a reduction
    1537           0 :   /// was not matched.
    1538           0 :   SDValue matchBinOpReduction(SDNode *Extract, ISD::NodeType &BinOp,
    1539             :                               ArrayRef<ISD::NodeType> CandidateBinOps);
    1540             : 
    1541             :   /// Utility function used by legalize and lowering to
    1542             :   /// "unroll" a vector operation by splitting out the scalars and operating
    1543             :   /// on each element individually.  If the ResNE is 0, fully unroll the vector
    1544             :   /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
    1545             :   /// If the  ResNE is greater than the width of the vector op, unroll the
    1546             :   /// vector op and fill the end of the resulting vector with UNDEFS.
    1547             :   SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
    1548             : 
    1549             :   /// Return true if loads are next to each other and can be
    1550           0 :   /// merged. Check that both are nonvolatile and if LD is loading
    1551       11322 :   /// 'Bytes' bytes from a location that is 'Dist' units away from the
    1552             :   /// location that the 'Base' load is loading from.
    1553             :   bool areNonVolatileConsecutiveLoads(LoadSDNode *LD, LoadSDNode *Base,
    1554             :                                       unsigned Bytes, int Dist) const;
    1555             : 
    1556             :   /// Infer alignment of a load / store address. Return 0 if
    1557             :   /// it cannot be inferred.
    1558             :   unsigned InferPtrAlignment(SDValue Ptr) const;
    1559             : 
    1560             :   /// Compute the VTs needed for the low/hi parts of a type
    1561             :   /// which is split (or expanded) into two not necessarily identical pieces.
    1562             :   std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
    1563             : 
    1564             :   /// Split the vector with EXTRACT_SUBVECTOR using the provides
    1565             :   /// VTs and return the low/high part.
    1566             :   std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
    1567             :                                           const EVT &LoVT, const EVT &HiVT);
    1568             : 
    1569             :   /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part.
    1570        6073 :   std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
    1571        6073 :     EVT LoVT, HiVT;
    1572       12146 :     std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
    1573        6073 :     return SplitVector(N, DL, LoVT, HiVT);
    1574             :   }
    1575             : 
    1576             :   /// Split the node's operand with EXTRACT_SUBVECTOR and
    1577             :   /// return the low/high part.
    1578        5259 :   std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
    1579             :   {
    1580       10802 :     return SplitVector(N->getOperand(OpNo), SDLoc(N));
    1581         284 :   }
    1582         568 : 
    1583         284 :   /// Append the extracted elements from Start to Count out of the vector Op
    1584             :   /// in Args. If Count is 0, all of the elements will be extracted.
    1585             :   void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
    1586             :                              unsigned Start = 0, unsigned Count = 0);
    1587             : 
    1588          38 :   /// Compute the default alignment value for the given type.
    1589             :   unsigned getEVTAlignment(EVT MemoryVT) const;
    1590          76 : 
    1591             :   /// Test whether the given value is a constant int or similar node.
    1592             :   SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N);
    1593             : 
    1594             :   /// Test whether the given value is a constant FP or similar node.
    1595             :   SDNode *isConstantFPBuildVectorOrConstantFP(SDValue N);
    1596             : 
    1597             :   /// \returns true if \p N is any kind of constant or build_vector of
    1598             :   /// constants, int or float. If a vector, it may not necessarily be a splat.
    1599        8100 :   inline bool isConstantValueOfAnyType(SDValue N) {
    1600       14262 :     return isConstantIntBuildVectorOrConstantInt(N) ||
    1601        6162 :            isConstantFPBuildVectorOrConstantFP(N);
    1602             :   }
    1603             : 
    1604             : private:
    1605             :   void InsertNode(SDNode *N);
    1606             :   bool RemoveNodeFromCSEMaps(SDNode *N);
    1607             :   void AddModifiedNodeToCSEMaps(SDNode *N);
    1608             :   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
    1609             :   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
    1610             :                                void *&InsertPos);
    1611             :   SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
    1612             :                                void *&InsertPos);
    1613             :   SDNode *UpdateSDLocOnMergeSDNode(SDNode *N, const SDLoc &loc);
    1614             : 
    1615             :   void DeleteNodeNotInCSEMaps(SDNode *N);
    1616             :   void DeallocateNode(SDNode *N);
    1617             : 
    1618             :   void allnodes_clear();
    1619             : 
    1620             :   /// Look up the node specified by ID in CSEMap.  If it exists, return it.  If
    1621             :   /// not, return the insertion token that will make insertion faster.  This
    1622             :   /// overload is for nodes other than Constant or ConstantFP, use the other one
    1623             :   /// for those.
    1624             :   SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
    1625             : 
    1626             :   /// Look up the node specified by ID in CSEMap.  If it exists, return it.  If
    1627             :   /// not, return the insertion token that will make insertion faster.  Performs
    1628             :   /// additional processing for constant nodes.
    1629             :   SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, const SDLoc &DL,
    1630             :                               void *&InsertPos);
    1631             : 
    1632             :   /// List of non-single value types.
    1633             :   FoldingSet<SDVTListNode> VTListMap;
    1634             : 
    1635             :   /// Maps to auto-CSE operations.
    1636             :   std::vector<CondCodeSDNode*> CondCodeNodes;
    1637             : 
    1638             :   std::vector<SDNode*> ValueTypeNodes;
    1639             :   std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
    1640             :   StringMap<SDNode*> ExternalSymbols;
    1641             : 
    1642         126 :   std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
    1643         126 :   DenseMap<MCSymbol *, SDNode *> MCSymbols;
    1644      257286 : };
    1645         126 : 
    1646      257034 : template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
    1647      257034 :   using nodes_iterator = pointer_iterator<SelectionDAG::allnodes_iterator>;
    1648             : 
    1649             :   static nodes_iterator nodes_begin(SelectionDAG *G) {
    1650          64 :     return nodes_iterator(G->allnodes_begin());
    1651             :   }
    1652         128 : 
    1653             :   static nodes_iterator nodes_end(SelectionDAG *G) {
    1654             :     return nodes_iterator(G->allnodes_end());
    1655             :   }
    1656             : };
    1657             : 
    1658             : template <class TargetMemSDNode>
    1659             : SDValue SelectionDAG::getTargetMemSDNode(SDVTList VTs,
    1660             :                                          ArrayRef<SDValue> Ops,
    1661             :                                          const SDLoc &dl, EVT MemVT,
    1662             :                                          MachineMemOperand *MMO) {
    1663             :   /// Compose node ID and try to find an existing node.
    1664             :   FoldingSetNodeID ID;
    1665             :   unsigned Opcode =
    1666             :     TargetMemSDNode(dl.getIROrder(), DebugLoc(), VTs, MemVT, MMO).getOpcode();
    1667             :   ID.AddInteger(Opcode);
    1668             :   ID.AddPointer(VTs.VTs);
    1669             :   for (auto& Op : Ops) {
    1670             :     ID.AddPointer(Op.getNode());
    1671             :     ID.AddInteger(Op.getResNo());
    1672             :   }
    1673             :   ID.AddInteger(MemVT.getRawBits());
    1674             :   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
    1675             :   ID.AddInteger(getSyntheticNodeSubclassData<TargetMemSDNode>(
    1676             :     dl.getIROrder(), VTs, MemVT, MMO));
    1677             : 
    1678             :   void *IP = nullptr;
    1679             :   if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP)) {
    1680             :     cast<TargetMemSDNode>(E)->refineAlignment(MMO);
    1681             :     return SDValue(E, 0);
    1682             :   }
    1683             : 
    1684             :   /// Existing node was not found. Create a new one.
    1685             :   auto *N = newSDNode<TargetMemSDNode>(dl.getIROrder(), dl.getDebugLoc(), VTs,
    1686             :                                        MemVT, MMO);
    1687             :   createOperands(N, Ops);
    1688             :   CSEMap.InsertNode(N, IP);
    1689             :   InsertNode(N);
    1690             :   return SDValue(N, 0);
    1691             : }
    1692             : 
    1693             : } // end namespace llvm
    1694             : 
    1695             : #endif // LLVM_CODEGEN_SELECTIONDAG_H

Generated by: LCOV version 1.13