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/SelectionDAGNodes.h"
24 #include "llvm/Support/RecyclingAllocator.h"
25 #include "llvm/Target/TargetMachine.h"
34 class MachineConstantPoolValue;
35 class MachineFunction;
39 class TargetSelectionDAGInfo;
41 class SDVTListNode : public FoldingSetNode {
42 friend struct FoldingSetTrait<SDVTListNode>;
43 /// FastID - A reference to an Interned FoldingSetNodeID for this node.
44 /// The Allocator in SelectionDAG holds the data.
45 /// SDVTList contains all types which are frequently accessed in SelectionDAG.
46 /// The size of this list is not expected big so it won't introduce memory penalty.
47 FoldingSetNodeIDRef FastID;
50 /// The hash value for SDVTList is fixed so cache it to avoid hash calculation
53 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
54 FastID(ID), VTs(VT), NumVTs(Num) {
55 HashValue = ID.ComputeHash();
57 SDVTList getSDVTList() {
58 SDVTList result = {VTs, NumVTs};
63 // Specialize FoldingSetTrait for SDVTListNode
64 // To avoid computing temp FoldingSetNodeID and hash value.
65 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
66 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
69 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
70 unsigned IDHash, FoldingSetNodeID &TempID) {
71 if (X.HashValue != IDHash)
73 return ID == X.FastID;
75 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
80 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
82 mutable ilist_half_node<SDNode> Sentinel;
84 SDNode *createSentinel() const {
85 return static_cast<SDNode*>(&Sentinel);
87 static void destroySentinel(SDNode *) {}
89 SDNode *provideInitialHead() const { return createSentinel(); }
90 SDNode *ensureHead(SDNode*) const { return createSentinel(); }
91 static void noteHead(SDNode*, SDNode*) {}
93 static void deleteNode(SDNode *) {
94 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
97 static void createNode(const SDNode &);
100 /// SDDbgInfo - Keeps track of dbg_value information through SDISel. We do
101 /// not build SDNodes for these so as not to perturb the generated code;
102 /// instead the info is kept off to the side in this structure. Each SDNode may
103 /// have one or more associated dbg_value entries. This information is kept in
105 /// Byval parameters are handled separately because they don't use alloca's,
106 /// which busts the normal mechanism. There is good reason for handling all
107 /// parameters separately: they may not have code generated for them, they
108 /// should always go at the beginning of the function regardless of other code
109 /// motion, and debug info for them is potentially useful even if the parameter
110 /// is unused. Right now only byval parameters are handled separately.
112 SmallVector<SDDbgValue*, 32> DbgValues;
113 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
114 typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType;
115 DbgValMapType DbgValMap;
117 void operator=(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
118 SDDbgInfo(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
122 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
124 ByvalParmDbgValues.push_back(V);
125 } else DbgValues.push_back(V);
127 DbgValMap[Node].push_back(V);
133 ByvalParmDbgValues.clear();
137 return DbgValues.empty() && ByvalParmDbgValues.empty();
140 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
141 DbgValMapType::iterator I = DbgValMap.find(Node);
142 if (I != DbgValMap.end())
144 return ArrayRef<SDDbgValue*>();
147 typedef SmallVectorImpl<SDDbgValue*>::iterator DbgIterator;
148 DbgIterator DbgBegin() { return DbgValues.begin(); }
149 DbgIterator DbgEnd() { return DbgValues.end(); }
150 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
151 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
155 void checkForCycles(const SelectionDAG *DAG, bool force = false);
157 /// SelectionDAG class - This is used to represent a portion of an LLVM function
158 /// in a low-level Data Dependence DAG representation suitable for instruction
159 /// selection. This DAG is constructed as the first step of instruction
160 /// selection in order to allow implementation of machine specific optimizations
161 /// and code simplifications.
163 /// The representation used by the SelectionDAG is a target-independent
164 /// representation, which has some similarities to the GCC RTL representation,
165 /// but is significantly more simple, powerful, and is a graph form instead of a
169 const TargetMachine &TM;
170 const TargetSelectionDAGInfo &TSI;
171 const TargetLowering *TLI;
173 LLVMContext *Context;
174 CodeGenOpt::Level OptLevel;
176 /// EntryNode - The starting token.
179 /// Root - The root of the entire DAG.
182 /// AllNodes - A linked list of nodes in the current DAG.
183 ilist<SDNode> AllNodes;
185 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
186 /// pool allocation with recycling.
187 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
188 AlignOf<MostAlignedSDNode>::Alignment>
191 /// NodeAllocator - Pool allocation for nodes.
192 NodeAllocatorType NodeAllocator;
194 /// CSEMap - This structure is used to memoize nodes, automatically performing
195 /// CSE with existing nodes when a duplicate is requested.
196 FoldingSet<SDNode> CSEMap;
198 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
199 BumpPtrAllocator OperandAllocator;
201 /// Allocator - Pool allocation for misc. objects that are created once per
203 BumpPtrAllocator Allocator;
205 /// DbgInfo - Tracks dbg_value information through SDISel.
209 /// DAGUpdateListener - Clients of various APIs that cause global effects on
210 /// the DAG can optionally implement this interface. This allows the clients
211 /// to handle the various sorts of updates that happen.
213 /// A DAGUpdateListener automatically registers itself with DAG when it is
214 /// constructed, and removes itself when destroyed in RAII fashion.
215 struct DAGUpdateListener {
216 DAGUpdateListener *const Next;
219 explicit DAGUpdateListener(SelectionDAG &D)
220 : Next(D.UpdateListeners), DAG(D) {
221 DAG.UpdateListeners = this;
224 virtual ~DAGUpdateListener() {
225 assert(DAG.UpdateListeners == this &&
226 "DAGUpdateListeners must be destroyed in LIFO order");
227 DAG.UpdateListeners = Next;
230 /// NodeDeleted - The node N that was deleted and, if E is not null, an
231 /// equivalent node E that replaced it.
232 virtual void NodeDeleted(SDNode *N, SDNode *E);
234 /// NodeUpdated - The node N that was updated.
235 virtual void NodeUpdated(SDNode *N);
238 /// NewNodesMustHaveLegalTypes - When true, additional steps are taken to
239 /// ensure that getConstant() and similar functions return DAG nodes that
240 /// have legal types. This is important after type legalization since
241 /// any illegally typed nodes generated after this point will not experience
242 /// type legalization.
243 bool NewNodesMustHaveLegalTypes;
246 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
247 friend struct DAGUpdateListener;
249 /// UpdateListeners - Linked list of registered DAGUpdateListener instances.
250 /// This stack is maintained by DAGUpdateListener RAII.
251 DAGUpdateListener *UpdateListeners;
253 /// setGraphColorHelper - Implementation of setSubgraphColor.
254 /// Return whether we had to truncate the search.
256 bool setSubgraphColorHelper(SDNode *N, const char *Color,
257 DenseSet<SDNode *> &visited,
258 int level, bool &printed);
260 void operator=(const SelectionDAG&) LLVM_DELETED_FUNCTION;
261 SelectionDAG(const SelectionDAG&) LLVM_DELETED_FUNCTION;
264 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
267 /// init - Prepare this SelectionDAG to process code in the given
270 void init(MachineFunction &mf, const TargetLowering *TLI);
272 /// clear - Clear state and free memory necessary to make this
273 /// SelectionDAG ready to process a new block.
277 MachineFunction &getMachineFunction() const { return *MF; }
278 const TargetMachine &getTarget() const { return TM; }
279 const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
280 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
281 LLVMContext *getContext() const {return Context; }
283 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
285 void viewGraph(const std::string &Title);
289 std::map<const SDNode *, std::string> NodeGraphAttrs;
292 /// clearGraphAttrs - Clear all previously defined node graph attributes.
293 /// Intended to be used from a debugging tool (eg. gdb).
294 void clearGraphAttrs();
296 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
298 void setGraphAttrs(const SDNode *N, const char *Attrs);
300 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
301 /// Used from getNodeAttributes.
302 const std::string getGraphAttrs(const SDNode *N) const;
304 /// setGraphColor - Convenience for setting node color attribute.
306 void setGraphColor(const SDNode *N, const char *Color);
308 /// setGraphColor - Convenience for setting subgraph color attribute.
310 void setSubgraphColor(SDNode *N, const char *Color);
312 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
313 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
314 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
315 typedef ilist<SDNode>::iterator allnodes_iterator;
316 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
317 allnodes_iterator allnodes_end() { return AllNodes.end(); }
318 ilist<SDNode>::size_type allnodes_size() const {
319 return AllNodes.size();
322 /// getRoot - Return the root tag of the SelectionDAG.
324 const SDValue &getRoot() const { return Root; }
326 /// getEntryNode - Return the token chain corresponding to the entry of the
328 SDValue getEntryNode() const {
329 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
332 /// setRoot - Set the current root tag of the SelectionDAG.
334 const SDValue &setRoot(SDValue N) {
335 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
336 "DAG root value is not a chain!");
338 checkForCycles(N.getNode(), this);
341 checkForCycles(this);
345 /// Combine - This iterates over the nodes in the SelectionDAG, folding
346 /// certain types of nodes together, or eliminating superfluous nodes. The
347 /// Level argument controls whether Combine is allowed to produce nodes and
348 /// types that are illegal on the target.
349 void Combine(CombineLevel Level, AliasAnalysis &AA,
350 CodeGenOpt::Level OptLevel);
352 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
353 /// only uses types natively supported by the target. Returns "true" if it
354 /// made any changes.
356 /// Note that this is an involved process that may invalidate pointers into
358 bool LegalizeTypes();
360 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
361 /// compatible with the target instruction selector, as indicated by the
362 /// TargetLowering object.
364 /// Note that this is an involved process that may invalidate pointers into
368 /// \brief Transforms a SelectionDAG node and any operands to it into a node
369 /// that is compatible with the target instruction selector, as indicated by
370 /// the TargetLowering object.
372 /// \returns true if \c N is a valid, legal node after calling this.
374 /// This essentially runs a single recursive walk of the \c Legalize process
375 /// over the given node (and its operands). This can be used to incrementally
376 /// legalize the DAG. All of the nodes which are directly replaced,
377 /// potentially including N, are added to the output parameter \c
378 /// UpdatedNodes so that the delta to the DAG can be understood by the
381 /// When this returns false, N has been legalized in a way that make the
382 /// pointer passed in no longer valid. It may have even been deleted from the
383 /// DAG, and so it shouldn't be used further. When this returns true, the
384 /// N passed in is a legal node, and can be immediately processed as such.
385 /// This may still have done some work on the DAG, and will still populate
386 /// UpdatedNodes with any new nodes replacing those originally in the DAG.
387 bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
389 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
390 /// that only uses vector math operations supported by the target. This is
391 /// necessary as a separate step from Legalize because unrolling a vector
392 /// operation can introduce illegal types, which requires running
393 /// LegalizeTypes again.
395 /// This returns true if it made any changes; in that case, LegalizeTypes
396 /// is called again before Legalize.
398 /// Note that this is an involved process that may invalidate pointers into
400 bool LegalizeVectors();
402 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
404 void RemoveDeadNodes();
406 /// DeleteNode - Remove the specified node from the system. This node must
407 /// have no referrers.
408 void DeleteNode(SDNode *N);
410 /// getVTList - Return an SDVTList that represents the list of values
412 SDVTList getVTList(EVT VT);
413 SDVTList getVTList(EVT VT1, EVT VT2);
414 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
415 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
416 SDVTList getVTList(ArrayRef<EVT> VTs);
418 //===--------------------------------------------------------------------===//
419 // Node creation methods.
421 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false,
422 bool isOpaque = false);
423 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false,
424 bool isOpaque = false);
425 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false,
426 bool isOpaque = false);
427 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
428 SDValue getTargetConstant(uint64_t Val, EVT VT, bool isOpaque = false) {
429 return getConstant(Val, VT, true, isOpaque);
431 SDValue getTargetConstant(const APInt &Val, EVT VT, bool isOpaque = false) {
432 return getConstant(Val, VT, true, isOpaque);
434 SDValue getTargetConstant(const ConstantInt &Val, EVT VT,
435 bool isOpaque = false) {
436 return getConstant(Val, VT, true, isOpaque);
438 // The forms below that take a double should only be used for simple
439 // constants that can be exactly represented in VT. No checks are made.
440 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
441 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
442 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
443 SDValue getTargetConstantFP(double Val, EVT VT) {
444 return getConstantFP(Val, VT, true);
446 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
447 return getConstantFP(Val, VT, true);
449 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
450 return getConstantFP(Val, VT, true);
452 SDValue getGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
453 int64_t offset = 0, bool isTargetGA = false,
454 unsigned char TargetFlags = 0);
455 SDValue getTargetGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
457 unsigned char TargetFlags = 0) {
458 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
460 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
461 SDValue getTargetFrameIndex(int FI, EVT VT) {
462 return getFrameIndex(FI, VT, true);
464 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
465 unsigned char TargetFlags = 0);
466 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
467 return getJumpTable(JTI, VT, true, TargetFlags);
469 SDValue getConstantPool(const Constant *C, EVT VT,
470 unsigned Align = 0, int Offs = 0, bool isT=false,
471 unsigned char TargetFlags = 0);
472 SDValue getTargetConstantPool(const Constant *C, EVT VT,
473 unsigned Align = 0, int Offset = 0,
474 unsigned char TargetFlags = 0) {
475 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
477 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
478 unsigned Align = 0, int Offs = 0, bool isT=false,
479 unsigned char TargetFlags = 0);
480 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
481 EVT VT, unsigned Align = 0,
482 int Offset = 0, unsigned char TargetFlags=0) {
483 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
485 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
486 unsigned char TargetFlags = 0);
487 // When generating a branch to a BB, we don't in general know enough
488 // to provide debug info for the BB at that time, so keep this one around.
489 SDValue getBasicBlock(MachineBasicBlock *MBB);
490 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
491 SDValue getExternalSymbol(const char *Sym, EVT VT);
492 SDValue getExternalSymbol(const char *Sym, SDLoc dl, EVT VT);
493 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
494 unsigned char TargetFlags = 0);
495 SDValue getValueType(EVT);
496 SDValue getRegister(unsigned Reg, EVT VT);
497 SDValue getRegisterMask(const uint32_t *RegMask);
498 SDValue getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label);
499 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
500 int64_t Offset = 0, bool isTarget = false,
501 unsigned char TargetFlags = 0);
502 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
504 unsigned char TargetFlags = 0) {
505 return getBlockAddress(BA, VT, Offset, true, TargetFlags);
508 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N) {
509 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
510 getRegister(Reg, N.getValueType()), N);
513 // This version of the getCopyToReg method takes an extra operand, which
514 // indicates that there is potentially an incoming glue value (if Glue is not
515 // null) and that there should be a glue result.
516 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N,
518 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
519 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
520 return getNode(ISD::CopyToReg, dl, VTs,
521 ArrayRef<SDValue>(Ops, Glue.getNode() ? 4 : 3));
524 // Similar to last getCopyToReg() except parameter Reg is a SDValue
525 SDValue getCopyToReg(SDValue Chain, SDLoc dl, SDValue Reg, SDValue N,
527 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
528 SDValue Ops[] = { Chain, Reg, N, Glue };
529 return getNode(ISD::CopyToReg, dl, VTs,
530 ArrayRef<SDValue>(Ops, Glue.getNode() ? 4 : 3));
533 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT) {
534 SDVTList VTs = getVTList(VT, MVT::Other);
535 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
536 return getNode(ISD::CopyFromReg, dl, VTs, Ops);
539 // This version of the getCopyFromReg method takes an extra operand, which
540 // indicates that there is potentially an incoming glue value (if Glue is not
541 // null) and that there should be a glue result.
542 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT,
544 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
545 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
546 return getNode(ISD::CopyFromReg, dl, VTs,
547 ArrayRef<SDValue>(Ops, Glue.getNode() ? 3 : 2));
550 SDValue getCondCode(ISD::CondCode Cond);
552 /// Returns the ConvertRndSat Note: Avoid using this node because it may
553 /// disappear in the future and most targets don't support it.
554 SDValue getConvertRndSat(EVT VT, SDLoc dl, SDValue Val, SDValue DTy,
556 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
558 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
559 /// elements in VT, which must be a vector type, must match the number of
560 /// mask elements NumElts. A integer mask element equal to -1 is treated as
562 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
563 const int *MaskElts);
564 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
565 ArrayRef<int> MaskElts) {
566 assert(VT.getVectorNumElements() == MaskElts.size() &&
567 "Must have the same number of vector elements as mask elements!");
568 return getVectorShuffle(VT, dl, N1, N2, MaskElts.data());
571 /// \brief Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
572 /// the shuffle node in input but with swapped operands.
574 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
575 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
577 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
578 /// integer type VT, by either any-extending or truncating it.
579 SDValue getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
581 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
582 /// integer type VT, by either sign-extending or truncating it.
583 SDValue getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
585 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
586 /// integer type VT, by either zero-extending or truncating it.
587 SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
589 /// getZeroExtendInReg - Return the expression required to zero extend the Op
590 /// value assuming it was the smaller SrcTy value.
591 SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy);
593 /// getAnyExtendVectorInReg - Return an operation which will any-extend the
594 /// low lanes of the operand into the specified vector type. For example,
595 /// this can convert a v16i8 into a v4i32 by any-extending the low four
596 /// lanes of the operand from i8 to i32.
597 SDValue getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
599 /// getSignExtendVectorInReg - Return an operation which will sign extend the
600 /// low lanes of the operand into the specified vector type. For example,
601 /// this can convert a v16i8 into a v4i32 by sign extending the low four
602 /// lanes of the operand from i8 to i32.
603 SDValue getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
605 /// getZeroExtendVectorInReg - Return an operation which will zero extend the
606 /// low lanes of the operand into the specified vector type. For example,
607 /// this can convert a v16i8 into a v4i32 by zero extending the low four
608 /// lanes of the operand from i8 to i32.
609 SDValue getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
611 /// getBoolExtOrTrunc - Convert Op, which must be of integer type, to the
612 /// integer type VT, by using an extension appropriate for the target's
613 /// BooleanContent for type OpVT or truncating it.
614 SDValue getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT, EVT OpVT);
616 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
617 SDValue getNOT(SDLoc DL, SDValue Val, EVT VT);
619 /// \brief Create a logical NOT operation as (XOR Val, BooleanOne).
620 SDValue getLogicalNOT(SDLoc DL, SDValue Val, EVT VT);
622 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
623 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a
625 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) {
626 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
627 SDValue Ops[] = { Chain, Op };
628 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
631 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
632 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have
634 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
635 SDValue InGlue, SDLoc DL) {
636 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
637 SmallVector<SDValue, 4> Ops;
638 Ops.push_back(Chain);
641 if (InGlue.getNode())
642 Ops.push_back(InGlue);
643 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
646 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful SDLoc.
647 SDValue getUNDEF(EVT VT) {
648 return getNode(ISD::UNDEF, SDLoc(), VT);
651 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
652 /// not have a useful SDLoc.
653 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
654 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
657 /// getNode - Gets or creates the specified node.
659 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT);
660 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N);
661 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
662 bool nuw = false, bool nsw = false, bool exact = false);
663 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
665 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
666 SDValue N3, SDValue N4);
667 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
668 SDValue N3, SDValue N4, SDValue N5);
669 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, ArrayRef<SDUse> Ops);
670 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
671 ArrayRef<SDValue> Ops);
672 SDValue getNode(unsigned Opcode, SDLoc DL,
673 ArrayRef<EVT> ResultTys,
674 ArrayRef<SDValue> Ops);
675 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
676 ArrayRef<SDValue> Ops);
677 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs);
678 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N);
679 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
680 SDValue N1, SDValue N2);
681 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
682 SDValue N1, SDValue N2, SDValue N3);
683 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
684 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
685 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
686 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
689 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
690 /// the incoming stack arguments to be loaded from the stack. This is
691 /// used in tail call lowering to protect stack arguments from being
693 SDValue getStackArgumentTokenFactor(SDValue Chain);
695 SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
696 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
697 MachinePointerInfo DstPtrInfo,
698 MachinePointerInfo SrcPtrInfo);
700 SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
701 SDValue Size, unsigned Align, bool isVol,
702 MachinePointerInfo DstPtrInfo,
703 MachinePointerInfo SrcPtrInfo);
705 SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
706 SDValue Size, unsigned Align, bool isVol,
707 MachinePointerInfo DstPtrInfo);
709 /// getSetCC - Helper function to make it easier to build SetCC's if you just
710 /// have an ISD::CondCode instead of an SDValue.
712 SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS,
713 ISD::CondCode Cond) {
714 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
715 "Cannot compare scalars to vectors");
716 assert(LHS.getValueType().isVector() == VT.isVector() &&
717 "Cannot compare scalars to vectors");
718 assert(Cond != ISD::SETCC_INVALID &&
719 "Cannot create a setCC of an invalid node.");
720 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
723 // getSelect - Helper function to make it easier to build Select's if you just
724 // have operands and don't want to check for vector.
725 SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond,
726 SDValue LHS, SDValue RHS) {
727 assert(LHS.getValueType() == RHS.getValueType() &&
728 "Cannot use select on differing types");
729 assert(VT.isVector() == LHS.getValueType().isVector() &&
730 "Cannot mix vectors and scalars");
731 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
735 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
736 /// just have an ISD::CondCode instead of an SDValue.
738 SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS,
739 SDValue True, SDValue False, ISD::CondCode Cond) {
740 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
741 LHS, RHS, True, False, getCondCode(Cond));
744 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
745 /// and a source value as input.
746 SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
747 SDValue SV, unsigned Align);
749 /// getAtomicCmpSwap - Gets a node for an atomic cmpxchg op. There are two
750 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces a the value loaded and a
751 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
752 /// a success flag (initially i1), and a chain.
753 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
754 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
755 MachinePointerInfo PtrInfo, unsigned Alignment,
756 AtomicOrdering SuccessOrdering,
757 AtomicOrdering FailureOrdering,
758 SynchronizationScope SynchScope);
759 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs,
760 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
761 MachineMemOperand *MMO,
762 AtomicOrdering SuccessOrdering,
763 AtomicOrdering FailureOrdering,
764 SynchronizationScope SynchScope);
766 /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
767 /// and chain and takes 2 operands.
768 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
769 SDValue Ptr, SDValue Val, const Value *PtrVal,
770 unsigned Alignment, AtomicOrdering Ordering,
771 SynchronizationScope SynchScope);
772 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
773 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
774 AtomicOrdering Ordering,
775 SynchronizationScope SynchScope);
777 /// getAtomic - Gets a node for an atomic op, produces result and chain and
779 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
780 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
781 AtomicOrdering Ordering,
782 SynchronizationScope SynchScope);
784 /// getAtomic - Gets a node for an atomic op, produces result and chain and
785 /// takes N operands.
786 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
787 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
788 AtomicOrdering SuccessOrdering,
789 AtomicOrdering FailureOrdering,
790 SynchronizationScope SynchScope);
791 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
792 ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
793 AtomicOrdering Ordering, SynchronizationScope SynchScope);
795 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
796 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
797 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
798 /// less than FIRST_TARGET_MEMORY_OPCODE.
799 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
800 ArrayRef<SDValue> Ops,
801 EVT MemVT, MachinePointerInfo PtrInfo,
802 unsigned Align = 0, bool Vol = false,
803 bool ReadMem = true, bool WriteMem = true);
805 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
806 ArrayRef<SDValue> Ops,
807 EVT MemVT, MachineMemOperand *MMO);
809 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
810 SDValue getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl);
812 /// getLoad - Loads are not normal binary operators: their result type is not
813 /// determined by their operands, and they produce a value AND a token chain.
815 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
816 MachinePointerInfo PtrInfo, bool isVolatile,
817 bool isNonTemporal, bool isInvariant, unsigned Alignment,
818 const AAMDNodes &AAInfo = AAMDNodes(),
819 const MDNode *Ranges = nullptr);
820 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
821 MachineMemOperand *MMO);
822 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
823 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
824 EVT MemVT, bool isVolatile,
825 bool isNonTemporal, bool isInvariant, unsigned Alignment,
826 const AAMDNodes &AAInfo = AAMDNodes());
827 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
828 SDValue Chain, SDValue Ptr, EVT MemVT,
829 MachineMemOperand *MMO);
830 SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
831 SDValue Offset, ISD::MemIndexedMode AM);
832 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
834 SDValue Chain, SDValue Ptr, SDValue Offset,
835 MachinePointerInfo PtrInfo, EVT MemVT,
836 bool isVolatile, bool isNonTemporal, bool isInvariant,
837 unsigned Alignment, const AAMDNodes &AAInfo = AAMDNodes(),
838 const MDNode *Ranges = nullptr);
839 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
841 SDValue Chain, SDValue Ptr, SDValue Offset,
842 EVT MemVT, MachineMemOperand *MMO);
844 /// getStore - Helper function to build ISD::STORE nodes.
846 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
847 MachinePointerInfo PtrInfo, bool isVolatile,
848 bool isNonTemporal, unsigned Alignment,
849 const AAMDNodes &AAInfo = AAMDNodes());
850 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
851 MachineMemOperand *MMO);
852 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
853 MachinePointerInfo PtrInfo, EVT TVT,
854 bool isNonTemporal, bool isVolatile,
856 const AAMDNodes &AAInfo = AAMDNodes());
857 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
858 EVT TVT, MachineMemOperand *MMO);
859 SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base,
860 SDValue Offset, ISD::MemIndexedMode AM);
862 /// getSrcValue - Construct a node to track a Value* through the backend.
863 SDValue getSrcValue(const Value *v);
865 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
866 SDValue getMDNode(const MDNode *MD);
868 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
869 SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
870 unsigned SrcAS, unsigned DestAS);
872 /// getShiftAmountOperand - Return the specified value casted to
873 /// the target's desired shift amount type.
874 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
876 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
877 /// specified operands. If the resultant node already exists in the DAG,
878 /// this does not modify the specified node, instead it returns the node that
879 /// already exists. If the resultant node does not exist in the DAG, the
880 /// input node is returned. As a degenerate case, if you specify the same
881 /// input operands as the node already has, the input node is returned.
882 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
883 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
884 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
886 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
887 SDValue Op3, SDValue Op4);
888 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
889 SDValue Op3, SDValue Op4, SDValue Op5);
890 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
892 /// SelectNodeTo - These are used for target selectors to *mutate* the
893 /// specified node to have the specified return type, Target opcode, and
894 /// operands. Note that target opcodes are stored as
895 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
896 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
897 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
898 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
899 SDValue Op1, SDValue Op2);
900 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
901 SDValue Op1, SDValue Op2, SDValue Op3);
902 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
903 ArrayRef<SDValue> Ops);
904 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
905 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
906 EVT VT2, ArrayRef<SDValue> Ops);
907 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
908 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
909 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
910 EVT VT2, EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
911 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
912 EVT VT2, SDValue Op1);
913 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
914 EVT VT2, SDValue Op1, SDValue Op2);
915 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
916 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
917 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
918 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
919 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
920 ArrayRef<SDValue> Ops);
922 /// MorphNodeTo - This *mutates* the specified node to have the specified
923 /// return type, opcode, and operands.
924 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
925 ArrayRef<SDValue> Ops);
927 /// getMachineNode - These are used for target selectors to create a new node
928 /// with specified return type(s), MachineInstr opcode, and operands.
930 /// Note that getMachineNode returns the resultant node. If there is already
931 /// a node of the specified opcode and operands, it returns that node instead
932 /// of the current one.
933 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT);
934 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
936 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
937 SDValue Op1, SDValue Op2);
938 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
939 SDValue Op1, SDValue Op2, SDValue Op3);
940 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
941 ArrayRef<SDValue> Ops);
942 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2);
943 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
945 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
946 SDValue Op1, SDValue Op2);
947 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
948 SDValue Op1, SDValue Op2, SDValue Op3);
949 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
950 ArrayRef<SDValue> Ops);
951 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
952 EVT VT3, SDValue Op1, SDValue Op2);
953 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
954 EVT VT3, SDValue Op1, SDValue Op2,
956 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
957 EVT VT3, ArrayRef<SDValue> Ops);
958 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
959 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
960 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl,
961 ArrayRef<EVT> ResultTys,
962 ArrayRef<SDValue> Ops);
963 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs,
964 ArrayRef<SDValue> Ops);
966 /// getTargetExtractSubreg - A convenience function for creating
967 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
968 SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
971 /// getTargetInsertSubreg - A convenience function for creating
972 /// TargetInstrInfo::INSERT_SUBREG nodes.
973 SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
974 SDValue Operand, SDValue Subreg);
976 /// getNodeIfExists - Get the specified node if it's already available, or
977 /// else return NULL.
978 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops,
979 bool nuw = false, bool nsw = false,
982 /// getDbgValue - Creates a SDDbgValue node.
984 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
985 bool IsIndirect, uint64_t Off,
986 DebugLoc DL, unsigned O);
988 SDDbgValue *getConstantDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
989 DebugLoc DL, unsigned O);
991 SDDbgValue *getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
992 DebugLoc DL, unsigned O);
994 /// RemoveDeadNode - Remove the specified node from the system. If any of its
995 /// operands then becomes dead, remove them as well. Inform UpdateListener
996 /// for each node deleted.
997 void RemoveDeadNode(SDNode *N);
999 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
1000 /// given list, and any nodes that become unreachable as a result.
1001 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
1003 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
1004 /// This can cause recursive merging of nodes in the DAG. Use the first
1005 /// version if 'From' is known to have a single result, use the second
1006 /// if you have two nodes with identical results (or if 'To' has a superset
1007 /// of the results of 'From'), use the third otherwise.
1009 /// These methods all take an optional UpdateListener, which (if not null) is
1010 /// informed about nodes that are deleted and modified due to recursive
1011 /// changes in the dag.
1013 /// These functions only replace all existing uses. It's possible that as
1014 /// these replacements are being performed, CSE may cause the From node
1015 /// to be given new uses. These new uses of From are left in place, and
1016 /// not automatically transferred to To.
1018 void ReplaceAllUsesWith(SDValue From, SDValue Op);
1019 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
1020 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
1022 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
1023 /// uses of other values produced by From.Val alone.
1024 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
1026 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
1027 /// for multiple values at once. This correctly handles the case where
1028 /// there is an overlap between the From values and the To values.
1029 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
1032 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
1033 /// assign a unique node id for each node in the DAG based on their
1034 /// topological order. Returns the number of nodes.
1035 unsigned AssignTopologicalOrder();
1037 /// RepositionNode - Move node N in the AllNodes list to be immediately
1038 /// before the given iterator Position. This may be used to update the
1039 /// topological ordering when the list of nodes is modified.
1040 void RepositionNode(allnodes_iterator Position, SDNode *N) {
1041 AllNodes.insert(Position, AllNodes.remove(N));
1044 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
1046 static bool isCommutativeBinOp(unsigned Opcode) {
1047 // FIXME: This should get its info from the td file, so that we can include
1054 case ISD::SMUL_LOHI:
1055 case ISD::UMUL_LOHI:
1064 case ISD::ADDE: return true;
1065 default: return false;
1069 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1070 /// a vector type, the element semantics are returned.
1071 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1072 switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1073 default: llvm_unreachable("Unknown FP format");
1074 case MVT::f16: return APFloat::IEEEhalf;
1075 case MVT::f32: return APFloat::IEEEsingle;
1076 case MVT::f64: return APFloat::IEEEdouble;
1077 case MVT::f80: return APFloat::x87DoubleExtended;
1078 case MVT::f128: return APFloat::IEEEquad;
1079 case MVT::ppcf128: return APFloat::PPCDoubleDouble;
1083 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
1084 /// value is produced by SD.
1085 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1087 /// GetDbgValues - Get the debug values which reference the given SDNode.
1088 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
1089 return DbgInfo->getSDDbgValues(SD);
1092 /// TransferDbgValues - Transfer SDDbgValues.
1093 void TransferDbgValues(SDValue From, SDValue To);
1095 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
1096 /// with this SelectionDAG.
1097 bool hasDebugValues() const { return !DbgInfo->empty(); }
1099 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
1100 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
1101 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
1102 return DbgInfo->ByvalParmDbgBegin();
1104 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
1105 return DbgInfo->ByvalParmDbgEnd();
1110 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1111 /// specified value type. If minAlign is specified, the slot size will have
1112 /// at least that alignment.
1113 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1115 /// CreateStackTemporary - Create a stack temporary suitable for holding
1116 /// either of the specified value types.
1117 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1119 /// FoldConstantArithmetic -
1120 SDValue FoldConstantArithmetic(unsigned Opcode, EVT VT,
1121 SDNode *Cst1, SDNode *Cst2);
1123 /// FoldSetCC - Constant fold a setcc to true or false.
1124 SDValue FoldSetCC(EVT VT, SDValue N1,
1125 SDValue N2, ISD::CondCode Cond, SDLoc dl);
1127 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1128 /// use this predicate to simplify operations downstream.
1129 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1131 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
1132 /// use this predicate to simplify operations downstream. Op and Mask are
1133 /// known to be the same type.
1134 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1137 /// Determine which bits of Op are known to be either zero or one and return
1138 /// them in the KnownZero/KnownOne bitsets. Targets can implement the
1139 /// computeKnownBitsForTargetNode method in the TargetLowering class to allow
1140 /// target nodes to be understood.
1141 void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1142 unsigned Depth = 0) const;
1144 /// ComputeNumSignBits - Return the number of times the sign bit of the
1145 /// register is replicated into the other bits. We know that at least 1 bit
1146 /// is always equal to the sign bit (itself), but other cases can give us
1147 /// information. For example, immediately after an "SRA X, 2", we know that
1148 /// the top 3 bits are all equal to each other, so we return 3. Targets can
1149 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1150 /// class to allow target nodes to be understood.
1151 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1153 /// isBaseWithConstantOffset - Return true if the specified operand is an
1154 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1155 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1156 /// semantics as an ADD. This handles the equivalence:
1157 /// X|Cst == X+Cst iff X&Cst = 0.
1158 bool isBaseWithConstantOffset(SDValue Op) const;
1160 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1161 bool isKnownNeverNaN(SDValue Op) const;
1163 /// isKnownNeverZero - Test whether the given SDValue is known to never be
1164 /// positive or negative Zero.
1165 bool isKnownNeverZero(SDValue Op) const;
1167 /// isEqualTo - Test whether two SDValues are known to compare equal. This
1168 /// is true if they are the same value, or if one is negative zero and the
1169 /// other positive zero.
1170 bool isEqualTo(SDValue A, SDValue B) const;
1172 /// UnrollVectorOp - Utility function used by legalize and lowering to
1173 /// "unroll" a vector operation by splitting out the scalars and operating
1174 /// on each element individually. If the ResNE is 0, fully unroll the vector
1175 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1176 /// If the ResNE is greater than the width of the vector op, unroll the
1177 /// vector op and fill the end of the resulting vector with UNDEFS.
1178 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1180 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1181 /// location that is 'Dist' units away from the location that the 'Base' load
1182 /// is loading from.
1183 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1184 unsigned Bytes, int Dist) const;
1186 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1187 /// it cannot be inferred.
1188 unsigned InferPtrAlignment(SDValue Ptr) const;
1190 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
1191 /// which is split (or expanded) into two not necessarily identical pieces.
1192 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1194 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR using the provides
1195 /// VTs and return the low/high part.
1196 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1197 const EVT &LoVT, const EVT &HiVT);
1199 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
1201 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1203 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1204 return SplitVector(N, DL, LoVT, HiVT);
1207 /// SplitVectorOperand - Split the node's operand with EXTRACT_SUBVECTOR and
1208 /// return the low/high part.
1209 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1211 return SplitVector(N->getOperand(OpNo), SDLoc(N));
1214 /// ExtractVectorElements - Append the extracted elements from Start to Count
1215 /// out of the vector Op in Args. If Count is 0, all of the elements will be
1217 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
1218 unsigned Start = 0, unsigned Count = 0);
1220 unsigned getEVTAlignment(EVT MemoryVT) const;
1223 void InsertNode(SDNode *N);
1224 bool RemoveNodeFromCSEMaps(SDNode *N);
1225 void AddModifiedNodeToCSEMaps(SDNode *N);
1226 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1227 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1229 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1231 SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
1233 void DeleteNodeNotInCSEMaps(SDNode *N);
1234 void DeallocateNode(SDNode *N);
1236 void allnodes_clear();
1238 BinarySDNode *GetBinarySDNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
1239 SDValue N1, SDValue N2, bool nuw, bool nsw,
1242 /// VTList - List of non-single value types.
1243 FoldingSet<SDVTListNode> VTListMap;
1245 /// CondCodeNodes - Maps to auto-CSE operations.
1246 std::vector<CondCodeSDNode*> CondCodeNodes;
1248 std::vector<SDNode*> ValueTypeNodes;
1249 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1250 StringMap<SDNode*> ExternalSymbols;
1252 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1255 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1256 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1257 static nodes_iterator nodes_begin(SelectionDAG *G) {
1258 return G->allnodes_begin();
1260 static nodes_iterator nodes_end(SelectionDAG *G) {
1261 return G->allnodes_end();
1265 } // end namespace llvm