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
);
131 /// \brief Invalidate all DbgValues attached to the node and remove
132 /// it from the Node-to-DbgValues map.
133 void erase(const SDNode
*Node
);
138 ByvalParmDbgValues
.clear();
142 return DbgValues
.empty() && ByvalParmDbgValues
.empty();
145 ArrayRef
<SDDbgValue
*> getSDDbgValues(const SDNode
*Node
) {
146 DbgValMapType::iterator I
= DbgValMap
.find(Node
);
147 if (I
!= DbgValMap
.end())
149 return ArrayRef
<SDDbgValue
*>();
152 typedef SmallVectorImpl
<SDDbgValue
*>::iterator DbgIterator
;
153 DbgIterator
DbgBegin() { return DbgValues
.begin(); }
154 DbgIterator
DbgEnd() { return DbgValues
.end(); }
155 DbgIterator
ByvalParmDbgBegin() { return ByvalParmDbgValues
.begin(); }
156 DbgIterator
ByvalParmDbgEnd() { return ByvalParmDbgValues
.end(); }
160 void checkForCycles(const SelectionDAG
*DAG
, bool force
= false);
162 /// SelectionDAG class - This is used to represent a portion of an LLVM function
163 /// in a low-level Data Dependence DAG representation suitable for instruction
164 /// selection. This DAG is constructed as the first step of instruction
165 /// selection in order to allow implementation of machine specific optimizations
166 /// and code simplifications.
168 /// The representation used by the SelectionDAG is a target-independent
169 /// representation, which has some similarities to the GCC RTL representation,
170 /// but is significantly more simple, powerful, and is a graph form instead of a
174 const TargetMachine
&TM
;
175 const TargetSelectionDAGInfo
*TSI
;
176 const TargetLowering
*TLI
;
178 LLVMContext
*Context
;
179 CodeGenOpt::Level OptLevel
;
181 /// EntryNode - The starting token.
184 /// Root - The root of the entire DAG.
187 /// AllNodes - A linked list of nodes in the current DAG.
188 ilist
<SDNode
> AllNodes
;
190 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
191 /// pool allocation with recycling.
192 typedef RecyclingAllocator
<BumpPtrAllocator
, SDNode
, sizeof(LargestSDNode
),
193 AlignOf
<MostAlignedSDNode
>::Alignment
>
196 /// NodeAllocator - Pool allocation for nodes.
197 NodeAllocatorType NodeAllocator
;
199 /// CSEMap - This structure is used to memoize nodes, automatically performing
200 /// CSE with existing nodes when a duplicate is requested.
201 FoldingSet
<SDNode
> CSEMap
;
203 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
204 BumpPtrAllocator OperandAllocator
;
206 /// Allocator - Pool allocation for misc. objects that are created once per
208 BumpPtrAllocator Allocator
;
210 /// DbgInfo - Tracks dbg_value information through SDISel.
214 /// DAGUpdateListener - Clients of various APIs that cause global effects on
215 /// the DAG can optionally implement this interface. This allows the clients
216 /// to handle the various sorts of updates that happen.
218 /// A DAGUpdateListener automatically registers itself with DAG when it is
219 /// constructed, and removes itself when destroyed in RAII fashion.
220 struct DAGUpdateListener
{
221 DAGUpdateListener
*const Next
;
224 explicit DAGUpdateListener(SelectionDAG
&D
)
225 : Next(D
.UpdateListeners
), DAG(D
) {
226 DAG
.UpdateListeners
= this;
229 virtual ~DAGUpdateListener() {
230 assert(DAG
.UpdateListeners
== this &&
231 "DAGUpdateListeners must be destroyed in LIFO order");
232 DAG
.UpdateListeners
= Next
;
235 /// NodeDeleted - The node N that was deleted and, if E is not null, an
236 /// equivalent node E that replaced it.
237 virtual void NodeDeleted(SDNode
*N
, SDNode
*E
);
239 /// NodeUpdated - The node N that was updated.
240 virtual void NodeUpdated(SDNode
*N
);
243 /// NewNodesMustHaveLegalTypes - When true, additional steps are taken to
244 /// ensure that getConstant() and similar functions return DAG nodes that
245 /// have legal types. This is important after type legalization since
246 /// any illegally typed nodes generated after this point will not experience
247 /// type legalization.
248 bool NewNodesMustHaveLegalTypes
;
251 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
252 friend struct DAGUpdateListener
;
254 /// UpdateListeners - Linked list of registered DAGUpdateListener instances.
255 /// This stack is maintained by DAGUpdateListener RAII.
256 DAGUpdateListener
*UpdateListeners
;
258 /// setGraphColorHelper - Implementation of setSubgraphColor.
259 /// Return whether we had to truncate the search.
261 bool setSubgraphColorHelper(SDNode
*N
, const char *Color
,
262 DenseSet
<SDNode
*> &visited
,
263 int level
, bool &printed
);
265 void operator=(const SelectionDAG
&) LLVM_DELETED_FUNCTION
;
266 SelectionDAG(const SelectionDAG
&) LLVM_DELETED_FUNCTION
;
269 explicit SelectionDAG(const TargetMachine
&TM
, llvm::CodeGenOpt::Level
);
272 /// init - Prepare this SelectionDAG to process code in the given
275 void init(MachineFunction
&mf
);
277 /// clear - Clear state and free memory necessary to make this
278 /// SelectionDAG ready to process a new block.
282 MachineFunction
&getMachineFunction() const { return *MF
; }
283 const TargetMachine
&getTarget() const { return TM
; }
284 const TargetSubtargetInfo
&getSubtarget() const { return MF
->getSubtarget(); }
285 const TargetLowering
&getTargetLoweringInfo() const { return *TLI
; }
286 const TargetSelectionDAGInfo
&getSelectionDAGInfo() const { return *TSI
; }
287 LLVMContext
*getContext() const {return Context
; }
289 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
291 void viewGraph(const std::string
&Title
);
295 std::map
<const SDNode
*, std::string
> NodeGraphAttrs
;
298 /// clearGraphAttrs - Clear all previously defined node graph attributes.
299 /// Intended to be used from a debugging tool (eg. gdb).
300 void clearGraphAttrs();
302 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
304 void setGraphAttrs(const SDNode
*N
, const char *Attrs
);
306 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
307 /// Used from getNodeAttributes.
308 const std::string
getGraphAttrs(const SDNode
*N
) const;
310 /// setGraphColor - Convenience for setting node color attribute.
312 void setGraphColor(const SDNode
*N
, const char *Color
);
314 /// setGraphColor - Convenience for setting subgraph color attribute.
316 void setSubgraphColor(SDNode
*N
, const char *Color
);
318 typedef ilist
<SDNode
>::const_iterator allnodes_const_iterator
;
319 allnodes_const_iterator
allnodes_begin() const { return AllNodes
.begin(); }
320 allnodes_const_iterator
allnodes_end() const { return AllNodes
.end(); }
321 typedef ilist
<SDNode
>::iterator allnodes_iterator
;
322 allnodes_iterator
allnodes_begin() { return AllNodes
.begin(); }
323 allnodes_iterator
allnodes_end() { return AllNodes
.end(); }
324 ilist
<SDNode
>::size_type
allnodes_size() const {
325 return AllNodes
.size();
328 /// getRoot - Return the root tag of the SelectionDAG.
330 const SDValue
&getRoot() const { return Root
; }
332 /// getEntryNode - Return the token chain corresponding to the entry of the
334 SDValue
getEntryNode() const {
335 return SDValue(const_cast<SDNode
*>(&EntryNode
), 0);
338 /// setRoot - Set the current root tag of the SelectionDAG.
340 const SDValue
&setRoot(SDValue N
) {
341 assert((!N
.getNode() || N
.getValueType() == MVT::Other
) &&
342 "DAG root value is not a chain!");
344 checkForCycles(N
.getNode(), this);
347 checkForCycles(this);
351 /// Combine - This iterates over the nodes in the SelectionDAG, folding
352 /// certain types of nodes together, or eliminating superfluous nodes. The
353 /// Level argument controls whether Combine is allowed to produce nodes and
354 /// types that are illegal on the target.
355 void Combine(CombineLevel Level
, AliasAnalysis
&AA
,
356 CodeGenOpt::Level OptLevel
);
358 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
359 /// only uses types natively supported by the target. Returns "true" if it
360 /// made any changes.
362 /// Note that this is an involved process that may invalidate pointers into
364 bool LegalizeTypes();
366 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
367 /// compatible with the target instruction selector, as indicated by the
368 /// TargetLowering object.
370 /// Note that this is an involved process that may invalidate pointers into
374 /// \brief Transforms a SelectionDAG node and any operands to it into a node
375 /// that is compatible with the target instruction selector, as indicated by
376 /// the TargetLowering object.
378 /// \returns true if \c N is a valid, legal node after calling this.
380 /// This essentially runs a single recursive walk of the \c Legalize process
381 /// over the given node (and its operands). This can be used to incrementally
382 /// legalize the DAG. All of the nodes which are directly replaced,
383 /// potentially including N, are added to the output parameter \c
384 /// UpdatedNodes so that the delta to the DAG can be understood by the
387 /// When this returns false, N has been legalized in a way that make the
388 /// pointer passed in no longer valid. It may have even been deleted from the
389 /// DAG, and so it shouldn't be used further. When this returns true, the
390 /// N passed in is a legal node, and can be immediately processed as such.
391 /// This may still have done some work on the DAG, and will still populate
392 /// UpdatedNodes with any new nodes replacing those originally in the DAG.
393 bool LegalizeOp(SDNode
*N
, SmallSetVector
<SDNode
*, 16> &UpdatedNodes
);
395 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
396 /// that only uses vector math operations supported by the target. This is
397 /// necessary as a separate step from Legalize because unrolling a vector
398 /// operation can introduce illegal types, which requires running
399 /// LegalizeTypes again.
401 /// This returns true if it made any changes; in that case, LegalizeTypes
402 /// is called again before Legalize.
404 /// Note that this is an involved process that may invalidate pointers into
406 bool LegalizeVectors();
408 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
410 void RemoveDeadNodes();
412 /// DeleteNode - Remove the specified node from the system. This node must
413 /// have no referrers.
414 void DeleteNode(SDNode
*N
);
416 /// getVTList - Return an SDVTList that represents the list of values
418 SDVTList
getVTList(EVT VT
);
419 SDVTList
getVTList(EVT VT1
, EVT VT2
);
420 SDVTList
getVTList(EVT VT1
, EVT VT2
, EVT VT3
);
421 SDVTList
getVTList(EVT VT1
, EVT VT2
, EVT VT3
, EVT VT4
);
422 SDVTList
getVTList(ArrayRef
<EVT
> VTs
);
424 //===--------------------------------------------------------------------===//
425 // Node creation methods.
427 SDValue
getConstant(uint64_t Val
, EVT VT
, bool isTarget
= false,
428 bool isOpaque
= false);
429 SDValue
getConstant(const APInt
&Val
, EVT VT
, bool isTarget
= false,
430 bool isOpaque
= false);
431 SDValue
getConstant(const ConstantInt
&Val
, EVT VT
, bool isTarget
= false,
432 bool isOpaque
= false);
433 SDValue
getIntPtrConstant(uint64_t Val
, bool isTarget
= false);
434 SDValue
getTargetConstant(uint64_t Val
, EVT VT
, bool isOpaque
= false) {
435 return getConstant(Val
, VT
, true, isOpaque
);
437 SDValue
getTargetConstant(const APInt
&Val
, EVT VT
, bool isOpaque
= false) {
438 return getConstant(Val
, VT
, true, isOpaque
);
440 SDValue
getTargetConstant(const ConstantInt
&Val
, EVT VT
,
441 bool isOpaque
= false) {
442 return getConstant(Val
, VT
, true, isOpaque
);
444 // The forms below that take a double should only be used for simple
445 // constants that can be exactly represented in VT. No checks are made.
446 SDValue
getConstantFP(double Val
, EVT VT
, bool isTarget
= false);
447 SDValue
getConstantFP(const APFloat
& Val
, EVT VT
, bool isTarget
= false);
448 SDValue
getConstantFP(const ConstantFP
&CF
, EVT VT
, bool isTarget
= false);
449 SDValue
getTargetConstantFP(double Val
, EVT VT
) {
450 return getConstantFP(Val
, VT
, true);
452 SDValue
getTargetConstantFP(const APFloat
& Val
, EVT VT
) {
453 return getConstantFP(Val
, VT
, true);
455 SDValue
getTargetConstantFP(const ConstantFP
&Val
, EVT VT
) {
456 return getConstantFP(Val
, VT
, true);
458 SDValue
getGlobalAddress(const GlobalValue
*GV
, SDLoc DL
, EVT VT
,
459 int64_t offset
= 0, bool isTargetGA
= false,
460 unsigned char TargetFlags
= 0);
461 SDValue
getTargetGlobalAddress(const GlobalValue
*GV
, SDLoc DL
, EVT VT
,
463 unsigned char TargetFlags
= 0) {
464 return getGlobalAddress(GV
, DL
, VT
, offset
, true, TargetFlags
);
466 SDValue
getFrameIndex(int FI
, EVT VT
, bool isTarget
= false);
467 SDValue
getTargetFrameIndex(int FI
, EVT VT
) {
468 return getFrameIndex(FI
, VT
, true);
470 SDValue
getJumpTable(int JTI
, EVT VT
, bool isTarget
= false,
471 unsigned char TargetFlags
= 0);
472 SDValue
getTargetJumpTable(int JTI
, EVT VT
, unsigned char TargetFlags
= 0) {
473 return getJumpTable(JTI
, VT
, true, TargetFlags
);
475 SDValue
getConstantPool(const Constant
*C
, EVT VT
,
476 unsigned Align
= 0, int Offs
= 0, bool isT
=false,
477 unsigned char TargetFlags
= 0);
478 SDValue
getTargetConstantPool(const Constant
*C
, EVT VT
,
479 unsigned Align
= 0, int Offset
= 0,
480 unsigned char TargetFlags
= 0) {
481 return getConstantPool(C
, VT
, Align
, Offset
, true, TargetFlags
);
483 SDValue
getConstantPool(MachineConstantPoolValue
*C
, EVT VT
,
484 unsigned Align
= 0, int Offs
= 0, bool isT
=false,
485 unsigned char TargetFlags
= 0);
486 SDValue
getTargetConstantPool(MachineConstantPoolValue
*C
,
487 EVT VT
, unsigned Align
= 0,
488 int Offset
= 0, unsigned char TargetFlags
=0) {
489 return getConstantPool(C
, VT
, Align
, Offset
, true, TargetFlags
);
491 SDValue
getTargetIndex(int Index
, EVT VT
, int64_t Offset
= 0,
492 unsigned char TargetFlags
= 0);
493 // When generating a branch to a BB, we don't in general know enough
494 // to provide debug info for the BB at that time, so keep this one around.
495 SDValue
getBasicBlock(MachineBasicBlock
*MBB
);
496 SDValue
getBasicBlock(MachineBasicBlock
*MBB
, SDLoc dl
);
497 SDValue
getExternalSymbol(const char *Sym
, EVT VT
);
498 SDValue
getExternalSymbol(const char *Sym
, SDLoc dl
, EVT VT
);
499 SDValue
getTargetExternalSymbol(const char *Sym
, EVT VT
,
500 unsigned char TargetFlags
= 0);
501 SDValue
getValueType(EVT
);
502 SDValue
getRegister(unsigned Reg
, EVT VT
);
503 SDValue
getRegisterMask(const uint32_t *RegMask
);
504 SDValue
getEHLabel(SDLoc dl
, SDValue Root
, MCSymbol
*Label
);
505 SDValue
getBlockAddress(const BlockAddress
*BA
, EVT VT
,
506 int64_t Offset
= 0, bool isTarget
= false,
507 unsigned char TargetFlags
= 0);
508 SDValue
getTargetBlockAddress(const BlockAddress
*BA
, EVT VT
,
510 unsigned char TargetFlags
= 0) {
511 return getBlockAddress(BA
, VT
, Offset
, true, TargetFlags
);
514 SDValue
getCopyToReg(SDValue Chain
, SDLoc dl
, unsigned Reg
, SDValue N
) {
515 return getNode(ISD::CopyToReg
, dl
, MVT::Other
, Chain
,
516 getRegister(Reg
, N
.getValueType()), N
);
519 // This version of the getCopyToReg method takes an extra operand, which
520 // indicates that there is potentially an incoming glue value (if Glue is not
521 // null) and that there should be a glue result.
522 SDValue
getCopyToReg(SDValue Chain
, SDLoc dl
, unsigned Reg
, SDValue N
,
524 SDVTList VTs
= getVTList(MVT::Other
, MVT::Glue
);
525 SDValue Ops
[] = { Chain
, getRegister(Reg
, N
.getValueType()), N
, Glue
};
526 return getNode(ISD::CopyToReg
, dl
, VTs
,
527 ArrayRef
<SDValue
>(Ops
, Glue
.getNode() ? 4 : 3));
530 // Similar to last getCopyToReg() except parameter Reg is a SDValue
531 SDValue
getCopyToReg(SDValue Chain
, SDLoc dl
, SDValue Reg
, SDValue N
,
533 SDVTList VTs
= getVTList(MVT::Other
, MVT::Glue
);
534 SDValue Ops
[] = { Chain
, Reg
, N
, Glue
};
535 return getNode(ISD::CopyToReg
, dl
, VTs
,
536 ArrayRef
<SDValue
>(Ops
, Glue
.getNode() ? 4 : 3));
539 SDValue
getCopyFromReg(SDValue Chain
, SDLoc dl
, unsigned Reg
, EVT VT
) {
540 SDVTList VTs
= getVTList(VT
, MVT::Other
);
541 SDValue Ops
[] = { Chain
, getRegister(Reg
, VT
) };
542 return getNode(ISD::CopyFromReg
, dl
, VTs
, Ops
);
545 // This version of the getCopyFromReg method takes an extra operand, which
546 // indicates that there is potentially an incoming glue value (if Glue is not
547 // null) and that there should be a glue result.
548 SDValue
getCopyFromReg(SDValue Chain
, SDLoc dl
, unsigned Reg
, EVT VT
,
550 SDVTList VTs
= getVTList(VT
, MVT::Other
, MVT::Glue
);
551 SDValue Ops
[] = { Chain
, getRegister(Reg
, VT
), Glue
};
552 return getNode(ISD::CopyFromReg
, dl
, VTs
,
553 ArrayRef
<SDValue
>(Ops
, Glue
.getNode() ? 3 : 2));
556 SDValue
getCondCode(ISD::CondCode Cond
);
558 /// Returns the ConvertRndSat Note: Avoid using this node because it may
559 /// disappear in the future and most targets don't support it.
560 SDValue
getConvertRndSat(EVT VT
, SDLoc dl
, SDValue Val
, SDValue DTy
,
562 SDValue Rnd
, SDValue Sat
, ISD::CvtCode Code
);
564 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
565 /// elements in VT, which must be a vector type, must match the number of
566 /// mask elements NumElts. A integer mask element equal to -1 is treated as
568 SDValue
getVectorShuffle(EVT VT
, SDLoc dl
, SDValue N1
, SDValue N2
,
569 const int *MaskElts
);
570 SDValue
getVectorShuffle(EVT VT
, SDLoc dl
, SDValue N1
, SDValue N2
,
571 ArrayRef
<int> MaskElts
) {
572 assert(VT
.getVectorNumElements() == MaskElts
.size() &&
573 "Must have the same number of vector elements as mask elements!");
574 return getVectorShuffle(VT
, dl
, N1
, N2
, MaskElts
.data());
577 /// \brief Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
578 /// the shuffle node in input but with swapped operands.
580 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
581 SDValue
getCommutedVectorShuffle(const ShuffleVectorSDNode
&SV
);
583 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
584 /// integer type VT, by either any-extending or truncating it.
585 SDValue
getAnyExtOrTrunc(SDValue Op
, SDLoc DL
, EVT VT
);
587 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
588 /// integer type VT, by either sign-extending or truncating it.
589 SDValue
getSExtOrTrunc(SDValue Op
, SDLoc DL
, EVT VT
);
591 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
592 /// integer type VT, by either zero-extending or truncating it.
593 SDValue
getZExtOrTrunc(SDValue Op
, SDLoc DL
, EVT VT
);
595 /// getZeroExtendInReg - Return the expression required to zero extend the Op
596 /// value assuming it was the smaller SrcTy value.
597 SDValue
getZeroExtendInReg(SDValue Op
, SDLoc DL
, EVT SrcTy
);
599 /// getAnyExtendVectorInReg - Return an operation which will any-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 any-extending the low four
602 /// lanes of the operand from i8 to i32.
603 SDValue
getAnyExtendVectorInReg(SDValue Op
, SDLoc DL
, EVT VT
);
605 /// getSignExtendVectorInReg - Return an operation which will sign 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 sign extending the low four
608 /// lanes of the operand from i8 to i32.
609 SDValue
getSignExtendVectorInReg(SDValue Op
, SDLoc DL
, EVT VT
);
611 /// getZeroExtendVectorInReg - Return an operation which will zero extend the
612 /// low lanes of the operand into the specified vector type. For example,
613 /// this can convert a v16i8 into a v4i32 by zero extending the low four
614 /// lanes of the operand from i8 to i32.
615 SDValue
getZeroExtendVectorInReg(SDValue Op
, SDLoc DL
, EVT VT
);
617 /// getBoolExtOrTrunc - Convert Op, which must be of integer type, to the
618 /// integer type VT, by using an extension appropriate for the target's
619 /// BooleanContent for type OpVT or truncating it.
620 SDValue
getBoolExtOrTrunc(SDValue Op
, SDLoc SL
, EVT VT
, EVT OpVT
);
622 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
623 SDValue
getNOT(SDLoc DL
, SDValue Val
, EVT VT
);
625 /// \brief Create a logical NOT operation as (XOR Val, BooleanOne).
626 SDValue
getLogicalNOT(SDLoc DL
, SDValue Val
, EVT VT
);
628 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
629 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a
631 SDValue
getCALLSEQ_START(SDValue Chain
, SDValue Op
, SDLoc DL
) {
632 SDVTList VTs
= getVTList(MVT::Other
, MVT::Glue
);
633 SDValue Ops
[] = { Chain
, Op
};
634 return getNode(ISD::CALLSEQ_START
, DL
, VTs
, Ops
);
637 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
638 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have
640 SDValue
getCALLSEQ_END(SDValue Chain
, SDValue Op1
, SDValue Op2
,
641 SDValue InGlue
, SDLoc DL
) {
642 SDVTList NodeTys
= getVTList(MVT::Other
, MVT::Glue
);
643 SmallVector
<SDValue
, 4> Ops
;
644 Ops
.push_back(Chain
);
647 if (InGlue
.getNode())
648 Ops
.push_back(InGlue
);
649 return getNode(ISD::CALLSEQ_END
, DL
, NodeTys
, Ops
);
652 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful SDLoc.
653 SDValue
getUNDEF(EVT VT
) {
654 return getNode(ISD::UNDEF
, SDLoc(), VT
);
657 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
658 /// not have a useful SDLoc.
659 SDValue
getGLOBAL_OFFSET_TABLE(EVT VT
) {
660 return getNode(ISD::GLOBAL_OFFSET_TABLE
, SDLoc(), VT
);
663 /// getNode - Gets or creates the specified node.
665 SDValue
getNode(unsigned Opcode
, SDLoc DL
, EVT VT
);
666 SDValue
getNode(unsigned Opcode
, SDLoc DL
, EVT VT
, SDValue N
);
667 SDValue
getNode(unsigned Opcode
, SDLoc DL
, EVT VT
, SDValue N1
, SDValue N2
,
668 bool nuw
= false, bool nsw
= false, bool exact
= false);
669 SDValue
getNode(unsigned Opcode
, SDLoc DL
, EVT VT
, SDValue N1
, SDValue N2
,
671 SDValue
getNode(unsigned Opcode
, SDLoc DL
, EVT VT
, SDValue N1
, SDValue N2
,
672 SDValue N3
, SDValue N4
);
673 SDValue
getNode(unsigned Opcode
, SDLoc DL
, EVT VT
, SDValue N1
, SDValue N2
,
674 SDValue N3
, SDValue N4
, SDValue N5
);
675 SDValue
getNode(unsigned Opcode
, SDLoc DL
, EVT VT
, ArrayRef
<SDUse
> Ops
);
676 SDValue
getNode(unsigned Opcode
, SDLoc DL
, EVT VT
,
677 ArrayRef
<SDValue
> Ops
);
678 SDValue
getNode(unsigned Opcode
, SDLoc DL
,
679 ArrayRef
<EVT
> ResultTys
,
680 ArrayRef
<SDValue
> Ops
);
681 SDValue
getNode(unsigned Opcode
, SDLoc DL
, SDVTList VTs
,
682 ArrayRef
<SDValue
> Ops
);
683 SDValue
getNode(unsigned Opcode
, SDLoc DL
, SDVTList VTs
);
684 SDValue
getNode(unsigned Opcode
, SDLoc DL
, SDVTList VTs
, SDValue N
);
685 SDValue
getNode(unsigned Opcode
, SDLoc DL
, SDVTList VTs
,
686 SDValue N1
, SDValue N2
);
687 SDValue
getNode(unsigned Opcode
, SDLoc DL
, SDVTList VTs
,
688 SDValue N1
, SDValue N2
, SDValue N3
);
689 SDValue
getNode(unsigned Opcode
, SDLoc DL
, SDVTList VTs
,
690 SDValue N1
, SDValue N2
, SDValue N3
, SDValue N4
);
691 SDValue
getNode(unsigned Opcode
, SDLoc DL
, SDVTList VTs
,
692 SDValue N1
, SDValue N2
, SDValue N3
, SDValue N4
,
695 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
696 /// the incoming stack arguments to be loaded from the stack. This is
697 /// used in tail call lowering to protect stack arguments from being
699 SDValue
getStackArgumentTokenFactor(SDValue Chain
);
701 SDValue
getMemcpy(SDValue Chain
, SDLoc dl
, SDValue Dst
, SDValue Src
,
702 SDValue Size
, unsigned Align
, bool isVol
, bool AlwaysInline
,
703 MachinePointerInfo DstPtrInfo
,
704 MachinePointerInfo SrcPtrInfo
);
706 SDValue
getMemmove(SDValue Chain
, SDLoc dl
, SDValue Dst
, SDValue Src
,
707 SDValue Size
, unsigned Align
, bool isVol
,
708 MachinePointerInfo DstPtrInfo
,
709 MachinePointerInfo SrcPtrInfo
);
711 SDValue
getMemset(SDValue Chain
, SDLoc dl
, SDValue Dst
, SDValue Src
,
712 SDValue Size
, unsigned Align
, bool isVol
,
713 MachinePointerInfo DstPtrInfo
);
715 /// getSetCC - Helper function to make it easier to build SetCC's if you just
716 /// have an ISD::CondCode instead of an SDValue.
718 SDValue
getSetCC(SDLoc DL
, EVT VT
, SDValue LHS
, SDValue RHS
,
719 ISD::CondCode Cond
) {
720 assert(LHS
.getValueType().isVector() == RHS
.getValueType().isVector() &&
721 "Cannot compare scalars to vectors");
722 assert(LHS
.getValueType().isVector() == VT
.isVector() &&
723 "Cannot compare scalars to vectors");
724 assert(Cond
!= ISD::SETCC_INVALID
&&
725 "Cannot create a setCC of an invalid node.");
726 return getNode(ISD::SETCC
, DL
, VT
, LHS
, RHS
, getCondCode(Cond
));
729 // getSelect - Helper function to make it easier to build Select's if you just
730 // have operands and don't want to check for vector.
731 SDValue
getSelect(SDLoc DL
, EVT VT
, SDValue Cond
,
732 SDValue LHS
, SDValue RHS
) {
733 assert(LHS
.getValueType() == RHS
.getValueType() &&
734 "Cannot use select on differing types");
735 assert(VT
.isVector() == LHS
.getValueType().isVector() &&
736 "Cannot mix vectors and scalars");
737 return getNode(Cond
.getValueType().isVector() ? ISD::VSELECT
: ISD::SELECT
, DL
, VT
,
741 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
742 /// just have an ISD::CondCode instead of an SDValue.
744 SDValue
getSelectCC(SDLoc DL
, SDValue LHS
, SDValue RHS
,
745 SDValue True
, SDValue False
, ISD::CondCode Cond
) {
746 return getNode(ISD::SELECT_CC
, DL
, True
.getValueType(),
747 LHS
, RHS
, True
, False
, getCondCode(Cond
));
750 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
751 /// and a source value as input.
752 SDValue
getVAArg(EVT VT
, SDLoc dl
, SDValue Chain
, SDValue Ptr
,
753 SDValue SV
, unsigned Align
);
755 /// getAtomicCmpSwap - Gets a node for an atomic cmpxchg op. There are two
756 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
757 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
758 /// a success flag (initially i1), and a chain.
759 SDValue
getAtomicCmpSwap(unsigned Opcode
, SDLoc dl
, EVT MemVT
, SDVTList VTs
,
760 SDValue Chain
, SDValue Ptr
, SDValue Cmp
, SDValue Swp
,
761 MachinePointerInfo PtrInfo
, unsigned Alignment
,
762 AtomicOrdering SuccessOrdering
,
763 AtomicOrdering FailureOrdering
,
764 SynchronizationScope SynchScope
);
765 SDValue
getAtomicCmpSwap(unsigned Opcode
, SDLoc dl
, EVT MemVT
, SDVTList VTs
,
766 SDValue Chain
, SDValue Ptr
, SDValue Cmp
, SDValue Swp
,
767 MachineMemOperand
*MMO
,
768 AtomicOrdering SuccessOrdering
,
769 AtomicOrdering FailureOrdering
,
770 SynchronizationScope SynchScope
);
772 /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
773 /// and chain and takes 2 operands.
774 SDValue
getAtomic(unsigned Opcode
, SDLoc dl
, EVT MemVT
, SDValue Chain
,
775 SDValue Ptr
, SDValue Val
, const Value
*PtrVal
,
776 unsigned Alignment
, AtomicOrdering Ordering
,
777 SynchronizationScope SynchScope
);
778 SDValue
getAtomic(unsigned Opcode
, SDLoc dl
, EVT MemVT
, SDValue Chain
,
779 SDValue Ptr
, SDValue Val
, MachineMemOperand
*MMO
,
780 AtomicOrdering Ordering
,
781 SynchronizationScope SynchScope
);
783 /// getAtomic - Gets a node for an atomic op, produces result and chain and
785 SDValue
getAtomic(unsigned Opcode
, SDLoc dl
, EVT MemVT
, EVT VT
,
786 SDValue Chain
, SDValue Ptr
, MachineMemOperand
*MMO
,
787 AtomicOrdering Ordering
,
788 SynchronizationScope SynchScope
);
790 /// getAtomic - Gets a node for an atomic op, produces result and chain and
791 /// takes N operands.
792 SDValue
getAtomic(unsigned Opcode
, SDLoc dl
, EVT MemVT
, SDVTList VTList
,
793 ArrayRef
<SDValue
> Ops
, MachineMemOperand
*MMO
,
794 AtomicOrdering SuccessOrdering
,
795 AtomicOrdering FailureOrdering
,
796 SynchronizationScope SynchScope
);
797 SDValue
getAtomic(unsigned Opcode
, SDLoc dl
, EVT MemVT
, SDVTList VTList
,
798 ArrayRef
<SDValue
> Ops
, MachineMemOperand
*MMO
,
799 AtomicOrdering Ordering
, SynchronizationScope SynchScope
);
801 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
802 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
803 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
804 /// less than FIRST_TARGET_MEMORY_OPCODE.
805 SDValue
getMemIntrinsicNode(unsigned Opcode
, SDLoc dl
, SDVTList VTList
,
806 ArrayRef
<SDValue
> Ops
,
807 EVT MemVT
, MachinePointerInfo PtrInfo
,
808 unsigned Align
= 0, bool Vol
= false,
809 bool ReadMem
= true, bool WriteMem
= true,
812 SDValue
getMemIntrinsicNode(unsigned Opcode
, SDLoc dl
, SDVTList VTList
,
813 ArrayRef
<SDValue
> Ops
,
814 EVT MemVT
, MachineMemOperand
*MMO
);
816 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
817 SDValue
getMergeValues(ArrayRef
<SDValue
> Ops
, SDLoc dl
);
819 /// getLoad - Loads are not normal binary operators: their result type is not
820 /// determined by their operands, and they produce a value AND a token chain.
822 SDValue
getLoad(EVT VT
, SDLoc dl
, SDValue Chain
, SDValue Ptr
,
823 MachinePointerInfo PtrInfo
, bool isVolatile
,
824 bool isNonTemporal
, bool isInvariant
, unsigned Alignment
,
825 const AAMDNodes
&AAInfo
= AAMDNodes(),
826 const MDNode
*Ranges
= nullptr);
827 SDValue
getLoad(EVT VT
, SDLoc dl
, SDValue Chain
, SDValue Ptr
,
828 MachineMemOperand
*MMO
);
829 SDValue
getExtLoad(ISD::LoadExtType ExtType
, SDLoc dl
, EVT VT
,
830 SDValue Chain
, SDValue Ptr
, MachinePointerInfo PtrInfo
,
831 EVT MemVT
, bool isVolatile
,
832 bool isNonTemporal
, bool isInvariant
, unsigned Alignment
,
833 const AAMDNodes
&AAInfo
= AAMDNodes());
834 SDValue
getExtLoad(ISD::LoadExtType ExtType
, SDLoc dl
, EVT VT
,
835 SDValue Chain
, SDValue Ptr
, EVT MemVT
,
836 MachineMemOperand
*MMO
);
837 SDValue
getIndexedLoad(SDValue OrigLoad
, SDLoc dl
, SDValue Base
,
838 SDValue Offset
, ISD::MemIndexedMode AM
);
839 SDValue
getLoad(ISD::MemIndexedMode AM
, ISD::LoadExtType ExtType
,
841 SDValue Chain
, SDValue Ptr
, SDValue Offset
,
842 MachinePointerInfo PtrInfo
, EVT MemVT
,
843 bool isVolatile
, bool isNonTemporal
, bool isInvariant
,
844 unsigned Alignment
, const AAMDNodes
&AAInfo
= AAMDNodes(),
845 const MDNode
*Ranges
= nullptr);
846 SDValue
getLoad(ISD::MemIndexedMode AM
, ISD::LoadExtType ExtType
,
848 SDValue Chain
, SDValue Ptr
, SDValue Offset
,
849 EVT MemVT
, MachineMemOperand
*MMO
);
851 /// getStore - Helper function to build ISD::STORE nodes.
853 SDValue
getStore(SDValue Chain
, SDLoc dl
, SDValue Val
, SDValue Ptr
,
854 MachinePointerInfo PtrInfo
, bool isVolatile
,
855 bool isNonTemporal
, unsigned Alignment
,
856 const AAMDNodes
&AAInfo
= AAMDNodes());
857 SDValue
getStore(SDValue Chain
, SDLoc dl
, SDValue Val
, SDValue Ptr
,
858 MachineMemOperand
*MMO
);
859 SDValue
getTruncStore(SDValue Chain
, SDLoc dl
, SDValue Val
, SDValue Ptr
,
860 MachinePointerInfo PtrInfo
, EVT TVT
,
861 bool isNonTemporal
, bool isVolatile
,
863 const AAMDNodes
&AAInfo
= AAMDNodes());
864 SDValue
getTruncStore(SDValue Chain
, SDLoc dl
, SDValue Val
, SDValue Ptr
,
865 EVT TVT
, MachineMemOperand
*MMO
);
866 SDValue
getIndexedStore(SDValue OrigStoe
, SDLoc dl
, SDValue Base
,
867 SDValue Offset
, ISD::MemIndexedMode AM
);
869 SDValue
getMaskedLoad(EVT VT
, SDLoc dl
, SDValue Chain
, SDValue Ptr
,
870 SDValue Mask
, SDValue Src0
, EVT MemVT
,
871 MachineMemOperand
*MMO
, ISD::LoadExtType
);
872 SDValue
getMaskedStore(SDValue Chain
, SDLoc dl
, SDValue Val
,
873 SDValue Ptr
, SDValue Mask
, EVT MemVT
,
874 MachineMemOperand
*MMO
, bool IsTrunc
);
875 /// getSrcValue - Construct a node to track a Value* through the backend.
876 SDValue
getSrcValue(const Value
*v
);
878 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
879 SDValue
getMDNode(const MDNode
*MD
);
881 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
882 SDValue
getAddrSpaceCast(SDLoc dl
, EVT VT
, SDValue Ptr
,
883 unsigned SrcAS
, unsigned DestAS
);
885 /// getShiftAmountOperand - Return the specified value casted to
886 /// the target's desired shift amount type.
887 SDValue
getShiftAmountOperand(EVT LHSTy
, SDValue Op
);
889 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
890 /// specified operands. If the resultant node already exists in the DAG,
891 /// this does not modify the specified node, instead it returns the node that
892 /// already exists. If the resultant node does not exist in the DAG, the
893 /// input node is returned. As a degenerate case, if you specify the same
894 /// input operands as the node already has, the input node is returned.
895 SDNode
*UpdateNodeOperands(SDNode
*N
, SDValue Op
);
896 SDNode
*UpdateNodeOperands(SDNode
*N
, SDValue Op1
, SDValue Op2
);
897 SDNode
*UpdateNodeOperands(SDNode
*N
, SDValue Op1
, SDValue Op2
,
899 SDNode
*UpdateNodeOperands(SDNode
*N
, SDValue Op1
, SDValue Op2
,
900 SDValue Op3
, SDValue Op4
);
901 SDNode
*UpdateNodeOperands(SDNode
*N
, SDValue Op1
, SDValue Op2
,
902 SDValue Op3
, SDValue Op4
, SDValue Op5
);
903 SDNode
*UpdateNodeOperands(SDNode
*N
, ArrayRef
<SDValue
> Ops
);
905 /// SelectNodeTo - These are used for target selectors to *mutate* the
906 /// specified node to have the specified return type, Target opcode, and
907 /// operands. Note that target opcodes are stored as
908 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
909 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT
);
910 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT
, SDValue Op1
);
911 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT
,
912 SDValue Op1
, SDValue Op2
);
913 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT
,
914 SDValue Op1
, SDValue Op2
, SDValue Op3
);
915 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT
,
916 ArrayRef
<SDValue
> Ops
);
917 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT1
, EVT VT2
);
918 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT1
,
919 EVT VT2
, ArrayRef
<SDValue
> Ops
);
920 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT1
,
921 EVT VT2
, EVT VT3
, ArrayRef
<SDValue
> Ops
);
922 SDNode
*SelectNodeTo(SDNode
*N
, unsigned MachineOpc
, EVT VT1
,
923 EVT VT2
, EVT VT3
, EVT VT4
, ArrayRef
<SDValue
> Ops
);
924 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT1
,
925 EVT VT2
, SDValue Op1
);
926 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT1
,
927 EVT VT2
, SDValue Op1
, SDValue Op2
);
928 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT1
,
929 EVT VT2
, SDValue Op1
, SDValue Op2
, SDValue Op3
);
930 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, EVT VT1
,
931 EVT VT2
, EVT VT3
, SDValue Op1
, SDValue Op2
, SDValue Op3
);
932 SDNode
*SelectNodeTo(SDNode
*N
, unsigned TargetOpc
, SDVTList VTs
,
933 ArrayRef
<SDValue
> Ops
);
935 /// MorphNodeTo - This *mutates* the specified node to have the specified
936 /// return type, opcode, and operands.
937 SDNode
*MorphNodeTo(SDNode
*N
, unsigned Opc
, SDVTList VTs
,
938 ArrayRef
<SDValue
> Ops
);
940 /// getMachineNode - These are used for target selectors to create a new node
941 /// with specified return type(s), MachineInstr opcode, and operands.
943 /// Note that getMachineNode returns the resultant node. If there is already
944 /// a node of the specified opcode and operands, it returns that node instead
945 /// of the current one.
946 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT
);
947 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT
,
949 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT
,
950 SDValue Op1
, SDValue Op2
);
951 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT
,
952 SDValue Op1
, SDValue Op2
, SDValue Op3
);
953 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT
,
954 ArrayRef
<SDValue
> Ops
);
955 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT1
, EVT VT2
);
956 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT1
, EVT VT2
,
958 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT1
, EVT VT2
,
959 SDValue Op1
, SDValue Op2
);
960 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT1
, EVT VT2
,
961 SDValue Op1
, SDValue Op2
, SDValue Op3
);
962 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT1
, EVT VT2
,
963 ArrayRef
<SDValue
> Ops
);
964 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT1
, EVT VT2
,
965 EVT VT3
, SDValue Op1
, SDValue Op2
);
966 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT1
, EVT VT2
,
967 EVT VT3
, SDValue Op1
, SDValue Op2
,
969 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT1
, EVT VT2
,
970 EVT VT3
, ArrayRef
<SDValue
> Ops
);
971 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, EVT VT1
, EVT VT2
,
972 EVT VT3
, EVT VT4
, ArrayRef
<SDValue
> Ops
);
973 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
,
974 ArrayRef
<EVT
> ResultTys
,
975 ArrayRef
<SDValue
> Ops
);
976 MachineSDNode
*getMachineNode(unsigned Opcode
, SDLoc dl
, SDVTList VTs
,
977 ArrayRef
<SDValue
> Ops
);
979 /// getTargetExtractSubreg - A convenience function for creating
980 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
981 SDValue
getTargetExtractSubreg(int SRIdx
, SDLoc DL
, EVT VT
,
984 /// getTargetInsertSubreg - A convenience function for creating
985 /// TargetInstrInfo::INSERT_SUBREG nodes.
986 SDValue
getTargetInsertSubreg(int SRIdx
, SDLoc DL
, EVT VT
,
987 SDValue Operand
, SDValue Subreg
);
989 /// getNodeIfExists - Get the specified node if it's already available, or
990 /// else return NULL.
991 SDNode
*getNodeIfExists(unsigned Opcode
, SDVTList VTs
, ArrayRef
<SDValue
> Ops
,
992 bool nuw
= false, bool nsw
= false,
995 /// getDbgValue - Creates a SDDbgValue node.
998 SDDbgValue
*getDbgValue(MDNode
*Var
, MDNode
*Expr
, SDNode
*N
, unsigned R
,
999 bool IsIndirect
, uint64_t Off
, DebugLoc DL
,
1003 SDDbgValue
*getConstantDbgValue(MDNode
*Var
, MDNode
*Expr
, const Value
*C
,
1004 uint64_t Off
, DebugLoc DL
, unsigned O
);
1007 SDDbgValue
*getFrameIndexDbgValue(MDNode
*Var
, MDNode
*Expr
, unsigned FI
,
1008 uint64_t Off
, DebugLoc DL
, unsigned O
);
1010 /// RemoveDeadNode - Remove the specified node from the system. If any of its
1011 /// operands then becomes dead, remove them as well. Inform UpdateListener
1012 /// for each node deleted.
1013 void RemoveDeadNode(SDNode
*N
);
1015 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
1016 /// given list, and any nodes that become unreachable as a result.
1017 void RemoveDeadNodes(SmallVectorImpl
<SDNode
*> &DeadNodes
);
1019 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
1020 /// This can cause recursive merging of nodes in the DAG. Use the first
1021 /// version if 'From' is known to have a single result, use the second
1022 /// if you have two nodes with identical results (or if 'To' has a superset
1023 /// of the results of 'From'), use the third otherwise.
1025 /// These methods all take an optional UpdateListener, which (if not null) is
1026 /// informed about nodes that are deleted and modified due to recursive
1027 /// changes in the dag.
1029 /// These functions only replace all existing uses. It's possible that as
1030 /// these replacements are being performed, CSE may cause the From node
1031 /// to be given new uses. These new uses of From are left in place, and
1032 /// not automatically transferred to To.
1034 void ReplaceAllUsesWith(SDValue From
, SDValue Op
);
1035 void ReplaceAllUsesWith(SDNode
*From
, SDNode
*To
);
1036 void ReplaceAllUsesWith(SDNode
*From
, const SDValue
*To
);
1038 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
1039 /// uses of other values produced by From.Val alone.
1040 void ReplaceAllUsesOfValueWith(SDValue From
, SDValue To
);
1042 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
1043 /// for multiple values at once. This correctly handles the case where
1044 /// there is an overlap between the From values and the To values.
1045 void ReplaceAllUsesOfValuesWith(const SDValue
*From
, const SDValue
*To
,
1048 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
1049 /// assign a unique node id for each node in the DAG based on their
1050 /// topological order. Returns the number of nodes.
1051 unsigned AssignTopologicalOrder();
1053 /// RepositionNode - Move node N in the AllNodes list to be immediately
1054 /// before the given iterator Position. This may be used to update the
1055 /// topological ordering when the list of nodes is modified.
1056 void RepositionNode(allnodes_iterator Position
, SDNode
*N
) {
1057 AllNodes
.insert(Position
, AllNodes
.remove(N
));
1060 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
1062 static bool isCommutativeBinOp(unsigned Opcode
) {
1063 // FIXME: This should get its info from the td file, so that we can include
1070 case ISD::SMUL_LOHI
:
1071 case ISD::UMUL_LOHI
:
1084 default: return false;
1088 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1089 /// a vector type, the element semantics are returned.
1090 static const fltSemantics
&EVTToAPFloatSemantics(EVT VT
) {
1091 switch (VT
.getScalarType().getSimpleVT().SimpleTy
) {
1092 default: llvm_unreachable("Unknown FP format");
1093 case MVT::f16
: return APFloat::IEEEhalf
;
1094 case MVT::f32
: return APFloat::IEEEsingle
;
1095 case MVT::f64
: return APFloat::IEEEdouble
;
1096 case MVT::f80
: return APFloat::x87DoubleExtended
;
1097 case MVT::f128
: return APFloat::IEEEquad
;
1098 case MVT::ppcf128
: return APFloat::PPCDoubleDouble
;
1102 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
1103 /// value is produced by SD.
1104 void AddDbgValue(SDDbgValue
*DB
, SDNode
*SD
, bool isParameter
);
1106 /// GetDbgValues - Get the debug values which reference the given SDNode.
1107 ArrayRef
<SDDbgValue
*> GetDbgValues(const SDNode
* SD
) {
1108 return DbgInfo
->getSDDbgValues(SD
);
1111 /// TransferDbgValues - Transfer SDDbgValues.
1112 void TransferDbgValues(SDValue From
, SDValue To
);
1114 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
1115 /// with this SelectionDAG.
1116 bool hasDebugValues() const { return !DbgInfo
->empty(); }
1118 SDDbgInfo::DbgIterator
DbgBegin() { return DbgInfo
->DbgBegin(); }
1119 SDDbgInfo::DbgIterator
DbgEnd() { return DbgInfo
->DbgEnd(); }
1120 SDDbgInfo::DbgIterator
ByvalParmDbgBegin() {
1121 return DbgInfo
->ByvalParmDbgBegin();
1123 SDDbgInfo::DbgIterator
ByvalParmDbgEnd() {
1124 return DbgInfo
->ByvalParmDbgEnd();
1129 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1130 /// specified value type. If minAlign is specified, the slot size will have
1131 /// at least that alignment.
1132 SDValue
CreateStackTemporary(EVT VT
, unsigned minAlign
= 1);
1134 /// CreateStackTemporary - Create a stack temporary suitable for holding
1135 /// either of the specified value types.
1136 SDValue
CreateStackTemporary(EVT VT1
, EVT VT2
);
1138 /// FoldConstantArithmetic -
1139 SDValue
FoldConstantArithmetic(unsigned Opcode
, EVT VT
,
1140 SDNode
*Cst1
, SDNode
*Cst2
);
1142 /// FoldSetCC - Constant fold a setcc to true or false.
1143 SDValue
FoldSetCC(EVT VT
, SDValue N1
,
1144 SDValue N2
, ISD::CondCode Cond
, SDLoc dl
);
1146 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1147 /// use this predicate to simplify operations downstream.
1148 bool SignBitIsZero(SDValue Op
, unsigned Depth
= 0) const;
1150 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
1151 /// use this predicate to simplify operations downstream. Op and Mask are
1152 /// known to be the same type.
1153 bool MaskedValueIsZero(SDValue Op
, const APInt
&Mask
, unsigned Depth
= 0)
1156 /// Determine which bits of Op are known to be either zero or one and return
1157 /// them in the KnownZero/KnownOne bitsets. Targets can implement the
1158 /// computeKnownBitsForTargetNode method in the TargetLowering class to allow
1159 /// target nodes to be understood.
1160 void computeKnownBits(SDValue Op
, APInt
&KnownZero
, APInt
&KnownOne
,
1161 unsigned Depth
= 0) const;
1163 /// ComputeNumSignBits - Return the number of times the sign bit of the
1164 /// register is replicated into the other bits. We know that at least 1 bit
1165 /// is always equal to the sign bit (itself), but other cases can give us
1166 /// information. For example, immediately after an "SRA X, 2", we know that
1167 /// the top 3 bits are all equal to each other, so we return 3. Targets can
1168 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1169 /// class to allow target nodes to be understood.
1170 unsigned ComputeNumSignBits(SDValue Op
, unsigned Depth
= 0) const;
1172 /// isBaseWithConstantOffset - Return true if the specified operand is an
1173 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1174 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1175 /// semantics as an ADD. This handles the equivalence:
1176 /// X|Cst == X+Cst iff X&Cst = 0.
1177 bool isBaseWithConstantOffset(SDValue Op
) const;
1179 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1180 bool isKnownNeverNaN(SDValue Op
) const;
1182 /// isKnownNeverZero - Test whether the given SDValue is known to never be
1183 /// positive or negative Zero.
1184 bool isKnownNeverZero(SDValue Op
) const;
1186 /// isEqualTo - Test whether two SDValues are known to compare equal. This
1187 /// is true if they are the same value, or if one is negative zero and the
1188 /// other positive zero.
1189 bool isEqualTo(SDValue A
, SDValue B
) const;
1191 /// UnrollVectorOp - Utility function used by legalize and lowering to
1192 /// "unroll" a vector operation by splitting out the scalars and operating
1193 /// on each element individually. If the ResNE is 0, fully unroll the vector
1194 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1195 /// If the ResNE is greater than the width of the vector op, unroll the
1196 /// vector op and fill the end of the resulting vector with UNDEFS.
1197 SDValue
UnrollVectorOp(SDNode
*N
, unsigned ResNE
= 0);
1199 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1200 /// location that is 'Dist' units away from the location that the 'Base' load
1201 /// is loading from.
1202 bool isConsecutiveLoad(LoadSDNode
*LD
, LoadSDNode
*Base
,
1203 unsigned Bytes
, int Dist
) const;
1205 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1206 /// it cannot be inferred.
1207 unsigned InferPtrAlignment(SDValue Ptr
) const;
1209 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
1210 /// which is split (or expanded) into two not necessarily identical pieces.
1211 std::pair
<EVT
, EVT
> GetSplitDestVTs(const EVT
&VT
) const;
1213 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR using the provides
1214 /// VTs and return the low/high part.
1215 std::pair
<SDValue
, SDValue
> SplitVector(const SDValue
&N
, const SDLoc
&DL
,
1216 const EVT
&LoVT
, const EVT
&HiVT
);
1218 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
1220 std::pair
<SDValue
, SDValue
> SplitVector(const SDValue
&N
, const SDLoc
&DL
) {
1222 std::tie(LoVT
, HiVT
) = GetSplitDestVTs(N
.getValueType());
1223 return SplitVector(N
, DL
, LoVT
, HiVT
);
1226 /// SplitVectorOperand - Split the node's operand with EXTRACT_SUBVECTOR and
1227 /// return the low/high part.
1228 std::pair
<SDValue
, SDValue
> SplitVectorOperand(const SDNode
*N
, unsigned OpNo
)
1230 return SplitVector(N
->getOperand(OpNo
), SDLoc(N
));
1233 /// ExtractVectorElements - Append the extracted elements from Start to Count
1234 /// out of the vector Op in Args. If Count is 0, all of the elements will be
1236 void ExtractVectorElements(SDValue Op
, SmallVectorImpl
<SDValue
> &Args
,
1237 unsigned Start
= 0, unsigned Count
= 0);
1239 unsigned getEVTAlignment(EVT MemoryVT
) const;
1242 void InsertNode(SDNode
*N
);
1243 bool RemoveNodeFromCSEMaps(SDNode
*N
);
1244 void AddModifiedNodeToCSEMaps(SDNode
*N
);
1245 SDNode
*FindModifiedNodeSlot(SDNode
*N
, SDValue Op
, void *&InsertPos
);
1246 SDNode
*FindModifiedNodeSlot(SDNode
*N
, SDValue Op1
, SDValue Op2
,
1248 SDNode
*FindModifiedNodeSlot(SDNode
*N
, ArrayRef
<SDValue
> Ops
,
1250 SDNode
*UpdadeSDLocOnMergedSDNode(SDNode
*N
, SDLoc loc
);
1252 void DeleteNodeNotInCSEMaps(SDNode
*N
);
1253 void DeallocateNode(SDNode
*N
);
1255 void allnodes_clear();
1257 BinarySDNode
*GetBinarySDNode(unsigned Opcode
, SDLoc DL
, SDVTList VTs
,
1258 SDValue N1
, SDValue N2
, bool nuw
, bool nsw
,
1261 /// VTList - List of non-single value types.
1262 FoldingSet
<SDVTListNode
> VTListMap
;
1264 /// CondCodeNodes - Maps to auto-CSE operations.
1265 std::vector
<CondCodeSDNode
*> CondCodeNodes
;
1267 std::vector
<SDNode
*> ValueTypeNodes
;
1268 std::map
<EVT
, SDNode
*, EVT::compareRawBits
> ExtendedValueTypeNodes
;
1269 StringMap
<SDNode
*> ExternalSymbols
;
1271 std::map
<std::pair
<std::string
, unsigned char>,SDNode
*> TargetExternalSymbols
;
1274 template <> struct GraphTraits
<SelectionDAG
*> : public GraphTraits
<SDNode
*> {
1275 typedef SelectionDAG::allnodes_iterator nodes_iterator
;
1276 static nodes_iterator
nodes_begin(SelectionDAG
*G
) {
1277 return G
->allnodes_begin();
1279 static nodes_iterator
nodes_end(SelectionDAG
*G
) {
1280 return G
->allnodes_end();
1284 } // end namespace llvm