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