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/CodeGen/DAGCombine.h"
23 #include "llvm/CodeGen/MachineFunction.h"
24 #include "llvm/CodeGen/SelectionDAGNodes.h"
25 #include "llvm/Support/RecyclingAllocator.h"
26 #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 /// FastID - 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 big so it won't introduce memory penalty.
48 FoldingSetNodeIDRef FastID;
51 /// The hash value for SDVTList is fixed so cache it to avoid hash calculation
54 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
55 FastID(ID), VTs(VT), NumVTs(Num) {
56 HashValue = ID.ComputeHash();
58 SDVTList getSDVTList() {
59 SDVTList result = {VTs, NumVTs};
64 // Specialize FoldingSetTrait for SDVTListNode
65 // To avoid computing temp FoldingSetNodeID and hash value.
66 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
67 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
70 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
71 unsigned IDHash, FoldingSetNodeID &TempID) {
72 if (X.HashValue != IDHash)
74 return ID == X.FastID;
76 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
81 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
83 mutable ilist_half_node<SDNode> Sentinel;
85 SDNode *createSentinel() const {
86 return static_cast<SDNode*>(&Sentinel);
88 static void destroySentinel(SDNode *) {}
90 SDNode *provideInitialHead() const { return createSentinel(); }
91 SDNode *ensureHead(SDNode*) const { return createSentinel(); }
92 static void noteHead(SDNode*, SDNode*) {}
94 static void deleteNode(SDNode *) {
95 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
98 static void createNode(const SDNode &);
101 /// SDDbgInfo - Keeps track of dbg_value information through SDISel. We do
102 /// not build SDNodes for these so as not to perturb the generated code;
103 /// instead the info is kept off to the side in this structure. Each SDNode may
104 /// have one or more associated dbg_value entries. This information is kept in
106 /// Byval parameters are handled separately because they don't use alloca's,
107 /// which busts the normal mechanism. There is good reason for handling all
108 /// parameters separately: they may not have code generated for them, they
109 /// should always go at the beginning of the function regardless of other code
110 /// motion, and debug info for them is potentially useful even if the parameter
111 /// is unused. Right now only byval parameters are handled separately.
113 SmallVector<SDDbgValue*, 32> DbgValues;
114 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
115 typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType;
116 DbgValMapType DbgValMap;
118 void operator=(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
119 SDDbgInfo(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
123 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
125 ByvalParmDbgValues.push_back(V);
126 } else DbgValues.push_back(V);
128 DbgValMap[Node].push_back(V);
134 ByvalParmDbgValues.clear();
138 return DbgValues.empty() && ByvalParmDbgValues.empty();
141 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
142 DbgValMapType::iterator I = DbgValMap.find(Node);
143 if (I != DbgValMap.end())
145 return ArrayRef<SDDbgValue*>();
148 typedef SmallVectorImpl<SDDbgValue*>::iterator DbgIterator;
149 DbgIterator DbgBegin() { return DbgValues.begin(); }
150 DbgIterator DbgEnd() { return DbgValues.end(); }
151 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
152 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
156 void checkForCycles(const SelectionDAG *DAG, bool force = false);
158 /// SelectionDAG class - This is used to represent a portion of an LLVM function
159 /// in a low-level Data Dependence DAG representation suitable for instruction
160 /// selection. This DAG is constructed as the first step of instruction
161 /// selection in order to allow implementation of machine specific optimizations
162 /// and code simplifications.
164 /// The representation used by the SelectionDAG is a target-independent
165 /// representation, which has some similarities to the GCC RTL representation,
166 /// but is significantly more simple, powerful, and is a graph form instead of a
170 const TargetMachine &TM;
171 const TargetSelectionDAGInfo *TSI;
172 const TargetLowering *TLI;
174 LLVMContext *Context;
175 CodeGenOpt::Level OptLevel;
177 /// EntryNode - The starting token.
180 /// Root - The root of the entire DAG.
183 /// AllNodes - A linked list of nodes in the current DAG.
184 ilist<SDNode> AllNodes;
186 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
187 /// pool allocation with recycling.
188 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
189 AlignOf<MostAlignedSDNode>::Alignment>
192 /// NodeAllocator - Pool allocation for nodes.
193 NodeAllocatorType NodeAllocator;
195 /// CSEMap - This structure is used to memoize nodes, automatically performing
196 /// CSE with existing nodes when a duplicate is requested.
197 FoldingSet<SDNode> CSEMap;
199 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
200 BumpPtrAllocator OperandAllocator;
202 /// Allocator - Pool allocation for misc. objects that are created once per
204 BumpPtrAllocator Allocator;
206 /// DbgInfo - Tracks dbg_value information through SDISel.
210 /// DAGUpdateListener - Clients of various APIs that cause global effects on
211 /// the DAG can optionally implement this interface. This allows the clients
212 /// to handle the various sorts of updates that happen.
214 /// A DAGUpdateListener automatically registers itself with DAG when it is
215 /// constructed, and removes itself when destroyed in RAII fashion.
216 struct DAGUpdateListener {
217 DAGUpdateListener *const Next;
220 explicit DAGUpdateListener(SelectionDAG &D)
221 : Next(D.UpdateListeners), DAG(D) {
222 DAG.UpdateListeners = this;
225 virtual ~DAGUpdateListener() {
226 assert(DAG.UpdateListeners == this &&
227 "DAGUpdateListeners must be destroyed in LIFO order");
228 DAG.UpdateListeners = Next;
231 /// NodeDeleted - The node N that was deleted and, if E is not null, an
232 /// equivalent node E that replaced it.
233 virtual void NodeDeleted(SDNode *N, SDNode *E);
235 /// NodeUpdated - The node N that was updated.
236 virtual void NodeUpdated(SDNode *N);
239 /// NewNodesMustHaveLegalTypes - When true, additional steps are taken to
240 /// ensure that getConstant() and similar functions return DAG nodes that
241 /// have legal types. This is important after type legalization since
242 /// any illegally typed nodes generated after this point will not experience
243 /// type legalization.
244 bool NewNodesMustHaveLegalTypes;
247 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
248 friend struct DAGUpdateListener;
250 /// UpdateListeners - Linked list of registered DAGUpdateListener instances.
251 /// This stack is maintained by DAGUpdateListener RAII.
252 DAGUpdateListener *UpdateListeners;
254 /// setGraphColorHelper - Implementation of setSubgraphColor.
255 /// Return whether we had to truncate the search.
257 bool setSubgraphColorHelper(SDNode *N, const char *Color,
258 DenseSet<SDNode *> &visited,
259 int level, bool &printed);
261 void operator=(const SelectionDAG&) LLVM_DELETED_FUNCTION;
262 SelectionDAG(const SelectionDAG&) LLVM_DELETED_FUNCTION;
265 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
268 /// init - Prepare this SelectionDAG to process code in the given
271 void init(MachineFunction &mf);
273 /// clear - Clear state and free memory necessary to make this
274 /// SelectionDAG ready to process a new block.
278 MachineFunction &getMachineFunction() const { return *MF; }
279 const TargetMachine &getTarget() const { return TM; }
280 const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
281 const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
282 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return *TSI; }
283 LLVMContext *getContext() const {return Context; }
285 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
287 void viewGraph(const std::string &Title);
291 std::map<const SDNode *, std::string> NodeGraphAttrs;
294 /// clearGraphAttrs - Clear all previously defined node graph attributes.
295 /// Intended to be used from a debugging tool (eg. gdb).
296 void clearGraphAttrs();
298 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
300 void setGraphAttrs(const SDNode *N, const char *Attrs);
302 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
303 /// Used from getNodeAttributes.
304 const std::string getGraphAttrs(const SDNode *N) const;
306 /// setGraphColor - Convenience for setting node color attribute.
308 void setGraphColor(const SDNode *N, const char *Color);
310 /// setGraphColor - Convenience for setting subgraph color attribute.
312 void setSubgraphColor(SDNode *N, const char *Color);
314 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
315 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
316 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
317 typedef ilist<SDNode>::iterator allnodes_iterator;
318 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
319 allnodes_iterator allnodes_end() { return AllNodes.end(); }
320 ilist<SDNode>::size_type allnodes_size() const {
321 return AllNodes.size();
324 /// getRoot - Return the root tag of the SelectionDAG.
326 const SDValue &getRoot() const { return Root; }
328 /// getEntryNode - Return the token chain corresponding to the entry of the
330 SDValue getEntryNode() const {
331 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
334 /// setRoot - Set the current root tag of the SelectionDAG.
336 const SDValue &setRoot(SDValue N) {
337 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
338 "DAG root value is not a chain!");
340 checkForCycles(N.getNode(), this);
343 checkForCycles(this);
347 /// Combine - This iterates over the nodes in the SelectionDAG, folding
348 /// certain types of nodes together, or eliminating superfluous nodes. The
349 /// Level argument controls whether Combine is allowed to produce nodes and
350 /// types that are illegal on the target.
351 void Combine(CombineLevel Level, AliasAnalysis &AA,
352 CodeGenOpt::Level OptLevel);
354 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
355 /// only uses types natively supported by the target. Returns "true" if it
356 /// made any changes.
358 /// Note that this is an involved process that may invalidate pointers into
360 bool LegalizeTypes();
362 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
363 /// compatible with the target instruction selector, as indicated by the
364 /// TargetLowering object.
366 /// Note that this is an involved process that may invalidate pointers into
370 /// \brief Transforms a SelectionDAG node and any operands to it into a node
371 /// that is compatible with the target instruction selector, as indicated by
372 /// the TargetLowering object.
374 /// \returns true if \c N is a valid, legal node after calling this.
376 /// This essentially runs a single recursive walk of the \c Legalize process
377 /// over the given node (and its operands). This can be used to incrementally
378 /// legalize the DAG. All of the nodes which are directly replaced,
379 /// potentially including N, are added to the output parameter \c
380 /// UpdatedNodes so that the delta to the DAG can be understood by the
383 /// When this returns false, N has been legalized in a way that make the
384 /// pointer passed in no longer valid. It may have even been deleted from the
385 /// DAG, and so it shouldn't be used further. When this returns true, the
386 /// N passed in is a legal node, and can be immediately processed as such.
387 /// This may still have done some work on the DAG, and will still populate
388 /// UpdatedNodes with any new nodes replacing those originally in the DAG.
389 bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
391 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
392 /// that only uses vector math operations supported by the target. This is
393 /// necessary as a separate step from Legalize because unrolling a vector
394 /// operation can introduce illegal types, which requires running
395 /// LegalizeTypes again.
397 /// This returns true if it made any changes; in that case, LegalizeTypes
398 /// is called again before Legalize.
400 /// Note that this is an involved process that may invalidate pointers into
402 bool LegalizeVectors();
404 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
406 void RemoveDeadNodes();
408 /// DeleteNode - Remove the specified node from the system. This node must
409 /// have no referrers.
410 void DeleteNode(SDNode *N);
412 /// getVTList - Return an SDVTList that represents the list of values
414 SDVTList getVTList(EVT VT);
415 SDVTList getVTList(EVT VT1, EVT VT2);
416 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
417 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
418 SDVTList getVTList(ArrayRef<EVT> VTs);
420 //===--------------------------------------------------------------------===//
421 // Node creation methods.
423 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false,
424 bool isOpaque = false);
425 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false,
426 bool isOpaque = false);
427 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false,
428 bool isOpaque = false);
429 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
430 SDValue getTargetConstant(uint64_t Val, EVT VT, bool isOpaque = false) {
431 return getConstant(Val, VT, true, isOpaque);
433 SDValue getTargetConstant(const APInt &Val, EVT VT, bool isOpaque = false) {
434 return getConstant(Val, VT, true, isOpaque);
436 SDValue getTargetConstant(const ConstantInt &Val, EVT VT,
437 bool isOpaque = false) {
438 return getConstant(Val, VT, true, isOpaque);
440 // The forms below that take a double should only be used for simple
441 // constants that can be exactly represented in VT. No checks are made.
442 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
443 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
444 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
445 SDValue getTargetConstantFP(double Val, EVT VT) {
446 return getConstantFP(Val, VT, true);
448 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
449 return getConstantFP(Val, VT, true);
451 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
452 return getConstantFP(Val, VT, true);
454 SDValue getGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
455 int64_t offset = 0, bool isTargetGA = false,
456 unsigned char TargetFlags = 0);
457 SDValue getTargetGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
459 unsigned char TargetFlags = 0) {
460 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
462 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
463 SDValue getTargetFrameIndex(int FI, EVT VT) {
464 return getFrameIndex(FI, VT, true);
466 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
467 unsigned char TargetFlags = 0);
468 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
469 return getJumpTable(JTI, VT, true, TargetFlags);
471 SDValue getConstantPool(const Constant *C, EVT VT,
472 unsigned Align = 0, int Offs = 0, bool isT=false,
473 unsigned char TargetFlags = 0);
474 SDValue getTargetConstantPool(const Constant *C, EVT VT,
475 unsigned Align = 0, int Offset = 0,
476 unsigned char TargetFlags = 0) {
477 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
479 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
480 unsigned Align = 0, int Offs = 0, bool isT=false,
481 unsigned char TargetFlags = 0);
482 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
483 EVT VT, unsigned Align = 0,
484 int Offset = 0, unsigned char TargetFlags=0) {
485 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
487 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
488 unsigned char TargetFlags = 0);
489 // When generating a branch to a BB, we don't in general know enough
490 // to provide debug info for the BB at that time, so keep this one around.
491 SDValue getBasicBlock(MachineBasicBlock *MBB);
492 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
493 SDValue getExternalSymbol(const char *Sym, EVT VT);
494 SDValue getExternalSymbol(const char *Sym, SDLoc dl, EVT VT);
495 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
496 unsigned char TargetFlags = 0);
497 SDValue getValueType(EVT);
498 SDValue getRegister(unsigned Reg, EVT VT);
499 SDValue getRegisterMask(const uint32_t *RegMask);
500 SDValue getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label);
501 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
502 int64_t Offset = 0, bool isTarget = false,
503 unsigned char TargetFlags = 0);
504 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
506 unsigned char TargetFlags = 0) {
507 return getBlockAddress(BA, VT, Offset, true, TargetFlags);
510 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N) {
511 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
512 getRegister(Reg, N.getValueType()), N);
515 // This version of the getCopyToReg method takes an extra operand, which
516 // indicates that there is potentially an incoming glue value (if Glue is not
517 // null) and that there should be a glue result.
518 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N,
520 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
521 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
522 return getNode(ISD::CopyToReg, dl, VTs,
523 ArrayRef<SDValue>(Ops, Glue.getNode() ? 4 : 3));
526 // Similar to last getCopyToReg() except parameter Reg is a SDValue
527 SDValue getCopyToReg(SDValue Chain, SDLoc dl, SDValue Reg, SDValue N,
529 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
530 SDValue Ops[] = { Chain, Reg, N, Glue };
531 return getNode(ISD::CopyToReg, dl, VTs,
532 ArrayRef<SDValue>(Ops, Glue.getNode() ? 4 : 3));
535 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT) {
536 SDVTList VTs = getVTList(VT, MVT::Other);
537 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
538 return getNode(ISD::CopyFromReg, dl, VTs, Ops);
541 // This version of the getCopyFromReg method takes an extra operand, which
542 // indicates that there is potentially an incoming glue value (if Glue is not
543 // null) and that there should be a glue result.
544 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT,
546 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
547 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
548 return getNode(ISD::CopyFromReg, dl, VTs,
549 ArrayRef<SDValue>(Ops, Glue.getNode() ? 3 : 2));
552 SDValue getCondCode(ISD::CondCode Cond);
554 /// Returns the ConvertRndSat Note: Avoid using this node because it may
555 /// disappear in the future and most targets don't support it.
556 SDValue getConvertRndSat(EVT VT, SDLoc dl, SDValue Val, SDValue DTy,
558 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
560 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
561 /// elements in VT, which must be a vector type, must match the number of
562 /// mask elements NumElts. A integer mask element equal to -1 is treated as
564 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
565 const int *MaskElts);
566 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
567 ArrayRef<int> MaskElts) {
568 assert(VT.getVectorNumElements() == MaskElts.size() &&
569 "Must have the same number of vector elements as mask elements!");
570 return getVectorShuffle(VT, dl, N1, N2, MaskElts.data());
573 /// \brief Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
574 /// the shuffle node in input but with swapped operands.
576 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
577 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
579 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
580 /// integer type VT, by either any-extending or truncating it.
581 SDValue getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
583 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
584 /// integer type VT, by either sign-extending or truncating it.
585 SDValue getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
587 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
588 /// integer type VT, by either zero-extending or truncating it.
589 SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
591 /// getZeroExtendInReg - Return the expression required to zero extend the Op
592 /// value assuming it was the smaller SrcTy value.
593 SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy);
595 /// getAnyExtendVectorInReg - Return an operation which will any-extend the
596 /// low lanes of the operand into the specified vector type. For example,
597 /// this can convert a v16i8 into a v4i32 by any-extending the low four
598 /// lanes of the operand from i8 to i32.
599 SDValue getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
601 /// getSignExtendVectorInReg - Return an operation which will sign extend the
602 /// low lanes of the operand into the specified vector type. For example,
603 /// this can convert a v16i8 into a v4i32 by sign extending the low four
604 /// lanes of the operand from i8 to i32.
605 SDValue getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
607 /// getZeroExtendVectorInReg - Return an operation which will zero extend the
608 /// low lanes of the operand into the specified vector type. For example,
609 /// this can convert a v16i8 into a v4i32 by zero extending the low four
610 /// lanes of the operand from i8 to i32.
611 SDValue getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
613 /// getBoolExtOrTrunc - Convert Op, which must be of integer type, to the
614 /// integer type VT, by using an extension appropriate for the target's
615 /// BooleanContent for type OpVT or truncating it.
616 SDValue getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT, EVT OpVT);
618 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
619 SDValue getNOT(SDLoc DL, SDValue Val, EVT VT);
621 /// \brief Create a logical NOT operation as (XOR Val, BooleanOne).
622 SDValue getLogicalNOT(SDLoc DL, SDValue Val, EVT VT);
624 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
625 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a
627 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) {
628 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
629 SDValue Ops[] = { Chain, Op };
630 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
633 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
634 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have
636 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
637 SDValue InGlue, SDLoc DL) {
638 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
639 SmallVector<SDValue, 4> Ops;
640 Ops.push_back(Chain);
643 if (InGlue.getNode())
644 Ops.push_back(InGlue);
645 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
648 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful SDLoc.
649 SDValue getUNDEF(EVT VT) {
650 return getNode(ISD::UNDEF, SDLoc(), VT);
653 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
654 /// not have a useful SDLoc.
655 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
656 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
659 /// getNode - Gets or creates the specified node.
661 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT);
662 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N);
663 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
664 bool nuw = false, bool nsw = false, bool exact = false);
665 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
667 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
668 SDValue N3, SDValue N4);
669 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
670 SDValue N3, SDValue N4, SDValue N5);
671 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, ArrayRef<SDUse> Ops);
672 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
673 ArrayRef<SDValue> Ops);
674 SDValue getNode(unsigned Opcode, SDLoc DL,
675 ArrayRef<EVT> ResultTys,
676 ArrayRef<SDValue> Ops);
677 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
678 ArrayRef<SDValue> Ops);
679 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs);
680 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N);
681 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
682 SDValue N1, SDValue N2);
683 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
684 SDValue N1, SDValue N2, SDValue N3);
685 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
686 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
687 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
688 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
691 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
692 /// the incoming stack arguments to be loaded from the stack. This is
693 /// used in tail call lowering to protect stack arguments from being
695 SDValue getStackArgumentTokenFactor(SDValue Chain);
697 SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
698 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
699 MachinePointerInfo DstPtrInfo,
700 MachinePointerInfo SrcPtrInfo);
702 SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
703 SDValue Size, unsigned Align, bool isVol,
704 MachinePointerInfo DstPtrInfo,
705 MachinePointerInfo SrcPtrInfo);
707 SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
708 SDValue Size, unsigned Align, bool isVol,
709 MachinePointerInfo DstPtrInfo);
711 /// getSetCC - Helper function to make it easier to build SetCC's if you just
712 /// have an ISD::CondCode instead of an SDValue.
714 SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS,
715 ISD::CondCode Cond) {
716 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
717 "Cannot compare scalars to vectors");
718 assert(LHS.getValueType().isVector() == VT.isVector() &&
719 "Cannot compare scalars to vectors");
720 assert(Cond != ISD::SETCC_INVALID &&
721 "Cannot create a setCC of an invalid node.");
722 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
725 // getSelect - Helper function to make it easier to build Select's if you just
726 // have operands and don't want to check for vector.
727 SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond,
728 SDValue LHS, SDValue RHS) {
729 assert(LHS.getValueType() == RHS.getValueType() &&
730 "Cannot use select on differing types");
731 assert(VT.isVector() == LHS.getValueType().isVector() &&
732 "Cannot mix vectors and scalars");
733 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
737 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
738 /// just have an ISD::CondCode instead of an SDValue.
740 SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS,
741 SDValue True, SDValue False, ISD::CondCode Cond) {
742 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
743 LHS, RHS, True, False, getCondCode(Cond));
746 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
747 /// and a source value as input.
748 SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
749 SDValue SV, unsigned Align);
751 /// getAtomicCmpSwap - Gets a node for an atomic cmpxchg op. There are two
752 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
753 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
754 /// a success flag (initially i1), and a chain.
755 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
756 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
757 MachinePointerInfo PtrInfo, unsigned Alignment,
758 AtomicOrdering SuccessOrdering,
759 AtomicOrdering FailureOrdering,
760 SynchronizationScope SynchScope);
761 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
762 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
763 MachineMemOperand *MMO,
764 AtomicOrdering SuccessOrdering,
765 AtomicOrdering FailureOrdering,
766 SynchronizationScope SynchScope);
768 /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
769 /// and chain and takes 2 operands.
770 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
771 SDValue Ptr, SDValue Val, const Value *PtrVal,
772 unsigned Alignment, AtomicOrdering Ordering,
773 SynchronizationScope SynchScope);
774 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
775 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
776 AtomicOrdering Ordering,
777 SynchronizationScope SynchScope);
779 /// getAtomic - Gets a node for an atomic op, produces result and chain and
781 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
782 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
783 AtomicOrdering Ordering,
784 SynchronizationScope SynchScope);
786 /// getAtomic - Gets a node for an atomic op, produces result and chain and
787 /// takes N operands.
788 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
789 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
790 AtomicOrdering SuccessOrdering,
791 AtomicOrdering FailureOrdering,
792 SynchronizationScope SynchScope);
793 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
794 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
795 AtomicOrdering Ordering, SynchronizationScope SynchScope);
797 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
798 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
799 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
800 /// less than FIRST_TARGET_MEMORY_OPCODE.
801 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
802 ArrayRef<SDValue> Ops,
803 EVT MemVT, MachinePointerInfo PtrInfo,
804 unsigned Align = 0, bool Vol = false,
805 bool ReadMem = true, bool WriteMem = true,
808 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
809 ArrayRef<SDValue> Ops,
810 EVT MemVT, MachineMemOperand *MMO);
812 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
813 SDValue getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl);
815 /// getLoad - Loads are not normal binary operators: their result type is not
816 /// determined by their operands, and they produce a value AND a token chain.
818 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
819 MachinePointerInfo PtrInfo, bool isVolatile,
820 bool isNonTemporal, bool isInvariant, unsigned Alignment,
821 const AAMDNodes &AAInfo = AAMDNodes(),
822 const MDNode *Ranges = nullptr);
823 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
824 MachineMemOperand *MMO);
825 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
826 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
827 EVT MemVT, bool isVolatile,
828 bool isNonTemporal, bool isInvariant, unsigned Alignment,
829 const AAMDNodes &AAInfo = AAMDNodes());
830 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
831 SDValue Chain, SDValue Ptr, EVT MemVT,
832 MachineMemOperand *MMO);
833 SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
834 SDValue Offset, ISD::MemIndexedMode AM);
835 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
837 SDValue Chain, SDValue Ptr, SDValue Offset,
838 MachinePointerInfo PtrInfo, EVT MemVT,
839 bool isVolatile, bool isNonTemporal, bool isInvariant,
840 unsigned Alignment, const AAMDNodes &AAInfo = AAMDNodes(),
841 const MDNode *Ranges = nullptr);
842 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
844 SDValue Chain, SDValue Ptr, SDValue Offset,
845 EVT MemVT, MachineMemOperand *MMO);
847 /// getStore - Helper function to build ISD::STORE nodes.
849 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
850 MachinePointerInfo PtrInfo, bool isVolatile,
851 bool isNonTemporal, unsigned Alignment,
852 const AAMDNodes &AAInfo = AAMDNodes());
853 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
854 MachineMemOperand *MMO);
855 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
856 MachinePointerInfo PtrInfo, EVT TVT,
857 bool isNonTemporal, bool isVolatile,
859 const AAMDNodes &AAInfo = AAMDNodes());
860 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
861 EVT TVT, MachineMemOperand *MMO);
862 SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base,
863 SDValue Offset, ISD::MemIndexedMode AM);
865 /// getSrcValue - Construct a node to track a Value* through the backend.
866 SDValue getSrcValue(const Value *v);
868 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
869 SDValue getMDNode(const MDNode *MD);
871 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
872 SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
873 unsigned SrcAS, unsigned DestAS);
875 /// getShiftAmountOperand - Return the specified value casted to
876 /// the target's desired shift amount type.
877 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
879 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
880 /// specified operands. If the resultant node already exists in the DAG,
881 /// this does not modify the specified node, instead it returns the node that
882 /// already exists. If the resultant node does not exist in the DAG, the
883 /// input node is returned. As a degenerate case, if you specify the same
884 /// input operands as the node already has, the input node is returned.
885 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
886 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
887 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
889 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
890 SDValue Op3, SDValue Op4);
891 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
892 SDValue Op3, SDValue Op4, SDValue Op5);
893 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
895 /// SelectNodeTo - These are used for target selectors to *mutate* the
896 /// specified node to have the specified return type, Target opcode, and
897 /// operands. Note that target opcodes are stored as
898 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
899 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
900 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
901 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
902 SDValue Op1, SDValue Op2);
903 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
904 SDValue Op1, SDValue Op2, SDValue Op3);
905 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
906 ArrayRef<SDValue> Ops);
907 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
908 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
909 EVT VT2, ArrayRef<SDValue> Ops);
910 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
911 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
912 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
913 EVT VT2, EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
914 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
915 EVT VT2, SDValue Op1);
916 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
917 EVT VT2, SDValue Op1, SDValue Op2);
918 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
919 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
920 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
921 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
922 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
923 ArrayRef<SDValue> Ops);
925 /// MorphNodeTo - This *mutates* the specified node to have the specified
926 /// return type, opcode, and operands.
927 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
928 ArrayRef<SDValue> Ops);
930 /// getMachineNode - These are used for target selectors to create a new node
931 /// with specified return type(s), MachineInstr opcode, and operands.
933 /// Note that getMachineNode returns the resultant node. If there is already
934 /// a node of the specified opcode and operands, it returns that node instead
935 /// of the current one.
936 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT);
937 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
939 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
940 SDValue Op1, SDValue Op2);
941 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
942 SDValue Op1, SDValue Op2, SDValue Op3);
943 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
944 ArrayRef<SDValue> Ops);
945 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2);
946 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
948 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
949 SDValue Op1, SDValue Op2);
950 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
951 SDValue Op1, SDValue Op2, SDValue Op3);
952 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
953 ArrayRef<SDValue> Ops);
954 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
955 EVT VT3, SDValue Op1, SDValue Op2);
956 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
957 EVT VT3, SDValue Op1, SDValue Op2,
959 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
960 EVT VT3, ArrayRef<SDValue> Ops);
961 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
962 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
963 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl,
964 ArrayRef<EVT> ResultTys,
965 ArrayRef<SDValue> Ops);
966 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs,
967 ArrayRef<SDValue> Ops);
969 /// getTargetExtractSubreg - A convenience function for creating
970 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
971 SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
974 /// getTargetInsertSubreg - A convenience function for creating
975 /// TargetInstrInfo::INSERT_SUBREG nodes.
976 SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
977 SDValue Operand, SDValue Subreg);
979 /// getNodeIfExists - Get the specified node if it's already available, or
980 /// else return NULL.
981 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops,
982 bool nuw = false, bool nsw = false,
985 /// getDbgValue - Creates a SDDbgValue node.
988 SDDbgValue *getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N, unsigned R,
989 bool IsIndirect, uint64_t Off, DebugLoc DL,
993 SDDbgValue *getConstantDbgValue(MDNode *Var, MDNode *Expr, const Value *C,
994 uint64_t Off, DebugLoc DL, unsigned O);
997 SDDbgValue *getFrameIndexDbgValue(MDNode *Var, MDNode *Expr, unsigned FI,
998 uint64_t Off, DebugLoc DL, unsigned O);
1000 /// RemoveDeadNode - Remove the specified node from the system. If any of its
1001 /// operands then becomes dead, remove them as well. Inform UpdateListener
1002 /// for each node deleted.
1003 void RemoveDeadNode(SDNode *N);
1005 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
1006 /// given list, and any nodes that become unreachable as a result.
1007 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
1009 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
1010 /// This can cause recursive merging of nodes in the DAG. Use the first
1011 /// version if 'From' is known to have a single result, use the second
1012 /// if you have two nodes with identical results (or if 'To' has a superset
1013 /// of the results of 'From'), use the third otherwise.
1015 /// These methods all take an optional UpdateListener, which (if not null) is
1016 /// informed about nodes that are deleted and modified due to recursive
1017 /// changes in the dag.
1019 /// These functions only replace all existing uses. It's possible that as
1020 /// these replacements are being performed, CSE may cause the From node
1021 /// to be given new uses. These new uses of From are left in place, and
1022 /// not automatically transferred to To.
1024 void ReplaceAllUsesWith(SDValue From, SDValue Op);
1025 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
1026 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
1028 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
1029 /// uses of other values produced by From.Val alone.
1030 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
1032 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
1033 /// for multiple values at once. This correctly handles the case where
1034 /// there is an overlap between the From values and the To values.
1035 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
1038 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
1039 /// assign a unique node id for each node in the DAG based on their
1040 /// topological order. Returns the number of nodes.
1041 unsigned AssignTopologicalOrder();
1043 /// RepositionNode - Move node N in the AllNodes list to be immediately
1044 /// before the given iterator Position. This may be used to update the
1045 /// topological ordering when the list of nodes is modified.
1046 void RepositionNode(allnodes_iterator Position, SDNode *N) {
1047 AllNodes.insert(Position, AllNodes.remove(N));
1050 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
1052 static bool isCommutativeBinOp(unsigned Opcode) {
1053 // FIXME: This should get its info from the td file, so that we can include
1060 case ISD::SMUL_LOHI:
1061 case ISD::UMUL_LOHI:
1070 case ISD::ADDE: return true;
1071 default: return false;
1075 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1076 /// a vector type, the element semantics are returned.
1077 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1078 switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1079 default: llvm_unreachable("Unknown FP format");
1080 case MVT::f16: return APFloat::IEEEhalf;
1081 case MVT::f32: return APFloat::IEEEsingle;
1082 case MVT::f64: return APFloat::IEEEdouble;
1083 case MVT::f80: return APFloat::x87DoubleExtended;
1084 case MVT::f128: return APFloat::IEEEquad;
1085 case MVT::ppcf128: return APFloat::PPCDoubleDouble;
1089 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
1090 /// value is produced by SD.
1091 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1093 /// GetDbgValues - Get the debug values which reference the given SDNode.
1094 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
1095 return DbgInfo->getSDDbgValues(SD);
1098 /// TransferDbgValues - Transfer SDDbgValues.
1099 void TransferDbgValues(SDValue From, SDValue To);
1101 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
1102 /// with this SelectionDAG.
1103 bool hasDebugValues() const { return !DbgInfo->empty(); }
1105 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
1106 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
1107 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
1108 return DbgInfo->ByvalParmDbgBegin();
1110 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
1111 return DbgInfo->ByvalParmDbgEnd();
1116 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1117 /// specified value type. If minAlign is specified, the slot size will have
1118 /// at least that alignment.
1119 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1121 /// CreateStackTemporary - Create a stack temporary suitable for holding
1122 /// either of the specified value types.
1123 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1125 /// FoldConstantArithmetic -
1126 SDValue FoldConstantArithmetic(unsigned Opcode, EVT VT,
1127 SDNode *Cst1, SDNode *Cst2);
1129 /// FoldSetCC - Constant fold a setcc to true or false.
1130 SDValue FoldSetCC(EVT VT, SDValue N1,
1131 SDValue N2, ISD::CondCode Cond, SDLoc dl);
1133 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1134 /// use this predicate to simplify operations downstream.
1135 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1137 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
1138 /// use this predicate to simplify operations downstream. Op and Mask are
1139 /// known to be the same type.
1140 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1143 /// Determine which bits of Op are known to be either zero or one and return
1144 /// them in the KnownZero/KnownOne bitsets. Targets can implement the
1145 /// computeKnownBitsForTargetNode method in the TargetLowering class to allow
1146 /// target nodes to be understood.
1147 void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1148 unsigned Depth = 0) const;
1150 /// ComputeNumSignBits - Return the number of times the sign bit of the
1151 /// register is replicated into the other bits. We know that at least 1 bit
1152 /// is always equal to the sign bit (itself), but other cases can give us
1153 /// information. For example, immediately after an "SRA X, 2", we know that
1154 /// the top 3 bits are all equal to each other, so we return 3. Targets can
1155 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1156 /// class to allow target nodes to be understood.
1157 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1159 /// isBaseWithConstantOffset - Return true if the specified operand is an
1160 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1161 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1162 /// semantics as an ADD. This handles the equivalence:
1163 /// X|Cst == X+Cst iff X&Cst = 0.
1164 bool isBaseWithConstantOffset(SDValue Op) const;
1166 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1167 bool isKnownNeverNaN(SDValue Op) const;
1169 /// isKnownNeverZero - Test whether the given SDValue is known to never be
1170 /// positive or negative Zero.
1171 bool isKnownNeverZero(SDValue Op) const;
1173 /// isEqualTo - Test whether two SDValues are known to compare equal. This
1174 /// is true if they are the same value, or if one is negative zero and the
1175 /// other positive zero.
1176 bool isEqualTo(SDValue A, SDValue B) const;
1178 /// UnrollVectorOp - Utility function used by legalize and lowering to
1179 /// "unroll" a vector operation by splitting out the scalars and operating
1180 /// on each element individually. If the ResNE is 0, fully unroll the vector
1181 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1182 /// If the ResNE is greater than the width of the vector op, unroll the
1183 /// vector op and fill the end of the resulting vector with UNDEFS.
1184 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1186 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1187 /// location that is 'Dist' units away from the location that the 'Base' load
1188 /// is loading from.
1189 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1190 unsigned Bytes, int Dist) const;
1192 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1193 /// it cannot be inferred.
1194 unsigned InferPtrAlignment(SDValue Ptr) const;
1196 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
1197 /// which is split (or expanded) into two not necessarily identical pieces.
1198 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1200 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR using the provides
1201 /// VTs and return the low/high part.
1202 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1203 const EVT &LoVT, const EVT &HiVT);
1205 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
1207 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1209 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1210 return SplitVector(N, DL, LoVT, HiVT);
1213 /// SplitVectorOperand - Split the node's operand with EXTRACT_SUBVECTOR and
1214 /// return the low/high part.
1215 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1217 return SplitVector(N->getOperand(OpNo), SDLoc(N));
1220 /// ExtractVectorElements - Append the extracted elements from Start to Count
1221 /// out of the vector Op in Args. If Count is 0, all of the elements will be
1223 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
1224 unsigned Start = 0, unsigned Count = 0);
1226 unsigned getEVTAlignment(EVT MemoryVT) const;
1229 void InsertNode(SDNode *N);
1230 bool RemoveNodeFromCSEMaps(SDNode *N);
1231 void AddModifiedNodeToCSEMaps(SDNode *N);
1232 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1233 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1235 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1237 SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
1239 void DeleteNodeNotInCSEMaps(SDNode *N);
1240 void DeallocateNode(SDNode *N);
1242 void allnodes_clear();
1244 BinarySDNode *GetBinarySDNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
1245 SDValue N1, SDValue N2, bool nuw, bool nsw,
1248 /// VTList - List of non-single value types.
1249 FoldingSet<SDVTListNode> VTListMap;
1251 /// CondCodeNodes - Maps to auto-CSE operations.
1252 std::vector<CondCodeSDNode*> CondCodeNodes;
1254 std::vector<SDNode*> ValueTypeNodes;
1255 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1256 StringMap<SDNode*> ExternalSymbols;
1258 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1261 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1262 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1263 static nodes_iterator nodes_begin(SelectionDAG *G) {
1264 return G->allnodes_begin();
1266 static nodes_iterator nodes_end(SelectionDAG *G) {
1267 return G->allnodes_end();
1271 } // end namespace llvm