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/DenseSet.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/StringMap.h"
21 #include "llvm/ADT/ilist.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/CodeGen/DAGCombine.h"
24 #include "llvm/CodeGen/MachineFunction.h"
25 #include "llvm/CodeGen/SelectionDAGNodes.h"
26 #include "llvm/Support/ArrayRecycler.h"
27 #include "llvm/Support/RecyclingAllocator.h"
28 #include "llvm/Target/TargetMachine.h"
36 class MachineConstantPoolValue;
37 class MachineFunction;
39 class OptimizationRemarkEmitter;
42 class SelectionDAGTargetInfo;
44 class SDVTListNode : public FoldingSetNode {
45 friend struct FoldingSetTrait<SDVTListNode>;
46 /// A reference to an Interned FoldingSetNodeID for this node.
47 /// The Allocator in SelectionDAG holds the data.
48 /// SDVTList contains all types which are frequently accessed in SelectionDAG.
49 /// The size of this list is not expected to be big so it won't introduce
51 FoldingSetNodeIDRef FastID;
54 /// The hash value for SDVTList is fixed, so cache it to avoid
58 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
59 FastID(ID), VTs(VT), NumVTs(Num) {
60 HashValue = ID.ComputeHash();
62 SDVTList getSDVTList() {
63 SDVTList result = {VTs, NumVTs};
68 /// Specialize FoldingSetTrait for SDVTListNode
69 /// to avoid computing temp FoldingSetNodeID and hash value.
70 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
71 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
74 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
75 unsigned IDHash, FoldingSetNodeID &TempID) {
76 if (X.HashValue != IDHash)
78 return ID == X.FastID;
80 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
85 template <> struct ilist_alloc_traits<SDNode> {
86 static void deleteNode(SDNode *) {
87 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
91 /// Keeps track of dbg_value information through SDISel. We do
92 /// not build SDNodes for these so as not to perturb the generated code;
93 /// instead the info is kept off to the side in this structure. Each SDNode may
94 /// have one or more associated dbg_value entries. This information is kept in
96 /// Byval parameters are handled separately because they don't use alloca's,
97 /// which busts the normal mechanism. There is good reason for handling all
98 /// parameters separately: they may not have code generated for them, they
99 /// should always go at the beginning of the function regardless of other code
100 /// motion, and debug info for them is potentially useful even if the parameter
101 /// is unused. Right now only byval parameters are handled separately.
103 BumpPtrAllocator Alloc;
104 SmallVector<SDDbgValue*, 32> DbgValues;
105 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
106 typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType;
107 DbgValMapType DbgValMap;
109 void operator=(const SDDbgInfo&) = delete;
110 SDDbgInfo(const SDDbgInfo&) = delete;
114 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
116 ByvalParmDbgValues.push_back(V);
117 } else DbgValues.push_back(V);
119 DbgValMap[Node].push_back(V);
122 /// \brief Invalidate all DbgValues attached to the node and remove
123 /// it from the Node-to-DbgValues map.
124 void erase(const SDNode *Node);
129 ByvalParmDbgValues.clear();
133 BumpPtrAllocator &getAlloc() { return Alloc; }
136 return DbgValues.empty() && ByvalParmDbgValues.empty();
139 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
140 DbgValMapType::iterator I = DbgValMap.find(Node);
141 if (I != DbgValMap.end())
143 return ArrayRef<SDDbgValue*>();
146 typedef SmallVectorImpl<SDDbgValue*>::iterator DbgIterator;
147 DbgIterator DbgBegin() { return DbgValues.begin(); }
148 DbgIterator DbgEnd() { return DbgValues.end(); }
149 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
150 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
154 void checkForCycles(const SelectionDAG *DAG, bool force = false);
156 /// This is used to represent a portion of an LLVM function in a low-level
157 /// Data Dependence DAG representation suitable for instruction selection.
158 /// This DAG is constructed as the first step of instruction selection in order
159 /// to allow implementation of machine specific optimizations
160 /// and code simplifications.
162 /// The representation used by the SelectionDAG is a target-independent
163 /// representation, which has some similarities to the GCC RTL representation,
164 /// but is significantly more simple, powerful, and is a graph form instead of a
168 const TargetMachine &TM;
169 const SelectionDAGTargetInfo *TSI;
170 const TargetLowering *TLI;
172 LLVMContext *Context;
173 CodeGenOpt::Level OptLevel;
175 /// The function-level optimization remark emitter. Used to emit remarks
176 /// whenever manipulating the DAG.
177 OptimizationRemarkEmitter *ORE;
179 /// The starting token.
182 /// The root of the entire DAG.
185 /// A linked list of nodes in the current DAG.
186 ilist<SDNode> AllNodes;
188 /// The AllocatorType for allocating SDNodes. We use
189 /// pool allocation with recycling.
190 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
191 alignof(MostAlignedSDNode)>
194 /// Pool allocation for nodes.
195 NodeAllocatorType NodeAllocator;
197 /// This structure is used to memoize nodes, automatically performing
198 /// CSE with existing nodes when a duplicate is requested.
199 FoldingSet<SDNode> CSEMap;
201 /// Pool allocation for machine-opcode SDNode operands.
202 BumpPtrAllocator OperandAllocator;
203 ArrayRecycler<SDUse> OperandRecycler;
205 /// Pool allocation for misc. objects that are created once per SelectionDAG.
206 BumpPtrAllocator Allocator;
208 /// Tracks dbg_value information through SDISel.
211 uint16_t NextPersistentId = 0;
214 /// Clients of various APIs that cause global effects on
215 /// the DAG can optionally implement this interface. This allows the clients
216 /// to handle the various sorts of updates that happen.
218 /// A DAGUpdateListener automatically registers itself with DAG when it is
219 /// constructed, and removes itself when destroyed in RAII fashion.
220 struct DAGUpdateListener {
221 DAGUpdateListener *const Next;
224 explicit DAGUpdateListener(SelectionDAG &D)
225 : Next(D.UpdateListeners), DAG(D) {
226 DAG.UpdateListeners = this;
229 virtual ~DAGUpdateListener() {
230 assert(DAG.UpdateListeners == this &&
231 "DAGUpdateListeners must be destroyed in LIFO order");
232 DAG.UpdateListeners = Next;
235 /// The node N that was deleted and, if E is not null, an
236 /// equivalent node E that replaced it.
237 virtual void NodeDeleted(SDNode *N, SDNode *E);
239 /// The node N that was updated.
240 virtual void NodeUpdated(SDNode *N);
243 struct DAGNodeDeletedListener : public DAGUpdateListener {
244 std::function<void(SDNode *, SDNode *)> Callback;
245 DAGNodeDeletedListener(SelectionDAG &DAG,
246 std::function<void(SDNode *, SDNode *)> Callback)
247 : DAGUpdateListener(DAG), Callback(std::move(Callback)) {}
248 void NodeDeleted(SDNode *N, SDNode *E) override { Callback(N, E); }
251 /// When true, additional steps are taken to
252 /// ensure that getConstant() and similar functions return DAG nodes that
253 /// have legal types. This is important after type legalization since
254 /// any illegally typed nodes generated after this point will not experience
255 /// type legalization.
256 bool NewNodesMustHaveLegalTypes;
259 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
260 friend struct DAGUpdateListener;
262 /// Linked list of registered DAGUpdateListener instances.
263 /// This stack is maintained by DAGUpdateListener RAII.
264 DAGUpdateListener *UpdateListeners;
266 /// Implementation of setSubgraphColor.
267 /// Return whether we had to truncate the search.
268 bool setSubgraphColorHelper(SDNode *N, const char *Color,
269 DenseSet<SDNode *> &visited,
270 int level, bool &printed);
272 template <typename SDNodeT, typename... ArgTypes>
273 SDNodeT *newSDNode(ArgTypes &&... Args) {
274 return new (NodeAllocator.template Allocate<SDNodeT>())
275 SDNodeT(std::forward<ArgTypes>(Args)...);
278 /// Build a synthetic SDNodeT with the given args and extract its subclass
279 /// data as an integer (e.g. for use in a folding set).
281 /// The args to this function are the same as the args to SDNodeT's
282 /// constructor, except the second arg (assumed to be a const DebugLoc&) is
284 template <typename SDNodeT, typename... ArgTypes>
285 static uint16_t getSyntheticNodeSubclassData(unsigned IROrder,
286 ArgTypes &&... Args) {
287 // The compiler can reduce this expression to a constant iff we pass an
288 // empty DebugLoc. Thankfully, the debug location doesn't have any bearing
289 // on the subclass data.
290 return SDNodeT(IROrder, DebugLoc(), std::forward<ArgTypes>(Args)...)
291 .getRawSubclassData();
294 void createOperands(SDNode *Node, ArrayRef<SDValue> Vals) {
295 assert(!Node->OperandList && "Node already has operands");
296 SDUse *Ops = OperandRecycler.allocate(
297 ArrayRecycler<SDUse>::Capacity::get(Vals.size()), OperandAllocator);
299 for (unsigned I = 0; I != Vals.size(); ++I) {
300 Ops[I].setUser(Node);
301 Ops[I].setInitial(Vals[I]);
303 Node->NumOperands = Vals.size();
304 Node->OperandList = Ops;
305 checkForCycles(Node);
308 void removeOperands(SDNode *Node) {
309 if (!Node->OperandList)
311 OperandRecycler.deallocate(
312 ArrayRecycler<SDUse>::Capacity::get(Node->NumOperands),
314 Node->NumOperands = 0;
315 Node->OperandList = nullptr;
318 void operator=(const SelectionDAG&) = delete;
319 SelectionDAG(const SelectionDAG&) = delete;
322 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
325 /// Prepare this SelectionDAG to process code in the given MachineFunction.
326 void init(MachineFunction &NewMF, OptimizationRemarkEmitter &NewORE);
328 /// Clear state and free memory necessary to make this
329 /// SelectionDAG ready to process a new block.
332 MachineFunction &getMachineFunction() const { return *MF; }
333 const DataLayout &getDataLayout() const { return MF->getDataLayout(); }
334 const TargetMachine &getTarget() const { return TM; }
335 const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
336 const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
337 const SelectionDAGTargetInfo &getSelectionDAGInfo() const { return *TSI; }
338 LLVMContext *getContext() const {return Context; }
339 OptimizationRemarkEmitter &getORE() const { return *ORE; }
341 /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
342 void viewGraph(const std::string &Title);
346 std::map<const SDNode *, std::string> NodeGraphAttrs;
349 /// Clear all previously defined node graph attributes.
350 /// Intended to be used from a debugging tool (eg. gdb).
351 void clearGraphAttrs();
353 /// Set graph attributes for a node. (eg. "color=red".)
354 void setGraphAttrs(const SDNode *N, const char *Attrs);
356 /// Get graph attributes for a node. (eg. "color=red".)
357 /// Used from getNodeAttributes.
358 const std::string getGraphAttrs(const SDNode *N) const;
360 /// Convenience for setting node color attribute.
361 void setGraphColor(const SDNode *N, const char *Color);
363 /// Convenience for setting subgraph color attribute.
364 void setSubgraphColor(SDNode *N, const char *Color);
366 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
367 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
368 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
369 typedef ilist<SDNode>::iterator allnodes_iterator;
370 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
371 allnodes_iterator allnodes_end() { return AllNodes.end(); }
372 ilist<SDNode>::size_type allnodes_size() const {
373 return AllNodes.size();
376 iterator_range<allnodes_iterator> allnodes() {
377 return make_range(allnodes_begin(), allnodes_end());
379 iterator_range<allnodes_const_iterator> allnodes() const {
380 return make_range(allnodes_begin(), allnodes_end());
383 /// Return the root tag of the SelectionDAG.
384 const SDValue &getRoot() const { return Root; }
386 /// Return the token chain corresponding to the entry of the function.
387 SDValue getEntryNode() const {
388 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
391 /// Set the current root tag of the SelectionDAG.
393 const SDValue &setRoot(SDValue N) {
394 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
395 "DAG root value is not a chain!");
397 checkForCycles(N.getNode(), this);
400 checkForCycles(this);
404 /// This iterates over the nodes in the SelectionDAG, folding
405 /// certain types of nodes together, or eliminating superfluous nodes. The
406 /// Level argument controls whether Combine is allowed to produce nodes and
407 /// types that are illegal on the target.
408 void Combine(CombineLevel Level, AliasAnalysis &AA,
409 CodeGenOpt::Level OptLevel);
411 /// This transforms the SelectionDAG into a SelectionDAG that
412 /// only uses types natively supported by the target.
413 /// Returns "true" if it made any changes.
415 /// Note that this is an involved process that may invalidate pointers into
417 bool LegalizeTypes();
419 /// This transforms the SelectionDAG into a SelectionDAG that is
420 /// compatible with the target instruction selector, as indicated by the
421 /// TargetLowering object.
423 /// Note that this is an involved process that may invalidate pointers into
427 /// \brief Transforms a SelectionDAG node and any operands to it into a node
428 /// that is compatible with the target instruction selector, as indicated by
429 /// the TargetLowering object.
431 /// \returns true if \c N is a valid, legal node after calling this.
433 /// This essentially runs a single recursive walk of the \c Legalize process
434 /// over the given node (and its operands). This can be used to incrementally
435 /// legalize the DAG. All of the nodes which are directly replaced,
436 /// potentially including N, are added to the output parameter \c
437 /// UpdatedNodes so that the delta to the DAG can be understood by the
440 /// When this returns false, N has been legalized in a way that make the
441 /// pointer passed in no longer valid. It may have even been deleted from the
442 /// DAG, and so it shouldn't be used further. When this returns true, the
443 /// N passed in is a legal node, and can be immediately processed as such.
444 /// This may still have done some work on the DAG, and will still populate
445 /// UpdatedNodes with any new nodes replacing those originally in the DAG.
446 bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
448 /// This transforms the SelectionDAG into a SelectionDAG
449 /// that only uses vector math operations supported by the target. This is
450 /// necessary as a separate step from Legalize because unrolling a vector
451 /// operation can introduce illegal types, which requires running
452 /// LegalizeTypes again.
454 /// This returns true if it made any changes; in that case, LegalizeTypes
455 /// is called again before Legalize.
457 /// Note that this is an involved process that may invalidate pointers into
459 bool LegalizeVectors();
461 /// This method deletes all unreachable nodes in the SelectionDAG.
462 void RemoveDeadNodes();
464 /// Remove the specified node from the system. This node must
465 /// have no referrers.
466 void DeleteNode(SDNode *N);
468 /// Return an SDVTList that represents the list of values specified.
469 SDVTList getVTList(EVT VT);
470 SDVTList getVTList(EVT VT1, EVT VT2);
471 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
472 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
473 SDVTList getVTList(ArrayRef<EVT> VTs);
475 //===--------------------------------------------------------------------===//
476 // Node creation methods.
479 /// \brief Create a ConstantSDNode wrapping a constant value.
480 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
482 /// If only legal types can be produced, this does the necessary
483 /// transformations (e.g., if the vector element type is illegal).
485 SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT,
486 bool isTarget = false, bool isOpaque = false);
487 SDValue getConstant(const APInt &Val, const SDLoc &DL, EVT VT,
488 bool isTarget = false, bool isOpaque = false);
490 SDValue getAllOnesConstant(const SDLoc &DL, EVT VT, bool IsTarget = false,
491 bool IsOpaque = false) {
492 return getConstant(APInt::getAllOnesValue(VT.getScalarSizeInBits()), DL,
493 VT, IsTarget, IsOpaque);
496 SDValue getConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
497 bool isTarget = false, bool isOpaque = false);
498 SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL,
499 bool isTarget = false);
500 SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT,
501 bool isOpaque = false) {
502 return getConstant(Val, DL, VT, true, isOpaque);
504 SDValue getTargetConstant(const APInt &Val, const SDLoc &DL, EVT VT,
505 bool isOpaque = false) {
506 return getConstant(Val, DL, VT, true, isOpaque);
508 SDValue getTargetConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
509 bool isOpaque = false) {
510 return getConstant(Val, DL, VT, true, isOpaque);
514 /// \brief Create a ConstantFPSDNode wrapping a constant value.
515 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
517 /// If only legal types can be produced, this does the necessary
518 /// transformations (e.g., if the vector element type is illegal).
519 /// The forms that take a double should only be used for simple constants
520 /// that can be exactly represented in VT. No checks are made.
522 SDValue getConstantFP(double Val, const SDLoc &DL, EVT VT,
523 bool isTarget = false);
524 SDValue getConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT,
525 bool isTarget = false);
526 SDValue getConstantFP(const ConstantFP &CF, const SDLoc &DL, EVT VT,
527 bool isTarget = false);
528 SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT) {
529 return getConstantFP(Val, DL, VT, true);
531 SDValue getTargetConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT) {
532 return getConstantFP(Val, DL, VT, true);
534 SDValue getTargetConstantFP(const ConstantFP &Val, const SDLoc &DL, EVT VT) {
535 return getConstantFP(Val, DL, VT, true);
539 SDValue getGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
540 int64_t offset = 0, bool isTargetGA = false,
541 unsigned char TargetFlags = 0);
542 SDValue getTargetGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
544 unsigned char TargetFlags = 0) {
545 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
547 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
548 SDValue getTargetFrameIndex(int FI, EVT VT) {
549 return getFrameIndex(FI, VT, true);
551 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
552 unsigned char TargetFlags = 0);
553 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
554 return getJumpTable(JTI, VT, true, TargetFlags);
556 SDValue getConstantPool(const Constant *C, EVT VT,
557 unsigned Align = 0, int Offs = 0, bool isT=false,
558 unsigned char TargetFlags = 0);
559 SDValue getTargetConstantPool(const Constant *C, EVT VT,
560 unsigned Align = 0, int Offset = 0,
561 unsigned char TargetFlags = 0) {
562 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
564 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
565 unsigned Align = 0, int Offs = 0, bool isT=false,
566 unsigned char TargetFlags = 0);
567 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
568 EVT VT, unsigned Align = 0,
569 int Offset = 0, unsigned char TargetFlags=0) {
570 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
572 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
573 unsigned char TargetFlags = 0);
574 // When generating a branch to a BB, we don't in general know enough
575 // to provide debug info for the BB at that time, so keep this one around.
576 SDValue getBasicBlock(MachineBasicBlock *MBB);
577 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
578 SDValue getExternalSymbol(const char *Sym, EVT VT);
579 SDValue getExternalSymbol(const char *Sym, const SDLoc &dl, EVT VT);
580 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
581 unsigned char TargetFlags = 0);
582 SDValue getMCSymbol(MCSymbol *Sym, EVT VT);
584 SDValue getValueType(EVT);
585 SDValue getRegister(unsigned Reg, EVT VT);
586 SDValue getRegisterMask(const uint32_t *RegMask);
587 SDValue getEHLabel(const SDLoc &dl, SDValue Root, MCSymbol *Label);
588 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
589 int64_t Offset = 0, bool isTarget = false,
590 unsigned char TargetFlags = 0);
591 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
593 unsigned char TargetFlags = 0) {
594 return getBlockAddress(BA, VT, Offset, true, TargetFlags);
597 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg,
599 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
600 getRegister(Reg, N.getValueType()), N);
603 // This version of the getCopyToReg method takes an extra operand, which
604 // indicates that there is potentially an incoming glue value (if Glue is not
605 // null) and that there should be a glue result.
606 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N,
608 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
609 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
610 return getNode(ISD::CopyToReg, dl, VTs,
611 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
614 // Similar to last getCopyToReg() except parameter Reg is a SDValue
615 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, SDValue Reg, SDValue N,
617 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
618 SDValue Ops[] = { Chain, Reg, N, Glue };
619 return getNode(ISD::CopyToReg, dl, VTs,
620 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
623 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT) {
624 SDVTList VTs = getVTList(VT, MVT::Other);
625 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
626 return getNode(ISD::CopyFromReg, dl, VTs, Ops);
629 // This version of the getCopyFromReg method takes an extra operand, which
630 // indicates that there is potentially an incoming glue value (if Glue is not
631 // null) and that there should be a glue result.
632 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT,
634 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
635 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
636 return getNode(ISD::CopyFromReg, dl, VTs,
637 makeArrayRef(Ops, Glue.getNode() ? 3 : 2));
640 SDValue getCondCode(ISD::CondCode Cond);
642 /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT,
643 /// which must be a vector type, must match the number of mask elements
644 /// NumElts. An integer mask element equal to -1 is treated as undefined.
645 SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2,
648 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
649 /// which must be a vector type, must match the number of operands in Ops.
650 /// The operands must have the same type as (or, for integers, a type wider
651 /// than) VT's element type.
652 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDValue> Ops) {
653 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
654 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
657 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
658 /// which must be a vector type, must match the number of operands in Ops.
659 /// The operands must have the same type as (or, for integers, a type wider
660 /// than) VT's element type.
661 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDUse> Ops) {
662 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
663 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
666 /// Return a splat ISD::BUILD_VECTOR node, consisting of Op splatted to all
667 /// elements. VT must be a vector type. Op's type must be the same as (or,
668 /// for integers, a type wider than) VT's element type.
669 SDValue getSplatBuildVector(EVT VT, const SDLoc &DL, SDValue Op) {
670 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
671 if (Op.getOpcode() == ISD::UNDEF) {
672 assert((VT.getVectorElementType() == Op.getValueType() ||
674 VT.getVectorElementType().bitsLE(Op.getValueType()))) &&
675 "A splatted value must have a width equal or (for integers) "
676 "greater than the vector element type!");
677 return getNode(ISD::UNDEF, SDLoc(), VT);
680 SmallVector<SDValue, 16> Ops(VT.getVectorNumElements(), Op);
681 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
684 /// \brief Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
685 /// the shuffle node in input but with swapped operands.
687 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
688 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
690 /// Convert Op, which must be of integer type, to the
691 /// integer type VT, by either any-extending or truncating it.
692 SDValue getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
694 /// Convert Op, which must be of integer type, to the
695 /// integer type VT, by either sign-extending or truncating it.
696 SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
698 /// Convert Op, which must be of integer type, to the
699 /// integer type VT, by either zero-extending or truncating it.
700 SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
702 /// Return the expression required to zero extend the Op
703 /// value assuming it was the smaller SrcTy value.
704 SDValue getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT SrcTy);
706 /// Return an operation which will any-extend the low lanes of the operand
707 /// into the specified vector type. For example,
708 /// this can convert a v16i8 into a v4i32 by any-extending the low four
709 /// lanes of the operand from i8 to i32.
710 SDValue getAnyExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
712 /// Return an operation which will sign extend the low lanes of the operand
713 /// into the specified vector type. For example,
714 /// this can convert a v16i8 into a v4i32 by sign extending the low four
715 /// lanes of the operand from i8 to i32.
716 SDValue getSignExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
718 /// Return an operation which will zero extend the low lanes of the operand
719 /// into the specified vector type. For example,
720 /// this can convert a v16i8 into a v4i32 by zero extending the low four
721 /// lanes of the operand from i8 to i32.
722 SDValue getZeroExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
724 /// Convert Op, which must be of integer type, to the integer type VT,
725 /// by using an extension appropriate for the target's
726 /// BooleanContent for type OpVT or truncating it.
727 SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT);
729 /// Create a bitwise NOT operation as (XOR Val, -1).
730 SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT);
732 /// \brief Create a logical NOT operation as (XOR Val, BooleanOne).
733 SDValue getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT);
735 /// Return a new CALLSEQ_START node, which always must have a glue result
736 /// (to ensure it's not CSE'd). CALLSEQ_START does not have a useful SDLoc.
737 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, const SDLoc &DL) {
738 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
739 SDValue Ops[] = { Chain, Op };
740 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
743 /// Return a new CALLSEQ_END node, which always must have a
744 /// glue result (to ensure it's not CSE'd).
745 /// CALLSEQ_END does not have a useful SDLoc.
746 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
747 SDValue InGlue, const SDLoc &DL) {
748 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
749 SmallVector<SDValue, 4> Ops;
750 Ops.push_back(Chain);
753 if (InGlue.getNode())
754 Ops.push_back(InGlue);
755 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
758 /// Return true if the result of this operation is always undefined.
759 bool isUndef(unsigned Opcode, ArrayRef<SDValue> Ops);
761 /// Return an UNDEF node. UNDEF does not have a useful SDLoc.
762 SDValue getUNDEF(EVT VT) {
763 return getNode(ISD::UNDEF, SDLoc(), VT);
766 /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc.
767 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
768 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
771 /// Gets or creates the specified node.
773 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
774 ArrayRef<SDUse> Ops);
775 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
776 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags = nullptr);
777 SDValue getNode(unsigned Opcode, const SDLoc &DL, ArrayRef<EVT> ResultTys,
778 ArrayRef<SDValue> Ops);
779 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs,
780 ArrayRef<SDValue> Ops);
782 // Specialize based on number of operands.
783 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT);
784 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N);
785 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
786 SDValue N2, const SDNodeFlags *Flags = nullptr);
787 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
788 SDValue N2, SDValue N3);
789 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
790 SDValue N2, SDValue N3, SDValue N4);
791 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
792 SDValue N2, SDValue N3, SDValue N4, SDValue N5);
794 // Specialize again based on number of operands for nodes with a VTList
795 // rather than a single VT.
796 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs);
797 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N);
798 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1,
800 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1,
801 SDValue N2, SDValue N3);
802 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1,
803 SDValue N2, SDValue N3, SDValue N4);
804 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1,
805 SDValue N2, SDValue N3, SDValue N4, SDValue N5);
807 /// Compute a TokenFactor to force all the incoming stack arguments to be
808 /// loaded from the stack. This is used in tail call lowering to protect
809 /// stack arguments from being clobbered.
810 SDValue getStackArgumentTokenFactor(SDValue Chain);
812 SDValue getMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
813 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
814 bool isTailCall, MachinePointerInfo DstPtrInfo,
815 MachinePointerInfo SrcPtrInfo);
817 SDValue getMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
818 SDValue Size, unsigned Align, bool isVol, bool isTailCall,
819 MachinePointerInfo DstPtrInfo,
820 MachinePointerInfo SrcPtrInfo);
822 SDValue getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
823 SDValue Size, unsigned Align, bool isVol, bool isTailCall,
824 MachinePointerInfo DstPtrInfo);
826 /// Helper function to make it easier to build SetCC's if you just
827 /// have an ISD::CondCode instead of an SDValue.
829 SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS,
830 ISD::CondCode Cond) {
831 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
832 "Cannot compare scalars to vectors");
833 assert(LHS.getValueType().isVector() == VT.isVector() &&
834 "Cannot compare scalars to vectors");
835 assert(Cond != ISD::SETCC_INVALID &&
836 "Cannot create a setCC of an invalid node.");
837 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
840 /// Helper function to make it easier to build Select's if you just
841 /// have operands and don't want to check for vector.
842 SDValue getSelect(const SDLoc &DL, EVT VT, SDValue Cond, SDValue LHS,
844 assert(LHS.getValueType() == RHS.getValueType() &&
845 "Cannot use select on differing types");
846 assert(VT.isVector() == LHS.getValueType().isVector() &&
847 "Cannot mix vectors and scalars");
848 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
852 /// Helper function to make it easier to build SelectCC's if you
853 /// just have an ISD::CondCode instead of an SDValue.
855 SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True,
856 SDValue False, ISD::CondCode Cond) {
857 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
858 LHS, RHS, True, False, getCondCode(Cond));
861 /// VAArg produces a result and token chain, and takes a pointer
862 /// and a source value as input.
863 SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
864 SDValue SV, unsigned Align);
866 /// Gets a node for an atomic cmpxchg op. There are two
867 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
868 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
869 /// a success flag (initially i1), and a chain.
870 SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
871 SDVTList VTs, SDValue Chain, SDValue Ptr,
872 SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
873 unsigned Alignment, AtomicOrdering SuccessOrdering,
874 AtomicOrdering FailureOrdering,
875 SynchronizationScope SynchScope);
876 SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
877 SDVTList VTs, SDValue Chain, SDValue Ptr,
878 SDValue Cmp, SDValue Swp, MachineMemOperand *MMO);
880 /// Gets a node for an atomic op, produces result (if relevant)
881 /// and chain and takes 2 operands.
882 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
883 SDValue Ptr, SDValue Val, const Value *PtrVal,
884 unsigned Alignment, AtomicOrdering Ordering,
885 SynchronizationScope SynchScope);
886 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
887 SDValue Ptr, SDValue Val, MachineMemOperand *MMO);
889 /// Gets a node for an atomic op, produces result and chain and
891 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, EVT VT,
892 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO);
894 /// Gets a node for an atomic op, produces result and chain and takes N
896 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT,
897 SDVTList VTList, ArrayRef<SDValue> Ops,
898 MachineMemOperand *MMO);
900 /// Creates a MemIntrinsicNode that may produce a
901 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
902 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
903 /// less than FIRST_TARGET_MEMORY_OPCODE.
904 SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList,
905 ArrayRef<SDValue> Ops, EVT MemVT,
906 MachinePointerInfo PtrInfo, unsigned Align = 0,
907 bool Vol = false, bool ReadMem = true,
908 bool WriteMem = true, unsigned Size = 0);
910 SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList,
911 ArrayRef<SDValue> Ops, EVT MemVT,
912 MachineMemOperand *MMO);
914 /// Create a MERGE_VALUES node from the given operands.
915 SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl);
917 /// Loads are not normal binary operators: their result type is not
918 /// determined by their operands, and they produce a value AND a token chain.
920 /// This function will set the MOLoad flag on MMOFlags, but you can set it if
921 /// you want. The MOStore flag must not be set.
922 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
923 MachinePointerInfo PtrInfo, unsigned Alignment = 0,
924 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
925 const AAMDNodes &AAInfo = AAMDNodes(),
926 const MDNode *Ranges = nullptr);
927 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
928 MachineMemOperand *MMO);
930 getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain,
931 SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT,
932 unsigned Alignment = 0,
933 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
934 const AAMDNodes &AAInfo = AAMDNodes());
935 SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT,
936 SDValue Chain, SDValue Ptr, EVT MemVT,
937 MachineMemOperand *MMO);
938 SDValue getIndexedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base,
939 SDValue Offset, ISD::MemIndexedMode AM);
940 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
941 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
942 MachinePointerInfo PtrInfo, EVT MemVT, unsigned Alignment = 0,
943 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
944 const AAMDNodes &AAInfo = AAMDNodes(),
945 const MDNode *Ranges = nullptr);
946 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
947 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
948 EVT MemVT, MachineMemOperand *MMO);
950 /// Helper function to build ISD::STORE nodes.
952 /// This function will set the MOStore flag on MMOFlags, but you can set it if
953 /// you want. The MOLoad and MOInvariant flags must not be set.
955 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
956 MachinePointerInfo PtrInfo, unsigned Alignment = 0,
957 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
958 const AAMDNodes &AAInfo = AAMDNodes());
959 SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
960 MachineMemOperand *MMO);
962 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
963 MachinePointerInfo PtrInfo, EVT TVT, unsigned Alignment = 0,
964 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
965 const AAMDNodes &AAInfo = AAMDNodes());
966 SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val,
967 SDValue Ptr, EVT TVT, MachineMemOperand *MMO);
968 SDValue getIndexedStore(SDValue OrigStoe, const SDLoc &dl, SDValue Base,
969 SDValue Offset, ISD::MemIndexedMode AM);
971 /// Returns sum of the base pointer and offset.
972 SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, const SDLoc &DL);
974 SDValue getMaskedLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
975 SDValue Mask, SDValue Src0, EVT MemVT,
976 MachineMemOperand *MMO, ISD::LoadExtType,
977 bool IsExpanding = false);
978 SDValue getMaskedStore(SDValue Chain, const SDLoc &dl, SDValue Val,
979 SDValue Ptr, SDValue Mask, EVT MemVT,
980 MachineMemOperand *MMO, bool IsTruncating = false,
981 bool IsCompressing = false);
982 SDValue getMaskedGather(SDVTList VTs, EVT VT, const SDLoc &dl,
983 ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
984 SDValue getMaskedScatter(SDVTList VTs, EVT VT, const SDLoc &dl,
985 ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
987 /// Return (create a new or find existing) a target-specific node.
988 /// TargetMemSDNode should be derived class from MemSDNode.
989 template <class TargetMemSDNode>
990 SDValue getTargetMemSDNode(SDVTList VTs, ArrayRef<SDValue> Ops,
991 const SDLoc &dl, EVT MemVT,
992 MachineMemOperand *MMO);
994 /// Construct a node to track a Value* through the backend.
995 SDValue getSrcValue(const Value *v);
997 /// Return an MDNodeSDNode which holds an MDNode.
998 SDValue getMDNode(const MDNode *MD);
1000 /// Return a bitcast using the SDLoc of the value operand, and casting to the
1001 /// provided type. Use getNode to set a custom SDLoc.
1002 SDValue getBitcast(EVT VT, SDValue V);
1004 /// Return an AddrSpaceCastSDNode.
1005 SDValue getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr, unsigned SrcAS,
1008 /// Return the specified value casted to
1009 /// the target's desired shift amount type.
1010 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
1012 /// Expand the specified \c ISD::VAARG node as the Legalize pass would.
1013 SDValue expandVAArg(SDNode *Node);
1015 /// Expand the specified \c ISD::VACOPY node as the Legalize pass would.
1016 SDValue expandVACopy(SDNode *Node);
1018 /// *Mutate* the specified node in-place to have the
1019 /// specified operands. If the resultant node already exists in the DAG,
1020 /// this does not modify the specified node, instead it returns the node that
1021 /// already exists. If the resultant node does not exist in the DAG, the
1022 /// input node is returned. As a degenerate case, if you specify the same
1023 /// input operands as the node already has, the input node is returned.
1024 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
1025 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
1026 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1028 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1029 SDValue Op3, SDValue Op4);
1030 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1031 SDValue Op3, SDValue Op4, SDValue Op5);
1032 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
1034 /// These are used for target selectors to *mutate* the
1035 /// specified node to have the specified return type, Target opcode, and
1036 /// operands. Note that target opcodes are stored as
1037 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
1038 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
1039 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
1040 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
1041 SDValue Op1, SDValue Op2);
1042 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
1043 SDValue Op1, SDValue Op2, SDValue Op3);
1044 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
1045 ArrayRef<SDValue> Ops);
1046 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
1047 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1048 EVT VT2, ArrayRef<SDValue> Ops);
1049 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1050 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1051 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1052 EVT VT2, SDValue Op1);
1053 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1054 EVT VT2, SDValue Op1, SDValue Op2);
1055 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
1056 ArrayRef<SDValue> Ops);
1058 /// This *mutates* the specified node to have the specified
1059 /// return type, opcode, and operands.
1060 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
1061 ArrayRef<SDValue> Ops);
1063 /// These are used for target selectors to create a new node
1064 /// with specified return type(s), MachineInstr opcode, and operands.
1066 /// Note that getMachineNode returns the resultant node. If there is already
1067 /// a node of the specified opcode and operands, it returns that node instead
1068 /// of the current one.
1069 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT);
1070 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1072 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1073 SDValue Op1, SDValue Op2);
1074 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1075 SDValue Op1, SDValue Op2, SDValue Op3);
1076 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1077 ArrayRef<SDValue> Ops);
1078 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1079 EVT VT2, SDValue Op1, SDValue Op2);
1080 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1081 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
1082 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1083 EVT VT2, ArrayRef<SDValue> Ops);
1084 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1085 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2);
1086 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1087 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2,
1089 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1090 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1091 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl,
1092 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops);
1093 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, SDVTList VTs,
1094 ArrayRef<SDValue> Ops);
1096 /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
1097 SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1100 /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes.
1101 SDValue getTargetInsertSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1102 SDValue Operand, SDValue Subreg);
1104 /// Get the specified node if it's already available, or else return NULL.
1105 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops,
1106 const SDNodeFlags *Flags = nullptr);
1108 /// Creates a SDDbgValue node.
1109 SDDbgValue *getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N, unsigned R,
1110 bool IsIndirect, uint64_t Off, const DebugLoc &DL,
1114 SDDbgValue *getConstantDbgValue(MDNode *Var, MDNode *Expr, const Value *C,
1115 uint64_t Off, const DebugLoc &DL, unsigned O);
1118 SDDbgValue *getFrameIndexDbgValue(MDNode *Var, MDNode *Expr, unsigned FI,
1119 uint64_t Off, const DebugLoc &DL,
1122 /// Remove the specified node from the system. If any of its
1123 /// operands then becomes dead, remove them as well. Inform UpdateListener
1124 /// for each node deleted.
1125 void RemoveDeadNode(SDNode *N);
1127 /// This method deletes the unreachable nodes in the
1128 /// given list, and any nodes that become unreachable as a result.
1129 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
1131 /// Modify anything using 'From' to use 'To' instead.
1132 /// This can cause recursive merging of nodes in the DAG. Use the first
1133 /// version if 'From' is known to have a single result, use the second
1134 /// if you have two nodes with identical results (or if 'To' has a superset
1135 /// of the results of 'From'), use the third otherwise.
1137 /// These methods all take an optional UpdateListener, which (if not null) is
1138 /// informed about nodes that are deleted and modified due to recursive
1139 /// changes in the dag.
1141 /// These functions only replace all existing uses. It's possible that as
1142 /// these replacements are being performed, CSE may cause the From node
1143 /// to be given new uses. These new uses of From are left in place, and
1144 /// not automatically transferred to To.
1146 void ReplaceAllUsesWith(SDValue From, SDValue Op);
1147 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
1148 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
1150 /// Replace any uses of From with To, leaving
1151 /// uses of other values produced by From.Val alone.
1152 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
1154 /// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
1155 /// This correctly handles the case where
1156 /// there is an overlap between the From values and the To values.
1157 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
1160 /// Topological-sort the AllNodes list and a
1161 /// assign a unique node id for each node in the DAG based on their
1162 /// topological order. Returns the number of nodes.
1163 unsigned AssignTopologicalOrder();
1165 /// Move node N in the AllNodes list to be immediately
1166 /// before the given iterator Position. This may be used to update the
1167 /// topological ordering when the list of nodes is modified.
1168 void RepositionNode(allnodes_iterator Position, SDNode *N) {
1169 AllNodes.insert(Position, AllNodes.remove(N));
1172 /// Returns true if the opcode is a commutative binary operation.
1173 static bool isCommutativeBinOp(unsigned Opcode) {
1174 // FIXME: This should get its info from the td file, so that we can include
1185 case ISD::SMUL_LOHI:
1186 case ISD::UMUL_LOHI:
1201 default: return false;
1205 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1206 /// a vector type, the element semantics are returned.
1207 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1208 switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1209 default: llvm_unreachable("Unknown FP format");
1210 case MVT::f16: return APFloat::IEEEhalf();
1211 case MVT::f32: return APFloat::IEEEsingle();
1212 case MVT::f64: return APFloat::IEEEdouble();
1213 case MVT::f80: return APFloat::x87DoubleExtended();
1214 case MVT::f128: return APFloat::IEEEquad();
1215 case MVT::ppcf128: return APFloat::PPCDoubleDouble();
1219 /// Add a dbg_value SDNode. If SD is non-null that means the
1220 /// value is produced by SD.
1221 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1223 /// Get the debug values which reference the given SDNode.
1224 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
1225 return DbgInfo->getSDDbgValues(SD);
1229 /// Transfer SDDbgValues. Called via ReplaceAllUses{OfValue}?With
1230 void TransferDbgValues(SDValue From, SDValue To);
1233 /// Return true if there are any SDDbgValue nodes associated
1234 /// with this SelectionDAG.
1235 bool hasDebugValues() const { return !DbgInfo->empty(); }
1237 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
1238 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
1239 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
1240 return DbgInfo->ByvalParmDbgBegin();
1242 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
1243 return DbgInfo->ByvalParmDbgEnd();
1248 /// Create a stack temporary, suitable for holding the specified value type.
1249 /// If minAlign is specified, the slot size will have at least that alignment.
1250 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1252 /// Create a stack temporary suitable for holding either of the specified
1254 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1256 SDValue FoldSymbolOffset(unsigned Opcode, EVT VT,
1257 const GlobalAddressSDNode *GA,
1260 SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1261 SDNode *Cst1, SDNode *Cst2);
1263 SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1264 const ConstantSDNode *Cst1,
1265 const ConstantSDNode *Cst2);
1267 SDValue FoldConstantVectorArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1268 ArrayRef<SDValue> Ops,
1269 const SDNodeFlags *Flags = nullptr);
1271 /// Constant fold a setcc to true or false.
1272 SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond,
1275 /// Return true if the sign bit of Op is known to be zero.
1276 /// We use this predicate to simplify operations downstream.
1277 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1279 /// Return true if 'Op & Mask' is known to be zero. We
1280 /// use this predicate to simplify operations downstream. Op and Mask are
1281 /// known to be the same type.
1282 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1285 /// Determine which bits of Op are known to be either zero or one and return
1286 /// them in the KnownZero/KnownOne bitsets. For vectors, the known bits are
1287 /// those that are shared by every vector element.
1288 /// Targets can implement the computeKnownBitsForTargetNode method in the
1289 /// TargetLowering class to allow target nodes to be understood.
1290 void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1291 unsigned Depth = 0) const;
1293 /// Determine which bits of Op are known to be either zero or one and return
1294 /// them in the KnownZero/KnownOne bitsets. The DemandedElts argument allows
1295 /// us to only collect the known bits that are shared by the requested vector
1297 /// Targets can implement the computeKnownBitsForTargetNode method in the
1298 /// TargetLowering class to allow target nodes to be understood.
1299 void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1300 const APInt &DemandedElts, unsigned Depth = 0) const;
1302 /// Used to represent the possible overflow behavior of an operation.
1303 /// Never: the operation cannot overflow.
1304 /// Always: the operation will always overflow.
1305 /// Sometime: the operation may or may not overflow.
1312 /// Determine if the result of the addition of 2 node can overflow.
1313 OverflowKind computeOverflowKind(SDValue N0, SDValue N1) const;
1315 /// Test if the given value is known to have exactly one bit set. This differs
1316 /// from computeKnownBits in that it doesn't necessarily determine which bit
1318 bool isKnownToBeAPowerOfTwo(SDValue Val) const;
1320 /// Return the number of times the sign bit of the register is replicated into
1321 /// the other bits. We know that at least 1 bit is always equal to the sign
1322 /// bit (itself), but other cases can give us information. For example,
1323 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
1324 /// to each other, so we return 3. Targets can implement the
1325 /// ComputeNumSignBitsForTarget method in the TargetLowering class to allow
1326 /// target nodes to be understood.
1327 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1329 /// Return the number of times the sign bit of the register is replicated into
1330 /// the other bits. We know that at least 1 bit is always equal to the sign
1331 /// bit (itself), but other cases can give us information. For example,
1332 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
1333 /// to each other, so we return 3. The DemandedElts argument allows
1334 /// us to only collect the minimum sign bits of the requested vector elements.
1335 /// Targets can implement the ComputeNumSignBitsForTarget method in the
1336 /// TargetLowering class to allow target nodes to be understood.
1337 unsigned ComputeNumSignBits(SDValue Op, const APInt &DemandedElts,
1338 unsigned Depth = 0) const;
1340 /// Return true if the specified operand is an ISD::ADD with a ConstantSDNode
1341 /// on the right-hand side, or if it is an ISD::OR with a ConstantSDNode that
1342 /// is guaranteed to have the same semantics as an ADD. This handles the
1344 /// X|Cst == X+Cst iff X&Cst = 0.
1345 bool isBaseWithConstantOffset(SDValue Op) const;
1347 /// Test whether the given SDValue is known to never be NaN.
1348 bool isKnownNeverNaN(SDValue Op) const;
1350 /// Test whether the given SDValue is known to never be positive or negative
1352 bool isKnownNeverZero(SDValue Op) const;
1354 /// Test whether two SDValues are known to compare equal. This
1355 /// is true if they are the same value, or if one is negative zero and the
1356 /// other positive zero.
1357 bool isEqualTo(SDValue A, SDValue B) const;
1359 /// Return true if A and B have no common bits set. As an example, this can
1360 /// allow an 'add' to be transformed into an 'or'.
1361 bool haveNoCommonBitsSet(SDValue A, SDValue B) const;
1363 /// Utility function used by legalize and lowering to
1364 /// "unroll" a vector operation by splitting out the scalars and operating
1365 /// on each element individually. If the ResNE is 0, fully unroll the vector
1366 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1367 /// If the ResNE is greater than the width of the vector op, unroll the
1368 /// vector op and fill the end of the resulting vector with UNDEFS.
1369 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1371 /// Return true if loads are next to each other and can be
1372 /// merged. Check that both are nonvolatile and if LD is loading
1373 /// 'Bytes' bytes from a location that is 'Dist' units away from the
1374 /// location that the 'Base' load is loading from.
1375 bool areNonVolatileConsecutiveLoads(LoadSDNode *LD, LoadSDNode *Base,
1376 unsigned Bytes, int Dist) const;
1378 /// Infer alignment of a load / store address. Return 0 if
1379 /// it cannot be inferred.
1380 unsigned InferPtrAlignment(SDValue Ptr) const;
1382 /// Compute the VTs needed for the low/hi parts of a type
1383 /// which is split (or expanded) into two not necessarily identical pieces.
1384 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1386 /// Split the vector with EXTRACT_SUBVECTOR using the provides
1387 /// VTs and return the low/high part.
1388 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1389 const EVT &LoVT, const EVT &HiVT);
1391 /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part.
1392 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1394 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1395 return SplitVector(N, DL, LoVT, HiVT);
1398 /// Split the node's operand with EXTRACT_SUBVECTOR and
1399 /// return the low/high part.
1400 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1402 return SplitVector(N->getOperand(OpNo), SDLoc(N));
1405 /// Append the extracted elements from Start to Count out of the vector Op
1406 /// in Args. If Count is 0, all of the elements will be extracted.
1407 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
1408 unsigned Start = 0, unsigned Count = 0);
1410 /// Compute the default alignment value for the given type.
1411 unsigned getEVTAlignment(EVT MemoryVT) const;
1413 /// Test whether the given value is a constant int or similar node.
1414 SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N);
1416 /// Test whether the given value is a constant FP or similar node.
1417 SDNode *isConstantFPBuildVectorOrConstantFP(SDValue N);
1419 /// \returns true if \p N is any kind of constant or build_vector of
1420 /// constants, int or float. If a vector, it may not necessarily be a splat.
1421 inline bool isConstantValueOfAnyType(SDValue N) {
1422 return isConstantIntBuildVectorOrConstantInt(N) ||
1423 isConstantFPBuildVectorOrConstantFP(N);
1427 void InsertNode(SDNode *N);
1428 bool RemoveNodeFromCSEMaps(SDNode *N);
1429 void AddModifiedNodeToCSEMaps(SDNode *N);
1430 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1431 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1433 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1435 SDNode *UpdateSDLocOnMergeSDNode(SDNode *N, const SDLoc &loc);
1437 void DeleteNodeNotInCSEMaps(SDNode *N);
1438 void DeallocateNode(SDNode *N);
1440 void allnodes_clear();
1442 SDNode *GetBinarySDNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs,
1443 SDValue N1, SDValue N2,
1444 const SDNodeFlags *Flags = nullptr);
1446 /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1447 /// not, return the insertion token that will make insertion faster. This
1448 /// overload is for nodes other than Constant or ConstantFP, use the other one
1450 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
1452 /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1453 /// not, return the insertion token that will make insertion faster. Performs
1454 /// additional processing for constant nodes.
1455 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, const SDLoc &DL,
1458 /// List of non-single value types.
1459 FoldingSet<SDVTListNode> VTListMap;
1461 /// Maps to auto-CSE operations.
1462 std::vector<CondCodeSDNode*> CondCodeNodes;
1464 std::vector<SDNode*> ValueTypeNodes;
1465 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1466 StringMap<SDNode*> ExternalSymbols;
1468 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1469 DenseMap<MCSymbol *, SDNode *> MCSymbols;
1472 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1473 typedef pointer_iterator<SelectionDAG::allnodes_iterator> nodes_iterator;
1474 static nodes_iterator nodes_begin(SelectionDAG *G) {
1475 return nodes_iterator(G->allnodes_begin());
1477 static nodes_iterator nodes_end(SelectionDAG *G) {
1478 return nodes_iterator(G->allnodes_end());
1482 template <class TargetMemSDNode>
1483 SDValue SelectionDAG::getTargetMemSDNode(SDVTList VTs,
1484 ArrayRef<SDValue> Ops,
1485 const SDLoc &dl, EVT MemVT,
1486 MachineMemOperand *MMO) {
1488 /// Compose node ID and try to find an existing node.
1489 FoldingSetNodeID ID;
1491 TargetMemSDNode(dl.getIROrder(), DebugLoc(), VTs, MemVT, MMO).getOpcode();
1492 ID.AddInteger(Opcode);
1493 ID.AddPointer(VTs.VTs);
1494 for (auto& Op : Ops) {
1495 ID.AddPointer(Op.getNode());
1496 ID.AddInteger(Op.getResNo());
1498 ID.AddInteger(MemVT.getRawBits());
1499 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
1500 ID.AddInteger(getSyntheticNodeSubclassData<TargetMemSDNode>(
1501 dl.getIROrder(), VTs, MemVT, MMO));
1504 if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP)) {
1505 cast<TargetMemSDNode>(E)->refineAlignment(MMO);
1506 return SDValue(E, 0);
1509 /// Existing node was not found. Create a new one.
1510 auto *N = newSDNode<TargetMemSDNode>(dl.getIROrder(), dl.getDebugLoc(), VTs,
1512 createOperands(N, Ops);
1513 CSEMap.InsertNode(N, IP);
1515 return SDValue(N, 0);
1518 } // end namespace llvm