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.
219 uint16_t NextPersistentId;
223 /// Clients of various APIs that cause global effects on
224 /// the DAG can optionally implement this interface. This allows the clients
225 /// to handle the various sorts of updates that happen.
227 /// A DAGUpdateListener automatically registers itself with DAG when it is
228 /// constructed, and removes itself when destroyed in RAII fashion.
229 struct DAGUpdateListener {
230 DAGUpdateListener *const Next;
233 explicit DAGUpdateListener(SelectionDAG &D)
234 : Next(D.UpdateListeners), DAG(D) {
235 DAG.UpdateListeners = this;
238 virtual ~DAGUpdateListener() {
239 assert(DAG.UpdateListeners == this &&
240 "DAGUpdateListeners must be destroyed in LIFO order");
241 DAG.UpdateListeners = Next;
244 /// The node N that was deleted and, if E is not null, an
245 /// equivalent node E that replaced it.
246 virtual void NodeDeleted(SDNode *N, SDNode *E);
248 /// The node N that was updated.
249 virtual void NodeUpdated(SDNode *N);
252 /// When true, additional steps are taken to
253 /// ensure that getConstant() and similar functions return DAG nodes that
254 /// have legal types. This is important after type legalization since
255 /// any illegally typed nodes generated after this point will not experience
256 /// type legalization.
257 bool NewNodesMustHaveLegalTypes;
260 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
261 friend struct DAGUpdateListener;
263 /// Linked list of registered DAGUpdateListener instances.
264 /// This stack is maintained by DAGUpdateListener RAII.
265 DAGUpdateListener *UpdateListeners;
267 /// Implementation of setSubgraphColor.
268 /// Return whether we had to truncate the search.
269 bool setSubgraphColorHelper(SDNode *N, const char *Color,
270 DenseSet<SDNode *> &visited,
271 int level, bool &printed);
273 void operator=(const SelectionDAG&) = delete;
274 SelectionDAG(const SelectionDAG&) = delete;
277 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
280 /// Prepare this SelectionDAG to process code in the given MachineFunction.
281 void init(MachineFunction &mf);
283 /// Clear state and free memory necessary to make this
284 /// SelectionDAG ready to process a new block.
287 MachineFunction &getMachineFunction() const { return *MF; }
288 const DataLayout &getDataLayout() const { return MF->getDataLayout(); }
289 const TargetMachine &getTarget() const { return TM; }
290 const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
291 const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
292 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return *TSI; }
293 LLVMContext *getContext() const {return Context; }
295 /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
296 void viewGraph(const std::string &Title);
300 std::map<const SDNode *, std::string> NodeGraphAttrs;
303 /// Clear all previously defined node graph attributes.
304 /// Intended to be used from a debugging tool (eg. gdb).
305 void clearGraphAttrs();
307 /// Set graph attributes for a node. (eg. "color=red".)
308 void setGraphAttrs(const SDNode *N, const char *Attrs);
310 /// Get graph attributes for a node. (eg. "color=red".)
311 /// Used from getNodeAttributes.
312 const std::string getGraphAttrs(const SDNode *N) const;
314 /// Convenience for setting node color attribute.
315 void setGraphColor(const SDNode *N, const char *Color);
317 /// Convenience for setting subgraph color attribute.
318 void setSubgraphColor(SDNode *N, const char *Color);
320 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
321 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
322 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
323 typedef ilist<SDNode>::iterator allnodes_iterator;
324 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
325 allnodes_iterator allnodes_end() { return AllNodes.end(); }
326 ilist<SDNode>::size_type allnodes_size() const {
327 return AllNodes.size();
330 iterator_range<allnodes_iterator> allnodes() {
331 return iterator_range<allnodes_iterator>(allnodes_begin(), allnodes_end());
333 iterator_range<allnodes_const_iterator> allnodes() const {
334 return iterator_range<allnodes_const_iterator>(allnodes_begin(),
338 /// Return the root tag of the SelectionDAG.
339 const SDValue &getRoot() const { return Root; }
341 /// Return the token chain corresponding to the entry of the function.
342 SDValue getEntryNode() const {
343 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
346 /// Set the current root tag of the SelectionDAG.
348 const SDValue &setRoot(SDValue N) {
349 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
350 "DAG root value is not a chain!");
352 checkForCycles(N.getNode(), this);
355 checkForCycles(this);
359 /// This iterates over the nodes in the SelectionDAG, folding
360 /// certain types of nodes together, or eliminating superfluous nodes. The
361 /// Level argument controls whether Combine is allowed to produce nodes and
362 /// types that are illegal on the target.
363 void Combine(CombineLevel Level, AliasAnalysis &AA,
364 CodeGenOpt::Level OptLevel);
366 /// This transforms the SelectionDAG into a SelectionDAG that
367 /// only uses types natively supported by the target.
368 /// Returns "true" if it made any changes.
370 /// Note that this is an involved process that may invalidate pointers into
372 bool LegalizeTypes();
374 /// This transforms the SelectionDAG into a SelectionDAG that is
375 /// compatible with the target instruction selector, as indicated by the
376 /// TargetLowering object.
378 /// Note that this is an involved process that may invalidate pointers into
382 /// \brief Transforms a SelectionDAG node and any operands to it into a node
383 /// that is compatible with the target instruction selector, as indicated by
384 /// the TargetLowering object.
386 /// \returns true if \c N is a valid, legal node after calling this.
388 /// This essentially runs a single recursive walk of the \c Legalize process
389 /// over the given node (and its operands). This can be used to incrementally
390 /// legalize the DAG. All of the nodes which are directly replaced,
391 /// potentially including N, are added to the output parameter \c
392 /// UpdatedNodes so that the delta to the DAG can be understood by the
395 /// When this returns false, N has been legalized in a way that make the
396 /// pointer passed in no longer valid. It may have even been deleted from the
397 /// DAG, and so it shouldn't be used further. When this returns true, the
398 /// N passed in is a legal node, and can be immediately processed as such.
399 /// This may still have done some work on the DAG, and will still populate
400 /// UpdatedNodes with any new nodes replacing those originally in the DAG.
401 bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
403 /// This transforms the SelectionDAG into a SelectionDAG
404 /// that only uses vector math operations supported by the target. This is
405 /// necessary as a separate step from Legalize because unrolling a vector
406 /// operation can introduce illegal types, which requires running
407 /// LegalizeTypes again.
409 /// This returns true if it made any changes; in that case, LegalizeTypes
410 /// is called again before Legalize.
412 /// Note that this is an involved process that may invalidate pointers into
414 bool LegalizeVectors();
416 /// This method deletes all unreachable nodes in the SelectionDAG.
417 void RemoveDeadNodes();
419 /// Remove the specified node from the system. This node must
420 /// have no referrers.
421 void DeleteNode(SDNode *N);
423 /// Return an SDVTList that represents the list of values specified.
424 SDVTList getVTList(EVT VT);
425 SDVTList getVTList(EVT VT1, EVT VT2);
426 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
427 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
428 SDVTList getVTList(ArrayRef<EVT> VTs);
430 //===--------------------------------------------------------------------===//
431 // Node creation methods.
433 SDValue getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isTarget = false,
434 bool isOpaque = false);
435 SDValue getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isTarget = false,
436 bool isOpaque = false);
437 SDValue getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
438 bool isTarget = false, bool isOpaque = false);
439 SDValue getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget = false);
440 SDValue getTargetConstant(uint64_t Val, SDLoc DL, EVT VT,
441 bool isOpaque = false) {
442 return getConstant(Val, DL, VT, true, isOpaque);
444 SDValue getTargetConstant(const APInt &Val, SDLoc DL, EVT VT,
445 bool isOpaque = false) {
446 return getConstant(Val, DL, VT, true, isOpaque);
448 SDValue getTargetConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
449 bool isOpaque = false) {
450 return getConstant(Val, DL, VT, true, isOpaque);
452 // The forms below that take a double should only be used for simple
453 // constants that can be exactly represented in VT. No checks are made.
454 SDValue getConstantFP(double Val, SDLoc DL, EVT VT, bool isTarget = false);
455 SDValue getConstantFP(const APFloat& Val, SDLoc DL, EVT VT,
456 bool isTarget = false);
457 SDValue getConstantFP(const ConstantFP &CF, SDLoc DL, EVT VT,
458 bool isTarget = false);
459 SDValue getTargetConstantFP(double Val, SDLoc DL, EVT VT) {
460 return getConstantFP(Val, DL, VT, true);
462 SDValue getTargetConstantFP(const APFloat& Val, SDLoc DL, EVT VT) {
463 return getConstantFP(Val, DL, VT, true);
465 SDValue getTargetConstantFP(const ConstantFP &Val, SDLoc DL, EVT VT) {
466 return getConstantFP(Val, DL, VT, true);
468 SDValue getGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
469 int64_t offset = 0, bool isTargetGA = false,
470 unsigned char TargetFlags = 0);
471 SDValue getTargetGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
473 unsigned char TargetFlags = 0) {
474 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
476 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
477 SDValue getTargetFrameIndex(int FI, EVT VT) {
478 return getFrameIndex(FI, VT, true);
480 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
481 unsigned char TargetFlags = 0);
482 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
483 return getJumpTable(JTI, VT, true, TargetFlags);
485 SDValue getConstantPool(const Constant *C, EVT VT,
486 unsigned Align = 0, int Offs = 0, bool isT=false,
487 unsigned char TargetFlags = 0);
488 SDValue getTargetConstantPool(const Constant *C, EVT VT,
489 unsigned Align = 0, int Offset = 0,
490 unsigned char TargetFlags = 0) {
491 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
493 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
494 unsigned Align = 0, int Offs = 0, bool isT=false,
495 unsigned char TargetFlags = 0);
496 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
497 EVT VT, unsigned Align = 0,
498 int Offset = 0, unsigned char TargetFlags=0) {
499 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
501 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
502 unsigned char TargetFlags = 0);
503 // When generating a branch to a BB, we don't in general know enough
504 // to provide debug info for the BB at that time, so keep this one around.
505 SDValue getBasicBlock(MachineBasicBlock *MBB);
506 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
507 SDValue getExternalSymbol(const char *Sym, EVT VT);
508 SDValue getExternalSymbol(const char *Sym, SDLoc dl, EVT VT);
509 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
510 unsigned char TargetFlags = 0);
511 SDValue getMCSymbol(MCSymbol *Sym, EVT VT);
513 SDValue getValueType(EVT);
514 SDValue getRegister(unsigned Reg, EVT VT);
515 SDValue getRegisterMask(const uint32_t *RegMask);
516 SDValue getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label);
517 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
518 int64_t Offset = 0, bool isTarget = false,
519 unsigned char TargetFlags = 0);
520 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
522 unsigned char TargetFlags = 0) {
523 return getBlockAddress(BA, VT, Offset, true, TargetFlags);
526 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N) {
527 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
528 getRegister(Reg, N.getValueType()), N);
531 // This version of the getCopyToReg method takes an extra operand, which
532 // indicates that there is potentially an incoming glue value (if Glue is not
533 // null) and that there should be a glue result.
534 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N,
536 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
537 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
538 return getNode(ISD::CopyToReg, dl, VTs,
539 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
542 // Similar to last getCopyToReg() except parameter Reg is a SDValue
543 SDValue getCopyToReg(SDValue Chain, SDLoc dl, SDValue Reg, SDValue N,
545 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
546 SDValue Ops[] = { Chain, Reg, N, Glue };
547 return getNode(ISD::CopyToReg, dl, VTs,
548 makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
551 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT) {
552 SDVTList VTs = getVTList(VT, MVT::Other);
553 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
554 return getNode(ISD::CopyFromReg, dl, VTs, Ops);
557 // This version of the getCopyFromReg method takes an extra operand, which
558 // indicates that there is potentially an incoming glue value (if Glue is not
559 // null) and that there should be a glue result.
560 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT,
562 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
563 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
564 return getNode(ISD::CopyFromReg, dl, VTs,
565 makeArrayRef(Ops, Glue.getNode() ? 3 : 2));
568 SDValue getCondCode(ISD::CondCode Cond);
570 /// Returns the ConvertRndSat Note: Avoid using this node because it may
571 /// disappear in the future and most targets don't support it.
572 SDValue getConvertRndSat(EVT VT, SDLoc dl, SDValue Val, SDValue DTy,
574 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
576 /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT,
577 /// which must be a vector type, must match the number of mask elements
578 /// NumElts. An integer mask element equal to -1 is treated as undefined.
579 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
580 const int *MaskElts);
581 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
582 ArrayRef<int> MaskElts) {
583 assert(VT.getVectorNumElements() == MaskElts.size() &&
584 "Must have the same number of vector elements as mask elements!");
585 return getVectorShuffle(VT, dl, N1, N2, MaskElts.data());
588 /// \brief Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
589 /// the shuffle node in input but with swapped operands.
591 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
592 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
594 /// Convert Op, which must be of integer type, to the
595 /// integer type VT, by either any-extending or truncating it.
596 SDValue getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
598 /// Convert Op, which must be of integer type, to the
599 /// integer type VT, by either sign-extending or truncating it.
600 SDValue getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
602 /// Convert Op, which must be of integer type, to the
603 /// integer type VT, by either zero-extending or truncating it.
604 SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
606 /// Return the expression required to zero extend the Op
607 /// value assuming it was the smaller SrcTy value.
608 SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy);
610 /// Return an operation which will any-extend the low lanes of the operand
611 /// into the specified vector type. For example,
612 /// this can convert a v16i8 into a v4i32 by any-extending the low four
613 /// lanes of the operand from i8 to i32.
614 SDValue getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
616 /// Return an operation which will sign extend the low lanes of the operand
617 /// into the specified vector type. For example,
618 /// this can convert a v16i8 into a v4i32 by sign extending the low four
619 /// lanes of the operand from i8 to i32.
620 SDValue getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
622 /// Return an operation which will zero extend the low lanes of the operand
623 /// into the specified vector type. For example,
624 /// this can convert a v16i8 into a v4i32 by zero extending the low four
625 /// lanes of the operand from i8 to i32.
626 SDValue getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
628 /// Convert Op, which must be of integer type, to the integer type VT,
629 /// by using an extension appropriate for the target's
630 /// BooleanContent for type OpVT or truncating it.
631 SDValue getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT, EVT OpVT);
633 /// Create a bitwise NOT operation as (XOR Val, -1).
634 SDValue getNOT(SDLoc DL, SDValue Val, EVT VT);
636 /// \brief Create a logical NOT operation as (XOR Val, BooleanOne).
637 SDValue getLogicalNOT(SDLoc DL, SDValue Val, EVT VT);
639 /// Return a new CALLSEQ_START node, which always must have a glue result
640 /// (to ensure it's not CSE'd). CALLSEQ_START does not have a useful SDLoc.
641 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) {
642 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
643 SDValue Ops[] = { Chain, Op };
644 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
647 /// Return a new CALLSEQ_END node, which always must have a
648 /// glue result (to ensure it's not CSE'd).
649 /// CALLSEQ_END does not have a useful SDLoc.
650 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
651 SDValue InGlue, SDLoc DL) {
652 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
653 SmallVector<SDValue, 4> Ops;
654 Ops.push_back(Chain);
657 if (InGlue.getNode())
658 Ops.push_back(InGlue);
659 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
662 /// Return an UNDEF node. UNDEF does not have a useful SDLoc.
663 SDValue getUNDEF(EVT VT) {
664 return getNode(ISD::UNDEF, SDLoc(), VT);
667 /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc.
668 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
669 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
672 /// Gets or creates the specified node.
674 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
675 ArrayRef<SDUse> Ops);
676 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
677 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags = nullptr);
678 SDValue getNode(unsigned Opcode, SDLoc DL, ArrayRef<EVT> ResultTys,
679 ArrayRef<SDValue> Ops);
680 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
681 ArrayRef<SDValue> Ops);
683 // Specialize based on number of operands.
684 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT);
685 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N);
686 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
687 const SDNodeFlags *Flags = nullptr);
688 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
690 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
691 SDValue N3, SDValue N4);
692 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
693 SDValue N3, SDValue N4, SDValue N5);
695 // Specialize again based on number of operands for nodes with a VTList
696 // rather than a single VT.
697 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs);
698 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N);
699 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
701 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
702 SDValue N2, SDValue N3);
703 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
704 SDValue N2, SDValue N3, SDValue N4);
705 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1,
706 SDValue N2, SDValue N3, SDValue N4, SDValue N5);
708 /// Compute a TokenFactor to force all the incoming stack arguments to be
709 /// loaded from the stack. This is used in tail call lowering to protect
710 /// stack arguments from being clobbered.
711 SDValue getStackArgumentTokenFactor(SDValue Chain);
713 SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
714 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
715 bool isTailCall, MachinePointerInfo DstPtrInfo,
716 MachinePointerInfo SrcPtrInfo);
718 SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
719 SDValue Size, unsigned Align, bool isVol, bool isTailCall,
720 MachinePointerInfo DstPtrInfo,
721 MachinePointerInfo SrcPtrInfo);
723 SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
724 SDValue Size, unsigned Align, bool isVol, bool isTailCall,
725 MachinePointerInfo DstPtrInfo);
727 /// Helper function to make it easier to build SetCC's if you just
728 /// have an ISD::CondCode instead of an SDValue.
730 SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS,
731 ISD::CondCode Cond) {
732 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
733 "Cannot compare scalars to vectors");
734 assert(LHS.getValueType().isVector() == VT.isVector() &&
735 "Cannot compare scalars to vectors");
736 assert(Cond != ISD::SETCC_INVALID &&
737 "Cannot create a setCC of an invalid node.");
738 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
741 /// Helper function to make it easier to build Select's if you just
742 /// have operands and don't want to check for vector.
743 SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond,
744 SDValue LHS, SDValue RHS) {
745 assert(LHS.getValueType() == RHS.getValueType() &&
746 "Cannot use select on differing types");
747 assert(VT.isVector() == LHS.getValueType().isVector() &&
748 "Cannot mix vectors and scalars");
749 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
753 /// Helper function to make it easier to build SelectCC's if you
754 /// just have an ISD::CondCode instead of an SDValue.
756 SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS,
757 SDValue True, SDValue False, ISD::CondCode Cond) {
758 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
759 LHS, RHS, True, False, getCondCode(Cond));
762 /// VAArg produces a result and token chain, and takes a pointer
763 /// and a source value as input.
764 SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
765 SDValue SV, unsigned Align);
767 /// Gets a node for an atomic cmpxchg op. There are two
768 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
769 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
770 /// a success flag (initially i1), and a chain.
771 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
772 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
773 MachinePointerInfo PtrInfo, unsigned Alignment,
774 AtomicOrdering SuccessOrdering,
775 AtomicOrdering FailureOrdering,
776 SynchronizationScope SynchScope);
777 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
778 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
779 MachineMemOperand *MMO,
780 AtomicOrdering SuccessOrdering,
781 AtomicOrdering FailureOrdering,
782 SynchronizationScope SynchScope);
784 /// Gets a node for an atomic op, produces result (if relevant)
785 /// and chain and takes 2 operands.
786 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
787 SDValue Ptr, SDValue Val, const Value *PtrVal,
788 unsigned Alignment, AtomicOrdering Ordering,
789 SynchronizationScope SynchScope);
790 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
791 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
792 AtomicOrdering Ordering,
793 SynchronizationScope SynchScope);
795 /// Gets a node for an atomic op, produces result and chain and
797 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
798 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
799 AtomicOrdering Ordering,
800 SynchronizationScope SynchScope);
802 /// Gets a node for an atomic op, produces result and chain and takes N
804 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
805 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
806 AtomicOrdering SuccessOrdering,
807 AtomicOrdering FailureOrdering,
808 SynchronizationScope SynchScope);
809 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
810 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
811 AtomicOrdering Ordering, SynchronizationScope SynchScope);
813 /// Creates a MemIntrinsicNode that may produce a
814 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
815 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
816 /// less than FIRST_TARGET_MEMORY_OPCODE.
817 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
818 ArrayRef<SDValue> Ops,
819 EVT MemVT, MachinePointerInfo PtrInfo,
820 unsigned Align = 0, bool Vol = false,
821 bool ReadMem = true, bool WriteMem = true,
824 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
825 ArrayRef<SDValue> Ops,
826 EVT MemVT, MachineMemOperand *MMO);
828 /// Create a MERGE_VALUES node from the given operands.
829 SDValue getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl);
831 /// Loads are not normal binary operators: their result type is not
832 /// determined by their operands, and they produce a value AND a token chain.
834 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
835 MachinePointerInfo PtrInfo, bool isVolatile,
836 bool isNonTemporal, bool isInvariant, unsigned Alignment,
837 const AAMDNodes &AAInfo = AAMDNodes(),
838 const MDNode *Ranges = nullptr);
839 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
840 MachineMemOperand *MMO);
841 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
842 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
843 EVT MemVT, bool isVolatile,
844 bool isNonTemporal, bool isInvariant, unsigned Alignment,
845 const AAMDNodes &AAInfo = AAMDNodes());
846 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
847 SDValue Chain, SDValue Ptr, EVT MemVT,
848 MachineMemOperand *MMO);
849 SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
850 SDValue Offset, ISD::MemIndexedMode AM);
851 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
853 SDValue Chain, SDValue Ptr, SDValue Offset,
854 MachinePointerInfo PtrInfo, EVT MemVT,
855 bool isVolatile, bool isNonTemporal, bool isInvariant,
856 unsigned Alignment, const AAMDNodes &AAInfo = AAMDNodes(),
857 const MDNode *Ranges = nullptr);
858 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
860 SDValue Chain, SDValue Ptr, SDValue Offset,
861 EVT MemVT, MachineMemOperand *MMO);
863 /// Helper function to build ISD::STORE nodes.
864 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
865 MachinePointerInfo PtrInfo, bool isVolatile,
866 bool isNonTemporal, unsigned Alignment,
867 const AAMDNodes &AAInfo = AAMDNodes());
868 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
869 MachineMemOperand *MMO);
870 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
871 MachinePointerInfo PtrInfo, EVT TVT,
872 bool isNonTemporal, bool isVolatile,
874 const AAMDNodes &AAInfo = AAMDNodes());
875 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
876 EVT TVT, MachineMemOperand *MMO);
877 SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base,
878 SDValue Offset, ISD::MemIndexedMode AM);
880 SDValue getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
881 SDValue Mask, SDValue Src0, EVT MemVT,
882 MachineMemOperand *MMO, ISD::LoadExtType);
883 SDValue getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
884 SDValue Ptr, SDValue Mask, EVT MemVT,
885 MachineMemOperand *MMO, bool IsTrunc);
886 SDValue getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
887 ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
888 SDValue getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
889 ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
890 /// Construct a node to track a Value* through the backend.
891 SDValue getSrcValue(const Value *v);
893 /// Return an MDNodeSDNode which holds an MDNode.
894 SDValue getMDNode(const MDNode *MD);
896 /// Return a bitcast using the SDLoc of the value operand, and casting to the
897 /// provided type. Use getNode to set a custom SDLoc.
898 SDValue getBitcast(EVT VT, SDValue V);
900 /// Return an AddrSpaceCastSDNode.
901 SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
902 unsigned SrcAS, unsigned DestAS);
904 /// Return the specified value casted to
905 /// the target's desired shift amount type.
906 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
908 /// Expand the specified \c ISD::VAARG node as the Legalize pass would.
909 SDValue expandVAArg(SDNode *Node);
911 /// Expand the specified \c ISD::VACOPY node as the Legalize pass would.
912 SDValue expandVACopy(SDNode *Node);
914 /// *Mutate* the specified node in-place to have the
915 /// specified operands. If the resultant node already exists in the DAG,
916 /// this does not modify the specified node, instead it returns the node that
917 /// already exists. If the resultant node does not exist in the DAG, the
918 /// input node is returned. As a degenerate case, if you specify the same
919 /// input operands as the node already has, the input node is returned.
920 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
921 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
922 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
924 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
925 SDValue Op3, SDValue Op4);
926 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
927 SDValue Op3, SDValue Op4, SDValue Op5);
928 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
930 /// These are used for target selectors to *mutate* the
931 /// specified node to have the specified return type, Target opcode, and
932 /// operands. Note that target opcodes are stored as
933 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
934 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
935 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
936 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
937 SDValue Op1, SDValue Op2);
938 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
939 SDValue Op1, SDValue Op2, SDValue Op3);
940 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
941 ArrayRef<SDValue> Ops);
942 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
943 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
944 EVT VT2, ArrayRef<SDValue> Ops);
945 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
946 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
947 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
948 EVT VT2, EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
949 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
950 EVT VT2, SDValue Op1);
951 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
952 EVT VT2, SDValue Op1, SDValue Op2);
953 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
954 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
955 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
956 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
957 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
958 ArrayRef<SDValue> Ops);
960 /// This *mutates* the specified node to have the specified
961 /// return type, opcode, and operands.
962 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
963 ArrayRef<SDValue> Ops);
965 /// These are used for target selectors to create a new node
966 /// with specified return type(s), MachineInstr opcode, and operands.
968 /// Note that getMachineNode returns the resultant node. If there is already
969 /// a node of the specified opcode and operands, it returns that node instead
970 /// of the current one.
971 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT);
972 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
974 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
975 SDValue Op1, SDValue Op2);
976 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
977 SDValue Op1, SDValue Op2, SDValue Op3);
978 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
979 ArrayRef<SDValue> Ops);
980 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2);
981 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
983 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
984 SDValue Op1, SDValue Op2);
985 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
986 SDValue Op1, SDValue Op2, SDValue Op3);
987 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
988 ArrayRef<SDValue> Ops);
989 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
990 EVT VT3, SDValue Op1, SDValue Op2);
991 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
992 EVT VT3, SDValue Op1, SDValue Op2,
994 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
995 EVT VT3, ArrayRef<SDValue> Ops);
996 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
997 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
998 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl,
999 ArrayRef<EVT> ResultTys,
1000 ArrayRef<SDValue> Ops);
1001 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs,
1002 ArrayRef<SDValue> Ops);
1004 /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
1005 SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
1008 /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes.
1009 SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
1010 SDValue Operand, SDValue Subreg);
1012 /// Get the specified node if it's already available, or else return NULL.
1013 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops,
1014 const SDNodeFlags *Flags = nullptr);
1016 /// Creates a SDDbgValue node.
1017 SDDbgValue *getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N, unsigned R,
1018 bool IsIndirect, uint64_t Off, DebugLoc DL,
1022 SDDbgValue *getConstantDbgValue(MDNode *Var, MDNode *Expr, const Value *C,
1023 uint64_t Off, DebugLoc DL, unsigned O);
1026 SDDbgValue *getFrameIndexDbgValue(MDNode *Var, MDNode *Expr, unsigned FI,
1027 uint64_t Off, DebugLoc DL, unsigned O);
1029 /// Remove the specified node from the system. If any of its
1030 /// operands then becomes dead, remove them as well. Inform UpdateListener
1031 /// for each node deleted.
1032 void RemoveDeadNode(SDNode *N);
1034 /// This method deletes the unreachable nodes in the
1035 /// given list, and any nodes that become unreachable as a result.
1036 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
1038 /// Modify anything using 'From' to use 'To' instead.
1039 /// This can cause recursive merging of nodes in the DAG. Use the first
1040 /// version if 'From' is known to have a single result, use the second
1041 /// if you have two nodes with identical results (or if 'To' has a superset
1042 /// of the results of 'From'), use the third otherwise.
1044 /// These methods all take an optional UpdateListener, which (if not null) is
1045 /// informed about nodes that are deleted and modified due to recursive
1046 /// changes in the dag.
1048 /// These functions only replace all existing uses. It's possible that as
1049 /// these replacements are being performed, CSE may cause the From node
1050 /// to be given new uses. These new uses of From are left in place, and
1051 /// not automatically transferred to To.
1053 void ReplaceAllUsesWith(SDValue From, SDValue Op);
1054 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
1055 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
1057 /// Replace any uses of From with To, leaving
1058 /// uses of other values produced by From.Val alone.
1059 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
1061 /// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
1062 /// This correctly handles the case where
1063 /// there is an overlap between the From values and the To values.
1064 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
1067 /// Topological-sort the AllNodes list and a
1068 /// assign a unique node id for each node in the DAG based on their
1069 /// topological order. Returns the number of nodes.
1070 unsigned AssignTopologicalOrder();
1072 /// Move node N in the AllNodes list to be immediately
1073 /// before the given iterator Position. This may be used to update the
1074 /// topological ordering when the list of nodes is modified.
1075 void RepositionNode(allnodes_iterator Position, SDNode *N) {
1076 AllNodes.insert(Position, AllNodes.remove(N));
1079 /// Returns true if the opcode is a commutative binary operation.
1080 static bool isCommutativeBinOp(unsigned Opcode) {
1081 // FIXME: This should get its info from the td file, so that we can include
1092 case ISD::SMUL_LOHI:
1093 case ISD::UMUL_LOHI:
1108 default: return false;
1112 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1113 /// a vector type, the element semantics are returned.
1114 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1115 switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1116 default: llvm_unreachable("Unknown FP format");
1117 case MVT::f16: return APFloat::IEEEhalf;
1118 case MVT::f32: return APFloat::IEEEsingle;
1119 case MVT::f64: return APFloat::IEEEdouble;
1120 case MVT::f80: return APFloat::x87DoubleExtended;
1121 case MVT::f128: return APFloat::IEEEquad;
1122 case MVT::ppcf128: return APFloat::PPCDoubleDouble;
1126 /// Add a dbg_value SDNode. If SD is non-null that means the
1127 /// value is produced by SD.
1128 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1130 /// Get the debug values which reference the given SDNode.
1131 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
1132 return DbgInfo->getSDDbgValues(SD);
1135 /// Transfer SDDbgValues.
1136 void TransferDbgValues(SDValue From, SDValue To);
1138 /// Return true if there are any SDDbgValue nodes associated
1139 /// with this SelectionDAG.
1140 bool hasDebugValues() const { return !DbgInfo->empty(); }
1142 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
1143 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
1144 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
1145 return DbgInfo->ByvalParmDbgBegin();
1147 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
1148 return DbgInfo->ByvalParmDbgEnd();
1153 /// Create a stack temporary, suitable for holding the
1154 /// specified value type. If minAlign is specified, the slot size will have
1155 /// at least that alignment.
1156 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1158 /// Create a stack temporary suitable for holding
1159 /// either of the specified value types.
1160 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1162 SDValue FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
1163 SDNode *Cst1, SDNode *Cst2);
1165 SDValue FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
1166 const ConstantSDNode *Cst1,
1167 const ConstantSDNode *Cst2);
1169 /// Constant fold a setcc to true or false.
1170 SDValue FoldSetCC(EVT VT, SDValue N1,
1171 SDValue N2, ISD::CondCode Cond, SDLoc dl);
1173 /// Return true if the sign bit of Op is known to be zero.
1174 /// We use this predicate to simplify operations downstream.
1175 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1177 /// Return true if 'Op & Mask' is known to be zero. We
1178 /// use this predicate to simplify operations downstream. Op and Mask are
1179 /// known to be the same type.
1180 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1183 /// Determine which bits of Op are known to be either zero or one and return
1184 /// them in the KnownZero/KnownOne bitsets. Targets can implement the
1185 /// computeKnownBitsForTargetNode method in the TargetLowering class to allow
1186 /// target nodes to be understood.
1187 void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1188 unsigned Depth = 0) const;
1190 /// Return the number of times the sign bit of the
1191 /// register is replicated into the other bits. We know that at least 1 bit
1192 /// is always equal to the sign bit (itself), but other cases can give us
1193 /// information. For example, immediately after an "SRA X, 2", we know that
1194 /// the top 3 bits are all equal to each other, so we return 3. Targets can
1195 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1196 /// class to allow target nodes to be understood.
1197 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1199 /// Return true if the specified operand is an
1200 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1201 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1202 /// semantics as an ADD. This handles the equivalence:
1203 /// X|Cst == X+Cst iff X&Cst = 0.
1204 bool isBaseWithConstantOffset(SDValue Op) const;
1206 /// Test whether the given SDValue is known to never be NaN.
1207 bool isKnownNeverNaN(SDValue Op) const;
1209 /// Test whether the given SDValue is known to never be
1210 /// positive or negative Zero.
1211 bool isKnownNeverZero(SDValue Op) const;
1213 /// Test whether two SDValues are known to compare equal. This
1214 /// is true if they are the same value, or if one is negative zero and the
1215 /// other positive zero.
1216 bool isEqualTo(SDValue A, SDValue B) const;
1218 /// Utility function used by legalize and lowering to
1219 /// "unroll" a vector operation by splitting out the scalars and operating
1220 /// on each element individually. If the ResNE is 0, fully unroll the vector
1221 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1222 /// If the ResNE is greater than the width of the vector op, unroll the
1223 /// vector op and fill the end of the resulting vector with UNDEFS.
1224 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1226 /// Return true if LD is loading 'Bytes' bytes from a location that is 'Dist'
1227 /// units away from the location that the 'Base' load is loading from.
1228 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1229 unsigned Bytes, int Dist) const;
1231 /// Infer alignment of a load / store address. Return 0 if
1232 /// it cannot be inferred.
1233 unsigned InferPtrAlignment(SDValue Ptr) const;
1235 /// Compute the VTs needed for the low/hi parts of a type
1236 /// which is split (or expanded) into two not necessarily identical pieces.
1237 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1239 /// Split the vector with EXTRACT_SUBVECTOR using the provides
1240 /// VTs and return the low/high part.
1241 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1242 const EVT &LoVT, const EVT &HiVT);
1244 /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part.
1245 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1247 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1248 return SplitVector(N, DL, LoVT, HiVT);
1251 /// Split the node's operand with EXTRACT_SUBVECTOR and
1252 /// return the low/high part.
1253 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1255 return SplitVector(N->getOperand(OpNo), SDLoc(N));
1258 /// Append the extracted elements from Start to Count out of the vector Op
1259 /// in Args. If Count is 0, all of the elements will be extracted.
1260 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
1261 unsigned Start = 0, unsigned Count = 0);
1263 unsigned getEVTAlignment(EVT MemoryVT) const;
1266 void InsertNode(SDNode *N);
1267 bool RemoveNodeFromCSEMaps(SDNode *N);
1268 void AddModifiedNodeToCSEMaps(SDNode *N);
1269 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1270 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1272 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1274 SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
1276 void DeleteNodeNotInCSEMaps(SDNode *N);
1277 void DeallocateNode(SDNode *N);
1279 void allnodes_clear();
1281 BinarySDNode *GetBinarySDNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
1282 SDValue N1, SDValue N2,
1283 const SDNodeFlags *Flags = nullptr);
1285 /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1286 /// not, return the insertion token that will make insertion faster. This
1287 /// overload is for nodes other than Constant or ConstantFP, use the other one
1289 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
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. Performs
1293 /// additional processing for constant nodes.
1294 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, DebugLoc DL,
1297 /// List of non-single value types.
1298 FoldingSet<SDVTListNode> VTListMap;
1300 /// Maps to auto-CSE operations.
1301 std::vector<CondCodeSDNode*> CondCodeNodes;
1303 std::vector<SDNode*> ValueTypeNodes;
1304 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1305 StringMap<SDNode*> ExternalSymbols;
1307 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1308 DenseMap<MCSymbol *, SDNode *> MCSymbols;
1311 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1312 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1313 static nodes_iterator nodes_begin(SelectionDAG *G) {
1314 return G->allnodes_begin();
1316 static nodes_iterator nodes_end(SelectionDAG *G) {
1317 return G->allnodes_end();
1321 } // end namespace llvm