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 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
43 mutable ilist_half_node<SDNode> Sentinel;
45 SDNode *createSentinel() const {
46 return static_cast<SDNode*>(&Sentinel);
48 static void destroySentinel(SDNode *) {}
50 SDNode *provideInitialHead() const { return createSentinel(); }
51 SDNode *ensureHead(SDNode*) const { return createSentinel(); }
52 static void noteHead(SDNode*, SDNode*) {}
54 static void deleteNode(SDNode *) {
55 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
58 static void createNode(const SDNode &);
61 /// SDDbgInfo - Keeps track of dbg_value information through SDISel. We do
62 /// not build SDNodes for these so as not to perturb the generated code;
63 /// instead the info is kept off to the side in this structure. Each SDNode may
64 /// have one or more associated dbg_value entries. This information is kept in
66 /// Byval parameters are handled separately because they don't use alloca's,
67 /// which busts the normal mechanism. There is good reason for handling all
68 /// parameters separately: they may not have code generated for them, they
69 /// should always go at the beginning of the function regardless of other code
70 /// motion, and debug info for them is potentially useful even if the parameter
71 /// is unused. Right now only byval parameters are handled separately.
73 SmallVector<SDDbgValue*, 32> DbgValues;
74 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
75 DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMap;
77 void operator=(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
78 SDDbgInfo(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
82 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
84 ByvalParmDbgValues.push_back(V);
85 } else DbgValues.push_back(V);
87 DbgValMap[Node].push_back(V);
93 ByvalParmDbgValues.clear();
97 return DbgValues.empty() && ByvalParmDbgValues.empty();
100 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
101 DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> >::iterator I =
102 DbgValMap.find(Node);
103 if (I != DbgValMap.end())
105 return ArrayRef<SDDbgValue*>();
108 typedef SmallVector<SDDbgValue*,32>::iterator DbgIterator;
109 DbgIterator DbgBegin() { return DbgValues.begin(); }
110 DbgIterator DbgEnd() { return DbgValues.end(); }
111 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
112 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
116 void checkForCycles(const SDNode *N);
117 void checkForCycles(const SelectionDAG *DAG);
119 /// SelectionDAG class - This is used to represent a portion of an LLVM function
120 /// in a low-level Data Dependence DAG representation suitable for instruction
121 /// selection. This DAG is constructed as the first step of instruction
122 /// selection in order to allow implementation of machine specific optimizations
123 /// and code simplifications.
125 /// The representation used by the SelectionDAG is a target-independent
126 /// representation, which has some similarities to the GCC RTL representation,
127 /// but is significantly more simple, powerful, and is a graph form instead of a
131 const TargetMachine &TM;
132 const TargetLowering &TLI;
133 const TargetSelectionDAGInfo &TSI;
134 const TargetTransformInfo *TTI;
136 LLVMContext *Context;
137 CodeGenOpt::Level OptLevel;
139 /// EntryNode - The starting token.
142 /// Root - The root of the entire DAG.
145 /// AllNodes - A linked list of nodes in the current DAG.
146 ilist<SDNode> AllNodes;
148 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
149 /// pool allocation with recycling.
150 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
151 AlignOf<MostAlignedSDNode>::Alignment>
154 /// NodeAllocator - Pool allocation for nodes.
155 NodeAllocatorType NodeAllocator;
157 /// CSEMap - This structure is used to memoize nodes, automatically performing
158 /// CSE with existing nodes when a duplicate is requested.
159 FoldingSet<SDNode> CSEMap;
161 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
162 BumpPtrAllocator OperandAllocator;
164 /// Allocator - Pool allocation for misc. objects that are created once per
166 BumpPtrAllocator Allocator;
168 /// DbgInfo - Tracks dbg_value information through SDISel.
172 /// DAGUpdateListener - Clients of various APIs that cause global effects on
173 /// the DAG can optionally implement this interface. This allows the clients
174 /// to handle the various sorts of updates that happen.
176 /// A DAGUpdateListener automatically registers itself with DAG when it is
177 /// constructed, and removes itself when destroyed in RAII fashion.
178 struct DAGUpdateListener {
179 DAGUpdateListener *const Next;
182 explicit DAGUpdateListener(SelectionDAG &D)
183 : Next(D.UpdateListeners), DAG(D) {
184 DAG.UpdateListeners = this;
187 virtual ~DAGUpdateListener() {
188 assert(DAG.UpdateListeners == this &&
189 "DAGUpdateListeners must be destroyed in LIFO order");
190 DAG.UpdateListeners = Next;
193 /// NodeDeleted - The node N that was deleted and, if E is not null, an
194 /// equivalent node E that replaced it.
195 virtual void NodeDeleted(SDNode *N, SDNode *E);
197 /// NodeUpdated - The node N that was updated.
198 virtual void NodeUpdated(SDNode *N);
202 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
203 friend struct DAGUpdateListener;
205 /// UpdateListeners - Linked list of registered DAGUpdateListener instances.
206 /// This stack is maintained by DAGUpdateListener RAII.
207 DAGUpdateListener *UpdateListeners;
209 /// setGraphColorHelper - Implementation of setSubgraphColor.
210 /// Return whether we had to truncate the search.
212 bool setSubgraphColorHelper(SDNode *N, const char *Color,
213 DenseSet<SDNode *> &visited,
214 int level, bool &printed);
216 void operator=(const SelectionDAG&) LLVM_DELETED_FUNCTION;
217 SelectionDAG(const SelectionDAG&) LLVM_DELETED_FUNCTION;
220 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
223 /// init - Prepare this SelectionDAG to process code in the given
226 void init(MachineFunction &mf, const TargetTransformInfo *TTI);
228 /// clear - Clear state and free memory necessary to make this
229 /// SelectionDAG ready to process a new block.
233 MachineFunction &getMachineFunction() const { return *MF; }
234 const TargetMachine &getTarget() const { return TM; }
235 const TargetLowering &getTargetLoweringInfo() const { return TLI; }
236 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
237 const TargetTransformInfo *getTargetTransformInfo() const { return TTI; }
238 LLVMContext *getContext() const {return Context; }
240 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
242 void viewGraph(const std::string &Title);
246 std::map<const SDNode *, std::string> NodeGraphAttrs;
249 /// clearGraphAttrs - Clear all previously defined node graph attributes.
250 /// Intended to be used from a debugging tool (eg. gdb).
251 void clearGraphAttrs();
253 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
255 void setGraphAttrs(const SDNode *N, const char *Attrs);
257 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
258 /// Used from getNodeAttributes.
259 const std::string getGraphAttrs(const SDNode *N) const;
261 /// setGraphColor - Convenience for setting node color attribute.
263 void setGraphColor(const SDNode *N, const char *Color);
265 /// setGraphColor - Convenience for setting subgraph color attribute.
267 void setSubgraphColor(SDNode *N, const char *Color);
269 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
270 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
271 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
272 typedef ilist<SDNode>::iterator allnodes_iterator;
273 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
274 allnodes_iterator allnodes_end() { return AllNodes.end(); }
275 ilist<SDNode>::size_type allnodes_size() const {
276 return AllNodes.size();
279 /// getRoot - Return the root tag of the SelectionDAG.
281 const SDValue &getRoot() const { return Root; }
283 /// getEntryNode - Return the token chain corresponding to the entry of the
285 SDValue getEntryNode() const {
286 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
289 /// setRoot - Set the current root tag of the SelectionDAG.
291 const SDValue &setRoot(SDValue N) {
292 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
293 "DAG root value is not a chain!");
295 checkForCycles(N.getNode());
298 checkForCycles(this);
302 /// Combine - This iterates over the nodes in the SelectionDAG, folding
303 /// certain types of nodes together, or eliminating superfluous nodes. The
304 /// Level argument controls whether Combine is allowed to produce nodes and
305 /// types that are illegal on the target.
306 void Combine(CombineLevel Level, AliasAnalysis &AA,
307 CodeGenOpt::Level OptLevel);
309 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
310 /// only uses types natively supported by the target. Returns "true" if it
311 /// made any changes.
313 /// Note that this is an involved process that may invalidate pointers into
315 bool LegalizeTypes();
317 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
318 /// compatible with the target instruction selector, as indicated by the
319 /// TargetLowering object.
321 /// Note that this is an involved process that may invalidate pointers into
325 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
326 /// that only uses vector math operations supported by the target. This is
327 /// necessary as a separate step from Legalize because unrolling a vector
328 /// operation can introduce illegal types, which requires running
329 /// LegalizeTypes again.
331 /// This returns true if it made any changes; in that case, LegalizeTypes
332 /// is called again before Legalize.
334 /// Note that this is an involved process that may invalidate pointers into
336 bool LegalizeVectors();
338 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
340 void RemoveDeadNodes();
342 /// DeleteNode - Remove the specified node from the system. This node must
343 /// have no referrers.
344 void DeleteNode(SDNode *N);
346 /// getVTList - Return an SDVTList that represents the list of values
348 SDVTList getVTList(EVT VT);
349 SDVTList getVTList(EVT VT1, EVT VT2);
350 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
351 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
352 SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
354 //===--------------------------------------------------------------------===//
355 // Node creation methods.
357 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
358 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
359 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
360 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
361 SDValue getTargetConstant(uint64_t Val, EVT VT) {
362 return getConstant(Val, VT, true);
364 SDValue getTargetConstant(const APInt &Val, EVT VT) {
365 return getConstant(Val, VT, true);
367 SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
368 return getConstant(Val, VT, true);
370 // The forms below that take a double should only be used for simple
371 // constants that can be exactly represented in VT. No checks are made.
372 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
373 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
374 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
375 SDValue getTargetConstantFP(double Val, EVT VT) {
376 return getConstantFP(Val, VT, true);
378 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
379 return getConstantFP(Val, VT, true);
381 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
382 return getConstantFP(Val, VT, true);
384 SDValue getGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
385 int64_t offset = 0, bool isTargetGA = false,
386 unsigned char TargetFlags = 0);
387 SDValue getTargetGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT,
389 unsigned char TargetFlags = 0) {
390 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
392 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
393 SDValue getTargetFrameIndex(int FI, EVT VT) {
394 return getFrameIndex(FI, VT, true);
396 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
397 unsigned char TargetFlags = 0);
398 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
399 return getJumpTable(JTI, VT, true, TargetFlags);
401 SDValue getConstantPool(const Constant *C, EVT VT,
402 unsigned Align = 0, int Offs = 0, bool isT=false,
403 unsigned char TargetFlags = 0);
404 SDValue getTargetConstantPool(const Constant *C, EVT VT,
405 unsigned Align = 0, int Offset = 0,
406 unsigned char TargetFlags = 0) {
407 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
409 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
410 unsigned Align = 0, int Offs = 0, bool isT=false,
411 unsigned char TargetFlags = 0);
412 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
413 EVT VT, unsigned Align = 0,
414 int Offset = 0, unsigned char TargetFlags=0) {
415 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
417 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
418 unsigned char TargetFlags = 0);
419 // When generating a branch to a BB, we don't in general know enough
420 // to provide debug info for the BB at that time, so keep this one around.
421 SDValue getBasicBlock(MachineBasicBlock *MBB);
422 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
423 SDValue getExternalSymbol(const char *Sym, EVT VT);
424 SDValue getExternalSymbol(const char *Sym, SDLoc dl, EVT VT);
425 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
426 unsigned char TargetFlags = 0);
427 SDValue getValueType(EVT);
428 SDValue getRegister(unsigned Reg, EVT VT);
429 SDValue getRegisterMask(const uint32_t *RegMask);
430 SDValue getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label);
431 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
432 int64_t Offset = 0, bool isTarget = false,
433 unsigned char TargetFlags = 0);
434 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
436 unsigned char TargetFlags = 0) {
437 return getBlockAddress(BA, VT, Offset, true, TargetFlags);
440 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N) {
441 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
442 getRegister(Reg, N.getValueType()), N);
445 // This version of the getCopyToReg method takes an extra operand, which
446 // indicates that there is potentially an incoming glue value (if Glue is not
447 // null) and that there should be a glue result.
448 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N,
450 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
451 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
452 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
455 // Similar to last getCopyToReg() except parameter Reg is a SDValue
456 SDValue getCopyToReg(SDValue Chain, SDLoc dl, SDValue Reg, SDValue N,
458 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
459 SDValue Ops[] = { Chain, Reg, N, Glue };
460 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
463 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT) {
464 SDVTList VTs = getVTList(VT, MVT::Other);
465 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
466 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
469 // This version of the getCopyFromReg method takes an extra operand, which
470 // indicates that there is potentially an incoming glue value (if Glue is not
471 // null) and that there should be a glue result.
472 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT,
474 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
475 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
476 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Glue.getNode() ? 3 : 2);
479 SDValue getCondCode(ISD::CondCode Cond);
481 /// Returns the ConvertRndSat Note: Avoid using this node because it may
482 /// disappear in the future and most targets don't support it.
483 SDValue getConvertRndSat(EVT VT, SDLoc dl, SDValue Val, SDValue DTy,
485 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
487 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
488 /// elements in VT, which must be a vector type, must match the number of
489 /// mask elements NumElts. A integer mask element equal to -1 is treated as
491 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2,
492 const int *MaskElts);
494 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
495 /// integer type VT, by either any-extending or truncating it.
496 SDValue getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
498 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
499 /// integer type VT, by either sign-extending or truncating it.
500 SDValue getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
502 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
503 /// integer type VT, by either zero-extending or truncating it.
504 SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
506 /// getZeroExtendInReg - Return the expression required to zero extend the Op
507 /// value assuming it was the smaller SrcTy value.
508 SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy);
510 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
511 SDValue getNOT(SDLoc DL, SDValue Val, EVT VT);
513 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
514 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a
516 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) {
517 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
518 SDValue Ops[] = { Chain, Op };
519 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops, 2);
522 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
523 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have
525 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
526 SDValue InGlue, SDLoc DL) {
527 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
528 SmallVector<SDValue, 4> Ops;
529 Ops.push_back(Chain);
532 Ops.push_back(InGlue);
533 return getNode(ISD::CALLSEQ_END, DL, NodeTys, &Ops[0],
534 (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0));
537 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful SDLoc.
538 SDValue getUNDEF(EVT VT) {
539 return getNode(ISD::UNDEF, SDLoc(), VT);
542 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
543 /// not have a useful SDLoc.
544 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
545 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
548 /// getNode - Gets or creates the specified node.
550 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT);
551 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N);
552 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2);
553 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
554 SDValue N1, SDValue N2, SDValue N3);
555 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
556 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
557 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
558 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
560 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
561 const SDUse *Ops, unsigned NumOps);
562 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
563 const SDValue *Ops, unsigned NumOps);
564 SDValue getNode(unsigned Opcode, SDLoc DL,
565 ArrayRef<EVT> ResultTys,
566 const SDValue *Ops, unsigned NumOps);
567 SDValue getNode(unsigned Opcode, SDLoc DL, const EVT *VTs, unsigned NumVTs,
568 const SDValue *Ops, unsigned NumOps);
569 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
570 const SDValue *Ops, unsigned NumOps);
571 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs);
572 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N);
573 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
574 SDValue N1, SDValue N2);
575 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
576 SDValue N1, SDValue N2, SDValue N3);
577 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
578 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
579 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
580 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
583 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
584 /// the incoming stack arguments to be loaded from the stack. This is
585 /// used in tail call lowering to protect stack arguments from being
587 SDValue getStackArgumentTokenFactor(SDValue Chain);
589 SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
590 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
591 MachinePointerInfo DstPtrInfo,
592 MachinePointerInfo SrcPtrInfo);
594 SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
595 SDValue Size, unsigned Align, bool isVol,
596 MachinePointerInfo DstPtrInfo,
597 MachinePointerInfo SrcPtrInfo);
599 SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
600 SDValue Size, unsigned Align, bool isVol,
601 MachinePointerInfo DstPtrInfo);
603 /// getSetCC - Helper function to make it easier to build SetCC's if you just
604 /// have an ISD::CondCode instead of an SDValue.
606 SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS,
607 ISD::CondCode Cond) {
608 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
609 "Cannot compare scalars to vectors");
610 assert(LHS.getValueType().isVector() == VT.isVector() &&
611 "Cannot compare scalars to vectors");
612 assert(Cond != ISD::SETCC_INVALID &&
613 "Cannot create a setCC of an invalid node.");
614 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
617 // getSelect - Helper function to make it easier to build Select's if you just
618 // have operands and don't want to check for vector.
619 SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond,
620 SDValue LHS, SDValue RHS) {
621 assert(LHS.getValueType() == RHS.getValueType() &&
622 "Cannot use select on differing types");
623 assert(VT.isVector() == LHS.getValueType().isVector() &&
624 "Cannot mix vectors and scalars");
625 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
629 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
630 /// just have an ISD::CondCode instead of an SDValue.
632 SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS,
633 SDValue True, SDValue False, ISD::CondCode Cond) {
634 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
635 LHS, RHS, True, False, getCondCode(Cond));
638 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
639 /// and a source value as input.
640 SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
641 SDValue SV, unsigned Align);
643 /// getAtomic - Gets a node for an atomic op, produces result and chain and
645 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
646 SDValue Ptr, SDValue Cmp, SDValue Swp,
647 MachinePointerInfo PtrInfo, unsigned Alignment,
648 AtomicOrdering Ordering,
649 SynchronizationScope SynchScope);
650 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
651 SDValue Ptr, SDValue Cmp, SDValue Swp,
652 MachineMemOperand *MMO,
653 AtomicOrdering Ordering,
654 SynchronizationScope SynchScope);
656 /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
657 /// and chain and takes 2 operands.
658 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
659 SDValue Ptr, SDValue Val, const Value* PtrVal,
660 unsigned Alignment, AtomicOrdering Ordering,
661 SynchronizationScope SynchScope);
662 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
663 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
664 AtomicOrdering Ordering,
665 SynchronizationScope SynchScope);
667 /// getAtomic - Gets a node for an atomic op, produces result and chain and
669 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
670 SDValue Chain, SDValue Ptr, const Value* PtrVal,
672 AtomicOrdering Ordering,
673 SynchronizationScope SynchScope);
674 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
675 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
676 AtomicOrdering Ordering,
677 SynchronizationScope SynchScope);
679 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
680 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
681 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
682 /// less than FIRST_TARGET_MEMORY_OPCODE.
683 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
684 const EVT *VTs, unsigned NumVTs,
685 const SDValue *Ops, unsigned NumOps,
686 EVT MemVT, MachinePointerInfo PtrInfo,
687 unsigned Align = 0, bool Vol = false,
688 bool ReadMem = true, bool WriteMem = true);
690 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
691 const SDValue *Ops, unsigned NumOps,
692 EVT MemVT, MachinePointerInfo PtrInfo,
693 unsigned Align = 0, bool Vol = false,
694 bool ReadMem = true, bool WriteMem = true);
696 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
697 const SDValue *Ops, unsigned NumOps,
698 EVT MemVT, MachineMemOperand *MMO);
700 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
701 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, SDLoc dl);
703 /// getLoad - Loads are not normal binary operators: their result type is not
704 /// determined by their operands, and they produce a value AND a token chain.
706 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
707 MachinePointerInfo PtrInfo, bool isVolatile,
708 bool isNonTemporal, bool isInvariant, unsigned Alignment,
709 const MDNode *TBAAInfo = 0, const MDNode *Ranges = 0);
710 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
711 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
712 EVT MemVT, bool isVolatile,
713 bool isNonTemporal, unsigned Alignment,
714 const MDNode *TBAAInfo = 0);
715 SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
716 SDValue Offset, ISD::MemIndexedMode AM);
717 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
719 SDValue Chain, SDValue Ptr, SDValue Offset,
720 MachinePointerInfo PtrInfo, EVT MemVT,
721 bool isVolatile, bool isNonTemporal, bool isInvariant,
722 unsigned Alignment, const MDNode *TBAAInfo = 0,
723 const MDNode *Ranges = 0);
724 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
726 SDValue Chain, SDValue Ptr, SDValue Offset,
727 EVT MemVT, MachineMemOperand *MMO);
729 /// getStore - Helper function to build ISD::STORE nodes.
731 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
732 MachinePointerInfo PtrInfo, bool isVolatile,
733 bool isNonTemporal, unsigned Alignment,
734 const MDNode *TBAAInfo = 0);
735 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
736 MachineMemOperand *MMO);
737 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
738 MachinePointerInfo PtrInfo, EVT TVT,
739 bool isNonTemporal, bool isVolatile,
741 const MDNode *TBAAInfo = 0);
742 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
743 EVT TVT, MachineMemOperand *MMO);
744 SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base,
745 SDValue Offset, ISD::MemIndexedMode AM);
747 /// getSrcValue - Construct a node to track a Value* through the backend.
748 SDValue getSrcValue(const Value *v);
750 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
751 SDValue getMDNode(const MDNode *MD);
753 /// getShiftAmountOperand - Return the specified value casted to
754 /// the target's desired shift amount type.
755 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
757 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
758 /// specified operands. If the resultant node already exists in the DAG,
759 /// this does not modify the specified node, instead it returns the node that
760 /// already exists. If the resultant node does not exist in the DAG, the
761 /// input node is returned. As a degenerate case, if you specify the same
762 /// input operands as the node already has, the input node is returned.
763 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
764 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
765 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
767 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
768 SDValue Op3, SDValue Op4);
769 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
770 SDValue Op3, SDValue Op4, SDValue Op5);
771 SDNode *UpdateNodeOperands(SDNode *N,
772 const SDValue *Ops, unsigned NumOps);
774 /// SelectNodeTo - These are used for target selectors to *mutate* the
775 /// specified node to have the specified return type, Target opcode, and
776 /// operands. Note that target opcodes are stored as
777 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
778 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
779 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
780 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
781 SDValue Op1, SDValue Op2);
782 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
783 SDValue Op1, SDValue Op2, SDValue Op3);
784 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
785 const SDValue *Ops, unsigned NumOps);
786 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
787 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
788 EVT VT2, const SDValue *Ops, unsigned NumOps);
789 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
790 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
791 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
792 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
794 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
795 EVT VT2, SDValue Op1);
796 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
797 EVT VT2, SDValue Op1, SDValue Op2);
798 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
799 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
800 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
801 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
802 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
803 const SDValue *Ops, unsigned NumOps);
805 /// MorphNodeTo - This *mutates* the specified node to have the specified
806 /// return type, opcode, and operands.
807 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
808 const SDValue *Ops, unsigned NumOps);
810 /// getMachineNode - These are used for target selectors to create a new node
811 /// with specified return type(s), MachineInstr opcode, and operands.
813 /// Note that getMachineNode returns the resultant node. If there is already
814 /// a node of the specified opcode and operands, it returns that node instead
815 /// of the current one.
816 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT);
817 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
819 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
820 SDValue Op1, SDValue Op2);
821 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
822 SDValue Op1, SDValue Op2, SDValue Op3);
823 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
824 ArrayRef<SDValue> Ops);
825 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2);
826 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
828 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
829 SDValue Op1, SDValue Op2);
830 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
831 SDValue Op1, SDValue Op2, SDValue Op3);
832 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
833 ArrayRef<SDValue> Ops);
834 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
835 EVT VT3, SDValue Op1, SDValue Op2);
836 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
837 EVT VT3, SDValue Op1, SDValue Op2,
839 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
840 EVT VT3, ArrayRef<SDValue> Ops);
841 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
842 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
843 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl,
844 ArrayRef<EVT> ResultTys,
845 ArrayRef<SDValue> Ops);
846 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs,
847 ArrayRef<SDValue> Ops);
849 /// getTargetExtractSubreg - A convenience function for creating
850 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
851 SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
854 /// getTargetInsertSubreg - A convenience function for creating
855 /// TargetInstrInfo::INSERT_SUBREG nodes.
856 SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
857 SDValue Operand, SDValue Subreg);
859 /// getNodeIfExists - Get the specified node if it's already available, or
860 /// else return NULL.
861 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
862 const SDValue *Ops, unsigned NumOps);
864 /// getDbgValue - Creates a SDDbgValue node.
866 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
867 DebugLoc DL, unsigned O);
868 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
869 DebugLoc DL, unsigned O);
870 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
871 DebugLoc DL, unsigned O);
873 /// RemoveDeadNode - Remove the specified node from the system. If any of its
874 /// operands then becomes dead, remove them as well. Inform UpdateListener
875 /// for each node deleted.
876 void RemoveDeadNode(SDNode *N);
878 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
879 /// given list, and any nodes that become unreachable as a result.
880 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
882 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
883 /// This can cause recursive merging of nodes in the DAG. Use the first
884 /// version if 'From' is known to have a single result, use the second
885 /// if you have two nodes with identical results (or if 'To' has a superset
886 /// of the results of 'From'), use the third otherwise.
888 /// These methods all take an optional UpdateListener, which (if not null) is
889 /// informed about nodes that are deleted and modified due to recursive
890 /// changes in the dag.
892 /// These functions only replace all existing uses. It's possible that as
893 /// these replacements are being performed, CSE may cause the From node
894 /// to be given new uses. These new uses of From are left in place, and
895 /// not automatically transferred to To.
897 void ReplaceAllUsesWith(SDValue From, SDValue Op);
898 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
899 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
901 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
902 /// uses of other values produced by From.Val alone.
903 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
905 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
906 /// for multiple values at once. This correctly handles the case where
907 /// there is an overlap between the From values and the To values.
908 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
911 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
912 /// assign a unique node id for each node in the DAG based on their
913 /// topological order. Returns the number of nodes.
914 unsigned AssignTopologicalOrder();
916 /// RepositionNode - Move node N in the AllNodes list to be immediately
917 /// before the given iterator Position. This may be used to update the
918 /// topological ordering when the list of nodes is modified.
919 void RepositionNode(allnodes_iterator Position, SDNode *N) {
920 AllNodes.insert(Position, AllNodes.remove(N));
923 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
925 static bool isCommutativeBinOp(unsigned Opcode) {
926 // FIXME: This should get its info from the td file, so that we can include
943 case ISD::ADDE: return true;
944 default: return false;
948 /// Returns an APFloat semantics tag appropriate for the given type. If VT is
949 /// a vector type, the element semantics are returned.
950 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
951 switch (VT.getScalarType().getSimpleVT().SimpleTy) {
952 default: llvm_unreachable("Unknown FP format");
953 case MVT::f16: return APFloat::IEEEhalf;
954 case MVT::f32: return APFloat::IEEEsingle;
955 case MVT::f64: return APFloat::IEEEdouble;
956 case MVT::f80: return APFloat::x87DoubleExtended;
957 case MVT::f128: return APFloat::IEEEquad;
958 case MVT::ppcf128: return APFloat::PPCDoubleDouble;
962 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
963 /// value is produced by SD.
964 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
966 /// GetDbgValues - Get the debug values which reference the given SDNode.
967 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
968 return DbgInfo->getSDDbgValues(SD);
971 /// TransferDbgValues - Transfer SDDbgValues.
972 void TransferDbgValues(SDValue From, SDValue To);
974 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
975 /// with this SelectionDAG.
976 bool hasDebugValues() const { return !DbgInfo->empty(); }
978 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
979 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
980 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
981 return DbgInfo->ByvalParmDbgBegin();
983 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
984 return DbgInfo->ByvalParmDbgEnd();
989 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
990 /// specified value type. If minAlign is specified, the slot size will have
991 /// at least that alignment.
992 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
994 /// CreateStackTemporary - Create a stack temporary suitable for holding
995 /// either of the specified value types.
996 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
998 /// FoldConstantArithmetic -
999 SDValue FoldConstantArithmetic(unsigned Opcode, EVT VT,
1000 SDNode *Cst1, SDNode *Cst2);
1002 /// FoldSetCC - Constant fold a setcc to true or false.
1003 SDValue FoldSetCC(EVT VT, SDValue N1,
1004 SDValue N2, ISD::CondCode Cond, SDLoc dl);
1006 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1007 /// use this predicate to simplify operations downstream.
1008 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1010 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
1011 /// use this predicate to simplify operations downstream. Op and Mask are
1012 /// known to be the same type.
1013 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1016 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1017 /// known to be either zero or one and return them in the KnownZero/KnownOne
1018 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1019 /// processing. Targets can implement the computeMaskedBitsForTargetNode
1020 /// method in the TargetLowering class to allow target nodes to be understood.
1021 void ComputeMaskedBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1022 unsigned Depth = 0) const;
1024 /// ComputeNumSignBits - Return the number of times the sign bit of the
1025 /// register is replicated into the other bits. We know that at least 1 bit
1026 /// is always equal to the sign bit (itself), but other cases can give us
1027 /// information. For example, immediately after an "SRA X, 2", we know that
1028 /// the top 3 bits are all equal to each other, so we return 3. Targets can
1029 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1030 /// class to allow target nodes to be understood.
1031 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1033 /// isBaseWithConstantOffset - Return true if the specified operand is an
1034 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1035 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1036 /// semantics as an ADD. This handles the equivalence:
1037 /// X|Cst == X+Cst iff X&Cst = 0.
1038 bool isBaseWithConstantOffset(SDValue Op) const;
1040 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1041 bool isKnownNeverNaN(SDValue Op) const;
1043 /// isKnownNeverZero - Test whether the given SDValue is known to never be
1044 /// positive or negative Zero.
1045 bool isKnownNeverZero(SDValue Op) const;
1047 /// isEqualTo - Test whether two SDValues are known to compare equal. This
1048 /// is true if they are the same value, or if one is negative zero and the
1049 /// other positive zero.
1050 bool isEqualTo(SDValue A, SDValue B) const;
1052 /// UnrollVectorOp - Utility function used by legalize and lowering to
1053 /// "unroll" a vector operation by splitting out the scalars and operating
1054 /// on each element individually. If the ResNE is 0, fully unroll the vector
1055 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1056 /// If the ResNE is greater than the width of the vector op, unroll the
1057 /// vector op and fill the end of the resulting vector with UNDEFS.
1058 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1060 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1061 /// location that is 'Dist' units away from the location that the 'Base' load
1062 /// is loading from.
1063 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1064 unsigned Bytes, int Dist) const;
1066 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1067 /// it cannot be inferred.
1068 unsigned InferPtrAlignment(SDValue Ptr) const;
1071 bool RemoveNodeFromCSEMaps(SDNode *N);
1072 void AddModifiedNodeToCSEMaps(SDNode *N);
1073 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1074 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1076 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1078 SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
1080 void DeleteNodeNotInCSEMaps(SDNode *N);
1081 void DeallocateNode(SDNode *N);
1083 unsigned getEVTAlignment(EVT MemoryVT) const;
1085 void allnodes_clear();
1087 /// VTList - List of non-single value types.
1088 std::vector<SDVTList> VTList;
1090 /// CondCodeNodes - Maps to auto-CSE operations.
1091 std::vector<CondCodeSDNode*> CondCodeNodes;
1093 std::vector<SDNode*> ValueTypeNodes;
1094 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1095 StringMap<SDNode*> ExternalSymbols;
1097 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1100 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1101 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1102 static nodes_iterator nodes_begin(SelectionDAG *G) {
1103 return G->allnodes_begin();
1105 static nodes_iterator nodes_end(SelectionDAG *G) {
1106 return G->allnodes_end();
1110 } // end namespace llvm