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