1 //===- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file declares the SelectionDAG class, and transitively defines the
11 // SDNode class and subclasses.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
16 #define LLVM_CODEGEN_SELECTIONDAG_H
18 #include "llvm/ADT/APFloat.h"
19 #include "llvm/ADT/APInt.h"
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/DenseSet.h"
23 #include "llvm/ADT/FoldingSet.h"
24 #include "llvm/ADT/SetVector.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/StringMap.h"
27 #include "llvm/ADT/ilist.h"
28 #include "llvm/ADT/iterator.h"
29 #include "llvm/ADT/iterator_range.h"
30 #include "llvm/Analysis/AliasAnalysis.h"
31 #include "llvm/CodeGen/DAGCombine.h"
32 #include "llvm/CodeGen/ISDOpcodes.h"
33 #include "llvm/CodeGen/MachineFunction.h"
34 #include "llvm/CodeGen/MachineMemOperand.h"
35 #include "llvm/CodeGen/MachineValueType.h"
36 #include "llvm/CodeGen/SelectionDAGNodes.h"
37 #include "llvm/CodeGen/ValueTypes.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"
42 #include "llvm/Support/ArrayRecycler.h"
43 #include "llvm/Support/AtomicOrdering.h"
44 #include "llvm/Support/Casting.h"
45 #include "llvm/Support/CodeGen.h"
46 #include "llvm/Support/ErrorHandling.h"
47 #include "llvm/Support/RecyclingAllocator.h"
69 class MachineBasicBlock;
70 class MachineConstantPoolValue;
72 class OptimizationRemarkEmitter;
75 class SelectionDAGTargetInfo;
78 class TargetSubtargetInfo;
81 class SDVTListNode : public FoldingSetNode {
82 friend struct FoldingSetTrait<SDVTListNode>;
84 /// A reference to an Interned FoldingSetNodeID for this node.
85 /// The Allocator in SelectionDAG holds the data.
86 /// SDVTList contains all types which are frequently accessed in SelectionDAG.
87 /// The size of this list is not expected to be big so it won't introduce
89 FoldingSetNodeIDRef FastID;
92 /// The hash value for SDVTList is fixed, so cache it to avoid
97 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
98 FastID(ID), VTs(VT), NumVTs(Num) {
99 HashValue = ID.ComputeHash();
102 SDVTList getSDVTList() {
103 SDVTList result = {VTs, NumVTs};
108 /// Specialize FoldingSetTrait for SDVTListNode
109 /// to avoid computing temp FoldingSetNodeID and hash value.
110 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
111 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
115 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
116 unsigned IDHash, FoldingSetNodeID &TempID) {
117 if (X.HashValue != IDHash)
119 return ID == X.FastID;
122 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
127 template <> struct ilist_alloc_traits<SDNode> {
128 static void deleteNode(SDNode *) {
129 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
133 /// Keeps track of dbg_value information through SDISel. We do
134 /// not build SDNodes for these so as not to perturb the generated code;
135 /// instead the info is kept off to the side in this structure. Each SDNode may
136 /// have one or more associated dbg_value entries. This information is kept in
138 /// Byval parameters are handled separately because they don't use alloca's,
139 /// which busts the normal mechanism. There is good reason for handling all
140 /// parameters separately: they may not have code generated for them, they
141 /// should always go at the beginning of the function regardless of other code
142 /// motion, and debug info for them is potentially useful even if the parameter
143 /// is unused. Right now only byval parameters are handled separately.
145 BumpPtrAllocator Alloc;
146 SmallVector<SDDbgValue*, 32> DbgValues;
147 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
148 using DbgValMapType = DenseMap<const SDNode *, SmallVector<SDDbgValue *, 2>>;
149 DbgValMapType DbgValMap;
152 SDDbgInfo() = default;
153 SDDbgInfo(const SDDbgInfo &) = delete;
154 SDDbgInfo &operator=(const SDDbgInfo &) = delete;
156 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
158 ByvalParmDbgValues.push_back(V);
159 } else DbgValues.push_back(V);
161 DbgValMap[Node].push_back(V);
164 /// \brief Invalidate all DbgValues attached to the node and remove
165 /// it from the Node-to-DbgValues map.
166 void erase(const SDNode *Node);
171 ByvalParmDbgValues.clear();
175 BumpPtrAllocator &getAlloc() { return Alloc; }
178 return DbgValues.empty() && ByvalParmDbgValues.empty();
181 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
182 DbgValMapType::iterator I = DbgValMap.find(Node);
183 if (I != DbgValMap.end())
185 return ArrayRef<SDDbgValue*>();
188 using DbgIterator = SmallVectorImpl<SDDbgValue*>::iterator;
190 DbgIterator DbgBegin() { return DbgValues.begin(); }
191 DbgIterator DbgEnd() { return DbgValues.end(); }
192 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
193 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
196 void checkForCycles(const SelectionDAG *DAG, bool force = false);
198 /// This is used to represent a portion of an LLVM function in a low-level
199 /// Data Dependence DAG representation suitable for instruction selection.
200 /// This DAG is constructed as the first step of instruction selection in order
201 /// to allow implementation of machine specific optimizations
202 /// and code simplifications.
204 /// The representation used by the SelectionDAG is a target-independent
205 /// representation, which has some similarities to the GCC RTL representation,
206 /// but is significantly more simple, powerful, and is a graph form instead of a
210 const TargetMachine &TM;
211 const SelectionDAGTargetInfo *TSI = nullptr;
212 const TargetLowering *TLI = nullptr;
214 LLVMContext *Context;
215 CodeGenOpt::Level OptLevel;
217 /// The function-level optimization remark emitter. Used to emit remarks
218 /// whenever manipulating the DAG.
219 OptimizationRemarkEmitter *ORE;
221 /// The starting token.
224 /// The root of the entire DAG.
227 /// A linked list of nodes in the current DAG.
228 ilist<SDNode> AllNodes;
230 /// The AllocatorType for allocating SDNodes. We use
231 /// pool allocation with recycling.
232 using NodeAllocatorType = RecyclingAllocator<BumpPtrAllocator, SDNode,
233 sizeof(LargestSDNode),
234 alignof(MostAlignedSDNode)>;
236 /// Pool allocation for nodes.
237 NodeAllocatorType NodeAllocator;
239 /// This structure is used to memoize nodes, automatically performing
240 /// CSE with existing nodes when a duplicate is requested.
241 FoldingSet<SDNode> CSEMap;
243 /// Pool allocation for machine-opcode SDNode operands.
244 BumpPtrAllocator OperandAllocator;
245 ArrayRecycler<SDUse> OperandRecycler;
247 /// Pool allocation for misc. objects that are created once per SelectionDAG.
248 BumpPtrAllocator Allocator;
250 /// Tracks dbg_value information through SDISel.
253 uint16_t NextPersistentId = 0;
256 /// Clients of various APIs that cause global effects on
257 /// the DAG can optionally implement this interface. This allows the clients
258 /// to handle the various sorts of updates that happen.
260 /// A DAGUpdateListener automatically registers itself with DAG when it is
261 /// constructed, and removes itself when destroyed in RAII fashion.
262 struct DAGUpdateListener {
263 DAGUpdateListener *const Next;
266 explicit DAGUpdateListener(SelectionDAG &D)
267 : Next(D.UpdateListeners), DAG(D) {
268 DAG.UpdateListeners = this;
271 virtual ~DAGUpdateListener() {
272 assert(DAG.UpdateListeners == this &&
273 "DAGUpdateListeners must be destroyed in LIFO order");
274 DAG.UpdateListeners = Next;
277 /// The node N that was deleted and, if E is not null, an
278 /// equivalent node E that replaced it.
279 virtual void NodeDeleted(SDNode *N, SDNode *E);
281 /// The node N that was updated.
282 virtual void NodeUpdated(SDNode *N);
285 struct DAGNodeDeletedListener : public DAGUpdateListener {
286 std::function<void(SDNode *, SDNode *)> Callback;
288 DAGNodeDeletedListener(SelectionDAG &DAG,
289 std::function<void(SDNode *, SDNode *)> Callback)
290 : DAGUpdateListener(DAG), Callback(std::move(Callback)) {}
292 void NodeDeleted(SDNode *N, SDNode *E) override { Callback(N, E); }
295 /// When true, additional steps are taken to
296 /// ensure that getConstant() and similar functions return DAG nodes that
297 /// have legal types. This is important after type legalization since
298 /// any illegally typed nodes generated after this point will not experience
299 /// type legalization.
300 bool NewNodesMustHaveLegalTypes = false;
303 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
304 friend struct DAGUpdateListener;
306 /// Linked list of registered DAGUpdateListener instances.
307 /// This stack is maintained by DAGUpdateListener RAII.
308 DAGUpdateListener *UpdateListeners = nullptr;
310 /// Implementation of setSubgraphColor.
311 /// Return whether we had to truncate the search.
312 bool setSubgraphColorHelper(SDNode *N, const char *Color,
313 DenseSet<SDNode *> &visited,
314 int level, bool &printed);
316 template <typename SDNodeT, typename... ArgTypes>
317 SDNodeT *newSDNode(ArgTypes &&... Args) {
318 return new (NodeAllocator.template Allocate<SDNodeT>())
319 SDNodeT(std::forward<ArgTypes>(Args)...);
322 /// Build a synthetic SDNodeT with the given args and extract its subclass
323 /// data as an integer (e.g. for use in a folding set).
325 /// The args to this function are the same as the args to SDNodeT's
326 /// constructor, except the second arg (assumed to be a const DebugLoc&) is
328 template <typename SDNodeT, typename... ArgTypes>
329 static uint16_t getSyntheticNodeSubclassData(unsigned IROrder,
330 ArgTypes &&... Args) {
331 // The compiler can reduce this expression to a constant iff we pass an
332 // empty DebugLoc. Thankfully, the debug location doesn't have any bearing
333 // on the subclass data.
334 return SDNodeT(IROrder, DebugLoc(), std::forward<ArgTypes>(Args)...)
335 .getRawSubclassData();
338 void createOperands(SDNode *Node, ArrayRef<SDValue> Vals) {
339 assert(!Node->OperandList && "Node already has operands");
340 SDUse *Ops = OperandRecycler.allocate(
341 ArrayRecycler<SDUse>::Capacity::get(Vals.size()), OperandAllocator);
343 for (unsigned I = 0; I != Vals.size(); ++I) {
344 Ops[I].setUser(Node);
345 Ops[I].setInitial(Vals[I]);
347 Node->NumOperands = Vals.size();
348 Node->OperandList = Ops;
349 checkForCycles(Node);
352 void removeOperands(SDNode *Node) {
353 if (!Node->OperandList)
355 OperandRecycler.deallocate(
356 ArrayRecycler<SDUse>::Capacity::get(Node->NumOperands),
358 Node->NumOperands = 0;
359 Node->OperandList = nullptr;
363 explicit SelectionDAG(const TargetMachine &TM, CodeGenOpt::Level);
364 SelectionDAG(const SelectionDAG &) = delete;
365 SelectionDAG &operator=(const SelectionDAG &) = delete;
368 /// Prepare this SelectionDAG to process code in the given MachineFunction.
369 void init(MachineFunction &NewMF, OptimizationRemarkEmitter &NewORE);
371 /// Clear state and free memory necessary to make this
372 /// SelectionDAG ready to process a new block.
375 MachineFunction &getMachineFunction() const { return *MF; }
376 const DataLayout &getDataLayout() const { return MF->getDataLayout(); }
377 const TargetMachine &getTarget() const { return TM; }
378 const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
379 const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
380 const SelectionDAGTargetInfo &getSelectionDAGInfo() const { return *TSI; }
381 LLVMContext *getContext() const {return Context; }
382 OptimizationRemarkEmitter &getORE() const { return *ORE; }
384 /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
385 void viewGraph(const std::string &Title);
389 std::map<const SDNode *, std::string> NodeGraphAttrs;
392 /// Clear all previously defined node graph attributes.
393 /// Intended to be used from a debugging tool (eg. gdb).
394 void clearGraphAttrs();
396 /// Set graph attributes for a node. (eg. "color=red".)
397 void setGraphAttrs(const SDNode *N, const char *Attrs);
399 /// Get graph attributes for a node. (eg. "color=red".)
400 /// Used from getNodeAttributes.
401 const std::string getGraphAttrs(const SDNode *N) const;
403 /// Convenience for setting node color attribute.
404 void setGraphColor(const SDNode *N, const char *Color);
406 /// Convenience for setting subgraph color attribute.
407 void setSubgraphColor(SDNode *N, const char *Color);
409 using allnodes_const_iterator = ilist<SDNode>::const_iterator;
411 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
412 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
414 using allnodes_iterator = ilist<SDNode>::iterator;
416 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
417 allnodes_iterator allnodes_end() { return AllNodes.end(); }
419 ilist<SDNode>::size_type allnodes_size() const {
420 return AllNodes.size();
423 iterator_range<allnodes_iterator> allnodes() {
424 return make_range(allnodes_begin(), allnodes_end());
426 iterator_range<allnodes_const_iterator> allnodes() const {
427 return make_range(allnodes_begin(), allnodes_end());
430 /// Return the root tag of the SelectionDAG.
431 const SDValue &getRoot() const { return Root; }
433 /// Return the token chain corresponding to the entry of the function.
434 SDValue getEntryNode() const {
435 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
438 /// Set the current root tag of the SelectionDAG.
440 const SDValue &setRoot(SDValue N) {
441 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
442 "DAG root value is not a chain!");
444 checkForCycles(N.getNode(), this);
447 checkForCycles(this);
451 /// This iterates over the nodes in the SelectionDAG, folding
452 /// certain types of nodes together, or eliminating superfluous nodes. The
453 /// Level argument controls whether Combine is allowed to produce nodes and
454 /// types that are illegal on the target.
455 void Combine(CombineLevel Level, AliasAnalysis *AA,
456 CodeGenOpt::Level OptLevel);
458 /// This transforms the SelectionDAG into a SelectionDAG that
459 /// only uses types natively supported by the target.
460 /// Returns "true" if it made any changes.
462 /// Note that this is an involved process that may invalidate pointers into
464 bool LegalizeTypes();
466 /// This transforms the SelectionDAG into a SelectionDAG that is
467 /// compatible with the target instruction selector, as indicated by the
468 /// TargetLowering object.
470 /// Note that this is an involved process that may invalidate pointers into
474 /// \brief Transforms a SelectionDAG node and any operands to it into a node
475 /// that is compatible with the target instruction selector, as indicated by
476 /// the TargetLowering object.
478 /// \returns true if \c N is a valid, legal node after calling this.
480 /// This essentially runs a single recursive walk of the \c Legalize process
481 /// over the given node (and its operands). This can be used to incrementally
482 /// legalize the DAG. All of the nodes which are directly replaced,
483 /// potentially including N, are added to the output parameter \c
484 /// UpdatedNodes so that the delta to the DAG can be understood by the
487 /// When this returns false, N has been legalized in a way that make the
488 /// pointer passed in no longer valid. It may have even been deleted from the
489 /// DAG, and so it shouldn't be used further. When this returns true, the
490 /// N passed in is a legal node, and can be immediately processed as such.
491 /// This may still have done some work on the DAG, and will still populate
492 /// UpdatedNodes with any new nodes replacing those originally in the DAG.
493 bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
495 /// This transforms the SelectionDAG into a SelectionDAG
496 /// that only uses vector math operations supported by the target. This is
497 /// necessary as a separate step from Legalize because unrolling a vector
498 /// operation can introduce illegal types, which requires running
499 /// LegalizeTypes again.
501 /// This returns true if it made any changes; in that case, LegalizeTypes
502 /// is called again before Legalize.
504 /// Note that this is an involved process that may invalidate pointers into
506 bool LegalizeVectors();
508 /// This method deletes all unreachable nodes in the SelectionDAG.
509 void RemoveDeadNodes();
511 /// Remove the specified node from the system. This node must
512 /// have no referrers.
513 void DeleteNode(SDNode *N);
515 /// Return an SDVTList that represents the list of values specified.
516 SDVTList getVTList(EVT VT);
517 SDVTList getVTList(EVT VT1, EVT VT2);
518 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
519 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
520 SDVTList getVTList(ArrayRef<EVT> VTs);
522 //===--------------------------------------------------------------------===//
523 // Node creation methods.
525 /// \brief Create a ConstantSDNode wrapping a constant value.
526 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
528 /// If only legal types can be produced, this does the necessary
529 /// transformations (e.g., if the vector element type is illegal).
531 SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT,
532 bool isTarget = false, bool isOpaque = false);
533 SDValue getConstant(const APInt &Val, const SDLoc &DL, EVT VT,
534 bool isTarget = false, bool isOpaque = false);
536 SDValue getAllOnesConstant(const SDLoc &DL, EVT VT, bool IsTarget = false,
537 bool IsOpaque = false) {
538 return getConstant(APInt::getAllOnesValue(VT.getScalarSizeInBits()), DL,
539 VT, IsTarget, IsOpaque);
542 SDValue getConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
543 bool isTarget = false, bool isOpaque = false);
544 SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL,
545 bool isTarget = false);
546 SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT,
547 bool isOpaque = false) {
548 return getConstant(Val, DL, VT, true, isOpaque);
550 SDValue getTargetConstant(const APInt &Val, const SDLoc &DL, EVT VT,
551 bool isOpaque = false) {
552 return getConstant(Val, DL, VT, true, isOpaque);
554 SDValue getTargetConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
555 bool isOpaque = false) {
556 return getConstant(Val, DL, VT, true, isOpaque);
560 /// \brief Create a ConstantFPSDNode wrapping a constant value.
561 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
563 /// If only legal types can be produced, this does the necessary
564 /// transformations (e.g., if the vector element type is illegal).
565 /// The forms that take a double should only be used for simple constants
566 /// that can be exactly represented in VT. No checks are made.
568 SDValue getConstantFP(double Val, const SDLoc &DL, EVT VT,
569 bool isTarget = false);
570 SDValue getConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT,
571 bool isTarget = false);
572 SDValue getConstantFP(const ConstantFP &CF, const SDLoc &DL, EVT VT,
573 bool isTarget = false);
574 SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT) {
575 return getConstantFP(Val, DL, VT, true);
577 SDValue getTargetConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT) {
578 return getConstantFP(Val, DL, VT, true);
580 SDValue getTargetConstantFP(const ConstantFP &Val, const SDLoc &DL, EVT VT) {
581 return getConstantFP(Val, DL, VT, true);
585 SDValue getGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
586 int64_t offset = 0, bool isTargetGA = false,
587 unsigned char TargetFlags = 0);
588 SDValue getTargetGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
590 unsigned char TargetFlags = 0) {
591 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
593 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
594 SDValue getTargetFrameIndex(int FI, EVT VT) {
595 return getFrameIndex(FI, VT, true);
597 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
598 unsigned char TargetFlags = 0);
599 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
600 return getJumpTable(JTI, VT, true, TargetFlags);
602 SDValue getConstantPool(const Constant *C, EVT VT,
603 unsigned Align = 0, int Offs = 0, bool isT=false,
604 unsigned char TargetFlags = 0);
605 SDValue getTargetConstantPool(const Constant *C, EVT VT,
606 unsigned Align = 0, int Offset = 0,
607 unsigned char TargetFlags = 0) {
608 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
610 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
611 unsigned Align = 0, int Offs = 0, bool isT=false,
612 unsigned char TargetFlags = 0);
613 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
614 EVT VT, unsigned Align = 0,
615 int Offset = 0, unsigned char TargetFlags=0) {
616 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
618 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
619 unsigned char TargetFlags = 0);
620 // When generating a branch to a BB, we don't in general know enough
621 // to provide debug info for the BB at that time, so keep this one around.
622 SDValue getBasicBlock(MachineBasicBlock *MBB);
623 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
624 SDValue getExternalSymbol(const char *Sym, EVT VT);
625 SDValue getExternalSymbol(const char *Sym, const SDLoc &dl, EVT VT);
626 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
627 unsigned char TargetFlags = 0);
628 SDValue getMCSymbol(MCSymbol *Sym, EVT VT);
630 SDValue getValueType(EVT);
631 SDValue getRegister(unsigned Reg, EVT VT);
632 SDValue getRegisterMask(const uint32_t *RegMask);
633 SDValue getEHLabel(const SDLoc &dl, SDValue Root, MCSymbol *Label);
634 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
635 int64_t Offset = 0, bool isTarget = false,
636 unsigned char TargetFlags = 0);
637 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
639 unsigned char TargetFlags = 0) {
640 return getBlockAddress(BA, VT, Offset, true, TargetFlags);
643 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg,
645 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
646 getRegister(Reg, N.getValueType()), N);
649 // This version of the getCopyToReg method takes an extra operand, which
650 // indicates that there is potentially an incoming glue value (if Glue is not
651 // null) and that there should be a glue result.
652 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N,
654 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
655 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
656 return getNode(ISD::CopyToReg, dl, VTs,
657 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
660 // Similar to last getCopyToReg() except parameter Reg is a SDValue
661 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, SDValue Reg, SDValue N,
663 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
664 SDValue Ops[] = { Chain, Reg, N, Glue };
665 return getNode(ISD::CopyToReg, dl, VTs,
666 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
669 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT) {
670 SDVTList VTs = getVTList(VT, MVT::Other);
671 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
672 return getNode(ISD::CopyFromReg, dl, VTs, Ops);
675 // This version of the getCopyFromReg method takes an extra operand, which
676 // indicates that there is potentially an incoming glue value (if Glue is not
677 // null) and that there should be a glue result.
678 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT,
680 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
681 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
682 return getNode(ISD::CopyFromReg, dl, VTs,
683 makeArrayRef(Ops, Glue.getNode() ? 3 : 2));
686 SDValue getCondCode(ISD::CondCode Cond);
688 /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT,
689 /// which must be a vector type, must match the number of mask elements
690 /// NumElts. An integer mask element equal to -1 is treated as undefined.
691 SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2,
694 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
695 /// which must be a vector type, must match the number of operands in Ops.
696 /// The operands must have the same type as (or, for integers, a type wider
697 /// than) VT's element type.
698 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDValue> Ops) {
699 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
700 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
703 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
704 /// which must be a vector type, must match the number of operands in Ops.
705 /// The operands must have the same type as (or, for integers, a type wider
706 /// than) VT's element type.
707 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDUse> Ops) {
708 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
709 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
712 /// Return a splat ISD::BUILD_VECTOR node, consisting of Op splatted to all
713 /// elements. VT must be a vector type. Op's type must be the same as (or,
714 /// for integers, a type wider than) VT's element type.
715 SDValue getSplatBuildVector(EVT VT, const SDLoc &DL, SDValue Op) {
716 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
717 if (Op.getOpcode() == ISD::UNDEF) {
718 assert((VT.getVectorElementType() == Op.getValueType() ||
720 VT.getVectorElementType().bitsLE(Op.getValueType()))) &&
721 "A splatted value must have a width equal or (for integers) "
722 "greater than the vector element type!");
723 return getNode(ISD::UNDEF, SDLoc(), VT);
726 SmallVector<SDValue, 16> Ops(VT.getVectorNumElements(), Op);
727 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
730 /// \brief Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
731 /// the shuffle node in input but with swapped operands.
733 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
734 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
736 /// Convert Op, which must be of float type, to the
737 /// float type VT, by either extending or rounding (by truncation).
738 SDValue getFPExtendOrRound(SDValue Op, const SDLoc &DL, EVT VT);
740 /// Convert Op, which must be of integer type, to the
741 /// integer type VT, by either any-extending or truncating it.
742 SDValue getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
744 /// Convert Op, which must be of integer type, to the
745 /// integer type VT, by either sign-extending or truncating it.
746 SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
748 /// Convert Op, which must be of integer type, to the
749 /// integer type VT, by either zero-extending or truncating it.
750 SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
752 /// Return the expression required to zero extend the Op
753 /// value assuming it was the smaller SrcTy value.
754 SDValue getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT SrcTy);
756 /// Return an operation which will any-extend the low lanes of the operand
757 /// into the specified vector type. For example,
758 /// this can convert a v16i8 into a v4i32 by any-extending the low four
759 /// lanes of the operand from i8 to i32.
760 SDValue getAnyExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
762 /// Return an operation which will sign extend the low lanes of the operand
763 /// into the specified vector type. For example,
764 /// this can convert a v16i8 into a v4i32 by sign extending the low four
765 /// lanes of the operand from i8 to i32.
766 SDValue getSignExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
768 /// Return an operation which will zero extend the low lanes of the operand
769 /// into the specified vector type. For example,
770 /// this can convert a v16i8 into a v4i32 by zero extending the low four
771 /// lanes of the operand from i8 to i32.
772 SDValue getZeroExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
774 /// Convert Op, which must be of integer type, to the integer type VT,
775 /// by using an extension appropriate for the target's
776 /// BooleanContent for type OpVT or truncating it.
777 SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT);
779 /// Create a bitwise NOT operation as (XOR Val, -1).
780 SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT);
782 /// \brief Create a logical NOT operation as (XOR Val, BooleanOne).
783 SDValue getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT);
785 /// Return a new CALLSEQ_START node, that starts new call frame, in which
786 /// InSize bytes are set up inside CALLSEQ_START..CALLSEQ_END sequence and
787 /// OutSize specifies part of the frame set up prior to the sequence.
788 SDValue getCALLSEQ_START(SDValue Chain, uint64_t InSize, uint64_t OutSize,
790 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
791 SDValue Ops[] = { Chain,
792 getIntPtrConstant(InSize, DL, true),
793 getIntPtrConstant(OutSize, DL, true) };
794 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
797 /// Return a new CALLSEQ_END node, which always must have a
798 /// glue result (to ensure it's not CSE'd).
799 /// CALLSEQ_END does not have a useful SDLoc.
800 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
801 SDValue InGlue, const SDLoc &DL) {
802 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
803 SmallVector<SDValue, 4> Ops;
804 Ops.push_back(Chain);
807 if (InGlue.getNode())
808 Ops.push_back(InGlue);
809 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
812 /// Return true if the result of this operation is always undefined.
813 bool isUndef(unsigned Opcode, ArrayRef<SDValue> Ops);
815 /// Return an UNDEF node. UNDEF does not have a useful SDLoc.
816 SDValue getUNDEF(EVT VT) {
817 return getNode(ISD::UNDEF, SDLoc(), VT);
820 /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc.
821 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
822 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
825 /// Gets or creates the specified node.
827 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
828 ArrayRef<SDUse> Ops);
829 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
830 ArrayRef<SDValue> Ops, const SDNodeFlags Flags = SDNodeFlags());
831 SDValue getNode(unsigned Opcode, const SDLoc &DL, ArrayRef<EVT> ResultTys,
832 ArrayRef<SDValue> Ops);
833 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs,
834 ArrayRef<SDValue> Ops);
836 // Specialize based on number of operands.
837 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT);
838 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N,
839 const SDNodeFlags Flags = SDNodeFlags());
840 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
841 SDValue N2, const SDNodeFlags Flags = SDNodeFlags());
842 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
843 SDValue N2, SDValue N3);
844 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
845 SDValue N2, SDValue N3, SDValue N4);
846 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
847 SDValue N2, SDValue N3, SDValue N4, SDValue N5);
849 // Specialize again based on number of operands for nodes with a VTList
850 // rather than a single VT.
851 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs);
852 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N);
853 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1,
855 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1,
856 SDValue N2, SDValue N3);
857 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1,
858 SDValue N2, SDValue N3, SDValue N4);
859 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1,
860 SDValue N2, SDValue N3, SDValue N4, SDValue N5);
862 /// Compute a TokenFactor to force all the incoming stack arguments to be
863 /// loaded from the stack. This is used in tail call lowering to protect
864 /// stack arguments from being clobbered.
865 SDValue getStackArgumentTokenFactor(SDValue Chain);
867 SDValue getMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
868 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
869 bool isTailCall, MachinePointerInfo DstPtrInfo,
870 MachinePointerInfo SrcPtrInfo);
872 SDValue getMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
873 SDValue Size, unsigned Align, bool isVol, bool isTailCall,
874 MachinePointerInfo DstPtrInfo,
875 MachinePointerInfo SrcPtrInfo);
877 SDValue getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
878 SDValue Size, unsigned Align, bool isVol, bool isTailCall,
879 MachinePointerInfo DstPtrInfo);
881 /// Helper function to make it easier to build SetCC's if you just
882 /// have an ISD::CondCode instead of an SDValue.
884 SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS,
885 ISD::CondCode Cond) {
886 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
887 "Cannot compare scalars to vectors");
888 assert(LHS.getValueType().isVector() == VT.isVector() &&
889 "Cannot compare scalars to vectors");
890 assert(Cond != ISD::SETCC_INVALID &&
891 "Cannot create a setCC of an invalid node.");
892 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
895 /// Helper function to make it easier to build Select's if you just
896 /// have operands and don't want to check for vector.
897 SDValue getSelect(const SDLoc &DL, EVT VT, SDValue Cond, SDValue LHS,
899 assert(LHS.getValueType() == RHS.getValueType() &&
900 "Cannot use select on differing types");
901 assert(VT.isVector() == LHS.getValueType().isVector() &&
902 "Cannot mix vectors and scalars");
903 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
907 /// Helper function to make it easier to build SelectCC's if you
908 /// just have an ISD::CondCode instead of an SDValue.
910 SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True,
911 SDValue False, ISD::CondCode Cond) {
912 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
913 LHS, RHS, True, False, getCondCode(Cond));
916 /// VAArg produces a result and token chain, and takes a pointer
917 /// and a source value as input.
918 SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
919 SDValue SV, unsigned Align);
921 /// Gets a node for an atomic cmpxchg op. There are two
922 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
923 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
924 /// a success flag (initially i1), and a chain.
925 SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
926 SDVTList VTs, SDValue Chain, SDValue Ptr,
927 SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
928 unsigned Alignment, AtomicOrdering SuccessOrdering,
929 AtomicOrdering FailureOrdering,
931 SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
932 SDVTList VTs, SDValue Chain, SDValue Ptr,
933 SDValue Cmp, SDValue Swp, MachineMemOperand *MMO);
935 /// Gets a node for an atomic op, produces result (if relevant)
936 /// and chain and takes 2 operands.
937 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
938 SDValue Ptr, SDValue Val, const Value *PtrVal,
939 unsigned Alignment, AtomicOrdering Ordering,
941 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
942 SDValue Ptr, SDValue Val, MachineMemOperand *MMO);
944 /// Gets a node for an atomic op, produces result and chain and
946 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, EVT VT,
947 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO);
949 /// Gets a node for an atomic op, produces result and chain and takes N
951 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT,
952 SDVTList VTList, ArrayRef<SDValue> Ops,
953 MachineMemOperand *MMO);
955 /// Creates a MemIntrinsicNode that may produce a
956 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
957 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
958 /// less than FIRST_TARGET_MEMORY_OPCODE.
959 SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList,
960 ArrayRef<SDValue> Ops, EVT MemVT,
961 MachinePointerInfo PtrInfo, unsigned Align = 0,
962 bool Vol = false, bool ReadMem = true,
963 bool WriteMem = true, unsigned Size = 0);
965 SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList,
966 ArrayRef<SDValue> Ops, EVT MemVT,
967 MachineMemOperand *MMO);
969 /// Create a MERGE_VALUES node from the given operands.
970 SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl);
972 /// Loads are not normal binary operators: their result type is not
973 /// determined by their operands, and they produce a value AND a token chain.
975 /// This function will set the MOLoad flag on MMOFlags, but you can set it if
976 /// you want. The MOStore flag must not be set.
977 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
978 MachinePointerInfo PtrInfo, unsigned Alignment = 0,
979 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
980 const AAMDNodes &AAInfo = AAMDNodes(),
981 const MDNode *Ranges = nullptr);
982 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
983 MachineMemOperand *MMO);
985 getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain,
986 SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT,
987 unsigned Alignment = 0,
988 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
989 const AAMDNodes &AAInfo = AAMDNodes());
990 SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT,
991 SDValue Chain, SDValue Ptr, EVT MemVT,
992 MachineMemOperand *MMO);
993 SDValue getIndexedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base,
994 SDValue Offset, ISD::MemIndexedMode AM);
995 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
996 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
997 MachinePointerInfo PtrInfo, EVT MemVT, unsigned Alignment = 0,
998 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
999 const AAMDNodes &AAInfo = AAMDNodes(),
1000 const MDNode *Ranges = nullptr);
1001 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1002 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1003 EVT MemVT, MachineMemOperand *MMO);
1005 /// Helper function to build ISD::STORE nodes.
1007 /// This function will set the MOStore flag on MMOFlags, but you can set it if
1008 /// you want. The MOLoad and MOInvariant flags must not be set.
1010 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1011 MachinePointerInfo PtrInfo, unsigned Alignment = 0,
1012 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1013 const AAMDNodes &AAInfo = AAMDNodes());
1014 SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1015 MachineMemOperand *MMO);
1017 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1018 MachinePointerInfo PtrInfo, EVT TVT, unsigned Alignment = 0,
1019 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1020 const AAMDNodes &AAInfo = AAMDNodes());
1021 SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val,
1022 SDValue Ptr, EVT TVT, MachineMemOperand *MMO);
1023 SDValue getIndexedStore(SDValue OrigStoe, const SDLoc &dl, SDValue Base,
1024 SDValue Offset, ISD::MemIndexedMode AM);
1026 /// Returns sum of the base pointer and offset.
1027 SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, const SDLoc &DL);
1029 SDValue getMaskedLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1030 SDValue Mask, SDValue Src0, EVT MemVT,
1031 MachineMemOperand *MMO, ISD::LoadExtType,
1032 bool IsExpanding = false);
1033 SDValue getMaskedStore(SDValue Chain, const SDLoc &dl, SDValue Val,
1034 SDValue Ptr, SDValue Mask, EVT MemVT,
1035 MachineMemOperand *MMO, bool IsTruncating = false,
1036 bool IsCompressing = false);
1037 SDValue getMaskedGather(SDVTList VTs, EVT VT, const SDLoc &dl,
1038 ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
1039 SDValue getMaskedScatter(SDVTList VTs, EVT VT, const SDLoc &dl,
1040 ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
1042 /// Return (create a new or find existing) a target-specific node.
1043 /// TargetMemSDNode should be derived class from MemSDNode.
1044 template <class TargetMemSDNode>
1045 SDValue getTargetMemSDNode(SDVTList VTs, ArrayRef<SDValue> Ops,
1046 const SDLoc &dl, EVT MemVT,
1047 MachineMemOperand *MMO);
1049 /// Construct a node to track a Value* through the backend.
1050 SDValue getSrcValue(const Value *v);
1052 /// Return an MDNodeSDNode which holds an MDNode.
1053 SDValue getMDNode(const MDNode *MD);
1055 /// Return a bitcast using the SDLoc of the value operand, and casting to the
1056 /// provided type. Use getNode to set a custom SDLoc.
1057 SDValue getBitcast(EVT VT, SDValue V);
1059 /// Return an AddrSpaceCastSDNode.
1060 SDValue getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr, unsigned SrcAS,
1063 /// Return the specified value casted to
1064 /// the target's desired shift amount type.
1065 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
1067 /// Expand the specified \c ISD::VAARG node as the Legalize pass would.
1068 SDValue expandVAArg(SDNode *Node);
1070 /// Expand the specified \c ISD::VACOPY node as the Legalize pass would.
1071 SDValue expandVACopy(SDNode *Node);
1073 /// *Mutate* the specified node in-place to have the
1074 /// specified operands. If the resultant node already exists in the DAG,
1075 /// this does not modify the specified node, instead it returns the node that
1076 /// already exists. If the resultant node does not exist in the DAG, the
1077 /// input node is returned. As a degenerate case, if you specify the same
1078 /// input operands as the node already has, the input node is returned.
1079 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
1080 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
1081 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1083 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1084 SDValue Op3, SDValue Op4);
1085 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1086 SDValue Op3, SDValue Op4, SDValue Op5);
1087 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
1089 /// These are used for target selectors to *mutate* the
1090 /// specified node to have the specified return type, Target opcode, and
1091 /// operands. Note that target opcodes are stored as
1092 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
1093 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
1094 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
1095 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
1096 SDValue Op1, SDValue Op2);
1097 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
1098 SDValue Op1, SDValue Op2, SDValue Op3);
1099 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
1100 ArrayRef<SDValue> Ops);
1101 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
1102 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1103 EVT VT2, ArrayRef<SDValue> Ops);
1104 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1105 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1106 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1107 EVT VT2, SDValue Op1);
1108 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1109 EVT VT2, SDValue Op1, SDValue Op2);
1110 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
1111 ArrayRef<SDValue> Ops);
1113 /// This *mutates* the specified node to have the specified
1114 /// return type, opcode, and operands.
1115 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
1116 ArrayRef<SDValue> Ops);
1118 /// Mutate the specified strict FP node to its non-strict equivalent,
1119 /// unlinking the node from its chain and dropping the metadata arguments.
1120 /// The node must be a strict FP node.
1121 SDNode *mutateStrictFPToFP(SDNode *Node);
1123 /// These are used for target selectors to create a new node
1124 /// with specified return type(s), MachineInstr opcode, and operands.
1126 /// Note that getMachineNode returns the resultant node. If there is already
1127 /// a node of the specified opcode and operands, it returns that node instead
1128 /// of the current one.
1129 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT);
1130 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1132 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1133 SDValue Op1, SDValue Op2);
1134 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1135 SDValue Op1, SDValue Op2, SDValue Op3);
1136 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1137 ArrayRef<SDValue> Ops);
1138 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1139 EVT VT2, SDValue Op1, SDValue Op2);
1140 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1141 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
1142 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1143 EVT VT2, ArrayRef<SDValue> Ops);
1144 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1145 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2);
1146 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1147 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2,
1149 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1150 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1151 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl,
1152 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops);
1153 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, SDVTList VTs,
1154 ArrayRef<SDValue> Ops);
1156 /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
1157 SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1160 /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes.
1161 SDValue getTargetInsertSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1162 SDValue Operand, SDValue Subreg);
1164 /// Get the specified node if it's already available, or else return NULL.
1165 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops,
1166 const SDNodeFlags Flags = SDNodeFlags());
1168 /// Creates a SDDbgValue node.
1169 SDDbgValue *getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N, unsigned R,
1170 bool IsIndirect, uint64_t Off, const DebugLoc &DL,
1174 SDDbgValue *getConstantDbgValue(MDNode *Var, MDNode *Expr, const Value *C,
1175 uint64_t Off, const DebugLoc &DL, unsigned O);
1178 SDDbgValue *getFrameIndexDbgValue(MDNode *Var, MDNode *Expr, unsigned FI,
1179 uint64_t Off, const DebugLoc &DL,
1182 /// Remove the specified node from the system. If any of its
1183 /// operands then becomes dead, remove them as well. Inform UpdateListener
1184 /// for each node deleted.
1185 void RemoveDeadNode(SDNode *N);
1187 /// This method deletes the unreachable nodes in the
1188 /// given list, and any nodes that become unreachable as a result.
1189 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
1191 /// Modify anything using 'From' to use 'To' instead.
1192 /// This can cause recursive merging of nodes in the DAG. Use the first
1193 /// version if 'From' is known to have a single result, use the second
1194 /// if you have two nodes with identical results (or if 'To' has a superset
1195 /// of the results of 'From'), use the third otherwise.
1197 /// These methods all take an optional UpdateListener, which (if not null) is
1198 /// informed about nodes that are deleted and modified due to recursive
1199 /// changes in the dag.
1201 /// These functions only replace all existing uses. It's possible that as
1202 /// these replacements are being performed, CSE may cause the From node
1203 /// to be given new uses. These new uses of From are left in place, and
1204 /// not automatically transferred to To.
1206 void ReplaceAllUsesWith(SDValue From, SDValue Op);
1207 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
1208 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
1210 /// Replace any uses of From with To, leaving
1211 /// uses of other values produced by From.Val alone.
1212 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
1214 /// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
1215 /// This correctly handles the case where
1216 /// there is an overlap between the From values and the To values.
1217 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
1220 /// If an existing load has uses of its chain, create a token factor node with
1221 /// that chain and the new memory node's chain and update users of the old
1222 /// chain to the token factor. This ensures that the new memory node will have
1223 /// the same relative memory dependency position as the old load. Returns the
1224 /// new merged load chain.
1225 SDValue makeEquivalentMemoryOrdering(LoadSDNode *Old, SDValue New);
1227 /// Topological-sort the AllNodes list and a
1228 /// assign a unique node id for each node in the DAG based on their
1229 /// topological order. Returns the number of nodes.
1230 unsigned AssignTopologicalOrder();
1232 /// Move node N in the AllNodes list to be immediately
1233 /// before the given iterator Position. This may be used to update the
1234 /// topological ordering when the list of nodes is modified.
1235 void RepositionNode(allnodes_iterator Position, SDNode *N) {
1236 AllNodes.insert(Position, AllNodes.remove(N));
1239 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1240 /// a vector type, the element semantics are returned.
1241 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1242 switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1243 default: llvm_unreachable("Unknown FP format");
1244 case MVT::f16: return APFloat::IEEEhalf();
1245 case MVT::f32: return APFloat::IEEEsingle();
1246 case MVT::f64: return APFloat::IEEEdouble();
1247 case MVT::f80: return APFloat::x87DoubleExtended();
1248 case MVT::f128: return APFloat::IEEEquad();
1249 case MVT::ppcf128: return APFloat::PPCDoubleDouble();
1253 /// Add a dbg_value SDNode. If SD is non-null that means the
1254 /// value is produced by SD.
1255 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1257 /// Get the debug values which reference the given SDNode.
1258 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
1259 return DbgInfo->getSDDbgValues(SD);
1263 /// Transfer SDDbgValues. Called via ReplaceAllUses{OfValue}?With
1264 void TransferDbgValues(SDValue From, SDValue To);
1267 /// Return true if there are any SDDbgValue nodes associated
1268 /// with this SelectionDAG.
1269 bool hasDebugValues() const { return !DbgInfo->empty(); }
1271 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
1272 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
1274 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
1275 return DbgInfo->ByvalParmDbgBegin();
1278 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
1279 return DbgInfo->ByvalParmDbgEnd();
1284 /// Create a stack temporary, suitable for holding the specified value type.
1285 /// If minAlign is specified, the slot size will have at least that alignment.
1286 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1288 /// Create a stack temporary suitable for holding either of the specified
1290 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1292 SDValue FoldSymbolOffset(unsigned Opcode, EVT VT,
1293 const GlobalAddressSDNode *GA,
1296 SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1297 SDNode *Cst1, SDNode *Cst2);
1299 SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1300 const ConstantSDNode *Cst1,
1301 const ConstantSDNode *Cst2);
1303 SDValue FoldConstantVectorArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1304 ArrayRef<SDValue> Ops,
1305 const SDNodeFlags Flags = SDNodeFlags());
1307 /// Constant fold a setcc to true or false.
1308 SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond,
1311 /// Return true if the sign bit of Op is known to be zero.
1312 /// We use this predicate to simplify operations downstream.
1313 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1315 /// Return true if 'Op & Mask' is known to be zero. We
1316 /// use this predicate to simplify operations downstream. Op and Mask are
1317 /// known to be the same type.
1318 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1321 /// Determine which bits of Op are known to be either zero or one and return
1322 /// them in Known. For vectors, the known bits are those that are shared by
1323 /// every vector element.
1324 /// Targets can implement the computeKnownBitsForTargetNode method in the
1325 /// TargetLowering class to allow target nodes to be understood.
1326 void computeKnownBits(SDValue Op, KnownBits &Known, unsigned Depth = 0) const;
1328 /// Determine which bits of Op are known to be either zero or one and return
1329 /// them in Known. The DemandedElts argument allows us to only collect the
1330 /// known bits that are shared by the requested vector elements.
1331 /// Targets can implement the computeKnownBitsForTargetNode method in the
1332 /// TargetLowering class to allow target nodes to be understood.
1333 void computeKnownBits(SDValue Op, KnownBits &Known, const APInt &DemandedElts,
1334 unsigned Depth = 0) const;
1336 /// Used to represent the possible overflow behavior of an operation.
1337 /// Never: the operation cannot overflow.
1338 /// Always: the operation will always overflow.
1339 /// Sometime: the operation may or may not overflow.
1346 /// Determine if the result of the addition of 2 node can overflow.
1347 OverflowKind computeOverflowKind(SDValue N0, SDValue N1) const;
1349 /// Test if the given value is known to have exactly one bit set. This differs
1350 /// from computeKnownBits in that it doesn't necessarily determine which bit
1352 bool isKnownToBeAPowerOfTwo(SDValue Val) const;
1354 /// Return the number of times the sign bit of the register is replicated into
1355 /// the other bits. We know that at least 1 bit is always equal to the sign
1356 /// bit (itself), but other cases can give us information. For example,
1357 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
1358 /// to each other, so we return 3. Targets can implement the
1359 /// ComputeNumSignBitsForTarget method in the TargetLowering class to allow
1360 /// target nodes to be understood.
1361 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1363 /// Return the number of times the sign bit of the register is replicated into
1364 /// the other bits. We know that at least 1 bit is always equal to the sign
1365 /// bit (itself), but other cases can give us information. For example,
1366 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
1367 /// to each other, so we return 3. The DemandedElts argument allows
1368 /// us to only collect the minimum sign bits of the requested vector elements.
1369 /// Targets can implement the ComputeNumSignBitsForTarget method in the
1370 /// TargetLowering class to allow target nodes to be understood.
1371 unsigned ComputeNumSignBits(SDValue Op, const APInt &DemandedElts,
1372 unsigned Depth = 0) const;
1374 /// Return true if the specified operand is an ISD::ADD with a ConstantSDNode
1375 /// on the right-hand side, or if it is an ISD::OR with a ConstantSDNode that
1376 /// is guaranteed to have the same semantics as an ADD. This handles the
1378 /// X|Cst == X+Cst iff X&Cst = 0.
1379 bool isBaseWithConstantOffset(SDValue Op) const;
1381 /// Test whether the given SDValue is known to never be NaN.
1382 bool isKnownNeverNaN(SDValue Op) const;
1384 /// Test whether the given SDValue is known to never be positive or negative
1386 bool isKnownNeverZero(SDValue Op) const;
1388 /// Test whether two SDValues are known to compare equal. This
1389 /// is true if they are the same value, or if one is negative zero and the
1390 /// other positive zero.
1391 bool isEqualTo(SDValue A, SDValue B) const;
1393 /// Return true if A and B have no common bits set. As an example, this can
1394 /// allow an 'add' to be transformed into an 'or'.
1395 bool haveNoCommonBitsSet(SDValue A, SDValue B) const;
1397 /// Utility function used by legalize and lowering to
1398 /// "unroll" a vector operation by splitting out the scalars and operating
1399 /// on each element individually. If the ResNE is 0, fully unroll the vector
1400 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1401 /// If the ResNE is greater than the width of the vector op, unroll the
1402 /// vector op and fill the end of the resulting vector with UNDEFS.
1403 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1405 /// Return true if loads are next to each other and can be
1406 /// merged. Check that both are nonvolatile and if LD is loading
1407 /// 'Bytes' bytes from a location that is 'Dist' units away from the
1408 /// location that the 'Base' load is loading from.
1409 bool areNonVolatileConsecutiveLoads(LoadSDNode *LD, LoadSDNode *Base,
1410 unsigned Bytes, int Dist) const;
1412 /// Infer alignment of a load / store address. Return 0 if
1413 /// it cannot be inferred.
1414 unsigned InferPtrAlignment(SDValue Ptr) const;
1416 /// Compute the VTs needed for the low/hi parts of a type
1417 /// which is split (or expanded) into two not necessarily identical pieces.
1418 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1420 /// Split the vector with EXTRACT_SUBVECTOR using the provides
1421 /// VTs and return the low/high part.
1422 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1423 const EVT &LoVT, const EVT &HiVT);
1425 /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part.
1426 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1428 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1429 return SplitVector(N, DL, LoVT, HiVT);
1432 /// Split the node's operand with EXTRACT_SUBVECTOR and
1433 /// return the low/high part.
1434 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1436 return SplitVector(N->getOperand(OpNo), SDLoc(N));
1439 /// Append the extracted elements from Start to Count out of the vector Op
1440 /// in Args. If Count is 0, all of the elements will be extracted.
1441 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
1442 unsigned Start = 0, unsigned Count = 0);
1444 /// Compute the default alignment value for the given type.
1445 unsigned getEVTAlignment(EVT MemoryVT) const;
1447 /// Test whether the given value is a constant int or similar node.
1448 SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N);
1450 /// Test whether the given value is a constant FP or similar node.
1451 SDNode *isConstantFPBuildVectorOrConstantFP(SDValue N);
1453 /// \returns true if \p N is any kind of constant or build_vector of
1454 /// constants, int or float. If a vector, it may not necessarily be a splat.
1455 inline bool isConstantValueOfAnyType(SDValue N) {
1456 return isConstantIntBuildVectorOrConstantInt(N) ||
1457 isConstantFPBuildVectorOrConstantFP(N);
1461 void InsertNode(SDNode *N);
1462 bool RemoveNodeFromCSEMaps(SDNode *N);
1463 void AddModifiedNodeToCSEMaps(SDNode *N);
1464 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1465 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1467 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1469 SDNode *UpdateSDLocOnMergeSDNode(SDNode *N, const SDLoc &loc);
1471 void DeleteNodeNotInCSEMaps(SDNode *N);
1472 void DeallocateNode(SDNode *N);
1474 void allnodes_clear();
1476 /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1477 /// not, return the insertion token that will make insertion faster. This
1478 /// overload is for nodes other than Constant or ConstantFP, use the other one
1480 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
1482 /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1483 /// not, return the insertion token that will make insertion faster. Performs
1484 /// additional processing for constant nodes.
1485 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, const SDLoc &DL,
1488 /// List of non-single value types.
1489 FoldingSet<SDVTListNode> VTListMap;
1491 /// Maps to auto-CSE operations.
1492 std::vector<CondCodeSDNode*> CondCodeNodes;
1494 std::vector<SDNode*> ValueTypeNodes;
1495 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1496 StringMap<SDNode*> ExternalSymbols;
1498 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1499 DenseMap<MCSymbol *, SDNode *> MCSymbols;
1502 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1503 using nodes_iterator = pointer_iterator<SelectionDAG::allnodes_iterator>;
1505 static nodes_iterator nodes_begin(SelectionDAG *G) {
1506 return nodes_iterator(G->allnodes_begin());
1509 static nodes_iterator nodes_end(SelectionDAG *G) {
1510 return nodes_iterator(G->allnodes_end());
1514 template <class TargetMemSDNode>
1515 SDValue SelectionDAG::getTargetMemSDNode(SDVTList VTs,
1516 ArrayRef<SDValue> Ops,
1517 const SDLoc &dl, EVT MemVT,
1518 MachineMemOperand *MMO) {
1519 /// Compose node ID and try to find an existing node.
1520 FoldingSetNodeID ID;
1522 TargetMemSDNode(dl.getIROrder(), DebugLoc(), VTs, MemVT, MMO).getOpcode();
1523 ID.AddInteger(Opcode);
1524 ID.AddPointer(VTs.VTs);
1525 for (auto& Op : Ops) {
1526 ID.AddPointer(Op.getNode());
1527 ID.AddInteger(Op.getResNo());
1529 ID.AddInteger(MemVT.getRawBits());
1530 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
1531 ID.AddInteger(getSyntheticNodeSubclassData<TargetMemSDNode>(
1532 dl.getIROrder(), VTs, MemVT, MMO));
1535 if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP)) {
1536 cast<TargetMemSDNode>(E)->refineAlignment(MMO);
1537 return SDValue(E, 0);
1540 /// Existing node was not found. Create a new one.
1541 auto *N = newSDNode<TargetMemSDNode>(dl.getIROrder(), dl.getDebugLoc(), VTs,
1543 createOperands(N, Ops);
1544 CSEMap.InsertNode(N, IP);
1546 return SDValue(N, 0);
1549 } // end namespace llvm
1551 #endif // LLVM_CODEGEN_SELECTIONDAG_H