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/RecyclingAllocator.h"
27 #include "llvm/Target/TargetMachine.h"
35 class MachineConstantPoolValue;
36 class MachineFunction;
40 class TargetSelectionDAGInfo;
42 class SDVTListNode : public FoldingSetNode {
43 friend struct FoldingSetTrait<SDVTListNode>;
44 /// A reference to an Interned FoldingSetNodeID for this node.
45 /// The Allocator in SelectionDAG holds the data.
46 /// SDVTList contains all types which are frequently accessed in SelectionDAG.
47 /// The size of this list is not expected to be big so it won't introduce
49 FoldingSetNodeIDRef FastID;
52 /// The hash value for SDVTList is fixed, so cache it to avoid
56 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
57 FastID(ID), VTs(VT), NumVTs(Num) {
58 HashValue = ID.ComputeHash();
60 SDVTList getSDVTList() {
61 SDVTList result = {VTs, NumVTs};
66 /// Specialize FoldingSetTrait for SDVTListNode
67 /// to avoid computing temp FoldingSetNodeID and hash value.
68 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
69 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
72 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
73 unsigned IDHash, FoldingSetNodeID &TempID) {
74 if (X.HashValue != IDHash)
76 return ID == X.FastID;
78 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
83 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
85 mutable ilist_half_node<SDNode> Sentinel;
87 SDNode *createSentinel() const {
88 return static_cast<SDNode*>(&Sentinel);
90 static void destroySentinel(SDNode *) {}
92 SDNode *provideInitialHead() const { return createSentinel(); }
93 SDNode *ensureHead(SDNode*) const { return createSentinel(); }
94 static void noteHead(SDNode*, SDNode*) {}
96 static void deleteNode(SDNode *) {
97 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
100 static void createNode(const SDNode &);
103 /// Keeps track of dbg_value information through SDISel. We do
104 /// not build SDNodes for these so as not to perturb the generated code;
105 /// instead the info is kept off to the side in this structure. Each SDNode may
106 /// have one or more associated dbg_value entries. This information is kept in
108 /// Byval parameters are handled separately because they don't use alloca's,
109 /// which busts the normal mechanism. There is good reason for handling all
110 /// parameters separately: they may not have code generated for them, they
111 /// should always go at the beginning of the function regardless of other code
112 /// motion, and debug info for them is potentially useful even if the parameter
113 /// is unused. Right now only byval parameters are handled separately.
115 BumpPtrAllocator Alloc;
116 SmallVector<SDDbgValue*, 32> DbgValues;
117 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
118 typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType;
119 DbgValMapType DbgValMap;
121 void operator=(const SDDbgInfo&) = delete;
122 SDDbgInfo(const SDDbgInfo&) = delete;
126 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
128 ByvalParmDbgValues.push_back(V);
129 } else DbgValues.push_back(V);
131 DbgValMap[Node].push_back(V);
134 /// \brief Invalidate all DbgValues attached to the node and remove
135 /// it from the Node-to-DbgValues map.
136 void erase(const SDNode *Node);
141 ByvalParmDbgValues.clear();
145 BumpPtrAllocator &getAlloc() { return Alloc; }
148 return DbgValues.empty() && ByvalParmDbgValues.empty();
151 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
152 DbgValMapType::iterator I = DbgValMap.find(Node);
153 if (I != DbgValMap.end())
155 return ArrayRef<SDDbgValue*>();
158 typedef SmallVectorImpl<SDDbgValue*>::iterator DbgIterator;
159 DbgIterator DbgBegin() { return DbgValues.begin(); }
160 DbgIterator DbgEnd() { return DbgValues.end(); }
161 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
162 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
166 void checkForCycles(const SelectionDAG *DAG, bool force = false);
168 /// This is used to represent a portion of an LLVM function in a low-level
169 /// Data Dependence DAG representation suitable for instruction selection.
170 /// This DAG is constructed as the first step of instruction selection in order
171 /// to allow implementation of machine specific optimizations
172 /// and code simplifications.
174 /// The representation used by the SelectionDAG is a target-independent
175 /// representation, which has some similarities to the GCC RTL representation,
176 /// but is significantly more simple, powerful, and is a graph form instead of a
180 const TargetMachine &TM;
181 const TargetSelectionDAGInfo *TSI;
182 const TargetLowering *TLI;
184 LLVMContext *Context;
185 CodeGenOpt::Level OptLevel;
187 /// The starting token.
190 /// The root of the entire DAG.
193 /// A linked list of nodes in the current DAG.
194 ilist<SDNode> AllNodes;
196 /// The AllocatorType for allocating SDNodes. We use
197 /// pool allocation with recycling.
198 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
199 AlignOf<MostAlignedSDNode>::Alignment>
202 /// Pool allocation for nodes.
203 NodeAllocatorType NodeAllocator;
205 /// This structure is used to memoize nodes, automatically performing
206 /// CSE with existing nodes when a duplicate is requested.
207 FoldingSet<SDNode> CSEMap;
209 /// Pool allocation for machine-opcode SDNode operands.
210 BumpPtrAllocator OperandAllocator;
212 /// Pool allocation for misc. objects that are created once per SelectionDAG.
213 BumpPtrAllocator Allocator;
215 /// Tracks dbg_value information through SDISel.
218 uint16_t NextPersistentId = 0;
221 /// Clients of various APIs that cause global effects on
222 /// the DAG can optionally implement this interface. This allows the clients
223 /// to handle the various sorts of updates that happen.
225 /// A DAGUpdateListener automatically registers itself with DAG when it is
226 /// constructed, and removes itself when destroyed in RAII fashion.
227 struct DAGUpdateListener {
228 DAGUpdateListener *const Next;
231 explicit DAGUpdateListener(SelectionDAG &D)
232 : Next(D.UpdateListeners), DAG(D) {
233 DAG.UpdateListeners = this;
236 virtual ~DAGUpdateListener() {
237 assert(DAG.UpdateListeners == this &&
238 "DAGUpdateListeners must be destroyed in LIFO order");
239 DAG.UpdateListeners = Next;
242 /// The node N that was deleted and, if E is not null, an
243 /// equivalent node E that replaced it.
244 virtual void NodeDeleted(SDNode *N, SDNode *E);
246 /// The node N that was updated.
247 virtual void NodeUpdated(SDNode *N);
250 /// When true, additional steps are taken to
251 /// ensure that getConstant() and similar functions return DAG nodes that
252 /// have legal types. This is important after type legalization since
253 /// any illegally typed nodes generated after this point will not experience
254 /// type legalization.
255 bool NewNodesMustHaveLegalTypes;
258 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
259 friend struct DAGUpdateListener;
261 /// Linked list of registered DAGUpdateListener instances.
262 /// This stack is maintained by DAGUpdateListener RAII.
263 DAGUpdateListener *UpdateListeners;
265 /// Implementation of setSubgraphColor.
266 /// Return whether we had to truncate the search.
267 bool setSubgraphColorHelper(SDNode *N, const char *Color,
268 DenseSet<SDNode *> &visited,
269 int level, bool &printed);
271 void operator=(const SelectionDAG&) = delete;
272 SelectionDAG(const SelectionDAG&) = delete;
275 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
278 /// Prepare this SelectionDAG to process code in the given MachineFunction.
279 void init(MachineFunction &mf);
281 /// Clear state and free memory necessary to make this
282 /// SelectionDAG ready to process a new block.
285 MachineFunction &getMachineFunction() const { return *MF; }
286 const DataLayout &getDataLayout() const { return MF->getDataLayout(); }
287 const TargetMachine &getTarget() const { return TM; }
288 const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
289 const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
290 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return *TSI; }
291 LLVMContext *getContext() const {return Context; }
293 /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
294 void viewGraph(const std::string &Title);
298 std::map<const SDNode *, std::string> NodeGraphAttrs;
301 /// Clear all previously defined node graph attributes.
302 /// Intended to be used from a debugging tool (eg. gdb).
303 void clearGraphAttrs();
305 /// Set graph attributes for a node. (eg. "color=red".)
306 void setGraphAttrs(const SDNode *N, const char *Attrs);
308 /// Get graph attributes for a node. (eg. "color=red".)
309 /// Used from getNodeAttributes.
310 const std::string getGraphAttrs(const SDNode *N) const;
312 /// Convenience for setting node color attribute.
313 void setGraphColor(const SDNode *N, const char *Color);
315 /// Convenience for setting subgraph color attribute.
316 void setSubgraphColor(SDNode *N, const char *Color);
318 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
319 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
320 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
321 typedef ilist<SDNode>::iterator allnodes_iterator;
322 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
323 allnodes_iterator allnodes_end() { return AllNodes.end(); }
324 ilist<SDNode>::size_type allnodes_size() const {
325 return AllNodes.size();
328 iterator_range<allnodes_iterator> allnodes() {
329 return iterator_range<allnodes_iterator>(allnodes_begin(), allnodes_end());
331 iterator_range<allnodes_const_iterator> allnodes() const {
332 return iterator_range<allnodes_const_iterator>(allnodes_begin(),
336 /// Return the root tag of the SelectionDAG.
337 const SDValue &getRoot() const { return Root; }
339 /// Return the token chain corresponding to the entry of the function.
340 SDValue getEntryNode() const {
341 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
344 /// Set the current root tag of the SelectionDAG.
346 const SDValue &setRoot(SDValue N) {
347 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
348 "DAG root value is not a chain!");
350 checkForCycles(N.getNode(), this);
353 checkForCycles(this);
357 /// This iterates over the nodes in the SelectionDAG, folding
358 /// certain types of nodes together, or eliminating superfluous nodes. The
359 /// Level argument controls whether Combine is allowed to produce nodes and
360 /// types that are illegal on the target.
361 void Combine(CombineLevel Level, AliasAnalysis &AA,
362 CodeGenOpt::Level OptLevel);
364 /// This transforms the SelectionDAG into a SelectionDAG that
365 /// only uses types natively supported by the target.
366 /// Returns "true" if it made any changes.
368 /// Note that this is an involved process that may invalidate pointers into
370 bool LegalizeTypes();
372 /// This transforms the SelectionDAG into a SelectionDAG that is
373 /// compatible with the target instruction selector, as indicated by the
374 /// TargetLowering object.
376 /// Note that this is an involved process that may invalidate pointers into
380 /// \brief Transforms a SelectionDAG node and any operands to it into a node
381 /// that is compatible with the target instruction selector, as indicated by
382 /// the TargetLowering object.
384 /// \returns true if \c N is a valid, legal node after calling this.
386 /// This essentially runs a single recursive walk of the \c Legalize process
387 /// over the given node (and its operands). This can be used to incrementally
388 /// legalize the DAG. All of the nodes which are directly replaced,
389 /// potentially including N, are added to the output parameter \c
390 /// UpdatedNodes so that the delta to the DAG can be understood by the
393 /// When this returns false, N has been legalized in a way that make the
394 /// pointer passed in no longer valid. It may have even been deleted from the
395 /// DAG, and so it shouldn't be used further. When this returns true, the
396 /// N passed in is a legal node, and can be immediately processed as such.
397 /// This may still have done some work on the DAG, and will still populate
398 /// UpdatedNodes with any new nodes replacing those originally in the DAG.
399 bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
401 /// This transforms the SelectionDAG into a SelectionDAG
402 /// that only uses vector math operations supported by the target. This is
403 /// necessary as a separate step from Legalize because unrolling a vector
404 /// operation can introduce illegal types, which requires running
405 /// LegalizeTypes again.
407 /// This returns true if it made any changes; in that case, LegalizeTypes
408 /// is called again before Legalize.
410 /// Note that this is an involved process that may invalidate pointers into
412 bool LegalizeVectors();
414 /// This method deletes all unreachable nodes in the SelectionDAG.
415 void RemoveDeadNodes();
417 /// Remove the specified node from the system. This node must
418 /// have no referrers.
419 void DeleteNode(SDNode *N);
421 /// Return an SDVTList that represents the list of values specified.
422 SDVTList getVTList(EVT VT);
423 SDVTList getVTList(EVT VT1, EVT VT2);
424 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
425 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
426 SDVTList getVTList(ArrayRef<EVT> VTs);
428 //===--------------------------------------------------------------------===//
429 // Node creation methods.
431 SDValue getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isTarget = false,
432 bool isOpaque = false);
433 SDValue getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isTarget = false,
434 bool isOpaque = false);
435 SDValue getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
436 bool isTarget = false, bool isOpaque = false);
437 SDValue getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget = false);
438 SDValue getTargetConstant(uint64_t Val, SDLoc DL, EVT VT,
439 bool isOpaque = false) {
440 return getConstant(Val, DL, VT, true, isOpaque);
442 SDValue getTargetConstant(const APInt &Val, SDLoc DL, EVT VT,
443 bool isOpaque = false) {
444 return getConstant(Val, DL, VT, true, isOpaque);
446 SDValue getTargetConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
447 bool isOpaque = false) {
448 return getConstant(Val, DL, VT, true, isOpaque);
450 // The forms below that take a double should only be used for simple
451 // constants that can be exactly represented in VT. No checks are made.
452 SDValue getConstantFP(double Val, SDLoc DL, EVT VT, bool isTarget = false);
453 SDValue getConstantFP(const APFloat& Val, SDLoc DL, EVT VT,
454 bool isTarget = false);
455 SDValue getConstantFP(const ConstantFP &CF, SDLoc DL, EVT VT,
456 bool isTarget = false);
457 SDValue getTargetConstantFP(double Val, SDLoc DL, EVT VT) {
458 return getConstantFP(Val, DL, VT, true);
460 SDValue getTargetConstantFP(const APFloat& Val, SDLoc DL, EVT VT) {
461 return getConstantFP(Val, DL, VT, true);
463 SDValue getTargetConstantFP(const ConstantFP &Val, SDLoc DL, EVT VT) {
464 return getConstantFP(Val, DL, VT, true);
466 SDValue getGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
467 int64_t offset = 0, bool isTargetGA = false,
468 unsigned char TargetFlags = 0);
469 SDValue getTargetGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
471 unsigned char TargetFlags = 0) {
472 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
474 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
475 SDValue getTargetFrameIndex(int FI, EVT VT) {
476 return getFrameIndex(FI, VT, true);
478 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
479 unsigned char TargetFlags = 0);
480 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
481 return getJumpTable(JTI, VT, true, TargetFlags);
483 SDValue getConstantPool(const Constant *C, EVT VT,
484 unsigned Align = 0, int Offs = 0, bool isT=false,
485 unsigned char TargetFlags = 0);
486 SDValue getTargetConstantPool(const Constant *C, EVT VT,
487 unsigned Align = 0, int Offset = 0,
488 unsigned char TargetFlags = 0) {
489 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
491 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
492 unsigned Align = 0, int Offs = 0, bool isT=false,
493 unsigned char TargetFlags = 0);
494 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
495 EVT VT, unsigned Align = 0,
496 int Offset = 0, unsigned char TargetFlags=0) {
497 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
499 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
500 unsigned char TargetFlags = 0);
501 // When generating a branch to a BB, we don't in general know enough
502 // to provide debug info for the BB at that time, so keep this one around.
503 SDValue getBasicBlock(MachineBasicBlock *MBB);
504 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
505 SDValue getExternalSymbol(const char *Sym, EVT VT);
506 SDValue getExternalSymbol(const char *Sym, SDLoc dl, EVT VT);
507 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
508 unsigned char TargetFlags = 0);
509 SDValue getMCSymbol(MCSymbol *Sym, EVT VT);
511 SDValue getValueType(EVT);
512 SDValue getRegister(unsigned Reg, EVT VT);
513 SDValue getRegisterMask(const uint32_t *RegMask);
514 SDValue getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label);
515 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
516 int64_t Offset = 0, bool isTarget = false,
517 unsigned char TargetFlags = 0);
518 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
520 unsigned char TargetFlags = 0) {
521 return getBlockAddress(BA, VT, Offset, true, TargetFlags);
524 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N) {
525 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
526 getRegister(Reg, N.getValueType()), N);
529 // This version of the getCopyToReg method takes an extra operand, which
530 // indicates that there is potentially an incoming glue value (if Glue is not
531 // null) and that there should be a glue result.
532 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N,
534 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
535 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
536 return getNode(ISD::CopyToReg, dl, VTs,
537 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
540 // Similar to last getCopyToReg() except parameter Reg is a SDValue
541 SDValue getCopyToReg(SDValue Chain, SDLoc dl, SDValue Reg, SDValue N,
543 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
544 SDValue Ops[] = { Chain, Reg, N, Glue };
545 return getNode(ISD::CopyToReg, dl, VTs,
546 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
549 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT) {
550 SDVTList VTs = getVTList(VT, MVT::Other);
551 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
552 return getNode(ISD::CopyFromReg, dl, VTs, Ops);
555 // This version of the getCopyFromReg method takes an extra operand, which
556 // indicates that there is potentially an incoming glue value (if Glue is not
557 // null) and that there should be a glue result.
558 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT,
560 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
561 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
562 return getNode(ISD::CopyFromReg, dl, VTs,
563 makeArrayRef(Ops, Glue.getNode() ? 3 : 2));
566 SDValue getCondCode(ISD::CondCode Cond);
568 /// Returns the ConvertRndSat Note: Avoid using this node because it may
569 /// disappear in the future and most targets don't support it.
570 SDValue getConvertRndSat(EVT VT, SDLoc dl, SDValue Val, SDValue DTy,
572 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
574 /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT,
575 /// which must be a vector type, must match the number of mask elements
576 /// NumElts. An integer mask element equal to -1 is treated as undefined.
577 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
578 const int *MaskElts);
579 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
580 ArrayRef<int> MaskElts) {
581 assert(VT.getVectorNumElements() == MaskElts.size() &&
582 "Must have the same number of vector elements as mask elements!");
583 return getVectorShuffle(VT, dl, N1, N2, MaskElts.data());
586 /// \brief Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
587 /// the shuffle node in input but with swapped operands.
589 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
590 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
592 /// Convert Op, which must be of integer type, to the
593 /// integer type VT, by either any-extending or truncating it.
594 SDValue getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
596 /// Convert Op, which must be of integer type, to the
597 /// integer type VT, by either sign-extending or truncating it.
598 SDValue getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
600 /// Convert Op, which must be of integer type, to the
601 /// integer type VT, by either zero-extending or truncating it.
602 SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
604 /// Return the expression required to zero extend the Op
605 /// value assuming it was the smaller SrcTy value.
606 SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy);
608 /// Return an operation which will any-extend the low lanes of the operand
609 /// into the specified vector type. For example,
610 /// this can convert a v16i8 into a v4i32 by any-extending the low four
611 /// lanes of the operand from i8 to i32.
612 SDValue getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
614 /// Return an operation which will sign extend the low lanes of the operand
615 /// into the specified vector type. For example,
616 /// this can convert a v16i8 into a v4i32 by sign extending the low four
617 /// lanes of the operand from i8 to i32.
618 SDValue getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
620 /// Return an operation which will zero extend the low lanes of the operand
621 /// into the specified vector type. For example,
622 /// this can convert a v16i8 into a v4i32 by zero extending the low four
623 /// lanes of the operand from i8 to i32.
624 SDValue getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
626 /// Convert Op, which must be of integer type, to the integer type VT,
627 /// by using an extension appropriate for the target's
628 /// BooleanContent for type OpVT or truncating it.
629 SDValue getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT, EVT OpVT);
631 /// Create a bitwise NOT operation as (XOR Val, -1).
632 SDValue getNOT(SDLoc DL, SDValue Val, EVT VT);
634 /// \brief Create a logical NOT operation as (XOR Val, BooleanOne).
635 SDValue getLogicalNOT(SDLoc DL, SDValue Val, EVT VT);
637 /// Return a new CALLSEQ_START node, which always must have a glue result
638 /// (to ensure it's not CSE'd). CALLSEQ_START does not have a useful SDLoc.
639 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) {
640 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
641 SDValue Ops[] = { Chain, Op };
642 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
645 /// Return a new CALLSEQ_END node, which always must have a
646 /// glue result (to ensure it's not CSE'd).
647 /// CALLSEQ_END does not have a useful SDLoc.
648 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
649 SDValue InGlue, SDLoc DL) {
650 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
651 SmallVector<SDValue, 4> Ops;
652 Ops.push_back(Chain);
655 if (InGlue.getNode())
656 Ops.push_back(InGlue);
657 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
660 /// Return an UNDEF node. UNDEF does not have a useful SDLoc.
661 SDValue getUNDEF(EVT VT) {
662 return getNode(ISD::UNDEF, SDLoc(), VT);
665 /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc.
666 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
667 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
670 /// Gets or creates the specified node.
672 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
673 ArrayRef<SDUse> Ops);
674 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
675 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags = nullptr);
676 SDValue getNode(unsigned Opcode, SDLoc DL, ArrayRef<EVT> ResultTys,
677 ArrayRef<SDValue> Ops);
678 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
679 ArrayRef<SDValue> Ops);
681 // Specialize based on number of operands.
682 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT);
683 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N);
684 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
685 const SDNodeFlags *Flags = nullptr);
686 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
688 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
689 SDValue N3, SDValue N4);
690 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
691 SDValue N3, SDValue N4, SDValue N5);
693 // Specialize again based on number of operands for nodes with a VTList
694 // rather than a single VT.
695 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs);
696 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N);
697 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
699 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
700 SDValue N2, SDValue N3);
701 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
702 SDValue N2, SDValue N3, SDValue N4);
703 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
704 SDValue N2, SDValue N3, SDValue N4, SDValue N5);
706 /// Compute a TokenFactor to force all the incoming stack arguments to be
707 /// loaded from the stack. This is used in tail call lowering to protect
708 /// stack arguments from being clobbered.
709 SDValue getStackArgumentTokenFactor(SDValue Chain);
711 SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
712 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
713 bool isTailCall, MachinePointerInfo DstPtrInfo,
714 MachinePointerInfo SrcPtrInfo);
716 SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
717 SDValue Size, unsigned Align, bool isVol, bool isTailCall,
718 MachinePointerInfo DstPtrInfo,
719 MachinePointerInfo SrcPtrInfo);
721 SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
722 SDValue Size, unsigned Align, bool isVol, bool isTailCall,
723 MachinePointerInfo DstPtrInfo);
725 /// Helper function to make it easier to build SetCC's if you just
726 /// have an ISD::CondCode instead of an SDValue.
728 SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS,
729 ISD::CondCode Cond) {
730 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
731 "Cannot compare scalars to vectors");
732 assert(LHS.getValueType().isVector() == VT.isVector() &&
733 "Cannot compare scalars to vectors");
734 assert(Cond != ISD::SETCC_INVALID &&
735 "Cannot create a setCC of an invalid node.");
736 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
739 /// Helper function to make it easier to build Select's if you just
740 /// have operands and don't want to check for vector.
741 SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond,
742 SDValue LHS, SDValue RHS) {
743 assert(LHS.getValueType() == RHS.getValueType() &&
744 "Cannot use select on differing types");
745 assert(VT.isVector() == LHS.getValueType().isVector() &&
746 "Cannot mix vectors and scalars");
747 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
751 /// Helper function to make it easier to build SelectCC's if you
752 /// just have an ISD::CondCode instead of an SDValue.
754 SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS,
755 SDValue True, SDValue False, ISD::CondCode Cond) {
756 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
757 LHS, RHS, True, False, getCondCode(Cond));
760 /// VAArg produces a result and token chain, and takes a pointer
761 /// and a source value as input.
762 SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
763 SDValue SV, unsigned Align);
765 /// Gets a node for an atomic cmpxchg op. There are two
766 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
767 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
768 /// a success flag (initially i1), and a chain.
769 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
770 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
771 MachinePointerInfo PtrInfo, unsigned Alignment,
772 AtomicOrdering SuccessOrdering,
773 AtomicOrdering FailureOrdering,
774 SynchronizationScope SynchScope);
775 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
776 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
777 MachineMemOperand *MMO,
778 AtomicOrdering SuccessOrdering,
779 AtomicOrdering FailureOrdering,
780 SynchronizationScope SynchScope);
782 /// Gets a node for an atomic op, produces result (if relevant)
783 /// and chain and takes 2 operands.
784 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
785 SDValue Ptr, SDValue Val, const Value *PtrVal,
786 unsigned Alignment, AtomicOrdering Ordering,
787 SynchronizationScope SynchScope);
788 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
789 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
790 AtomicOrdering Ordering,
791 SynchronizationScope SynchScope);
793 /// Gets a node for an atomic op, produces result and chain and
795 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
796 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
797 AtomicOrdering Ordering,
798 SynchronizationScope SynchScope);
800 /// Gets a node for an atomic op, produces result and chain and takes N
802 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
803 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
804 AtomicOrdering SuccessOrdering,
805 AtomicOrdering FailureOrdering,
806 SynchronizationScope SynchScope);
807 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
808 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
809 AtomicOrdering Ordering, SynchronizationScope SynchScope);
811 /// Creates a MemIntrinsicNode that may produce a
812 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
813 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
814 /// less than FIRST_TARGET_MEMORY_OPCODE.
815 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
816 ArrayRef<SDValue> Ops,
817 EVT MemVT, MachinePointerInfo PtrInfo,
818 unsigned Align = 0, bool Vol = false,
819 bool ReadMem = true, bool WriteMem = true,
822 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
823 ArrayRef<SDValue> Ops,
824 EVT MemVT, MachineMemOperand *MMO);
826 /// Create a MERGE_VALUES node from the given operands.
827 SDValue getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl);
829 /// Loads are not normal binary operators: their result type is not
830 /// determined by their operands, and they produce a value AND a token chain.
832 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
833 MachinePointerInfo PtrInfo, bool isVolatile,
834 bool isNonTemporal, bool isInvariant, unsigned Alignment,
835 const AAMDNodes &AAInfo = AAMDNodes(),
836 const MDNode *Ranges = nullptr);
837 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
838 MachineMemOperand *MMO);
839 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
840 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
841 EVT MemVT, bool isVolatile,
842 bool isNonTemporal, bool isInvariant, unsigned Alignment,
843 const AAMDNodes &AAInfo = AAMDNodes());
844 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
845 SDValue Chain, SDValue Ptr, EVT MemVT,
846 MachineMemOperand *MMO);
847 SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
848 SDValue Offset, ISD::MemIndexedMode AM);
849 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
851 SDValue Chain, SDValue Ptr, SDValue Offset,
852 MachinePointerInfo PtrInfo, EVT MemVT,
853 bool isVolatile, bool isNonTemporal, bool isInvariant,
854 unsigned Alignment, const AAMDNodes &AAInfo = AAMDNodes(),
855 const MDNode *Ranges = nullptr);
856 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
858 SDValue Chain, SDValue Ptr, SDValue Offset,
859 EVT MemVT, MachineMemOperand *MMO);
861 /// Helper function to build ISD::STORE nodes.
862 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
863 MachinePointerInfo PtrInfo, bool isVolatile,
864 bool isNonTemporal, unsigned Alignment,
865 const AAMDNodes &AAInfo = AAMDNodes());
866 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
867 MachineMemOperand *MMO);
868 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
869 MachinePointerInfo PtrInfo, EVT TVT,
870 bool isNonTemporal, bool isVolatile,
872 const AAMDNodes &AAInfo = AAMDNodes());
873 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
874 EVT TVT, MachineMemOperand *MMO);
875 SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base,
876 SDValue Offset, ISD::MemIndexedMode AM);
878 SDValue getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
879 SDValue Mask, SDValue Src0, EVT MemVT,
880 MachineMemOperand *MMO, ISD::LoadExtType);
881 SDValue getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
882 SDValue Ptr, SDValue Mask, EVT MemVT,
883 MachineMemOperand *MMO, bool IsTrunc);
884 SDValue getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
885 ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
886 SDValue getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
887 ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
888 /// Construct a node to track a Value* through the backend.
889 SDValue getSrcValue(const Value *v);
891 /// Return an MDNodeSDNode which holds an MDNode.
892 SDValue getMDNode(const MDNode *MD);
894 /// Return a bitcast using the SDLoc of the value operand, and casting to the
895 /// provided type. Use getNode to set a custom SDLoc.
896 SDValue getBitcast(EVT VT, SDValue V);
898 /// Return an AddrSpaceCastSDNode.
899 SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
900 unsigned SrcAS, unsigned DestAS);
902 /// Return the specified value casted to
903 /// the target's desired shift amount type.
904 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
906 /// Expand the specified \c ISD::VAARG node as the Legalize pass would.
907 SDValue expandVAArg(SDNode *Node);
909 /// Expand the specified \c ISD::VACOPY node as the Legalize pass would.
910 SDValue expandVACopy(SDNode *Node);
912 /// *Mutate* the specified node in-place to have the
913 /// specified operands. If the resultant node already exists in the DAG,
914 /// this does not modify the specified node, instead it returns the node that
915 /// already exists. If the resultant node does not exist in the DAG, the
916 /// input node is returned. As a degenerate case, if you specify the same
917 /// input operands as the node already has, the input node is returned.
918 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
919 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
920 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
922 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
923 SDValue Op3, SDValue Op4);
924 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
925 SDValue Op3, SDValue Op4, SDValue Op5);
926 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
928 /// These are used for target selectors to *mutate* the
929 /// specified node to have the specified return type, Target opcode, and
930 /// operands. Note that target opcodes are stored as
931 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
932 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
933 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
934 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
935 SDValue Op1, SDValue Op2);
936 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
937 SDValue Op1, SDValue Op2, SDValue Op3);
938 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
939 ArrayRef<SDValue> Ops);
940 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
941 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
942 EVT VT2, ArrayRef<SDValue> Ops);
943 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
944 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
945 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
946 EVT VT2, EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
947 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
948 EVT VT2, SDValue Op1);
949 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
950 EVT VT2, SDValue Op1, SDValue Op2);
951 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
952 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
953 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
954 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
955 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
956 ArrayRef<SDValue> Ops);
958 /// This *mutates* the specified node to have the specified
959 /// return type, opcode, and operands.
960 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
961 ArrayRef<SDValue> Ops);
963 /// These are used for target selectors to create a new node
964 /// with specified return type(s), MachineInstr opcode, and operands.
966 /// Note that getMachineNode returns the resultant node. If there is already
967 /// a node of the specified opcode and operands, it returns that node instead
968 /// of the current one.
969 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT);
970 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
972 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
973 SDValue Op1, SDValue Op2);
974 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
975 SDValue Op1, SDValue Op2, SDValue Op3);
976 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
977 ArrayRef<SDValue> Ops);
978 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2);
979 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
981 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
982 SDValue Op1, SDValue Op2);
983 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
984 SDValue Op1, SDValue Op2, SDValue Op3);
985 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
986 ArrayRef<SDValue> Ops);
987 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
988 EVT VT3, SDValue Op1, SDValue Op2);
989 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
990 EVT VT3, SDValue Op1, SDValue Op2,
992 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
993 EVT VT3, ArrayRef<SDValue> Ops);
994 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
995 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
996 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl,
997 ArrayRef<EVT> ResultTys,
998 ArrayRef<SDValue> Ops);
999 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs,
1000 ArrayRef<SDValue> Ops);
1002 /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
1003 SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
1006 /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes.
1007 SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
1008 SDValue Operand, SDValue Subreg);
1010 /// Get the specified node if it's already available, or else return NULL.
1011 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops,
1012 const SDNodeFlags *Flags = nullptr);
1014 /// Creates a SDDbgValue node.
1015 SDDbgValue *getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N, unsigned R,
1016 bool IsIndirect, uint64_t Off, DebugLoc DL,
1020 SDDbgValue *getConstantDbgValue(MDNode *Var, MDNode *Expr, const Value *C,
1021 uint64_t Off, DebugLoc DL, unsigned O);
1024 SDDbgValue *getFrameIndexDbgValue(MDNode *Var, MDNode *Expr, unsigned FI,
1025 uint64_t Off, DebugLoc DL, unsigned O);
1027 /// Remove the specified node from the system. If any of its
1028 /// operands then becomes dead, remove them as well. Inform UpdateListener
1029 /// for each node deleted.
1030 void RemoveDeadNode(SDNode *N);
1032 /// This method deletes the unreachable nodes in the
1033 /// given list, and any nodes that become unreachable as a result.
1034 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
1036 /// Modify anything using 'From' to use 'To' instead.
1037 /// This can cause recursive merging of nodes in the DAG. Use the first
1038 /// version if 'From' is known to have a single result, use the second
1039 /// if you have two nodes with identical results (or if 'To' has a superset
1040 /// of the results of 'From'), use the third otherwise.
1042 /// These methods all take an optional UpdateListener, which (if not null) is
1043 /// informed about nodes that are deleted and modified due to recursive
1044 /// changes in the dag.
1046 /// These functions only replace all existing uses. It's possible that as
1047 /// these replacements are being performed, CSE may cause the From node
1048 /// to be given new uses. These new uses of From are left in place, and
1049 /// not automatically transferred to To.
1051 void ReplaceAllUsesWith(SDValue From, SDValue Op);
1052 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
1053 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
1055 /// Replace any uses of From with To, leaving
1056 /// uses of other values produced by From.Val alone.
1057 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
1059 /// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
1060 /// This correctly handles the case where
1061 /// there is an overlap between the From values and the To values.
1062 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
1065 /// Topological-sort the AllNodes list and a
1066 /// assign a unique node id for each node in the DAG based on their
1067 /// topological order. Returns the number of nodes.
1068 unsigned AssignTopologicalOrder();
1070 /// Move node N in the AllNodes list to be immediately
1071 /// before the given iterator Position. This may be used to update the
1072 /// topological ordering when the list of nodes is modified.
1073 void RepositionNode(allnodes_iterator Position, SDNode *N) {
1074 AllNodes.insert(Position, AllNodes.remove(N));
1077 /// Returns true if the opcode is a commutative binary operation.
1078 static bool isCommutativeBinOp(unsigned Opcode) {
1079 // FIXME: This should get its info from the td file, so that we can include
1090 case ISD::SMUL_LOHI:
1091 case ISD::UMUL_LOHI:
1106 default: return false;
1110 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1111 /// a vector type, the element semantics are returned.
1112 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1113 switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1114 default: llvm_unreachable("Unknown FP format");
1115 case MVT::f16: return APFloat::IEEEhalf;
1116 case MVT::f32: return APFloat::IEEEsingle;
1117 case MVT::f64: return APFloat::IEEEdouble;
1118 case MVT::f80: return APFloat::x87DoubleExtended;
1119 case MVT::f128: return APFloat::IEEEquad;
1120 case MVT::ppcf128: return APFloat::PPCDoubleDouble;
1124 /// Add a dbg_value SDNode. If SD is non-null that means the
1125 /// value is produced by SD.
1126 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1128 /// Get the debug values which reference the given SDNode.
1129 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
1130 return DbgInfo->getSDDbgValues(SD);
1133 /// Transfer SDDbgValues.
1134 void TransferDbgValues(SDValue From, SDValue To);
1136 /// Return true if there are any SDDbgValue nodes associated
1137 /// with this SelectionDAG.
1138 bool hasDebugValues() const { return !DbgInfo->empty(); }
1140 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
1141 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
1142 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
1143 return DbgInfo->ByvalParmDbgBegin();
1145 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
1146 return DbgInfo->ByvalParmDbgEnd();
1151 /// Create a stack temporary, suitable for holding the
1152 /// specified value type. If minAlign is specified, the slot size will have
1153 /// at least that alignment.
1154 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1156 /// Create a stack temporary suitable for holding
1157 /// either of the specified value types.
1158 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1160 SDValue FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
1161 SDNode *Cst1, SDNode *Cst2);
1163 SDValue FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
1164 const ConstantSDNode *Cst1,
1165 const ConstantSDNode *Cst2);
1167 SDValue FoldConstantVectorArithmetic(unsigned Opcode, SDLoc DL,
1168 EVT VT, ArrayRef<SDValue> Ops,
1169 const SDNodeFlags *Flags = nullptr);
1171 /// Constant fold a setcc to true or false.
1172 SDValue FoldSetCC(EVT VT, SDValue N1,
1173 SDValue N2, ISD::CondCode Cond, SDLoc dl);
1175 /// Return true if the sign bit of Op is known to be zero.
1176 /// We use this predicate to simplify operations downstream.
1177 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1179 /// Return true if 'Op & Mask' is known to be zero. We
1180 /// use this predicate to simplify operations downstream. Op and Mask are
1181 /// known to be the same type.
1182 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1185 /// Determine which bits of Op are known to be either zero or one and return
1186 /// them in the KnownZero/KnownOne bitsets. Targets can implement the
1187 /// computeKnownBitsForTargetNode method in the TargetLowering class to allow
1188 /// target nodes to be understood.
1189 void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1190 unsigned Depth = 0) const;
1192 /// Return the number of times the sign bit of the
1193 /// register is replicated into the other bits. We know that at least 1 bit
1194 /// is always equal to the sign bit (itself), but other cases can give us
1195 /// information. For example, immediately after an "SRA X, 2", we know that
1196 /// the top 3 bits are all equal to each other, so we return 3. Targets can
1197 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1198 /// class to allow target nodes to be understood.
1199 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1201 /// Return true if the specified operand is an
1202 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1203 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1204 /// semantics as an ADD. This handles the equivalence:
1205 /// X|Cst == X+Cst iff X&Cst = 0.
1206 bool isBaseWithConstantOffset(SDValue Op) const;
1208 /// Test whether the given SDValue is known to never be NaN.
1209 bool isKnownNeverNaN(SDValue Op) const;
1211 /// Test whether the given SDValue is known to never be
1212 /// positive or negative Zero.
1213 bool isKnownNeverZero(SDValue Op) const;
1215 /// Test whether two SDValues are known to compare equal. This
1216 /// is true if they are the same value, or if one is negative zero and the
1217 /// other positive zero.
1218 bool isEqualTo(SDValue A, SDValue B) const;
1220 /// Return true if A and B have no common bits set. As an example, this can
1221 /// allow an 'add' to be transformed into an 'or'.
1222 bool haveNoCommonBitsSet(SDValue A, SDValue B) const;
1224 /// Utility function used by legalize and lowering to
1225 /// "unroll" a vector operation by splitting out the scalars and operating
1226 /// on each element individually. If the ResNE is 0, fully unroll the vector
1227 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1228 /// If the ResNE is greater than the width of the vector op, unroll the
1229 /// vector op and fill the end of the resulting vector with UNDEFS.
1230 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1232 /// Return true if LD is loading 'Bytes' bytes from a location that is 'Dist'
1233 /// units away from the location that the 'Base' load is loading from.
1234 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1235 unsigned Bytes, int Dist) const;
1237 /// Infer alignment of a load / store address. Return 0 if
1238 /// it cannot be inferred.
1239 unsigned InferPtrAlignment(SDValue Ptr) const;
1241 /// Compute the VTs needed for the low/hi parts of a type
1242 /// which is split (or expanded) into two not necessarily identical pieces.
1243 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1245 /// Split the vector with EXTRACT_SUBVECTOR using the provides
1246 /// VTs and return the low/high part.
1247 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1248 const EVT &LoVT, const EVT &HiVT);
1250 /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part.
1251 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1253 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1254 return SplitVector(N, DL, LoVT, HiVT);
1257 /// Split the node's operand with EXTRACT_SUBVECTOR and
1258 /// return the low/high part.
1259 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1261 return SplitVector(N->getOperand(OpNo), SDLoc(N));
1264 /// Append the extracted elements from Start to Count out of the vector Op
1265 /// in Args. If Count is 0, all of the elements will be extracted.
1266 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
1267 unsigned Start = 0, unsigned Count = 0);
1269 unsigned getEVTAlignment(EVT MemoryVT) const;
1272 void InsertNode(SDNode *N);
1273 bool RemoveNodeFromCSEMaps(SDNode *N);
1274 void AddModifiedNodeToCSEMaps(SDNode *N);
1275 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1276 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1278 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1280 SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
1282 void DeleteNodeNotInCSEMaps(SDNode *N);
1283 void DeallocateNode(SDNode *N);
1285 void allnodes_clear();
1287 BinarySDNode *GetBinarySDNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
1288 SDValue N1, SDValue N2,
1289 const SDNodeFlags *Flags = nullptr);
1291 /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1292 /// not, return the insertion token that will make insertion faster. This
1293 /// overload is for nodes other than Constant or ConstantFP, use the other one
1295 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
1297 /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1298 /// not, return the insertion token that will make insertion faster. Performs
1299 /// additional processing for constant nodes.
1300 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, DebugLoc DL,
1303 /// List of non-single value types.
1304 FoldingSet<SDVTListNode> VTListMap;
1306 /// Maps to auto-CSE operations.
1307 std::vector<CondCodeSDNode*> CondCodeNodes;
1309 std::vector<SDNode*> ValueTypeNodes;
1310 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1311 StringMap<SDNode*> ExternalSymbols;
1313 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1314 DenseMap<MCSymbol *, SDNode *> MCSymbols;
1317 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1318 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1319 static nodes_iterator nodes_begin(SelectionDAG *G) {
1320 return G->allnodes_begin();
1322 static nodes_iterator nodes_end(SelectionDAG *G) {
1323 return G->allnodes_end();
1327 } // end namespace llvm