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