1 //===- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ----------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file declares the SelectionDAG class, and transitively defines the
10 // SDNode class and subclasses.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
15 #define LLVM_CODEGEN_SELECTIONDAG_H
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"
28 #include "llvm/ADT/iterator_range.h"
29 #include "llvm/CodeGen/DAGCombine.h"
30 #include "llvm/CodeGen/FunctionLoweringInfo.h"
31 #include "llvm/CodeGen/ISDOpcodes.h"
32 #include "llvm/CodeGen/MachineFunction.h"
33 #include "llvm/CodeGen/MachineMemOperand.h"
34 #include "llvm/CodeGen/SelectionDAGNodes.h"
35 #include "llvm/CodeGen/ValueTypes.h"
36 #include "llvm/IR/DebugLoc.h"
37 #include "llvm/IR/Instructions.h"
38 #include "llvm/IR/Metadata.h"
39 #include "llvm/Support/Allocator.h"
40 #include "llvm/Support/ArrayRecycler.h"
41 #include "llvm/Support/AtomicOrdering.h"
42 #include "llvm/Support/Casting.h"
43 #include "llvm/Support/CodeGen.h"
44 #include "llvm/Support/ErrorHandling.h"
45 #include "llvm/Support/MachineValueType.h"
46 #include "llvm/Support/RecyclingAllocator.h"
61 class BlockFrequencyInfo;
69 class LegacyDivergenceAnalysis;
71 class MachineBasicBlock;
72 class MachineConstantPoolValue;
74 class OptimizationRemarkEmitter;
75 class ProfileSummaryInfo;
79 class SelectionDAGTargetInfo;
80 class TargetLibraryInfo;
83 class TargetSubtargetInfo;
86 class SDVTListNode : public FoldingSetNode {
87 friend struct FoldingSetTrait<SDVTListNode>;
89 /// A reference to an Interned FoldingSetNodeID for this node.
90 /// The Allocator in SelectionDAG holds the data.
91 /// SDVTList contains all types which are frequently accessed in SelectionDAG.
92 /// The size of this list is not expected to be big so it won't introduce
94 FoldingSetNodeIDRef FastID;
97 /// The hash value for SDVTList is fixed, so cache it to avoid
102 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
103 FastID(ID), VTs(VT), NumVTs(Num) {
104 HashValue = ID.ComputeHash();
107 SDVTList getSDVTList() {
108 SDVTList result = {VTs, NumVTs};
113 /// Specialize FoldingSetTrait for SDVTListNode
114 /// to avoid computing temp FoldingSetNodeID and hash value.
115 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
116 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
120 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
121 unsigned IDHash, FoldingSetNodeID &TempID) {
122 if (X.HashValue != IDHash)
124 return ID == X.FastID;
127 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
132 template <> struct ilist_alloc_traits<SDNode> {
133 static void deleteNode(SDNode *) {
134 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
138 /// Keeps track of dbg_value information through SDISel. We do
139 /// not build SDNodes for these so as not to perturb the generated code;
140 /// instead the info is kept off to the side in this structure. Each SDNode may
141 /// have one or more associated dbg_value entries. This information is kept in
143 /// Byval parameters are handled separately because they don't use alloca's,
144 /// which busts the normal mechanism. There is good reason for handling all
145 /// parameters separately: they may not have code generated for them, they
146 /// should always go at the beginning of the function regardless of other code
147 /// motion, and debug info for them is potentially useful even if the parameter
148 /// is unused. Right now only byval parameters are handled separately.
150 BumpPtrAllocator Alloc;
151 SmallVector<SDDbgValue*, 32> DbgValues;
152 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
153 SmallVector<SDDbgLabel*, 4> DbgLabels;
154 using DbgValMapType = DenseMap<const SDNode *, SmallVector<SDDbgValue *, 2>>;
155 DbgValMapType DbgValMap;
158 SDDbgInfo() = default;
159 SDDbgInfo(const SDDbgInfo &) = delete;
160 SDDbgInfo &operator=(const SDDbgInfo &) = delete;
162 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
164 ByvalParmDbgValues.push_back(V);
165 } else DbgValues.push_back(V);
167 DbgValMap[Node].push_back(V);
170 void add(SDDbgLabel *L) {
171 DbgLabels.push_back(L);
174 /// Invalidate all DbgValues attached to the node and remove
175 /// it from the Node-to-DbgValues map.
176 void erase(const SDNode *Node);
181 ByvalParmDbgValues.clear();
186 BumpPtrAllocator &getAlloc() { return Alloc; }
189 return DbgValues.empty() && ByvalParmDbgValues.empty() && DbgLabels.empty();
192 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) const {
193 auto I = DbgValMap.find(Node);
194 if (I != DbgValMap.end())
196 return ArrayRef<SDDbgValue*>();
199 using DbgIterator = SmallVectorImpl<SDDbgValue*>::iterator;
200 using DbgLabelIterator = SmallVectorImpl<SDDbgLabel*>::iterator;
202 DbgIterator DbgBegin() { return DbgValues.begin(); }
203 DbgIterator DbgEnd() { return DbgValues.end(); }
204 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
205 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
206 DbgLabelIterator DbgLabelBegin() { return DbgLabels.begin(); }
207 DbgLabelIterator DbgLabelEnd() { return DbgLabels.end(); }
210 void checkForCycles(const SelectionDAG *DAG, bool force = false);
212 /// This is used to represent a portion of an LLVM function in a low-level
213 /// Data Dependence DAG representation suitable for instruction selection.
214 /// This DAG is constructed as the first step of instruction selection in order
215 /// to allow implementation of machine specific optimizations
216 /// and code simplifications.
218 /// The representation used by the SelectionDAG is a target-independent
219 /// representation, which has some similarities to the GCC RTL representation,
220 /// but is significantly more simple, powerful, and is a graph form instead of a
224 const TargetMachine &TM;
225 const SelectionDAGTargetInfo *TSI = nullptr;
226 const TargetLowering *TLI = nullptr;
227 const TargetLibraryInfo *LibInfo = nullptr;
229 Pass *SDAGISelPass = nullptr;
230 LLVMContext *Context;
231 CodeGenOpt::Level OptLevel;
233 LegacyDivergenceAnalysis * DA = nullptr;
234 FunctionLoweringInfo * FLI = nullptr;
236 /// The function-level optimization remark emitter. Used to emit remarks
237 /// whenever manipulating the DAG.
238 OptimizationRemarkEmitter *ORE;
240 ProfileSummaryInfo *PSI = nullptr;
241 BlockFrequencyInfo *BFI = nullptr;
243 /// The starting token.
246 /// The root of the entire DAG.
249 /// A linked list of nodes in the current DAG.
250 ilist<SDNode> AllNodes;
252 /// The AllocatorType for allocating SDNodes. We use
253 /// pool allocation with recycling.
254 using NodeAllocatorType = RecyclingAllocator<BumpPtrAllocator, SDNode,
255 sizeof(LargestSDNode),
256 alignof(MostAlignedSDNode)>;
258 /// Pool allocation for nodes.
259 NodeAllocatorType NodeAllocator;
261 /// This structure is used to memoize nodes, automatically performing
262 /// CSE with existing nodes when a duplicate is requested.
263 FoldingSet<SDNode> CSEMap;
265 /// Pool allocation for machine-opcode SDNode operands.
266 BumpPtrAllocator OperandAllocator;
267 ArrayRecycler<SDUse> OperandRecycler;
269 /// Pool allocation for misc. objects that are created once per SelectionDAG.
270 BumpPtrAllocator Allocator;
272 /// Tracks dbg_value and dbg_label information through SDISel.
275 using CallSiteInfo = MachineFunction::CallSiteInfo;
276 using CallSiteInfoImpl = MachineFunction::CallSiteInfoImpl;
278 struct CallSiteDbgInfo {
280 MDNode *HeapAllocSite = nullptr;
281 bool NoMerge = false;
284 DenseMap<const SDNode *, CallSiteDbgInfo> SDCallSiteDbgInfo;
286 uint16_t NextPersistentId = 0;
289 /// Clients of various APIs that cause global effects on
290 /// the DAG can optionally implement this interface. This allows the clients
291 /// to handle the various sorts of updates that happen.
293 /// A DAGUpdateListener automatically registers itself with DAG when it is
294 /// constructed, and removes itself when destroyed in RAII fashion.
295 struct DAGUpdateListener {
296 DAGUpdateListener *const Next;
299 explicit DAGUpdateListener(SelectionDAG &D)
300 : Next(D.UpdateListeners), DAG(D) {
301 DAG.UpdateListeners = this;
304 virtual ~DAGUpdateListener() {
305 assert(DAG.UpdateListeners == this &&
306 "DAGUpdateListeners must be destroyed in LIFO order");
307 DAG.UpdateListeners = Next;
310 /// The node N that was deleted and, if E is not null, an
311 /// equivalent node E that replaced it.
312 virtual void NodeDeleted(SDNode *N, SDNode *E);
314 /// The node N that was updated.
315 virtual void NodeUpdated(SDNode *N);
317 /// The node N that was inserted.
318 virtual void NodeInserted(SDNode *N);
321 struct DAGNodeDeletedListener : public DAGUpdateListener {
322 std::function<void(SDNode *, SDNode *)> Callback;
324 DAGNodeDeletedListener(SelectionDAG &DAG,
325 std::function<void(SDNode *, SDNode *)> Callback)
326 : DAGUpdateListener(DAG), Callback(std::move(Callback)) {}
328 void NodeDeleted(SDNode *N, SDNode *E) override { Callback(N, E); }
331 virtual void anchor();
334 /// When true, additional steps are taken to
335 /// ensure that getConstant() and similar functions return DAG nodes that
336 /// have legal types. This is important after type legalization since
337 /// any illegally typed nodes generated after this point will not experience
338 /// type legalization.
339 bool NewNodesMustHaveLegalTypes = false;
342 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
343 friend struct DAGUpdateListener;
345 /// Linked list of registered DAGUpdateListener instances.
346 /// This stack is maintained by DAGUpdateListener RAII.
347 DAGUpdateListener *UpdateListeners = nullptr;
349 /// Implementation of setSubgraphColor.
350 /// Return whether we had to truncate the search.
351 bool setSubgraphColorHelper(SDNode *N, const char *Color,
352 DenseSet<SDNode *> &visited,
353 int level, bool &printed);
355 template <typename SDNodeT, typename... ArgTypes>
356 SDNodeT *newSDNode(ArgTypes &&... Args) {
357 return new (NodeAllocator.template Allocate<SDNodeT>())
358 SDNodeT(std::forward<ArgTypes>(Args)...);
361 /// Build a synthetic SDNodeT with the given args and extract its subclass
362 /// data as an integer (e.g. for use in a folding set).
364 /// The args to this function are the same as the args to SDNodeT's
365 /// constructor, except the second arg (assumed to be a const DebugLoc&) is
367 template <typename SDNodeT, typename... ArgTypes>
368 static uint16_t getSyntheticNodeSubclassData(unsigned IROrder,
369 ArgTypes &&... Args) {
370 // The compiler can reduce this expression to a constant iff we pass an
371 // empty DebugLoc. Thankfully, the debug location doesn't have any bearing
372 // on the subclass data.
373 return SDNodeT(IROrder, DebugLoc(), std::forward<ArgTypes>(Args)...)
374 .getRawSubclassData();
377 template <typename SDNodeTy>
378 static uint16_t getSyntheticNodeSubclassData(unsigned Opc, unsigned Order,
379 SDVTList VTs, EVT MemoryVT,
380 MachineMemOperand *MMO) {
381 return SDNodeTy(Opc, Order, DebugLoc(), VTs, MemoryVT, MMO)
382 .getRawSubclassData();
385 void createOperands(SDNode *Node, ArrayRef<SDValue> Vals);
387 void removeOperands(SDNode *Node) {
388 if (!Node->OperandList)
390 OperandRecycler.deallocate(
391 ArrayRecycler<SDUse>::Capacity::get(Node->NumOperands),
393 Node->NumOperands = 0;
394 Node->OperandList = nullptr;
396 void CreateTopologicalOrder(std::vector<SDNode*>& Order);
399 // Maximum depth for recursive analysis such as computeKnownBits, etc.
400 static constexpr unsigned MaxRecursionDepth = 6;
402 explicit SelectionDAG(const TargetMachine &TM, CodeGenOpt::Level);
403 SelectionDAG(const SelectionDAG &) = delete;
404 SelectionDAG &operator=(const SelectionDAG &) = delete;
407 /// Prepare this SelectionDAG to process code in the given MachineFunction.
408 void init(MachineFunction &NewMF, OptimizationRemarkEmitter &NewORE,
409 Pass *PassPtr, const TargetLibraryInfo *LibraryInfo,
410 LegacyDivergenceAnalysis * Divergence,
411 ProfileSummaryInfo *PSIin, BlockFrequencyInfo *BFIin);
413 void setFunctionLoweringInfo(FunctionLoweringInfo * FuncInfo) {
417 /// Clear state and free memory necessary to make this
418 /// SelectionDAG ready to process a new block.
421 MachineFunction &getMachineFunction() const { return *MF; }
422 const Pass *getPass() const { return SDAGISelPass; }
424 const DataLayout &getDataLayout() const { return MF->getDataLayout(); }
425 const TargetMachine &getTarget() const { return TM; }
426 const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
427 const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
428 const TargetLibraryInfo &getLibInfo() const { return *LibInfo; }
429 const SelectionDAGTargetInfo &getSelectionDAGInfo() const { return *TSI; }
430 const LegacyDivergenceAnalysis *getDivergenceAnalysis() const { return DA; }
431 LLVMContext *getContext() const { return Context; }
432 OptimizationRemarkEmitter &getORE() const { return *ORE; }
433 ProfileSummaryInfo *getPSI() const { return PSI; }
434 BlockFrequencyInfo *getBFI() const { return BFI; }
436 /// Just dump dot graph to a user-provided path and title.
437 /// This doesn't open the dot viewer program and
438 /// helps visualization when outside debugging session.
439 /// FileName expects absolute path. If provided
440 /// without any path separators then the file
441 /// will be created in the current directory.
442 /// Error will be emitted if the path is insane.
443 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
444 LLVM_DUMP_METHOD void dumpDotGraph(const Twine &FileName, const Twine &Title);
447 /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
448 void viewGraph(const std::string &Title);
452 std::map<const SDNode *, std::string> NodeGraphAttrs;
455 /// Clear all previously defined node graph attributes.
456 /// Intended to be used from a debugging tool (eg. gdb).
457 void clearGraphAttrs();
459 /// Set graph attributes for a node. (eg. "color=red".)
460 void setGraphAttrs(const SDNode *N, const char *Attrs);
462 /// Get graph attributes for a node. (eg. "color=red".)
463 /// Used from getNodeAttributes.
464 const std::string getGraphAttrs(const SDNode *N) const;
466 /// Convenience for setting node color attribute.
467 void setGraphColor(const SDNode *N, const char *Color);
469 /// Convenience for setting subgraph color attribute.
470 void setSubgraphColor(SDNode *N, const char *Color);
472 using allnodes_const_iterator = ilist<SDNode>::const_iterator;
474 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
475 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
477 using allnodes_iterator = ilist<SDNode>::iterator;
479 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
480 allnodes_iterator allnodes_end() { return AllNodes.end(); }
482 ilist<SDNode>::size_type allnodes_size() const {
483 return AllNodes.size();
486 iterator_range<allnodes_iterator> allnodes() {
487 return make_range(allnodes_begin(), allnodes_end());
489 iterator_range<allnodes_const_iterator> allnodes() const {
490 return make_range(allnodes_begin(), allnodes_end());
493 /// Return the root tag of the SelectionDAG.
494 const SDValue &getRoot() const { return Root; }
496 /// Return the token chain corresponding to the entry of the function.
497 SDValue getEntryNode() const {
498 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
501 /// Set the current root tag of the SelectionDAG.
503 const SDValue &setRoot(SDValue N) {
504 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
505 "DAG root value is not a chain!");
507 checkForCycles(N.getNode(), this);
510 checkForCycles(this);
515 void VerifyDAGDiverence();
518 /// This iterates over the nodes in the SelectionDAG, folding
519 /// certain types of nodes together, or eliminating superfluous nodes. The
520 /// Level argument controls whether Combine is allowed to produce nodes and
521 /// types that are illegal on the target.
522 void Combine(CombineLevel Level, AAResults *AA,
523 CodeGenOpt::Level OptLevel);
525 /// This transforms the SelectionDAG into a SelectionDAG that
526 /// only uses types natively supported by the target.
527 /// Returns "true" if it made any changes.
529 /// Note that this is an involved process that may invalidate pointers into
531 bool LegalizeTypes();
533 /// This transforms the SelectionDAG into a SelectionDAG that is
534 /// compatible with the target instruction selector, as indicated by the
535 /// TargetLowering object.
537 /// Note that this is an involved process that may invalidate pointers into
541 /// Transforms a SelectionDAG node and any operands to it into a node
542 /// that is compatible with the target instruction selector, as indicated by
543 /// the TargetLowering object.
545 /// \returns true if \c N is a valid, legal node after calling this.
547 /// This essentially runs a single recursive walk of the \c Legalize process
548 /// over the given node (and its operands). This can be used to incrementally
549 /// legalize the DAG. All of the nodes which are directly replaced,
550 /// potentially including N, are added to the output parameter \c
551 /// UpdatedNodes so that the delta to the DAG can be understood by the
554 /// When this returns false, N has been legalized in a way that make the
555 /// pointer passed in no longer valid. It may have even been deleted from the
556 /// DAG, and so it shouldn't be used further. When this returns true, the
557 /// N passed in is a legal node, and can be immediately processed as such.
558 /// This may still have done some work on the DAG, and will still populate
559 /// UpdatedNodes with any new nodes replacing those originally in the DAG.
560 bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
562 /// This transforms the SelectionDAG into a SelectionDAG
563 /// that only uses vector math operations supported by the target. This is
564 /// necessary as a separate step from Legalize because unrolling a vector
565 /// operation can introduce illegal types, which requires running
566 /// LegalizeTypes again.
568 /// This returns true if it made any changes; in that case, LegalizeTypes
569 /// is called again before Legalize.
571 /// Note that this is an involved process that may invalidate pointers into
573 bool LegalizeVectors();
575 /// This method deletes all unreachable nodes in the SelectionDAG.
576 void RemoveDeadNodes();
578 /// Remove the specified node from the system. This node must
579 /// have no referrers.
580 void DeleteNode(SDNode *N);
582 /// Return an SDVTList that represents the list of values specified.
583 SDVTList getVTList(EVT VT);
584 SDVTList getVTList(EVT VT1, EVT VT2);
585 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
586 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
587 SDVTList getVTList(ArrayRef<EVT> VTs);
589 //===--------------------------------------------------------------------===//
590 // Node creation methods.
592 /// Create a ConstantSDNode wrapping a constant value.
593 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
595 /// If only legal types can be produced, this does the necessary
596 /// transformations (e.g., if the vector element type is illegal).
598 SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT,
599 bool isTarget = false, bool isOpaque = false);
600 SDValue getConstant(const APInt &Val, const SDLoc &DL, EVT VT,
601 bool isTarget = false, bool isOpaque = false);
603 SDValue getAllOnesConstant(const SDLoc &DL, EVT VT, bool IsTarget = false,
604 bool IsOpaque = false) {
605 return getConstant(APInt::getAllOnesValue(VT.getScalarSizeInBits()), DL,
606 VT, IsTarget, IsOpaque);
609 SDValue getConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
610 bool isTarget = false, bool isOpaque = false);
611 SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL,
612 bool isTarget = false);
613 SDValue getShiftAmountConstant(uint64_t Val, EVT VT, const SDLoc &DL,
614 bool LegalTypes = true);
615 SDValue getVectorIdxConstant(uint64_t Val, const SDLoc &DL,
616 bool isTarget = false);
618 SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT,
619 bool isOpaque = false) {
620 return getConstant(Val, DL, VT, true, isOpaque);
622 SDValue getTargetConstant(const APInt &Val, const SDLoc &DL, EVT VT,
623 bool isOpaque = false) {
624 return getConstant(Val, DL, VT, true, isOpaque);
626 SDValue getTargetConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
627 bool isOpaque = false) {
628 return getConstant(Val, DL, VT, true, isOpaque);
631 /// Create a true or false constant of type \p VT using the target's
632 /// BooleanContent for type \p OpVT.
633 SDValue getBoolConstant(bool V, const SDLoc &DL, EVT VT, EVT OpVT);
636 /// Create a ConstantFPSDNode wrapping a constant value.
637 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
639 /// If only legal types can be produced, this does the necessary
640 /// transformations (e.g., if the vector element type is illegal).
641 /// The forms that take a double should only be used for simple constants
642 /// that can be exactly represented in VT. No checks are made.
644 SDValue getConstantFP(double Val, const SDLoc &DL, EVT VT,
645 bool isTarget = false);
646 SDValue getConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT,
647 bool isTarget = false);
648 SDValue getConstantFP(const ConstantFP &V, const SDLoc &DL, EVT VT,
649 bool isTarget = false);
650 SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT) {
651 return getConstantFP(Val, DL, VT, true);
653 SDValue getTargetConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT) {
654 return getConstantFP(Val, DL, VT, true);
656 SDValue getTargetConstantFP(const ConstantFP &Val, const SDLoc &DL, EVT VT) {
657 return getConstantFP(Val, DL, VT, true);
661 SDValue getGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
662 int64_t offset = 0, bool isTargetGA = false,
663 unsigned TargetFlags = 0);
664 SDValue getTargetGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
665 int64_t offset = 0, unsigned TargetFlags = 0) {
666 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
668 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
669 SDValue getTargetFrameIndex(int FI, EVT VT) {
670 return getFrameIndex(FI, VT, true);
672 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
673 unsigned TargetFlags = 0);
674 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned TargetFlags = 0) {
675 return getJumpTable(JTI, VT, true, TargetFlags);
677 SDValue getConstantPool(const Constant *C, EVT VT, MaybeAlign Align = None,
678 int Offs = 0, bool isT = false,
679 unsigned TargetFlags = 0);
680 SDValue getTargetConstantPool(const Constant *C, EVT VT,
681 MaybeAlign Align = None, int Offset = 0,
682 unsigned TargetFlags = 0) {
683 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
685 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
686 MaybeAlign Align = None, int Offs = 0,
687 bool isT = false, unsigned TargetFlags = 0);
688 SDValue getTargetConstantPool(MachineConstantPoolValue *C, EVT VT,
689 MaybeAlign Align = None, int Offset = 0,
690 unsigned TargetFlags = 0) {
691 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
693 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
694 unsigned TargetFlags = 0);
695 // When generating a branch to a BB, we don't in general know enough
696 // to provide debug info for the BB at that time, so keep this one around.
697 SDValue getBasicBlock(MachineBasicBlock *MBB);
698 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
699 SDValue getExternalSymbol(const char *Sym, EVT VT);
700 SDValue getExternalSymbol(const char *Sym, const SDLoc &dl, EVT VT);
701 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
702 unsigned TargetFlags = 0);
703 SDValue getMCSymbol(MCSymbol *Sym, EVT VT);
705 SDValue getValueType(EVT);
706 SDValue getRegister(unsigned Reg, EVT VT);
707 SDValue getRegisterMask(const uint32_t *RegMask);
708 SDValue getEHLabel(const SDLoc &dl, SDValue Root, MCSymbol *Label);
709 SDValue getLabelNode(unsigned Opcode, const SDLoc &dl, SDValue Root,
711 SDValue getBlockAddress(const BlockAddress *BA, EVT VT, int64_t Offset = 0,
712 bool isTarget = false, unsigned TargetFlags = 0);
713 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
714 int64_t Offset = 0, unsigned TargetFlags = 0) {
715 return getBlockAddress(BA, VT, Offset, true, TargetFlags);
718 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg,
720 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
721 getRegister(Reg, N.getValueType()), N);
724 // This version of the getCopyToReg method takes an extra operand, which
725 // indicates that there is potentially an incoming glue value (if Glue is not
726 // null) and that there should be a glue result.
727 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N,
729 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
730 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
731 return getNode(ISD::CopyToReg, dl, VTs,
732 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
735 // Similar to last getCopyToReg() except parameter Reg is a SDValue
736 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, SDValue Reg, SDValue N,
738 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
739 SDValue Ops[] = { Chain, Reg, N, Glue };
740 return getNode(ISD::CopyToReg, dl, VTs,
741 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
744 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT) {
745 SDVTList VTs = getVTList(VT, MVT::Other);
746 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
747 return getNode(ISD::CopyFromReg, dl, VTs, Ops);
750 // This version of the getCopyFromReg method takes an extra operand, which
751 // indicates that there is potentially an incoming glue value (if Glue is not
752 // null) and that there should be a glue result.
753 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT,
755 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
756 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
757 return getNode(ISD::CopyFromReg, dl, VTs,
758 makeArrayRef(Ops, Glue.getNode() ? 3 : 2));
761 SDValue getCondCode(ISD::CondCode Cond);
763 /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT,
764 /// which must be a vector type, must match the number of mask elements
765 /// NumElts. An integer mask element equal to -1 is treated as undefined.
766 SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2,
769 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
770 /// which must be a vector type, must match the number of operands in Ops.
771 /// The operands must have the same type as (or, for integers, a type wider
772 /// than) VT's element type.
773 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDValue> Ops) {
774 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
775 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
778 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
779 /// which must be a vector type, must match the number of operands in Ops.
780 /// The operands must have the same type as (or, for integers, a type wider
781 /// than) VT's element type.
782 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDUse> Ops) {
783 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
784 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
787 /// Return a splat ISD::BUILD_VECTOR node, consisting of Op splatted to all
788 /// elements. VT must be a vector type. Op's type must be the same as (or,
789 /// for integers, a type wider than) VT's element type.
790 SDValue getSplatBuildVector(EVT VT, const SDLoc &DL, SDValue Op) {
791 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
792 if (Op.getOpcode() == ISD::UNDEF) {
793 assert((VT.getVectorElementType() == Op.getValueType() ||
795 VT.getVectorElementType().bitsLE(Op.getValueType()))) &&
796 "A splatted value must have a width equal or (for integers) "
797 "greater than the vector element type!");
798 return getNode(ISD::UNDEF, SDLoc(), VT);
801 SmallVector<SDValue, 16> Ops(VT.getVectorNumElements(), Op);
802 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
805 // Return a splat ISD::SPLAT_VECTOR node, consisting of Op splatted to all
807 SDValue getSplatVector(EVT VT, const SDLoc &DL, SDValue Op) {
808 if (Op.getOpcode() == ISD::UNDEF) {
809 assert((VT.getVectorElementType() == Op.getValueType() ||
811 VT.getVectorElementType().bitsLE(Op.getValueType()))) &&
812 "A splatted value must have a width equal or (for integers) "
813 "greater than the vector element type!");
814 return getNode(ISD::UNDEF, SDLoc(), VT);
816 return getNode(ISD::SPLAT_VECTOR, DL, VT, Op);
819 /// Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
820 /// the shuffle node in input but with swapped operands.
822 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
823 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
825 /// Convert Op, which must be of float type, to the
826 /// float type VT, by either extending or rounding (by truncation).
827 SDValue getFPExtendOrRound(SDValue Op, const SDLoc &DL, EVT VT);
829 /// Convert Op, which must be a STRICT operation of float type, to the
830 /// float type VT, by either extending or rounding (by truncation).
831 std::pair<SDValue, SDValue>
832 getStrictFPExtendOrRound(SDValue Op, SDValue Chain, const SDLoc &DL, EVT VT);
834 /// Convert Op, which must be of integer type, to the
835 /// integer type VT, by either any-extending or truncating it.
836 SDValue getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
838 /// Convert Op, which must be of integer type, to the
839 /// integer type VT, by either sign-extending or truncating it.
840 SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
842 /// Convert Op, which must be of integer type, to the
843 /// integer type VT, by either zero-extending or truncating it.
844 SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
846 /// Return the expression required to zero extend the Op
847 /// value assuming it was the smaller SrcTy value.
848 SDValue getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT VT);
850 /// Convert Op, which must be of integer type, to the integer type VT, by
851 /// either truncating it or performing either zero or sign extension as
852 /// appropriate extension for the pointer's semantics.
853 SDValue getPtrExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
855 /// Return the expression required to extend the Op as a pointer value
856 /// assuming it was the smaller SrcTy value. This may be either a zero extend
857 /// or a sign extend.
858 SDValue getPtrExtendInReg(SDValue Op, const SDLoc &DL, EVT VT);
860 /// Convert Op, which must be of integer type, to the integer type VT,
861 /// by using an extension appropriate for the target's
862 /// BooleanContent for type OpVT or truncating it.
863 SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT);
865 /// Create a bitwise NOT operation as (XOR Val, -1).
866 SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT);
868 /// Create a logical NOT operation as (XOR Val, BooleanOne).
869 SDValue getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT);
871 /// Returns sum of the base pointer and offset.
872 /// Unlike getObjectPtrOffset this does not set NoUnsignedWrap by default.
873 SDValue getMemBasePlusOffset(SDValue Base, int64_t Offset, const SDLoc &DL,
874 const SDNodeFlags Flags = SDNodeFlags());
875 SDValue getMemBasePlusOffset(SDValue Base, SDValue Offset, const SDLoc &DL,
876 const SDNodeFlags Flags = SDNodeFlags());
878 /// Create an add instruction with appropriate flags when used for
879 /// addressing some offset of an object. i.e. if a load is split into multiple
880 /// components, create an add nuw from the base pointer to the offset.
881 SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Ptr, int64_t Offset) {
883 Flags.setNoUnsignedWrap(true);
884 return getMemBasePlusOffset(Ptr, Offset, SL, Flags);
887 SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Ptr, SDValue Offset) {
888 // The object itself can't wrap around the address space, so it shouldn't be
889 // possible for the adds of the offsets to the split parts to overflow.
891 Flags.setNoUnsignedWrap(true);
892 return getMemBasePlusOffset(Ptr, Offset, SL, Flags);
895 /// Return a new CALLSEQ_START node, that starts new call frame, in which
896 /// InSize bytes are set up inside CALLSEQ_START..CALLSEQ_END sequence and
897 /// OutSize specifies part of the frame set up prior to the sequence.
898 SDValue getCALLSEQ_START(SDValue Chain, uint64_t InSize, uint64_t OutSize,
900 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
901 SDValue Ops[] = { Chain,
902 getIntPtrConstant(InSize, DL, true),
903 getIntPtrConstant(OutSize, DL, true) };
904 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
907 /// Return a new CALLSEQ_END node, which always must have a
908 /// glue result (to ensure it's not CSE'd).
909 /// CALLSEQ_END does not have a useful SDLoc.
910 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
911 SDValue InGlue, const SDLoc &DL) {
912 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
913 SmallVector<SDValue, 4> Ops;
914 Ops.push_back(Chain);
917 if (InGlue.getNode())
918 Ops.push_back(InGlue);
919 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
922 /// Return true if the result of this operation is always undefined.
923 bool isUndef(unsigned Opcode, ArrayRef<SDValue> Ops);
925 /// Return an UNDEF node. UNDEF does not have a useful SDLoc.
926 SDValue getUNDEF(EVT VT) {
927 return getNode(ISD::UNDEF, SDLoc(), VT);
930 /// Return a node that represents the runtime scaling 'MulImm * RuntimeVL'.
931 SDValue getVScale(const SDLoc &DL, EVT VT, APInt MulImm) {
932 assert(MulImm.getMinSignedBits() <= VT.getSizeInBits() &&
933 "Immediate does not fit VT");
934 return getNode(ISD::VSCALE, DL, VT,
935 getConstant(MulImm.sextOrTrunc(VT.getSizeInBits()), DL, VT));
938 /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc.
939 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
940 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
943 /// Gets or creates the specified node.
945 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
946 ArrayRef<SDUse> Ops);
947 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
948 ArrayRef<SDValue> Ops, const SDNodeFlags Flags = SDNodeFlags());
949 SDValue getNode(unsigned Opcode, const SDLoc &DL, ArrayRef<EVT> ResultTys,
950 ArrayRef<SDValue> Ops);
951 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList,
952 ArrayRef<SDValue> Ops, const SDNodeFlags Flags = SDNodeFlags());
954 // Specialize based on number of operands.
955 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT);
956 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue Operand,
957 const SDNodeFlags Flags = SDNodeFlags());
958 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
959 SDValue N2, const SDNodeFlags Flags = SDNodeFlags());
960 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
961 SDValue N2, SDValue N3,
962 const SDNodeFlags Flags = SDNodeFlags());
963 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
964 SDValue N2, SDValue N3, SDValue N4);
965 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
966 SDValue N2, SDValue N3, SDValue N4, SDValue N5);
968 // Specialize again based on number of operands for nodes with a VTList
969 // rather than a single VT.
970 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList);
971 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N);
972 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
974 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
975 SDValue N2, SDValue N3);
976 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
977 SDValue N2, SDValue N3, SDValue N4);
978 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
979 SDValue N2, SDValue N3, SDValue N4, SDValue N5);
981 /// Compute a TokenFactor to force all the incoming stack arguments to be
982 /// loaded from the stack. This is used in tail call lowering to protect
983 /// stack arguments from being clobbered.
984 SDValue getStackArgumentTokenFactor(SDValue Chain);
986 LLVM_ATTRIBUTE_DEPRECATED(SDValue getMemcpy(SDValue Chain, const SDLoc &dl,
987 SDValue Dst, SDValue Src,
988 SDValue Size, unsigned Align,
989 bool isVol, bool AlwaysInline,
991 MachinePointerInfo DstPtrInfo,
992 MachinePointerInfo SrcPtrInfo),
993 "Use the version that takes Align instead") {
994 return getMemcpy(Chain, dl, Dst, Src, Size, llvm::Align(Align), isVol,
995 AlwaysInline, isTailCall, DstPtrInfo, SrcPtrInfo);
998 SDValue getMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
999 SDValue Size, Align Alignment, bool isVol,
1000 bool AlwaysInline, bool isTailCall,
1001 MachinePointerInfo DstPtrInfo,
1002 MachinePointerInfo SrcPtrInfo);
1004 LLVM_ATTRIBUTE_DEPRECATED(SDValue getMemmove(SDValue Chain, const SDLoc &dl,
1005 SDValue Dst, SDValue Src,
1006 SDValue Size, unsigned Align,
1007 bool isVol, bool isTailCall,
1008 MachinePointerInfo DstPtrInfo,
1009 MachinePointerInfo SrcPtrInfo),
1010 "Use the version that takes Align instead") {
1011 return getMemmove(Chain, dl, Dst, Src, Size, llvm::Align(Align), isVol,
1012 isTailCall, DstPtrInfo, SrcPtrInfo);
1014 SDValue getMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
1015 SDValue Size, Align Alignment, bool isVol, bool isTailCall,
1016 MachinePointerInfo DstPtrInfo,
1017 MachinePointerInfo SrcPtrInfo);
1019 LLVM_ATTRIBUTE_DEPRECATED(SDValue getMemset(SDValue Chain, const SDLoc &dl,
1020 SDValue Dst, SDValue Src,
1021 SDValue Size, unsigned Align,
1022 bool isVol, bool isTailCall,
1023 MachinePointerInfo DstPtrInfo),
1024 "Use the version that takes Align instead") {
1025 return getMemset(Chain, dl, Dst, Src, Size, llvm::Align(Align), isVol,
1026 isTailCall, DstPtrInfo);
1028 SDValue getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
1029 SDValue Size, Align Alignment, bool isVol, bool isTailCall,
1030 MachinePointerInfo DstPtrInfo);
1032 SDValue getAtomicMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst,
1033 unsigned DstAlign, SDValue Src, unsigned SrcAlign,
1034 SDValue Size, Type *SizeTy, unsigned ElemSz,
1035 bool isTailCall, MachinePointerInfo DstPtrInfo,
1036 MachinePointerInfo SrcPtrInfo);
1038 SDValue getAtomicMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst,
1039 unsigned DstAlign, SDValue Src, unsigned SrcAlign,
1040 SDValue Size, Type *SizeTy, unsigned ElemSz,
1041 bool isTailCall, MachinePointerInfo DstPtrInfo,
1042 MachinePointerInfo SrcPtrInfo);
1044 SDValue getAtomicMemset(SDValue Chain, const SDLoc &dl, SDValue Dst,
1045 unsigned DstAlign, SDValue Value, SDValue Size,
1046 Type *SizeTy, unsigned ElemSz, bool isTailCall,
1047 MachinePointerInfo DstPtrInfo);
1049 /// Helper function to make it easier to build SetCC's if you just have an
1050 /// ISD::CondCode instead of an SDValue.
1051 SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS,
1052 ISD::CondCode Cond, SDValue Chain = SDValue(),
1053 bool IsSignaling = false) {
1054 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
1055 "Cannot compare scalars to vectors");
1056 assert(LHS.getValueType().isVector() == VT.isVector() &&
1057 "Cannot compare scalars to vectors");
1058 assert(Cond != ISD::SETCC_INVALID &&
1059 "Cannot create a setCC of an invalid node.");
1061 return getNode(IsSignaling ? ISD::STRICT_FSETCCS : ISD::STRICT_FSETCC, DL,
1062 {VT, MVT::Other}, {Chain, LHS, RHS, getCondCode(Cond)});
1063 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
1066 /// Helper function to make it easier to build Select's if you just have
1067 /// operands and don't want to check for vector.
1068 SDValue getSelect(const SDLoc &DL, EVT VT, SDValue Cond, SDValue LHS,
1070 assert(LHS.getValueType() == RHS.getValueType() &&
1071 "Cannot use select on differing types");
1072 assert(VT.isVector() == LHS.getValueType().isVector() &&
1073 "Cannot mix vectors and scalars");
1074 auto Opcode = Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT;
1075 return getNode(Opcode, DL, VT, Cond, LHS, RHS);
1078 /// Helper function to make it easier to build SelectCC's if you just have an
1079 /// ISD::CondCode instead of an SDValue.
1080 SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True,
1081 SDValue False, ISD::CondCode Cond) {
1082 return getNode(ISD::SELECT_CC, DL, True.getValueType(), LHS, RHS, True,
1083 False, getCondCode(Cond));
1086 /// Try to simplify a select/vselect into 1 of its operands or a constant.
1087 SDValue simplifySelect(SDValue Cond, SDValue TVal, SDValue FVal);
1089 /// Try to simplify a shift into 1 of its operands or a constant.
1090 SDValue simplifyShift(SDValue X, SDValue Y);
1092 /// Try to simplify a floating-point binary operation into 1 of its operands
1094 SDValue simplifyFPBinop(unsigned Opcode, SDValue X, SDValue Y,
1097 /// VAArg produces a result and token chain, and takes a pointer
1098 /// and a source value as input.
1099 SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1100 SDValue SV, unsigned Align);
1102 /// Gets a node for an atomic cmpxchg op. There are two
1103 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
1104 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
1105 /// a success flag (initially i1), and a chain.
1106 SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
1107 SDVTList VTs, SDValue Chain, SDValue Ptr,
1108 SDValue Cmp, SDValue Swp, MachineMemOperand *MMO);
1110 /// Gets a node for an atomic op, produces result (if relevant)
1111 /// and chain and takes 2 operands.
1112 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
1113 SDValue Ptr, SDValue Val, MachineMemOperand *MMO);
1115 /// Gets a node for an atomic op, produces result and chain and
1116 /// takes 1 operand.
1117 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, EVT VT,
1118 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO);
1120 /// Gets a node for an atomic op, produces result and chain and takes N
1122 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT,
1123 SDVTList VTList, ArrayRef<SDValue> Ops,
1124 MachineMemOperand *MMO);
1126 /// Creates a MemIntrinsicNode that may produce a
1127 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
1128 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
1129 /// less than FIRST_TARGET_MEMORY_OPCODE.
1130 SDValue getMemIntrinsicNode(
1131 unsigned Opcode, const SDLoc &dl, SDVTList VTList, ArrayRef<SDValue> Ops,
1132 EVT MemVT, MachinePointerInfo PtrInfo, Align Alignment,
1133 MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad |
1134 MachineMemOperand::MOStore,
1135 uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes());
1137 inline SDValue getMemIntrinsicNode(
1138 unsigned Opcode, const SDLoc &dl, SDVTList VTList, ArrayRef<SDValue> Ops,
1139 EVT MemVT, MachinePointerInfo PtrInfo, MaybeAlign Alignment = None,
1140 MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad |
1141 MachineMemOperand::MOStore,
1142 uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes()) {
1143 // Ensure that codegen never sees alignment 0
1144 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, PtrInfo,
1145 Alignment.getValueOr(getEVTAlign(MemVT)), Flags,
1149 LLVM_ATTRIBUTE_DEPRECATED(
1150 inline SDValue getMemIntrinsicNode(
1151 unsigned Opcode, const SDLoc &dl, SDVTList VTList,
1152 ArrayRef<SDValue> Ops, EVT MemVT, MachinePointerInfo PtrInfo,
1154 MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad |
1155 MachineMemOperand::MOStore,
1156 uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes()),
1158 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, PtrInfo,
1159 MaybeAlign(Alignment), Flags, Size, AAInfo);
1162 SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList,
1163 ArrayRef<SDValue> Ops, EVT MemVT,
1164 MachineMemOperand *MMO);
1166 /// Creates a LifetimeSDNode that starts (`IsStart==true`) or ends
1167 /// (`IsStart==false`) the lifetime of the portion of `FrameIndex` between
1168 /// offsets `Offset` and `Offset + Size`.
1169 SDValue getLifetimeNode(bool IsStart, const SDLoc &dl, SDValue Chain,
1170 int FrameIndex, int64_t Size, int64_t Offset = -1);
1172 /// Create a MERGE_VALUES node from the given operands.
1173 SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl);
1175 /// Loads are not normal binary operators: their result type is not
1176 /// determined by their operands, and they produce a value AND a token chain.
1178 /// This function will set the MOLoad flag on MMOFlags, but you can set it if
1179 /// you want. The MOStore flag must not be set.
1180 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1181 MachinePointerInfo PtrInfo, MaybeAlign Alignment,
1182 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1183 const AAMDNodes &AAInfo = AAMDNodes(),
1184 const MDNode *Ranges = nullptr);
1185 /// FIXME: Remove once transition to Align is over.
1187 getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1188 MachinePointerInfo PtrInfo, unsigned Alignment = 0,
1189 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1190 const AAMDNodes &AAInfo = AAMDNodes(),
1191 const MDNode *Ranges = nullptr) {
1192 return getLoad(VT, dl, Chain, Ptr, PtrInfo, MaybeAlign(Alignment), MMOFlags,
1195 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1196 MachineMemOperand *MMO);
1198 getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain,
1199 SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT,
1200 MaybeAlign Alignment,
1201 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1202 const AAMDNodes &AAInfo = AAMDNodes());
1203 /// FIXME: Remove once transition to Align is over.
1205 getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain,
1206 SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT,
1207 unsigned Alignment = 0,
1208 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1209 const AAMDNodes &AAInfo = AAMDNodes()) {
1210 return getExtLoad(ExtType, dl, VT, Chain, Ptr, PtrInfo, MemVT,
1211 MaybeAlign(Alignment), MMOFlags, AAInfo);
1213 SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT,
1214 SDValue Chain, SDValue Ptr, EVT MemVT,
1215 MachineMemOperand *MMO);
1216 SDValue getIndexedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base,
1217 SDValue Offset, ISD::MemIndexedMode AM);
1218 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1219 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1220 MachinePointerInfo PtrInfo, EVT MemVT, Align Alignment,
1221 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1222 const AAMDNodes &AAInfo = AAMDNodes(),
1223 const MDNode *Ranges = nullptr);
1225 getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1226 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1227 MachinePointerInfo PtrInfo, EVT MemVT, MaybeAlign Alignment,
1228 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1229 const AAMDNodes &AAInfo = AAMDNodes(),
1230 const MDNode *Ranges = nullptr) {
1231 // Ensures that codegen never sees a None Alignment.
1232 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, PtrInfo, MemVT,
1233 Alignment.getValueOr(getEVTAlign(MemVT)), MMOFlags, AAInfo,
1236 /// FIXME: Remove once transition to Align is over.
1238 getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1239 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1240 MachinePointerInfo PtrInfo, EVT MemVT, unsigned Alignment = 0,
1241 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1242 const AAMDNodes &AAInfo = AAMDNodes(),
1243 const MDNode *Ranges = nullptr) {
1244 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, PtrInfo, MemVT,
1245 MaybeAlign(Alignment), MMOFlags, AAInfo, Ranges);
1247 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1248 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1249 EVT MemVT, MachineMemOperand *MMO);
1251 /// Helper function to build ISD::STORE nodes.
1253 /// This function will set the MOStore flag on MMOFlags, but you can set it if
1254 /// you want. The MOLoad and MOInvariant flags must not be set.
1257 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1258 MachinePointerInfo PtrInfo, Align Alignment,
1259 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1260 const AAMDNodes &AAInfo = AAMDNodes());
1262 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1263 MachinePointerInfo PtrInfo, MaybeAlign Alignment,
1264 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1265 const AAMDNodes &AAInfo = AAMDNodes()) {
1266 return getStore(Chain, dl, Val, Ptr, PtrInfo,
1267 Alignment.getValueOr(getEVTAlign(Val.getValueType())),
1270 /// FIXME: Remove once transition to Align is over.
1272 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1273 MachinePointerInfo PtrInfo, unsigned Alignment = 0,
1274 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1275 const AAMDNodes &AAInfo = AAMDNodes()) {
1276 return getStore(Chain, dl, Val, Ptr, PtrInfo, MaybeAlign(Alignment),
1279 SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1280 MachineMemOperand *MMO);
1282 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1283 MachinePointerInfo PtrInfo, EVT SVT, Align Alignment,
1284 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1285 const AAMDNodes &AAInfo = AAMDNodes());
1287 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1288 MachinePointerInfo PtrInfo, EVT SVT, MaybeAlign Alignment,
1289 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1290 const AAMDNodes &AAInfo = AAMDNodes()) {
1291 return getTruncStore(Chain, dl, Val, Ptr, PtrInfo, SVT,
1292 Alignment.getValueOr(getEVTAlign(SVT)), MMOFlags,
1295 /// FIXME: Remove once transition to Align is over.
1297 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1298 MachinePointerInfo PtrInfo, EVT SVT, unsigned Alignment = 0,
1299 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1300 const AAMDNodes &AAInfo = AAMDNodes()) {
1301 return getTruncStore(Chain, dl, Val, Ptr, PtrInfo, SVT,
1302 MaybeAlign(Alignment), MMOFlags, AAInfo);
1304 SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val,
1305 SDValue Ptr, EVT SVT, MachineMemOperand *MMO);
1306 SDValue getIndexedStore(SDValue OrigStore, const SDLoc &dl, SDValue Base,
1307 SDValue Offset, ISD::MemIndexedMode AM);
1309 SDValue getMaskedLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Base,
1310 SDValue Offset, SDValue Mask, SDValue Src0, EVT MemVT,
1311 MachineMemOperand *MMO, ISD::MemIndexedMode AM,
1312 ISD::LoadExtType, bool IsExpanding = false);
1313 SDValue getIndexedMaskedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base,
1314 SDValue Offset, ISD::MemIndexedMode AM);
1315 SDValue getMaskedStore(SDValue Chain, const SDLoc &dl, SDValue Val,
1316 SDValue Base, SDValue Offset, SDValue Mask, EVT MemVT,
1317 MachineMemOperand *MMO, ISD::MemIndexedMode AM,
1318 bool IsTruncating = false, bool IsCompressing = false);
1319 SDValue getIndexedMaskedStore(SDValue OrigStore, const SDLoc &dl,
1320 SDValue Base, SDValue Offset,
1321 ISD::MemIndexedMode AM);
1322 SDValue getMaskedGather(SDVTList VTs, EVT VT, const SDLoc &dl,
1323 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
1324 ISD::MemIndexType IndexType);
1325 SDValue getMaskedScatter(SDVTList VTs, EVT VT, const SDLoc &dl,
1326 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
1327 ISD::MemIndexType IndexType);
1329 /// Construct a node to track a Value* through the backend.
1330 SDValue getSrcValue(const Value *v);
1332 /// Return an MDNodeSDNode which holds an MDNode.
1333 SDValue getMDNode(const MDNode *MD);
1335 /// Return a bitcast using the SDLoc of the value operand, and casting to the
1336 /// provided type. Use getNode to set a custom SDLoc.
1337 SDValue getBitcast(EVT VT, SDValue V);
1339 /// Return an AddrSpaceCastSDNode.
1340 SDValue getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr, unsigned SrcAS,
1343 /// Return a freeze using the SDLoc of the value operand.
1344 SDValue getFreeze(SDValue V);
1346 /// Return an AssertAlignSDNode.
1347 SDValue getAssertAlign(const SDLoc &DL, SDValue V, Align A);
1349 /// Return the specified value casted to
1350 /// the target's desired shift amount type.
1351 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
1353 /// Expand the specified \c ISD::VAARG node as the Legalize pass would.
1354 SDValue expandVAArg(SDNode *Node);
1356 /// Expand the specified \c ISD::VACOPY node as the Legalize pass would.
1357 SDValue expandVACopy(SDNode *Node);
1359 /// Returs an GlobalAddress of the function from the current module with
1360 /// name matching the given ExternalSymbol. Additionally can provide the
1361 /// matched function.
1362 /// Panics the function doesn't exists.
1363 SDValue getSymbolFunctionGlobalAddress(SDValue Op,
1364 Function **TargetFunction = nullptr);
1366 /// *Mutate* the specified node in-place to have the
1367 /// specified operands. If the resultant node already exists in the DAG,
1368 /// this does not modify the specified node, instead it returns the node that
1369 /// already exists. If the resultant node does not exist in the DAG, the
1370 /// input node is returned. As a degenerate case, if you specify the same
1371 /// input operands as the node already has, the input node is returned.
1372 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
1373 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
1374 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1376 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1377 SDValue Op3, SDValue Op4);
1378 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1379 SDValue Op3, SDValue Op4, SDValue Op5);
1380 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
1382 /// Creates a new TokenFactor containing \p Vals. If \p Vals contains 64k
1383 /// values or more, move values into new TokenFactors in 64k-1 blocks, until
1384 /// the final TokenFactor has less than 64k operands.
1385 SDValue getTokenFactor(const SDLoc &DL, SmallVectorImpl<SDValue> &Vals);
1387 /// *Mutate* the specified machine node's memory references to the provided
1389 void setNodeMemRefs(MachineSDNode *N,
1390 ArrayRef<MachineMemOperand *> NewMemRefs);
1392 // Propagates the change in divergence to users
1393 void updateDivergence(SDNode * N);
1395 /// These are used for target selectors to *mutate* the
1396 /// specified node to have the specified return type, Target opcode, and
1397 /// operands. Note that target opcodes are stored as
1398 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
1399 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT);
1400 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, SDValue Op1);
1401 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
1402 SDValue Op1, SDValue Op2);
1403 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
1404 SDValue Op1, SDValue Op2, SDValue Op3);
1405 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
1406 ArrayRef<SDValue> Ops);
1407 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, EVT VT2);
1408 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
1409 EVT VT2, ArrayRef<SDValue> Ops);
1410 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
1411 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1412 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1413 EVT VT2, SDValue Op1);
1414 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
1415 EVT VT2, SDValue Op1, SDValue Op2);
1416 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, SDVTList VTs,
1417 ArrayRef<SDValue> Ops);
1419 /// This *mutates* the specified node to have the specified
1420 /// return type, opcode, and operands.
1421 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
1422 ArrayRef<SDValue> Ops);
1424 /// Mutate the specified strict FP node to its non-strict equivalent,
1425 /// unlinking the node from its chain and dropping the metadata arguments.
1426 /// The node must be a strict FP node.
1427 SDNode *mutateStrictFPToFP(SDNode *Node);
1429 /// These are used for target selectors to create a new node
1430 /// with specified return type(s), MachineInstr opcode, and operands.
1432 /// Note that getMachineNode returns the resultant node. If there is already
1433 /// a node of the specified opcode and operands, it returns that node instead
1434 /// of the current one.
1435 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT);
1436 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1438 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1439 SDValue Op1, SDValue Op2);
1440 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1441 SDValue Op1, SDValue Op2, SDValue Op3);
1442 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1443 ArrayRef<SDValue> Ops);
1444 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1445 EVT VT2, SDValue Op1, SDValue Op2);
1446 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1447 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
1448 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1449 EVT VT2, ArrayRef<SDValue> Ops);
1450 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1451 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2);
1452 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1453 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2,
1455 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1456 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1457 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl,
1458 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops);
1459 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, SDVTList VTs,
1460 ArrayRef<SDValue> Ops);
1462 /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
1463 SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1466 /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes.
1467 SDValue getTargetInsertSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1468 SDValue Operand, SDValue Subreg);
1470 /// Get the specified node if it's already available, or else return NULL.
1471 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTList, ArrayRef<SDValue> Ops,
1472 const SDNodeFlags Flags = SDNodeFlags());
1474 /// Creates a SDDbgValue node.
1475 SDDbgValue *getDbgValue(DIVariable *Var, DIExpression *Expr, SDNode *N,
1476 unsigned R, bool IsIndirect, const DebugLoc &DL,
1479 /// Creates a constant SDDbgValue node.
1480 SDDbgValue *getConstantDbgValue(DIVariable *Var, DIExpression *Expr,
1481 const Value *C, const DebugLoc &DL,
1484 /// Creates a FrameIndex SDDbgValue node.
1485 SDDbgValue *getFrameIndexDbgValue(DIVariable *Var, DIExpression *Expr,
1486 unsigned FI, bool IsIndirect,
1487 const DebugLoc &DL, unsigned O);
1489 /// Creates a VReg SDDbgValue node.
1490 SDDbgValue *getVRegDbgValue(DIVariable *Var, DIExpression *Expr,
1491 unsigned VReg, bool IsIndirect,
1492 const DebugLoc &DL, unsigned O);
1494 /// Creates a SDDbgLabel node.
1495 SDDbgLabel *getDbgLabel(DILabel *Label, const DebugLoc &DL, unsigned O);
1497 /// Transfer debug values from one node to another, while optionally
1498 /// generating fragment expressions for split-up values. If \p InvalidateDbg
1499 /// is set, debug values are invalidated after they are transferred.
1500 void transferDbgValues(SDValue From, SDValue To, unsigned OffsetInBits = 0,
1501 unsigned SizeInBits = 0, bool InvalidateDbg = true);
1503 /// Remove the specified node from the system. If any of its
1504 /// operands then becomes dead, remove them as well. Inform UpdateListener
1505 /// for each node deleted.
1506 void RemoveDeadNode(SDNode *N);
1508 /// This method deletes the unreachable nodes in the
1509 /// given list, and any nodes that become unreachable as a result.
1510 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
1512 /// Modify anything using 'From' to use 'To' instead.
1513 /// This can cause recursive merging of nodes in the DAG. Use the first
1514 /// version if 'From' is known to have a single result, use the second
1515 /// if you have two nodes with identical results (or if 'To' has a superset
1516 /// of the results of 'From'), use the third otherwise.
1518 /// These methods all take an optional UpdateListener, which (if not null) is
1519 /// informed about nodes that are deleted and modified due to recursive
1520 /// changes in the dag.
1522 /// These functions only replace all existing uses. It's possible that as
1523 /// these replacements are being performed, CSE may cause the From node
1524 /// to be given new uses. These new uses of From are left in place, and
1525 /// not automatically transferred to To.
1527 void ReplaceAllUsesWith(SDValue From, SDValue To);
1528 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
1529 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
1531 /// Replace any uses of From with To, leaving
1532 /// uses of other values produced by From.getNode() alone.
1533 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
1535 /// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
1536 /// This correctly handles the case where
1537 /// there is an overlap between the From values and the To values.
1538 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
1541 /// If an existing load has uses of its chain, create a token factor node with
1542 /// that chain and the new memory node's chain and update users of the old
1543 /// chain to the token factor. This ensures that the new memory node will have
1544 /// the same relative memory dependency position as the old load. Returns the
1545 /// new merged load chain.
1546 SDValue makeEquivalentMemoryOrdering(LoadSDNode *Old, SDValue New);
1548 /// Topological-sort the AllNodes list and a
1549 /// assign a unique node id for each node in the DAG based on their
1550 /// topological order. Returns the number of nodes.
1551 unsigned AssignTopologicalOrder();
1553 /// Move node N in the AllNodes list to be immediately
1554 /// before the given iterator Position. This may be used to update the
1555 /// topological ordering when the list of nodes is modified.
1556 void RepositionNode(allnodes_iterator Position, SDNode *N) {
1557 AllNodes.insert(Position, AllNodes.remove(N));
1560 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1561 /// a vector type, the element semantics are returned.
1562 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1563 switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1564 default: llvm_unreachable("Unknown FP format");
1565 case MVT::f16: return APFloat::IEEEhalf();
1566 case MVT::bf16: return APFloat::BFloat();
1567 case MVT::f32: return APFloat::IEEEsingle();
1568 case MVT::f64: return APFloat::IEEEdouble();
1569 case MVT::f80: return APFloat::x87DoubleExtended();
1570 case MVT::f128: return APFloat::IEEEquad();
1571 case MVT::ppcf128: return APFloat::PPCDoubleDouble();
1575 /// Add a dbg_value SDNode. If SD is non-null that means the
1576 /// value is produced by SD.
1577 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1579 /// Add a dbg_label SDNode.
1580 void AddDbgLabel(SDDbgLabel *DB);
1582 /// Get the debug values which reference the given SDNode.
1583 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) const {
1584 return DbgInfo->getSDDbgValues(SD);
1588 /// Return true if there are any SDDbgValue nodes associated
1589 /// with this SelectionDAG.
1590 bool hasDebugValues() const { return !DbgInfo->empty(); }
1592 SDDbgInfo::DbgIterator DbgBegin() const { return DbgInfo->DbgBegin(); }
1593 SDDbgInfo::DbgIterator DbgEnd() const { return DbgInfo->DbgEnd(); }
1595 SDDbgInfo::DbgIterator ByvalParmDbgBegin() const {
1596 return DbgInfo->ByvalParmDbgBegin();
1598 SDDbgInfo::DbgIterator ByvalParmDbgEnd() const {
1599 return DbgInfo->ByvalParmDbgEnd();
1602 SDDbgInfo::DbgLabelIterator DbgLabelBegin() const {
1603 return DbgInfo->DbgLabelBegin();
1605 SDDbgInfo::DbgLabelIterator DbgLabelEnd() const {
1606 return DbgInfo->DbgLabelEnd();
1609 /// To be invoked on an SDNode that is slated to be erased. This
1610 /// function mirrors \c llvm::salvageDebugInfo.
1611 void salvageDebugInfo(SDNode &N);
1615 /// In most cases this function returns the ABI alignment for a given type,
1616 /// except for illegal vector types where the alignment exceeds that of the
1617 /// stack. In such cases we attempt to break the vector down to a legal type
1618 /// and return the ABI alignment for that instead.
1619 Align getReducedAlign(EVT VT, bool UseABI);
1621 /// Create a stack temporary based on the size in bytes and the alignment
1622 SDValue CreateStackTemporary(TypeSize Bytes, Align Alignment);
1624 /// Create a stack temporary, suitable for holding the specified value type.
1625 /// If minAlign is specified, the slot size will have at least that alignment.
1626 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1628 /// Create a stack temporary suitable for holding either of the specified
1630 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1632 SDValue FoldSymbolOffset(unsigned Opcode, EVT VT,
1633 const GlobalAddressSDNode *GA,
1636 SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1637 ArrayRef<SDValue> Ops);
1639 SDValue FoldConstantVectorArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1640 ArrayRef<SDValue> Ops,
1641 const SDNodeFlags Flags = SDNodeFlags());
1643 /// Fold floating-point operations with 2 operands when both operands are
1644 /// constants and/or undefined.
1645 SDValue foldConstantFPMath(unsigned Opcode, const SDLoc &DL, EVT VT,
1646 SDValue N1, SDValue N2);
1648 /// Constant fold a setcc to true or false.
1649 SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond,
1652 /// See if the specified operand can be simplified with the knowledge that
1653 /// only the bits specified by DemandedBits are used. If so, return the
1654 /// simpler operand, otherwise return a null SDValue.
1656 /// (This exists alongside SimplifyDemandedBits because GetDemandedBits can
1657 /// simplify nodes with multiple uses more aggressively.)
1658 SDValue GetDemandedBits(SDValue V, const APInt &DemandedBits);
1660 /// See if the specified operand can be simplified with the knowledge that
1661 /// only the bits specified by DemandedBits are used in the elements specified
1662 /// by DemandedElts. If so, return the simpler operand, otherwise return a
1665 /// (This exists alongside SimplifyDemandedBits because GetDemandedBits can
1666 /// simplify nodes with multiple uses more aggressively.)
1667 SDValue GetDemandedBits(SDValue V, const APInt &DemandedBits,
1668 const APInt &DemandedElts);
1670 /// Return true if the sign bit of Op is known to be zero.
1671 /// We use this predicate to simplify operations downstream.
1672 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1674 /// Return true if 'Op & Mask' is known to be zero. We
1675 /// use this predicate to simplify operations downstream. Op and Mask are
1676 /// known to be the same type.
1677 bool MaskedValueIsZero(SDValue Op, const APInt &Mask,
1678 unsigned Depth = 0) const;
1680 /// Return true if 'Op & Mask' is known to be zero in DemandedElts. We
1681 /// use this predicate to simplify operations downstream. Op and Mask are
1682 /// known to be the same type.
1683 bool MaskedValueIsZero(SDValue Op, const APInt &Mask,
1684 const APInt &DemandedElts, unsigned Depth = 0) const;
1686 /// Return true if '(Op & Mask) == Mask'.
1687 /// Op and Mask are known to be the same type.
1688 bool MaskedValueIsAllOnes(SDValue Op, const APInt &Mask,
1689 unsigned Depth = 0) const;
1691 /// Determine which bits of Op are known to be either zero or one and return
1692 /// them in Known. For vectors, the known bits are those that are shared by
1693 /// every vector element.
1694 /// Targets can implement the computeKnownBitsForTargetNode method in the
1695 /// TargetLowering class to allow target nodes to be understood.
1696 KnownBits computeKnownBits(SDValue Op, unsigned Depth = 0) const;
1698 /// Determine which bits of Op are known to be either zero or one and return
1699 /// them in Known. The DemandedElts argument allows us to only collect the
1700 /// known bits that are shared by the requested vector elements.
1701 /// Targets can implement the computeKnownBitsForTargetNode method in the
1702 /// TargetLowering class to allow target nodes to be understood.
1703 KnownBits computeKnownBits(SDValue Op, const APInt &DemandedElts,
1704 unsigned Depth = 0) const;
1706 /// Used to represent the possible overflow behavior of an operation.
1707 /// Never: the operation cannot overflow.
1708 /// Always: the operation will always overflow.
1709 /// Sometime: the operation may or may not overflow.
1716 /// Determine if the result of the addition of 2 node can overflow.
1717 OverflowKind computeOverflowKind(SDValue N0, SDValue N1) const;
1719 /// Test if the given value is known to have exactly one bit set. This differs
1720 /// from computeKnownBits in that it doesn't necessarily determine which bit
1722 bool isKnownToBeAPowerOfTwo(SDValue Val) const;
1724 /// Return the number of times the sign bit of the register is replicated into
1725 /// the other bits. We know that at least 1 bit is always equal to the sign
1726 /// bit (itself), but other cases can give us information. For example,
1727 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
1728 /// to each other, so we return 3. Targets can implement the
1729 /// ComputeNumSignBitsForTarget method in the TargetLowering class to allow
1730 /// target nodes to be understood.
1731 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1733 /// Return the number of times the sign bit of the register is replicated into
1734 /// the other bits. We know that at least 1 bit is always equal to the sign
1735 /// bit (itself), but other cases can give us information. For example,
1736 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
1737 /// to each other, so we return 3. The DemandedElts argument allows
1738 /// us to only collect the minimum sign bits of the requested vector elements.
1739 /// Targets can implement the ComputeNumSignBitsForTarget method in the
1740 /// TargetLowering class to allow target nodes to be understood.
1741 unsigned ComputeNumSignBits(SDValue Op, const APInt &DemandedElts,
1742 unsigned Depth = 0) const;
1744 /// Return true if the specified operand is an ISD::ADD with a ConstantSDNode
1745 /// on the right-hand side, or if it is an ISD::OR with a ConstantSDNode that
1746 /// is guaranteed to have the same semantics as an ADD. This handles the
1748 /// X|Cst == X+Cst iff X&Cst = 0.
1749 bool isBaseWithConstantOffset(SDValue Op) const;
1751 /// Test whether the given SDValue is known to never be NaN. If \p SNaN is
1752 /// true, returns if \p Op is known to never be a signaling NaN (it may still
1754 bool isKnownNeverNaN(SDValue Op, bool SNaN = false, unsigned Depth = 0) const;
1756 /// \returns true if \p Op is known to never be a signaling NaN.
1757 bool isKnownNeverSNaN(SDValue Op, unsigned Depth = 0) const {
1758 return isKnownNeverNaN(Op, true, Depth);
1761 /// Test whether the given floating point SDValue is known to never be
1762 /// positive or negative zero.
1763 bool isKnownNeverZeroFloat(SDValue Op) const;
1765 /// Test whether the given SDValue is known to contain non-zero value(s).
1766 bool isKnownNeverZero(SDValue Op) const;
1768 /// Test whether two SDValues are known to compare equal. This
1769 /// is true if they are the same value, or if one is negative zero and the
1770 /// other positive zero.
1771 bool isEqualTo(SDValue A, SDValue B) const;
1773 /// Return true if A and B have no common bits set. As an example, this can
1774 /// allow an 'add' to be transformed into an 'or'.
1775 bool haveNoCommonBitsSet(SDValue A, SDValue B) const;
1777 /// Test whether \p V has a splatted value for all the demanded elements.
1779 /// On success \p UndefElts will indicate the elements that have UNDEF
1780 /// values instead of the splat value, this is only guaranteed to be correct
1781 /// for \p DemandedElts.
1783 /// NOTE: The function will return true for a demanded splat of UNDEF values.
1784 bool isSplatValue(SDValue V, const APInt &DemandedElts, APInt &UndefElts);
1786 /// Test whether \p V has a splatted value.
1787 bool isSplatValue(SDValue V, bool AllowUndefs = false);
1789 /// If V is a splatted value, return the source vector and its splat index.
1790 SDValue getSplatSourceVector(SDValue V, int &SplatIndex);
1792 /// If V is a splat vector, return its scalar source operand by extracting
1793 /// that element from the source vector.
1794 SDValue getSplatValue(SDValue V);
1796 /// If a SHL/SRA/SRL node \p V has a constant or splat constant shift amount
1797 /// that is less than the element bit-width of the shift node, return it.
1798 const APInt *getValidShiftAmountConstant(SDValue V,
1799 const APInt &DemandedElts) const;
1801 /// If a SHL/SRA/SRL node \p V has constant shift amounts that are all less
1802 /// than the element bit-width of the shift node, return the minimum value.
1804 getValidMinimumShiftAmountConstant(SDValue V,
1805 const APInt &DemandedElts) const;
1807 /// If a SHL/SRA/SRL node \p V has constant shift amounts that are all less
1808 /// than the element bit-width of the shift node, return the maximum value.
1810 getValidMaximumShiftAmountConstant(SDValue V,
1811 const APInt &DemandedElts) const;
1813 /// Match a binop + shuffle pyramid that represents a horizontal reduction
1814 /// over the elements of a vector starting from the EXTRACT_VECTOR_ELT node /p
1815 /// Extract. The reduction must use one of the opcodes listed in /p
1816 /// CandidateBinOps and on success /p BinOp will contain the matching opcode.
1817 /// Returns the vector that is being reduced on, or SDValue() if a reduction
1818 /// was not matched. If \p AllowPartials is set then in the case of a
1819 /// reduction pattern that only matches the first few stages, the extracted
1820 /// subvector of the start of the reduction is returned.
1821 SDValue matchBinOpReduction(SDNode *Extract, ISD::NodeType &BinOp,
1822 ArrayRef<ISD::NodeType> CandidateBinOps,
1823 bool AllowPartials = false);
1825 /// Utility function used by legalize and lowering to
1826 /// "unroll" a vector operation by splitting out the scalars and operating
1827 /// on each element individually. If the ResNE is 0, fully unroll the vector
1828 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1829 /// If the ResNE is greater than the width of the vector op, unroll the
1830 /// vector op and fill the end of the resulting vector with UNDEFS.
1831 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1833 /// Like UnrollVectorOp(), but for the [US](ADD|SUB|MUL)O family of opcodes.
1834 /// This is a separate function because those opcodes have two results.
1835 std::pair<SDValue, SDValue> UnrollVectorOverflowOp(SDNode *N,
1836 unsigned ResNE = 0);
1838 /// Return true if loads are next to each other and can be
1839 /// merged. Check that both are nonvolatile and if LD is loading
1840 /// 'Bytes' bytes from a location that is 'Dist' units away from the
1841 /// location that the 'Base' load is loading from.
1842 bool areNonVolatileConsecutiveLoads(LoadSDNode *LD, LoadSDNode *Base,
1843 unsigned Bytes, int Dist) const;
1845 /// Infer alignment of a load / store address. Return None if it cannot be
1847 MaybeAlign InferPtrAlign(SDValue Ptr) const;
1849 LLVM_ATTRIBUTE_DEPRECATED(inline unsigned InferPtrAlignment(SDValue Ptr)
1851 "Use InferPtrAlign instead") {
1852 if (auto A = InferPtrAlign(Ptr))
1857 /// Compute the VTs needed for the low/hi parts of a type
1858 /// which is split (or expanded) into two not necessarily identical pieces.
1859 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1861 /// Compute the VTs needed for the low/hi parts of a type, dependent on an
1862 /// enveloping VT that has been split into two identical pieces. Sets the
1863 /// HisIsEmpty flag when hi type has zero storage size.
1864 std::pair<EVT, EVT> GetDependentSplitDestVTs(const EVT &VT, const EVT &EnvVT,
1865 bool *HiIsEmpty) const;
1867 /// Split the vector with EXTRACT_SUBVECTOR using the provides
1868 /// VTs and return the low/high part.
1869 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1870 const EVT &LoVT, const EVT &HiVT);
1872 /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part.
1873 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1875 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1876 return SplitVector(N, DL, LoVT, HiVT);
1879 /// Split the node's operand with EXTRACT_SUBVECTOR and
1880 /// return the low/high part.
1881 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1883 return SplitVector(N->getOperand(OpNo), SDLoc(N));
1886 /// Widen the vector up to the next power of two using INSERT_SUBVECTOR.
1887 SDValue WidenVector(const SDValue &N, const SDLoc &DL);
1889 /// Append the extracted elements from Start to Count out of the vector Op in
1890 /// Args. If Count is 0, all of the elements will be extracted. The extracted
1891 /// elements will have type EVT if it is provided, and otherwise their type
1892 /// will be Op's element type.
1893 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
1894 unsigned Start = 0, unsigned Count = 0,
1897 /// Compute the default alignment value for the given type.
1898 Align getEVTAlign(EVT MemoryVT) const;
1899 /// Compute the default alignment value for the given type.
1900 /// FIXME: Remove once transition to Align is over.
1901 inline unsigned getEVTAlignment(EVT MemoryVT) const {
1902 return getEVTAlign(MemoryVT).value();
1905 /// Test whether the given value is a constant int or similar node.
1906 SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N);
1908 /// Test whether the given value is a constant FP or similar node.
1909 SDNode *isConstantFPBuildVectorOrConstantFP(SDValue N);
1911 /// \returns true if \p N is any kind of constant or build_vector of
1912 /// constants, int or float. If a vector, it may not necessarily be a splat.
1913 inline bool isConstantValueOfAnyType(SDValue N) {
1914 return isConstantIntBuildVectorOrConstantInt(N) ||
1915 isConstantFPBuildVectorOrConstantFP(N);
1918 void addCallSiteInfo(const SDNode *CallNode, CallSiteInfoImpl &&CallInfo) {
1919 SDCallSiteDbgInfo[CallNode].CSInfo = std::move(CallInfo);
1922 CallSiteInfo getSDCallSiteInfo(const SDNode *CallNode) {
1923 auto I = SDCallSiteDbgInfo.find(CallNode);
1924 if (I != SDCallSiteDbgInfo.end())
1925 return std::move(I->second).CSInfo;
1926 return CallSiteInfo();
1929 void addHeapAllocSite(const SDNode *Node, MDNode *MD) {
1930 SDCallSiteDbgInfo[Node].HeapAllocSite = MD;
1933 /// Return the HeapAllocSite type associated with the SDNode, if it exists.
1934 MDNode *getHeapAllocSite(const SDNode *Node) {
1935 auto It = SDCallSiteDbgInfo.find(Node);
1936 if (It == SDCallSiteDbgInfo.end())
1938 return It->second.HeapAllocSite;
1941 void addNoMergeSiteInfo(const SDNode *Node, bool NoMerge) {
1943 SDCallSiteDbgInfo[Node].NoMerge = NoMerge;
1946 bool getNoMergeSiteInfo(const SDNode *Node) {
1947 auto I = SDCallSiteDbgInfo.find(Node);
1948 if (I == SDCallSiteDbgInfo.end())
1950 return I->second.NoMerge;
1953 /// Return the current function's default denormal handling kind for the given
1954 /// floating point type.
1955 DenormalMode getDenormalMode(EVT VT) const {
1956 return MF->getDenormalMode(EVTToAPFloatSemantics(VT));
1959 bool shouldOptForSize() const;
1962 void InsertNode(SDNode *N);
1963 bool RemoveNodeFromCSEMaps(SDNode *N);
1964 void AddModifiedNodeToCSEMaps(SDNode *N);
1965 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1966 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1968 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1970 SDNode *UpdateSDLocOnMergeSDNode(SDNode *N, const SDLoc &loc);
1972 void DeleteNodeNotInCSEMaps(SDNode *N);
1973 void DeallocateNode(SDNode *N);
1975 void allnodes_clear();
1977 /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1978 /// not, return the insertion token that will make insertion faster. This
1979 /// overload is for nodes other than Constant or ConstantFP, use the other one
1981 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
1983 /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1984 /// not, return the insertion token that will make insertion faster. Performs
1985 /// additional processing for constant nodes.
1986 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, const SDLoc &DL,
1989 /// List of non-single value types.
1990 FoldingSet<SDVTListNode> VTListMap;
1992 /// Maps to auto-CSE operations.
1993 std::vector<CondCodeSDNode*> CondCodeNodes;
1995 std::vector<SDNode*> ValueTypeNodes;
1996 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1997 StringMap<SDNode*> ExternalSymbols;
1999 std::map<std::pair<std::string, unsigned>, SDNode *> TargetExternalSymbols;
2000 DenseMap<MCSymbol *, SDNode *> MCSymbols;
2003 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
2004 using nodes_iterator = pointer_iterator<SelectionDAG::allnodes_iterator>;
2006 static nodes_iterator nodes_begin(SelectionDAG *G) {
2007 return nodes_iterator(G->allnodes_begin());
2010 static nodes_iterator nodes_end(SelectionDAG *G) {
2011 return nodes_iterator(G->allnodes_end());
2015 } // end namespace llvm
2017 #endif // LLVM_CODEGEN_SELECTIONDAG_H