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/StringMap.h"
20 #include "llvm/ADT/ilist.h"
21 #include "llvm/CodeGen/DAGCombine.h"
22 #include "llvm/CodeGen/SelectionDAGNodes.h"
23 #include "llvm/Support/RecyclingAllocator.h"
24 #include "llvm/Target/TargetMachine.h"
33 class MachineConstantPoolValue;
34 class MachineFunction;
38 class TargetSelectionDAGInfo;
39 class TargetTransformInfo;
41 class SDVTListNode : public FoldingSetNode {
42 friend struct FoldingSetTrait<SDVTListNode>;
43 /// FastID - A reference to an Interned FoldingSetNodeID for this node.
44 /// The Allocator in SelectionDAG holds the data.
45 /// SDVTList contains all types which are frequently accessed in SelectionDAG.
46 /// The size of this list is not expected big so it won't introduce memory penalty.
47 FoldingSetNodeIDRef FastID;
50 /// The hash value for SDVTList is fixed so cache it to avoid hash calculation
53 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
54 FastID(ID), VTs(VT), NumVTs(Num) {
55 HashValue = ID.ComputeHash();
57 SDVTList getSDVTList() {
58 SDVTList result = {VTs, NumVTs};
63 // Specialize FoldingSetTrait for SDVTListNode
64 // To avoid computing temp FoldingSetNodeID and hash value.
65 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
66 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
69 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
70 unsigned IDHash, FoldingSetNodeID &TempID) {
71 if (X.HashValue != IDHash)
73 return ID == X.FastID;
75 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
80 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
82 mutable ilist_half_node<SDNode> Sentinel;
84 SDNode *createSentinel() const {
85 return static_cast<SDNode*>(&Sentinel);
87 static void destroySentinel(SDNode *) {}
89 SDNode *provideInitialHead() const { return createSentinel(); }
90 SDNode *ensureHead(SDNode*) const { return createSentinel(); }
91 static void noteHead(SDNode*, SDNode*) {}
93 static void deleteNode(SDNode *) {
94 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
97 static void createNode(const SDNode &);
100 /// SDDbgInfo - Keeps track of dbg_value information through SDISel. We do
101 /// not build SDNodes for these so as not to perturb the generated code;
102 /// instead the info is kept off to the side in this structure. Each SDNode may
103 /// have one or more associated dbg_value entries. This information is kept in
105 /// Byval parameters are handled separately because they don't use alloca's,
106 /// which busts the normal mechanism. There is good reason for handling all
107 /// parameters separately: they may not have code generated for them, they
108 /// should always go at the beginning of the function regardless of other code
109 /// motion, and debug info for them is potentially useful even if the parameter
110 /// is unused. Right now only byval parameters are handled separately.
112 SmallVector<SDDbgValue*, 32> DbgValues;
113 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
114 typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType;
115 DbgValMapType DbgValMap;
117 void operator=(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
118 SDDbgInfo(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
122 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
124 ByvalParmDbgValues.push_back(V);
125 } else DbgValues.push_back(V);
127 DbgValMap[Node].push_back(V);
130 /// \brief Invalidate all DbgValues attached to the node and remove
131 /// it from the Node-to-DbgValues map.
132 void erase(const SDNode *Node);
137 ByvalParmDbgValues.clear();
141 return DbgValues.empty() && ByvalParmDbgValues.empty();
144 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
145 DbgValMapType::iterator I = DbgValMap.find(Node);
146 if (I != DbgValMap.end())
148 return ArrayRef<SDDbgValue*>();
151 typedef SmallVectorImpl<SDDbgValue*>::iterator DbgIterator;
152 DbgIterator DbgBegin() { return DbgValues.begin(); }
153 DbgIterator DbgEnd() { return DbgValues.end(); }
154 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
155 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
159 void checkForCycles(const SDNode *N);
160 void checkForCycles(const SelectionDAG *DAG);
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 TargetTransformInfo *TTI;
177 const TargetLowering *TLI;
179 LLVMContext *Context;
180 CodeGenOpt::Level OptLevel;
182 /// EntryNode - The starting token.
185 /// Root - The root of the entire DAG.
188 /// AllNodes - A linked list of nodes in the current DAG.
189 ilist<SDNode> AllNodes;
191 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
192 /// pool allocation with recycling.
193 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
194 AlignOf<MostAlignedSDNode>::Alignment>
197 /// NodeAllocator - Pool allocation for nodes.
198 NodeAllocatorType NodeAllocator;
200 /// CSEMap - This structure is used to memoize nodes, automatically performing
201 /// CSE with existing nodes when a duplicate is requested.
202 FoldingSet<SDNode> CSEMap;
204 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
205 BumpPtrAllocator OperandAllocator;
207 /// Allocator - Pool allocation for misc. objects that are created once per
209 BumpPtrAllocator Allocator;
211 /// DbgInfo - Tracks dbg_value information through SDISel.
215 /// DAGUpdateListener - Clients of various APIs that cause global effects on
216 /// the DAG can optionally implement this interface. This allows the clients
217 /// to handle the various sorts of updates that happen.
219 /// A DAGUpdateListener automatically registers itself with DAG when it is
220 /// constructed, and removes itself when destroyed in RAII fashion.
221 struct DAGUpdateListener {
222 DAGUpdateListener *const Next;
225 explicit DAGUpdateListener(SelectionDAG &D)
226 : Next(D.UpdateListeners), DAG(D) {
227 DAG.UpdateListeners = this;
230 virtual ~DAGUpdateListener() {
231 assert(DAG.UpdateListeners == this &&
232 "DAGUpdateListeners must be destroyed in LIFO order");
233 DAG.UpdateListeners = Next;
236 /// NodeDeleted - The node N that was deleted and, if E is not null, an
237 /// equivalent node E that replaced it.
238 virtual void NodeDeleted(SDNode *N, SDNode *E);
240 /// NodeUpdated - The node N that was updated.
241 virtual void NodeUpdated(SDNode *N);
244 /// NewNodesMustHaveLegalTypes - When true, additional steps are taken to
245 /// ensure that getConstant() and similar functions return DAG nodes that
246 /// have legal types. This is important after type legalization since
247 /// any illegally typed nodes generated after this point will not experience
248 /// type legalization.
249 bool NewNodesMustHaveLegalTypes;
252 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
253 friend struct DAGUpdateListener;
255 /// UpdateListeners - Linked list of registered DAGUpdateListener instances.
256 /// This stack is maintained by DAGUpdateListener RAII.
257 DAGUpdateListener *UpdateListeners;
259 /// setGraphColorHelper - Implementation of setSubgraphColor.
260 /// Return whether we had to truncate the search.
262 bool setSubgraphColorHelper(SDNode *N, const char *Color,
263 DenseSet<SDNode *> &visited,
264 int level, bool &printed);
266 void operator=(const SelectionDAG&) LLVM_DELETED_FUNCTION;
267 SelectionDAG(const SelectionDAG&) LLVM_DELETED_FUNCTION;
270 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
273 /// init - Prepare this SelectionDAG to process code in the given
276 void init(MachineFunction &mf, const TargetTransformInfo *TTI,
277 const TargetLowering *TLI);
279 /// clear - Clear state and free memory necessary to make this
280 /// SelectionDAG ready to process a new block.
284 MachineFunction &getMachineFunction() const { return *MF; }
285 const TargetMachine &getTarget() const { return TM; }
286 const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
287 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
288 const TargetTransformInfo *getTargetTransformInfo() const { return TTI; }
289 LLVMContext *getContext() const {return Context; }
291 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
293 void viewGraph(const std::string &Title);
297 std::map<const SDNode *, std::string> NodeGraphAttrs;
300 /// clearGraphAttrs - Clear all previously defined node graph attributes.
301 /// Intended to be used from a debugging tool (eg. gdb).
302 void clearGraphAttrs();
304 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
306 void setGraphAttrs(const SDNode *N, const char *Attrs);
308 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
309 /// Used from getNodeAttributes.
310 const std::string getGraphAttrs(const SDNode *N) const;
312 /// setGraphColor - Convenience for setting node color attribute.
314 void setGraphColor(const SDNode *N, const char *Color);
316 /// setGraphColor - Convenience for setting subgraph color attribute.
318 void setSubgraphColor(SDNode *N, const char *Color);
320 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
321 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
322 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
323 typedef ilist<SDNode>::iterator allnodes_iterator;
324 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
325 allnodes_iterator allnodes_end() { return AllNodes.end(); }
326 ilist<SDNode>::size_type allnodes_size() const {
327 return AllNodes.size();
330 /// getRoot - Return the root tag of the SelectionDAG.
332 const SDValue &getRoot() const { return Root; }
334 /// getEntryNode - Return the token chain corresponding to the entry of the
336 SDValue getEntryNode() const {
337 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
340 /// setRoot - Set the current root tag of the SelectionDAG.
342 const SDValue &setRoot(SDValue N) {
343 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
344 "DAG root value is not a chain!");
346 checkForCycles(N.getNode());
349 checkForCycles(this);
353 /// Combine - This iterates over the nodes in the SelectionDAG, folding
354 /// certain types of nodes together, or eliminating superfluous nodes. The
355 /// Level argument controls whether Combine is allowed to produce nodes and
356 /// types that are illegal on the target.
357 void Combine(CombineLevel Level, AliasAnalysis &AA,
358 CodeGenOpt::Level OptLevel);
360 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
361 /// only uses types natively supported by the target. Returns "true" if it
362 /// made any changes.
364 /// Note that this is an involved process that may invalidate pointers into
366 bool LegalizeTypes();
368 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
369 /// compatible with the target instruction selector, as indicated by the
370 /// TargetLowering object.
372 /// Note that this is an involved process that may invalidate pointers into
376 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
377 /// that only uses vector math operations supported by the target. This is
378 /// necessary as a separate step from Legalize because unrolling a vector
379 /// operation can introduce illegal types, which requires running
380 /// LegalizeTypes again.
382 /// This returns true if it made any changes; in that case, LegalizeTypes
383 /// is called again before Legalize.
385 /// Note that this is an involved process that may invalidate pointers into
387 bool LegalizeVectors();
389 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
391 void RemoveDeadNodes();
393 /// DeleteNode - Remove the specified node from the system. This node must
394 /// have no referrers.
395 void DeleteNode(SDNode *N);
397 /// getVTList - Return an SDVTList that represents the list of values
399 SDVTList getVTList(EVT VT);
400 SDVTList getVTList(EVT VT1, EVT VT2);
401 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
402 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
403 SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
405 //===--------------------------------------------------------------------===//
406 // Node creation methods.
408 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
409 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
410 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
411 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
412 SDValue getTargetConstant(uint64_t Val, EVT VT) {
413 return getConstant(Val, VT, true);
415 SDValue getTargetConstant(const APInt &Val, EVT VT) {
416 return getConstant(Val, VT, true);
418 SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
419 return getConstant(Val, VT, true);
421 // The forms below that take a double should only be used for simple
422 // constants that can be exactly represented in VT. No checks are made.
423 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
424 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
425 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
426 SDValue getTargetConstantFP(double Val, EVT VT) {
427 return getConstantFP(Val, VT, true);
429 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
430 return getConstantFP(Val, VT, true);
432 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
433 return getConstantFP(Val, VT, true);
435 SDValue getGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
436 int64_t offset = 0, bool isTargetGA = false,
437 unsigned char TargetFlags = 0);
438 SDValue getTargetGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
440 unsigned char TargetFlags = 0) {
441 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
443 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
444 SDValue getTargetFrameIndex(int FI, EVT VT) {
445 return getFrameIndex(FI, VT, true);
447 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
448 unsigned char TargetFlags = 0);
449 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
450 return getJumpTable(JTI, VT, true, TargetFlags);
452 SDValue getConstantPool(const Constant *C, EVT VT,
453 unsigned Align = 0, int Offs = 0, bool isT=false,
454 unsigned char TargetFlags = 0);
455 SDValue getTargetConstantPool(const Constant *C, EVT VT,
456 unsigned Align = 0, int Offset = 0,
457 unsigned char TargetFlags = 0) {
458 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
460 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
461 unsigned Align = 0, int Offs = 0, bool isT=false,
462 unsigned char TargetFlags = 0);
463 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
464 EVT VT, unsigned Align = 0,
465 int Offset = 0, unsigned char TargetFlags=0) {
466 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
468 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
469 unsigned char TargetFlags = 0);
470 // When generating a branch to a BB, we don't in general know enough
471 // to provide debug info for the BB at that time, so keep this one around.
472 SDValue getBasicBlock(MachineBasicBlock *MBB);
473 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
474 SDValue getExternalSymbol(const char *Sym, EVT VT);
475 SDValue getExternalSymbol(const char *Sym, SDLoc dl, EVT VT);
476 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
477 unsigned char TargetFlags = 0);
478 SDValue getValueType(EVT);
479 SDValue getRegister(unsigned Reg, EVT VT);
480 SDValue getRegisterMask(const uint32_t *RegMask);
481 SDValue getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label);
482 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
483 int64_t Offset = 0, bool isTarget = false,
484 unsigned char TargetFlags = 0);
485 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
487 unsigned char TargetFlags = 0) {
488 return getBlockAddress(BA, VT, Offset, true, TargetFlags);
491 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N) {
492 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
493 getRegister(Reg, N.getValueType()), N);
496 // This version of the getCopyToReg method takes an extra operand, which
497 // indicates that there is potentially an incoming glue value (if Glue is not
498 // null) and that there should be a glue result.
499 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N,
501 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
502 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
503 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
506 // Similar to last getCopyToReg() except parameter Reg is a SDValue
507 SDValue getCopyToReg(SDValue Chain, SDLoc dl, SDValue Reg, SDValue N,
509 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
510 SDValue Ops[] = { Chain, Reg, N, Glue };
511 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
514 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT) {
515 SDVTList VTs = getVTList(VT, MVT::Other);
516 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
517 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
520 // This version of the getCopyFromReg method takes an extra operand, which
521 // indicates that there is potentially an incoming glue value (if Glue is not
522 // null) and that there should be a glue result.
523 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT,
525 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
526 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
527 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Glue.getNode() ? 3 : 2);
530 SDValue getCondCode(ISD::CondCode Cond);
532 /// Returns the ConvertRndSat Note: Avoid using this node because it may
533 /// disappear in the future and most targets don't support it.
534 SDValue getConvertRndSat(EVT VT, SDLoc dl, SDValue Val, SDValue DTy,
536 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
538 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
539 /// elements in VT, which must be a vector type, must match the number of
540 /// mask elements NumElts. A integer mask element equal to -1 is treated as
542 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
543 const int *MaskElts);
545 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
546 /// integer type VT, by either any-extending or truncating it.
547 SDValue getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
549 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
550 /// integer type VT, by either sign-extending or truncating it.
551 SDValue getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
553 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
554 /// integer type VT, by either zero-extending or truncating it.
555 SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
557 /// getZeroExtendInReg - Return the expression required to zero extend the Op
558 /// value assuming it was the smaller SrcTy value.
559 SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy);
561 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
562 SDValue getNOT(SDLoc DL, SDValue Val, EVT VT);
564 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
565 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a
567 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) {
568 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
569 SDValue Ops[] = { Chain, Op };
570 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops, 2);
573 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
574 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have
576 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
577 SDValue InGlue, SDLoc DL) {
578 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
579 SmallVector<SDValue, 4> Ops;
580 Ops.push_back(Chain);
583 Ops.push_back(InGlue);
584 return getNode(ISD::CALLSEQ_END, DL, NodeTys, &Ops[0],
585 (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0));
588 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful SDLoc.
589 SDValue getUNDEF(EVT VT) {
590 return getNode(ISD::UNDEF, SDLoc(), VT);
593 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
594 /// not have a useful SDLoc.
595 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
596 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
599 /// getNode - Gets or creates the specified node.
601 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT);
602 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N);
603 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2);
604 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
605 SDValue N1, SDValue N2, SDValue N3);
606 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
607 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
608 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
609 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
611 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
612 const SDUse *Ops, unsigned NumOps);
613 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
614 const SDValue *Ops, unsigned NumOps);
615 SDValue getNode(unsigned Opcode, SDLoc DL,
616 ArrayRef<EVT> ResultTys,
617 const SDValue *Ops, unsigned NumOps);
618 SDValue getNode(unsigned Opcode, SDLoc DL, const EVT *VTs, unsigned NumVTs,
619 const SDValue *Ops, unsigned NumOps);
620 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
621 const SDValue *Ops, unsigned NumOps);
622 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs);
623 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N);
624 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
625 SDValue N1, SDValue N2);
626 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
627 SDValue N1, SDValue N2, SDValue N3);
628 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
629 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
630 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
631 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
634 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
635 /// the incoming stack arguments to be loaded from the stack. This is
636 /// used in tail call lowering to protect stack arguments from being
638 SDValue getStackArgumentTokenFactor(SDValue Chain);
640 SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
641 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
642 MachinePointerInfo DstPtrInfo,
643 MachinePointerInfo SrcPtrInfo);
645 SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
646 SDValue Size, unsigned Align, bool isVol,
647 MachinePointerInfo DstPtrInfo,
648 MachinePointerInfo SrcPtrInfo);
650 SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
651 SDValue Size, unsigned Align, bool isVol,
652 MachinePointerInfo DstPtrInfo);
654 /// getSetCC - Helper function to make it easier to build SetCC's if you just
655 /// have an ISD::CondCode instead of an SDValue.
657 SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS,
658 ISD::CondCode Cond) {
659 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
660 "Cannot compare scalars to vectors");
661 assert(LHS.getValueType().isVector() == VT.isVector() &&
662 "Cannot compare scalars to vectors");
663 assert(Cond != ISD::SETCC_INVALID &&
664 "Cannot create a setCC of an invalid node.");
665 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
668 // getSelect - Helper function to make it easier to build Select's if you just
669 // have operands and don't want to check for vector.
670 SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond,
671 SDValue LHS, SDValue RHS) {
672 assert(LHS.getValueType() == RHS.getValueType() &&
673 "Cannot use select on differing types");
674 assert(VT.isVector() == LHS.getValueType().isVector() &&
675 "Cannot mix vectors and scalars");
676 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
680 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
681 /// just have an ISD::CondCode instead of an SDValue.
683 SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS,
684 SDValue True, SDValue False, ISD::CondCode Cond) {
685 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
686 LHS, RHS, True, False, getCondCode(Cond));
689 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
690 /// and a source value as input.
691 SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
692 SDValue SV, unsigned Align);
694 /// getAtomic - Gets a node for an atomic op, produces result and chain and
696 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
697 SDValue Ptr, SDValue Cmp, SDValue Swp,
698 MachinePointerInfo PtrInfo, unsigned Alignment,
699 AtomicOrdering Ordering,
700 SynchronizationScope SynchScope);
701 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
702 SDValue Ptr, SDValue Cmp, SDValue Swp,
703 MachineMemOperand *MMO,
704 AtomicOrdering Ordering,
705 SynchronizationScope SynchScope);
707 /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
708 /// and chain and takes 2 operands.
709 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
710 SDValue Ptr, SDValue Val, const Value* PtrVal,
711 unsigned Alignment, AtomicOrdering Ordering,
712 SynchronizationScope SynchScope);
713 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
714 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
715 AtomicOrdering Ordering,
716 SynchronizationScope SynchScope);
718 /// getAtomic - Gets a node for an atomic op, produces result and chain and
720 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
721 SDValue Chain, SDValue Ptr, const Value* PtrVal,
723 AtomicOrdering Ordering,
724 SynchronizationScope SynchScope);
725 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
726 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
727 AtomicOrdering Ordering,
728 SynchronizationScope SynchScope);
730 /// getAtomic - Gets a node for an atomic op, produces result and chain and
731 /// takes N operands.
732 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
733 SDValue* Ops, unsigned NumOps, MachineMemOperand *MMO,
734 AtomicOrdering Ordering,
735 SynchronizationScope SynchScope);
737 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
738 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
739 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
740 /// less than FIRST_TARGET_MEMORY_OPCODE.
741 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
742 const EVT *VTs, unsigned NumVTs,
743 const SDValue *Ops, unsigned NumOps,
744 EVT MemVT, MachinePointerInfo PtrInfo,
745 unsigned Align = 0, bool Vol = false,
746 bool ReadMem = true, bool WriteMem = true);
748 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
749 const SDValue *Ops, unsigned NumOps,
750 EVT MemVT, MachinePointerInfo PtrInfo,
751 unsigned Align = 0, bool Vol = false,
752 bool ReadMem = true, bool WriteMem = true);
754 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
755 const SDValue *Ops, unsigned NumOps,
756 EVT MemVT, MachineMemOperand *MMO);
758 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
759 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, SDLoc dl);
761 /// getLoad - Loads are not normal binary operators: their result type is not
762 /// determined by their operands, and they produce a value AND a token chain.
764 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
765 MachinePointerInfo PtrInfo, bool isVolatile,
766 bool isNonTemporal, bool isInvariant, unsigned Alignment,
767 const MDNode *TBAAInfo = 0, const MDNode *Ranges = 0);
768 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
769 MachineMemOperand *MMO);
770 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
771 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
772 EVT MemVT, bool isVolatile,
773 bool isNonTemporal, unsigned Alignment,
774 const MDNode *TBAAInfo = 0);
775 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
776 SDValue Chain, SDValue Ptr, EVT MemVT,
777 MachineMemOperand *MMO);
778 SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
779 SDValue Offset, ISD::MemIndexedMode AM);
780 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
782 SDValue Chain, SDValue Ptr, SDValue Offset,
783 MachinePointerInfo PtrInfo, EVT MemVT,
784 bool isVolatile, bool isNonTemporal, bool isInvariant,
785 unsigned Alignment, const MDNode *TBAAInfo = 0,
786 const MDNode *Ranges = 0);
787 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
789 SDValue Chain, SDValue Ptr, SDValue Offset,
790 EVT MemVT, MachineMemOperand *MMO);
792 /// getStore - Helper function to build ISD::STORE nodes.
794 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
795 MachinePointerInfo PtrInfo, bool isVolatile,
796 bool isNonTemporal, unsigned Alignment,
797 const MDNode *TBAAInfo = 0);
798 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
799 MachineMemOperand *MMO);
800 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
801 MachinePointerInfo PtrInfo, EVT TVT,
802 bool isNonTemporal, bool isVolatile,
804 const MDNode *TBAAInfo = 0);
805 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
806 EVT TVT, MachineMemOperand *MMO);
807 SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base,
808 SDValue Offset, ISD::MemIndexedMode AM);
810 /// getSrcValue - Construct a node to track a Value* through the backend.
811 SDValue getSrcValue(const Value *v);
813 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
814 SDValue getMDNode(const MDNode *MD);
816 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
817 SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
818 unsigned SrcAS, unsigned DestAS);
820 /// getShiftAmountOperand - Return the specified value casted to
821 /// the target's desired shift amount type.
822 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
824 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
825 /// specified operands. If the resultant node already exists in the DAG,
826 /// this does not modify the specified node, instead it returns the node that
827 /// already exists. If the resultant node does not exist in the DAG, the
828 /// input node is returned. As a degenerate case, if you specify the same
829 /// input operands as the node already has, the input node is returned.
830 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
831 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
832 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
834 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
835 SDValue Op3, SDValue Op4);
836 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
837 SDValue Op3, SDValue Op4, SDValue Op5);
838 SDNode *UpdateNodeOperands(SDNode *N,
839 const SDValue *Ops, unsigned NumOps);
841 /// SelectNodeTo - These are used for target selectors to *mutate* the
842 /// specified node to have the specified return type, Target opcode, and
843 /// operands. Note that target opcodes are stored as
844 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
845 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
846 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
847 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
848 SDValue Op1, SDValue Op2);
849 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
850 SDValue Op1, SDValue Op2, SDValue Op3);
851 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
852 const SDValue *Ops, unsigned NumOps);
853 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
854 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
855 EVT VT2, const SDValue *Ops, unsigned NumOps);
856 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
857 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
858 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
859 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
861 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
862 EVT VT2, SDValue Op1);
863 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
864 EVT VT2, SDValue Op1, SDValue Op2);
865 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
866 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
867 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
868 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
869 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
870 const SDValue *Ops, unsigned NumOps);
872 /// MorphNodeTo - This *mutates* the specified node to have the specified
873 /// return type, opcode, and operands.
874 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
875 const SDValue *Ops, unsigned NumOps);
877 /// getMachineNode - These are used for target selectors to create a new node
878 /// with specified return type(s), MachineInstr opcode, and operands.
880 /// Note that getMachineNode returns the resultant node. If there is already
881 /// a node of the specified opcode and operands, it returns that node instead
882 /// of the current one.
883 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT);
884 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
886 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
887 SDValue Op1, SDValue Op2);
888 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
889 SDValue Op1, SDValue Op2, SDValue Op3);
890 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
891 ArrayRef<SDValue> Ops);
892 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2);
893 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
895 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
896 SDValue Op1, SDValue Op2);
897 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
898 SDValue Op1, SDValue Op2, SDValue Op3);
899 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
900 ArrayRef<SDValue> Ops);
901 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
902 EVT VT3, SDValue Op1, SDValue Op2);
903 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
904 EVT VT3, SDValue Op1, SDValue Op2,
906 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
907 EVT VT3, ArrayRef<SDValue> Ops);
908 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
909 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
910 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl,
911 ArrayRef<EVT> ResultTys,
912 ArrayRef<SDValue> Ops);
913 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs,
914 ArrayRef<SDValue> Ops);
916 /// getTargetExtractSubreg - A convenience function for creating
917 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
918 SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
921 /// getTargetInsertSubreg - A convenience function for creating
922 /// TargetInstrInfo::INSERT_SUBREG nodes.
923 SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
924 SDValue Operand, SDValue Subreg);
926 /// getNodeIfExists - Get the specified node if it's already available, or
927 /// else return NULL.
928 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
929 const SDValue *Ops, unsigned NumOps);
931 /// getDbgValue - Creates a SDDbgValue node.
933 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
934 DebugLoc DL, unsigned O);
935 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
936 DebugLoc DL, unsigned O);
937 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
938 DebugLoc DL, unsigned O);
940 /// RemoveDeadNode - Remove the specified node from the system. If any of its
941 /// operands then becomes dead, remove them as well. Inform UpdateListener
942 /// for each node deleted.
943 void RemoveDeadNode(SDNode *N);
945 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
946 /// given list, and any nodes that become unreachable as a result.
947 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
949 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
950 /// This can cause recursive merging of nodes in the DAG. Use the first
951 /// version if 'From' is known to have a single result, use the second
952 /// if you have two nodes with identical results (or if 'To' has a superset
953 /// of the results of 'From'), use the third otherwise.
955 /// These methods all take an optional UpdateListener, which (if not null) is
956 /// informed about nodes that are deleted and modified due to recursive
957 /// changes in the dag.
959 /// These functions only replace all existing uses. It's possible that as
960 /// these replacements are being performed, CSE may cause the From node
961 /// to be given new uses. These new uses of From are left in place, and
962 /// not automatically transferred to To.
964 void ReplaceAllUsesWith(SDValue From, SDValue Op);
965 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
966 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
968 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
969 /// uses of other values produced by From.Val alone.
970 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
972 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
973 /// for multiple values at once. This correctly handles the case where
974 /// there is an overlap between the From values and the To values.
975 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
978 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
979 /// assign a unique node id for each node in the DAG based on their
980 /// topological order. Returns the number of nodes.
981 unsigned AssignTopologicalOrder();
983 /// RepositionNode - Move node N in the AllNodes list to be immediately
984 /// before the given iterator Position. This may be used to update the
985 /// topological ordering when the list of nodes is modified.
986 void RepositionNode(allnodes_iterator Position, SDNode *N) {
987 AllNodes.insert(Position, AllNodes.remove(N));
990 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
992 static bool isCommutativeBinOp(unsigned Opcode) {
993 // FIXME: This should get its info from the td file, so that we can include
1000 case ISD::SMUL_LOHI:
1001 case ISD::UMUL_LOHI:
1010 case ISD::ADDE: return true;
1011 default: return false;
1015 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1016 /// a vector type, the element semantics are returned.
1017 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1018 switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1019 default: llvm_unreachable("Unknown FP format");
1020 case MVT::f16: return APFloat::IEEEhalf;
1021 case MVT::f32: return APFloat::IEEEsingle;
1022 case MVT::f64: return APFloat::IEEEdouble;
1023 case MVT::f80: return APFloat::x87DoubleExtended;
1024 case MVT::f128: return APFloat::IEEEquad;
1025 case MVT::ppcf128: return APFloat::PPCDoubleDouble;
1029 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
1030 /// value is produced by SD.
1031 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1033 /// GetDbgValues - Get the debug values which reference the given SDNode.
1034 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
1035 return DbgInfo->getSDDbgValues(SD);
1038 /// TransferDbgValues - Transfer SDDbgValues.
1039 void TransferDbgValues(SDValue From, SDValue To);
1041 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
1042 /// with this SelectionDAG.
1043 bool hasDebugValues() const { return !DbgInfo->empty(); }
1045 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
1046 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
1047 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
1048 return DbgInfo->ByvalParmDbgBegin();
1050 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
1051 return DbgInfo->ByvalParmDbgEnd();
1056 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1057 /// specified value type. If minAlign is specified, the slot size will have
1058 /// at least that alignment.
1059 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1061 /// CreateStackTemporary - Create a stack temporary suitable for holding
1062 /// either of the specified value types.
1063 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1065 /// FoldConstantArithmetic -
1066 SDValue FoldConstantArithmetic(unsigned Opcode, EVT VT,
1067 SDNode *Cst1, SDNode *Cst2);
1069 /// FoldSetCC - Constant fold a setcc to true or false.
1070 SDValue FoldSetCC(EVT VT, SDValue N1,
1071 SDValue N2, ISD::CondCode Cond, SDLoc dl);
1073 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1074 /// use this predicate to simplify operations downstream.
1075 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1077 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
1078 /// use this predicate to simplify operations downstream. Op and Mask are
1079 /// known to be the same type.
1080 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1083 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1084 /// known to be either zero or one and return them in the KnownZero/KnownOne
1085 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1086 /// processing. Targets can implement the computeMaskedBitsForTargetNode
1087 /// method in the TargetLowering class to allow target nodes to be understood.
1088 void ComputeMaskedBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1089 unsigned Depth = 0) const;
1091 /// ComputeNumSignBits - Return the number of times the sign bit of the
1092 /// register is replicated into the other bits. We know that at least 1 bit
1093 /// is always equal to the sign bit (itself), but other cases can give us
1094 /// information. For example, immediately after an "SRA X, 2", we know that
1095 /// the top 3 bits are all equal to each other, so we return 3. Targets can
1096 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1097 /// class to allow target nodes to be understood.
1098 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1100 /// isBaseWithConstantOffset - Return true if the specified operand is an
1101 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1102 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1103 /// semantics as an ADD. This handles the equivalence:
1104 /// X|Cst == X+Cst iff X&Cst = 0.
1105 bool isBaseWithConstantOffset(SDValue Op) const;
1107 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1108 bool isKnownNeverNaN(SDValue Op) const;
1110 /// isKnownNeverZero - Test whether the given SDValue is known to never be
1111 /// positive or negative Zero.
1112 bool isKnownNeverZero(SDValue Op) const;
1114 /// isEqualTo - Test whether two SDValues are known to compare equal. This
1115 /// is true if they are the same value, or if one is negative zero and the
1116 /// other positive zero.
1117 bool isEqualTo(SDValue A, SDValue B) const;
1119 /// UnrollVectorOp - Utility function used by legalize and lowering to
1120 /// "unroll" a vector operation by splitting out the scalars and operating
1121 /// on each element individually. If the ResNE is 0, fully unroll the vector
1122 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1123 /// If the ResNE is greater than the width of the vector op, unroll the
1124 /// vector op and fill the end of the resulting vector with UNDEFS.
1125 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1127 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1128 /// location that is 'Dist' units away from the location that the 'Base' load
1129 /// is loading from.
1130 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1131 unsigned Bytes, int Dist) const;
1133 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1134 /// it cannot be inferred.
1135 unsigned InferPtrAlignment(SDValue Ptr) const;
1137 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
1138 /// which is split (or expanded) into two not necessarily identical pieces.
1139 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1141 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR using the provides
1142 /// VTs and return the low/high part.
1143 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1144 const EVT &LoVT, const EVT &HiVT);
1146 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
1148 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1150 llvm::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1151 return SplitVector(N, DL, LoVT, HiVT);
1154 /// SplitVectorOperand - Split the node's operand with EXTRACT_SUBVECTOR and
1155 /// return the low/high part.
1156 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1158 return SplitVector(N->getOperand(OpNo), SDLoc(N));
1162 bool RemoveNodeFromCSEMaps(SDNode *N);
1163 void AddModifiedNodeToCSEMaps(SDNode *N);
1164 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1165 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1167 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1169 SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
1171 void DeleteNodeNotInCSEMaps(SDNode *N);
1172 void DeallocateNode(SDNode *N);
1174 unsigned getEVTAlignment(EVT MemoryVT) const;
1176 void allnodes_clear();
1178 /// VTList - List of non-single value types.
1179 FoldingSet<SDVTListNode> VTListMap;
1181 /// CondCodeNodes - Maps to auto-CSE operations.
1182 std::vector<CondCodeSDNode*> CondCodeNodes;
1184 std::vector<SDNode*> ValueTypeNodes;
1185 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1186 StringMap<SDNode*> ExternalSymbols;
1188 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1191 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1192 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1193 static nodes_iterator nodes_begin(SelectionDAG *G) {
1194 return G->allnodes_begin();
1196 static nodes_iterator nodes_end(SelectionDAG *G) {
1197 return G->allnodes_end();
1201 } // end namespace llvm