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/ilist.h"
19 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/ADT/StringMap.h"
21 #include "llvm/CodeGen/SelectionDAGNodes.h"
22 #include "llvm/Support/RecyclingAllocator.h"
23 #include "llvm/Target/TargetMachine.h"
32 class MachineConstantPoolValue;
33 class MachineFunction;
38 class TargetSelectionDAGInfo;
40 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
42 mutable ilist_half_node<SDNode> Sentinel;
44 SDNode *createSentinel() const {
45 return static_cast<SDNode*>(&Sentinel);
47 static void destroySentinel(SDNode *) {}
49 SDNode *provideInitialHead() const { return createSentinel(); }
50 SDNode *ensureHead(SDNode*) const { return createSentinel(); }
51 static void noteHead(SDNode*, SDNode*) {}
53 static void deleteNode(SDNode *) {
54 assert(0 && "ilist_traits<SDNode> shouldn't see a deleteNode call!");
57 static void createNode(const SDNode &);
60 /// SDDbgInfo - Keeps track of dbg_value information through SDISel. We do
61 /// not build SDNodes for these so as not to perturb the generated code;
62 /// instead the info is kept off to the side in this structure. Each SDNode may
63 /// have one or more associated dbg_value entries. This information is kept in
65 /// Byval parameters are handled separately because they don't use alloca's,
66 /// which busts the normal mechanism. There is good reason for handling all
67 /// parameters separately: they may not have code generated for them, they
68 /// should always go at the beginning of the function regardless of other code
69 /// motion, and debug info for them is potentially useful even if the parameter
70 /// is unused. Right now only byval parameters are handled separately.
72 SmallVector<SDDbgValue*, 32> DbgValues;
73 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
74 DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMap;
76 void operator=(const SDDbgInfo&); // Do not implement.
77 SDDbgInfo(const SDDbgInfo&); // Do not implement.
81 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
83 ByvalParmDbgValues.push_back(V);
84 } else DbgValues.push_back(V);
86 DbgValMap[Node].push_back(V);
92 ByvalParmDbgValues.clear();
96 return DbgValues.empty() && ByvalParmDbgValues.empty();
99 SmallVector<SDDbgValue*,2> &getSDDbgValues(const SDNode *Node) {
100 return DbgValMap[Node];
103 typedef SmallVector<SDDbgValue*,32>::iterator DbgIterator;
104 DbgIterator DbgBegin() { return DbgValues.begin(); }
105 DbgIterator DbgEnd() { return DbgValues.end(); }
106 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
107 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
111 Unrestricted, // Combine may create illegal operations and illegal types.
112 NoIllegalTypes, // Combine may create illegal operations but no illegal types.
113 NoIllegalOperations // Combine may only create legal operations and types.
117 void checkForCycles(const SDNode *N);
118 void checkForCycles(const SelectionDAG *DAG);
120 /// SelectionDAG class - This is used to represent a portion of an LLVM function
121 /// in a low-level Data Dependence DAG representation suitable for instruction
122 /// selection. This DAG is constructed as the first step of instruction
123 /// selection in order to allow implementation of machine specific optimizations
124 /// and code simplifications.
126 /// The representation used by the SelectionDAG is a target-independent
127 /// representation, which has some similarities to the GCC RTL representation,
128 /// but is significantly more simple, powerful, and is a graph form instead of a
132 const TargetMachine &TM;
133 const TargetLowering &TLI;
134 const TargetSelectionDAGInfo &TSI;
136 LLVMContext *Context;
138 /// EntryNode - The starting token.
141 /// Root - The root of the entire DAG.
144 /// AllNodes - A linked list of nodes in the current DAG.
145 ilist<SDNode> AllNodes;
147 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
148 /// pool allocation with recycling.
149 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
150 AlignOf<MostAlignedSDNode>::Alignment>
153 /// NodeAllocator - Pool allocation for nodes.
154 NodeAllocatorType NodeAllocator;
156 /// CSEMap - This structure is used to memoize nodes, automatically performing
157 /// CSE with existing nodes when a duplicate is requested.
158 FoldingSet<SDNode> CSEMap;
160 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
161 BumpPtrAllocator OperandAllocator;
163 /// Allocator - Pool allocation for misc. objects that are created once per
165 BumpPtrAllocator Allocator;
167 /// SDNodeOrdering - The ordering of the SDNodes. It roughly corresponds to
168 /// the ordering of the original LLVM instructions.
169 SDNodeOrdering *Ordering;
171 /// DbgInfo - Tracks dbg_value information through SDISel.
174 /// VerifyNode - Sanity check the given node. Aborts if it is invalid.
175 void VerifyNode(SDNode *N);
177 /// setGraphColorHelper - Implementation of setSubgraphColor.
178 /// Return whether we had to truncate the search.
180 bool setSubgraphColorHelper(SDNode *N, const char *Color,
181 DenseSet<SDNode *> &visited,
182 int level, bool &printed);
184 void operator=(const SelectionDAG&); // Do not implement.
185 SelectionDAG(const SelectionDAG&); // Do not implement.
188 explicit SelectionDAG(const TargetMachine &TM);
191 /// init - Prepare this SelectionDAG to process code in the given
194 void init(MachineFunction &mf);
196 /// clear - Clear state and free memory necessary to make this
197 /// SelectionDAG ready to process a new block.
201 MachineFunction &getMachineFunction() const { return *MF; }
202 const TargetMachine &getTarget() const { return TM; }
203 const TargetLowering &getTargetLoweringInfo() const { return TLI; }
204 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
205 LLVMContext *getContext() const {return Context; }
207 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
209 void viewGraph(const std::string &Title);
213 std::map<const SDNode *, std::string> NodeGraphAttrs;
216 /// clearGraphAttrs - Clear all previously defined node graph attributes.
217 /// Intended to be used from a debugging tool (eg. gdb).
218 void clearGraphAttrs();
220 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
222 void setGraphAttrs(const SDNode *N, const char *Attrs);
224 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
225 /// Used from getNodeAttributes.
226 const std::string getGraphAttrs(const SDNode *N) const;
228 /// setGraphColor - Convenience for setting node color attribute.
230 void setGraphColor(const SDNode *N, const char *Color);
232 /// setGraphColor - Convenience for setting subgraph color attribute.
234 void setSubgraphColor(SDNode *N, const char *Color);
236 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
237 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
238 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
239 typedef ilist<SDNode>::iterator allnodes_iterator;
240 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
241 allnodes_iterator allnodes_end() { return AllNodes.end(); }
242 ilist<SDNode>::size_type allnodes_size() const {
243 return AllNodes.size();
246 /// getRoot - Return the root tag of the SelectionDAG.
248 const SDValue &getRoot() const { return Root; }
250 /// getEntryNode - Return the token chain corresponding to the entry of the
252 SDValue getEntryNode() const {
253 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
256 /// setRoot - Set the current root tag of the SelectionDAG.
258 const SDValue &setRoot(SDValue N) {
259 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
260 "DAG root value is not a chain!");
262 checkForCycles(N.getNode());
265 checkForCycles(this);
269 /// Combine - This iterates over the nodes in the SelectionDAG, folding
270 /// certain types of nodes together, or eliminating superfluous nodes. The
271 /// Level argument controls whether Combine is allowed to produce nodes and
272 /// types that are illegal on the target.
273 void Combine(CombineLevel Level, AliasAnalysis &AA,
274 CodeGenOpt::Level OptLevel);
276 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
277 /// only uses types natively supported by the target. Returns "true" if it
278 /// made any changes.
280 /// Note that this is an involved process that may invalidate pointers into
282 bool LegalizeTypes();
284 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
285 /// compatible with the target instruction selector, as indicated by the
286 /// TargetLowering object.
288 /// Note that this is an involved process that may invalidate pointers into
290 void Legalize(CodeGenOpt::Level OptLevel);
292 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
293 /// that only uses vector math operations supported by the target. This is
294 /// necessary as a separate step from Legalize because unrolling a vector
295 /// operation can introduce illegal types, which requires running
296 /// LegalizeTypes again.
298 /// This returns true if it made any changes; in that case, LegalizeTypes
299 /// is called again before Legalize.
301 /// Note that this is an involved process that may invalidate pointers into
303 bool LegalizeVectors();
305 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
307 void RemoveDeadNodes();
309 /// DeleteNode - Remove the specified node from the system. This node must
310 /// have no referrers.
311 void DeleteNode(SDNode *N);
313 /// getVTList - Return an SDVTList that represents the list of values
315 SDVTList getVTList(EVT VT);
316 SDVTList getVTList(EVT VT1, EVT VT2);
317 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
318 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
319 SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
321 //===--------------------------------------------------------------------===//
322 // Node creation methods.
324 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
325 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
326 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
327 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
328 SDValue getTargetConstant(uint64_t Val, EVT VT) {
329 return getConstant(Val, VT, true);
331 SDValue getTargetConstant(const APInt &Val, EVT VT) {
332 return getConstant(Val, VT, true);
334 SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
335 return getConstant(Val, VT, true);
337 // The forms below that take a double should only be used for simple
338 // constants that can be exactly represented in VT. No checks are made.
339 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
340 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
341 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
342 SDValue getTargetConstantFP(double Val, EVT VT) {
343 return getConstantFP(Val, VT, true);
345 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
346 return getConstantFP(Val, VT, true);
348 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
349 return getConstantFP(Val, VT, true);
351 SDValue getGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
352 int64_t offset = 0, bool isTargetGA = false,
353 unsigned char TargetFlags = 0);
354 SDValue getTargetGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
356 unsigned char TargetFlags = 0) {
357 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
359 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
360 SDValue getTargetFrameIndex(int FI, EVT VT) {
361 return getFrameIndex(FI, VT, true);
363 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
364 unsigned char TargetFlags = 0);
365 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
366 return getJumpTable(JTI, VT, true, TargetFlags);
368 SDValue getConstantPool(const Constant *C, EVT VT,
369 unsigned Align = 0, int Offs = 0, bool isT=false,
370 unsigned char TargetFlags = 0);
371 SDValue getTargetConstantPool(const Constant *C, EVT VT,
372 unsigned Align = 0, int Offset = 0,
373 unsigned char TargetFlags = 0) {
374 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
376 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
377 unsigned Align = 0, int Offs = 0, bool isT=false,
378 unsigned char TargetFlags = 0);
379 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
380 EVT VT, unsigned Align = 0,
381 int Offset = 0, unsigned char TargetFlags=0) {
382 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
384 // When generating a branch to a BB, we don't in general know enough
385 // to provide debug info for the BB at that time, so keep this one around.
386 SDValue getBasicBlock(MachineBasicBlock *MBB);
387 SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl);
388 SDValue getExternalSymbol(const char *Sym, EVT VT);
389 SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT);
390 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
391 unsigned char TargetFlags = 0);
392 SDValue getValueType(EVT);
393 SDValue getRegister(unsigned Reg, EVT VT);
394 SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label);
395 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
396 bool isTarget = false, unsigned char TargetFlags = 0);
398 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) {
399 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
400 getRegister(Reg, N.getValueType()), N);
403 // This version of the getCopyToReg method takes an extra operand, which
404 // indicates that there is potentially an incoming flag value (if Flag is not
405 // null) and that there should be a flag result.
406 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N,
408 SDVTList VTs = getVTList(MVT::Other, MVT::Flag);
409 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag };
410 return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3);
413 // Similar to last getCopyToReg() except parameter Reg is a SDValue
414 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N,
416 SDVTList VTs = getVTList(MVT::Other, MVT::Flag);
417 SDValue Ops[] = { Chain, Reg, N, Flag };
418 return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3);
421 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) {
422 SDVTList VTs = getVTList(VT, MVT::Other);
423 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
424 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
427 // This version of the getCopyFromReg method takes an extra operand, which
428 // indicates that there is potentially an incoming flag value (if Flag is not
429 // null) and that there should be a flag result.
430 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT,
432 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Flag);
433 SDValue Ops[] = { Chain, getRegister(Reg, VT), Flag };
434 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Flag.getNode() ? 3 : 2);
437 SDValue getCondCode(ISD::CondCode Cond);
439 /// Returns the ConvertRndSat Note: Avoid using this node because it may
440 /// disappear in the future and most targets don't support it.
441 SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy,
443 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
445 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
446 /// elements in VT, which must be a vector type, must match the number of
447 /// mask elements NumElts. A integer mask element equal to -1 is treated as
449 SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2,
450 const int *MaskElts);
452 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
453 /// integer type VT, by either sign-extending or truncating it.
454 SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
456 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
457 /// integer type VT, by either zero-extending or truncating it.
458 SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
460 /// getZeroExtendInReg - Return the expression required to zero extend the Op
461 /// value assuming it was the smaller SrcTy value.
462 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy);
464 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
465 SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT);
467 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
468 /// a flag result (to ensure it's not CSE'd). CALLSEQ_START does not have a
470 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) {
471 SDVTList VTs = getVTList(MVT::Other, MVT::Flag);
472 SDValue Ops[] = { Chain, Op };
473 return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2);
476 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
477 /// flag result (to ensure it's not CSE'd). CALLSEQ_END does not have
478 /// a useful DebugLoc.
479 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
481 SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag);
482 SmallVector<SDValue, 4> Ops;
483 Ops.push_back(Chain);
486 Ops.push_back(InFlag);
487 return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0],
488 (unsigned)Ops.size() - (InFlag.getNode() == 0 ? 1 : 0));
491 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc.
492 SDValue getUNDEF(EVT VT) {
493 return getNode(ISD::UNDEF, DebugLoc(), VT);
496 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
497 /// not have a useful DebugLoc.
498 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
499 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc(), VT);
502 /// getNode - Gets or creates the specified node.
504 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT);
505 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N);
506 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2);
507 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
508 SDValue N1, SDValue N2, SDValue N3);
509 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
510 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
511 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
512 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
514 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
515 const SDUse *Ops, unsigned NumOps);
516 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
517 const SDValue *Ops, unsigned NumOps);
518 SDValue getNode(unsigned Opcode, DebugLoc DL,
519 const std::vector<EVT> &ResultTys,
520 const SDValue *Ops, unsigned NumOps);
521 SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs,
522 const SDValue *Ops, unsigned NumOps);
523 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
524 const SDValue *Ops, unsigned NumOps);
525 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs);
526 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N);
527 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
528 SDValue N1, SDValue N2);
529 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
530 SDValue N1, SDValue N2, SDValue N3);
531 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
532 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
533 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
534 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
537 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
538 /// the incoming stack arguments to be loaded from the stack. This is
539 /// used in tail call lowering to protect stack arguments from being
541 SDValue getStackArgumentTokenFactor(SDValue Chain);
543 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
544 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
545 MachinePointerInfo DstPtrInfo,
546 MachinePointerInfo SrcPtrInfo);
548 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
549 SDValue Size, unsigned Align, bool isVol,
550 MachinePointerInfo DstPtrInfo,
551 MachinePointerInfo SrcPtrInfo);
553 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
554 SDValue Size, unsigned Align, bool isVol,
555 MachinePointerInfo DstPtrInfo);
557 /// getSetCC - Helper function to make it easier to build SetCC's if you just
558 /// have an ISD::CondCode instead of an SDValue.
560 SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
561 ISD::CondCode Cond) {
562 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
565 /// getVSetCC - Helper function to make it easier to build VSetCC's nodes
566 /// if you just have an ISD::CondCode instead of an SDValue.
568 SDValue getVSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
569 ISD::CondCode Cond) {
570 return getNode(ISD::VSETCC, DL, VT, LHS, RHS, getCondCode(Cond));
573 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
574 /// just have an ISD::CondCode instead of an SDValue.
576 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS,
577 SDValue True, SDValue False, ISD::CondCode Cond) {
578 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
579 LHS, RHS, True, False, getCondCode(Cond));
582 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
583 /// and a source value as input.
584 SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
585 SDValue SV, unsigned Align);
587 /// getAtomic - Gets a node for an atomic op, produces result and chain and
589 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
590 SDValue Ptr, SDValue Cmp, SDValue Swp,
591 MachinePointerInfo PtrInfo, unsigned Alignment=0);
592 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
593 SDValue Ptr, SDValue Cmp, SDValue Swp,
594 MachineMemOperand *MMO);
596 /// getAtomic - Gets a node for an atomic op, produces result and chain and
597 /// takes 2 operands.
598 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
599 SDValue Ptr, SDValue Val, const Value* PtrVal,
600 unsigned Alignment = 0);
601 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
602 SDValue Ptr, SDValue Val,
603 MachineMemOperand *MMO);
605 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
606 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
607 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
608 /// less than FIRST_TARGET_MEMORY_OPCODE.
609 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
610 const EVT *VTs, unsigned NumVTs,
611 const SDValue *Ops, unsigned NumOps,
612 EVT MemVT, MachinePointerInfo PtrInfo,
613 unsigned Align = 0, bool Vol = false,
614 bool ReadMem = true, bool WriteMem = true);
616 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
617 const SDValue *Ops, unsigned NumOps,
618 EVT MemVT, MachinePointerInfo PtrInfo,
619 unsigned Align = 0, bool Vol = false,
620 bool ReadMem = true, bool WriteMem = true);
622 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
623 const SDValue *Ops, unsigned NumOps,
624 EVT MemVT, MachineMemOperand *MMO);
626 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
627 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl);
629 /// getLoad - Loads are not normal binary operators: their result type is not
630 /// determined by their operands, and they produce a value AND a token chain.
632 SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
633 MachinePointerInfo PtrInfo, bool isVolatile,
634 bool isNonTemporal, unsigned Alignment);
635 SDValue getExtLoad(ISD::LoadExtType ExtType, EVT VT, DebugLoc dl,
636 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
637 EVT MemVT, bool isVolatile,
638 bool isNonTemporal, unsigned Alignment);
639 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
640 SDValue Offset, ISD::MemIndexedMode AM);
641 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
643 SDValue Chain, SDValue Ptr, SDValue Offset,
644 MachinePointerInfo PtrInfo, EVT MemVT,
645 bool isVolatile, bool isNonTemporal, unsigned Alignment);
646 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
648 SDValue Chain, SDValue Ptr, SDValue Offset,
649 EVT MemVT, MachineMemOperand *MMO);
651 /// getStore - Helper function to build ISD::STORE nodes.
653 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
654 MachinePointerInfo PtrInfo, bool isVolatile,
655 bool isNonTemporal, unsigned Alignment);
656 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
657 const Value *V, int SVOffset, bool isVolatile,
658 bool isNonTemporal, unsigned Alignment);
659 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
660 MachineMemOperand *MMO);
661 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
662 MachinePointerInfo PtrInfo, EVT TVT,
663 bool isNonTemporal, bool isVolatile,
665 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
666 const Value *SV, int SVOffset, EVT TVT,
667 bool isNonTemporal, bool isVolatile,
669 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
670 EVT TVT, MachineMemOperand *MMO);
671 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base,
672 SDValue Offset, ISD::MemIndexedMode AM);
674 /// getSrcValue - Construct a node to track a Value* through the backend.
675 SDValue getSrcValue(const Value *v);
677 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
678 SDValue getMDNode(const MDNode *MD);
680 /// getShiftAmountOperand - Return the specified value casted to
681 /// the target's desired shift amount type.
682 SDValue getShiftAmountOperand(SDValue Op);
684 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
685 /// specified operands. If the resultant node already exists in the DAG,
686 /// this does not modify the specified node, instead it returns the node that
687 /// already exists. If the resultant node does not exist in the DAG, the
688 /// input node is returned. As a degenerate case, if you specify the same
689 /// input operands as the node already has, the input node is returned.
690 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
691 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
692 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
694 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
695 SDValue Op3, SDValue Op4);
696 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
697 SDValue Op3, SDValue Op4, SDValue Op5);
698 SDNode *UpdateNodeOperands(SDNode *N,
699 const SDValue *Ops, unsigned NumOps);
701 /// SelectNodeTo - These are used for target selectors to *mutate* the
702 /// specified node to have the specified return type, Target opcode, and
703 /// operands. Note that target opcodes are stored as
704 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
705 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
706 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
707 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
708 SDValue Op1, SDValue Op2);
709 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
710 SDValue Op1, SDValue Op2, SDValue Op3);
711 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
712 const SDValue *Ops, unsigned NumOps);
713 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
714 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
715 EVT VT2, const SDValue *Ops, unsigned NumOps);
716 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
717 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
718 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
719 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
721 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
722 EVT VT2, SDValue Op1);
723 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
724 EVT VT2, SDValue Op1, SDValue Op2);
725 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
726 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
727 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
728 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
729 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
730 const SDValue *Ops, unsigned NumOps);
732 /// MorphNodeTo - This *mutates* the specified node to have the specified
733 /// return type, opcode, and operands.
734 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
735 const SDValue *Ops, unsigned NumOps);
737 /// getMachineNode - These are used for target selectors to create a new node
738 /// with specified return type(s), MachineInstr opcode, and operands.
740 /// Note that getMachineNode returns the resultant node. If there is already
741 /// a node of the specified opcode and operands, it returns that node instead
742 /// of the current one.
743 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
744 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
746 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
747 SDValue Op1, SDValue Op2);
748 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
749 SDValue Op1, SDValue Op2, SDValue Op3);
750 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
751 const SDValue *Ops, unsigned NumOps);
752 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2);
753 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
755 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
756 EVT VT2, SDValue Op1, SDValue Op2);
757 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
758 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
759 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
760 const SDValue *Ops, unsigned NumOps);
761 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
762 EVT VT3, SDValue Op1, SDValue Op2);
763 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
764 EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
765 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
766 EVT VT3, const SDValue *Ops, unsigned NumOps);
767 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
768 EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
769 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
770 const std::vector<EVT> &ResultTys, const SDValue *Ops,
772 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
773 const SDValue *Ops, unsigned NumOps);
775 /// getTargetExtractSubreg - A convenience function for creating
776 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
777 SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
780 /// getTargetInsertSubreg - A convenience function for creating
781 /// TargetInstrInfo::INSERT_SUBREG nodes.
782 SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
783 SDValue Operand, SDValue Subreg);
785 /// getNodeIfExists - Get the specified node if it's already available, or
786 /// else return NULL.
787 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
788 const SDValue *Ops, unsigned NumOps);
790 /// getDbgValue - Creates a SDDbgValue node.
792 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
793 DebugLoc DL, unsigned O);
794 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
795 DebugLoc DL, unsigned O);
796 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
797 DebugLoc DL, unsigned O);
799 /// DAGUpdateListener - Clients of various APIs that cause global effects on
800 /// the DAG can optionally implement this interface. This allows the clients
801 /// to handle the various sorts of updates that happen.
802 class DAGUpdateListener {
804 virtual ~DAGUpdateListener();
806 /// NodeDeleted - The node N that was deleted and, if E is not null, an
807 /// equivalent node E that replaced it.
808 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0;
810 /// NodeUpdated - The node N that was updated.
811 virtual void NodeUpdated(SDNode *N) = 0;
814 /// RemoveDeadNode - Remove the specified node from the system. If any of its
815 /// operands then becomes dead, remove them as well. Inform UpdateListener
816 /// for each node deleted.
817 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0);
819 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
820 /// given list, and any nodes that become unreachable as a result.
821 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
822 DAGUpdateListener *UpdateListener = 0);
824 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
825 /// This can cause recursive merging of nodes in the DAG. Use the first
826 /// version if 'From' is known to have a single result, use the second
827 /// if you have two nodes with identical results (or if 'To' has a superset
828 /// of the results of 'From'), use the third otherwise.
830 /// These methods all take an optional UpdateListener, which (if not null) is
831 /// informed about nodes that are deleted and modified due to recursive
832 /// changes in the dag.
834 /// These functions only replace all existing uses. It's possible that as
835 /// these replacements are being performed, CSE may cause the From node
836 /// to be given new uses. These new uses of From are left in place, and
837 /// not automatically transfered to To.
839 void ReplaceAllUsesWith(SDValue From, SDValue Op,
840 DAGUpdateListener *UpdateListener = 0);
841 void ReplaceAllUsesWith(SDNode *From, SDNode *To,
842 DAGUpdateListener *UpdateListener = 0);
843 void ReplaceAllUsesWith(SDNode *From, const SDValue *To,
844 DAGUpdateListener *UpdateListener = 0);
846 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
847 /// uses of other values produced by From.Val alone.
848 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
849 DAGUpdateListener *UpdateListener = 0);
851 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
852 /// for multiple values at once. This correctly handles the case where
853 /// there is an overlap between the From values and the To values.
854 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
856 DAGUpdateListener *UpdateListener = 0);
858 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
859 /// assign a unique node id for each node in the DAG based on their
860 /// topological order. Returns the number of nodes.
861 unsigned AssignTopologicalOrder();
863 /// RepositionNode - Move node N in the AllNodes list to be immediately
864 /// before the given iterator Position. This may be used to update the
865 /// topological ordering when the list of nodes is modified.
866 void RepositionNode(allnodes_iterator Position, SDNode *N) {
867 AllNodes.insert(Position, AllNodes.remove(N));
870 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
872 static bool isCommutativeBinOp(unsigned Opcode) {
873 // FIXME: This should get its info from the td file, so that we can include
890 case ISD::ADDE: return true;
891 default: return false;
895 /// AssignOrdering - Assign an order to the SDNode.
896 void AssignOrdering(const SDNode *SD, unsigned Order);
898 /// GetOrdering - Get the order for the SDNode.
899 unsigned GetOrdering(const SDNode *SD) const;
901 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
902 /// value is produced by SD.
903 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
905 /// GetDbgValues - Get the debug values which reference the given SDNode.
906 SmallVector<SDDbgValue*,2> &GetDbgValues(const SDNode* SD) {
907 return DbgInfo->getSDDbgValues(SD);
910 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
911 /// with this SelectionDAG.
912 bool hasDebugValues() const { return !DbgInfo->empty(); }
914 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
915 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
916 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
917 return DbgInfo->ByvalParmDbgBegin();
919 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
920 return DbgInfo->ByvalParmDbgEnd();
925 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
926 /// specified value type. If minAlign is specified, the slot size will have
927 /// at least that alignment.
928 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
930 /// CreateStackTemporary - Create a stack temporary suitable for holding
931 /// either of the specified value types.
932 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
934 /// FoldConstantArithmetic -
935 SDValue FoldConstantArithmetic(unsigned Opcode,
937 ConstantSDNode *Cst1,
938 ConstantSDNode *Cst2);
940 /// FoldSetCC - Constant fold a setcc to true or false.
941 SDValue FoldSetCC(EVT VT, SDValue N1,
942 SDValue N2, ISD::CondCode Cond, DebugLoc dl);
944 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
945 /// use this predicate to simplify operations downstream.
946 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
948 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
949 /// use this predicate to simplify operations downstream. Op and Mask are
950 /// known to be the same type.
951 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
954 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
955 /// known to be either zero or one and return them in the KnownZero/KnownOne
956 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
957 /// processing. Targets can implement the computeMaskedBitsForTargetNode
958 /// method in the TargetLowering class to allow target nodes to be understood.
959 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero,
960 APInt &KnownOne, unsigned Depth = 0) const;
962 /// ComputeNumSignBits - Return the number of times the sign bit of the
963 /// register is replicated into the other bits. We know that at least 1 bit
964 /// is always equal to the sign bit (itself), but other cases can give us
965 /// information. For example, immediately after an "SRA X, 2", we know that
966 /// the top 3 bits are all equal to each other, so we return 3. Targets can
967 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
968 /// class to allow target nodes to be understood.
969 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
971 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
972 bool isKnownNeverNaN(SDValue Op) const;
974 /// isKnownNeverZero - Test whether the given SDValue is known to never be
975 /// positive or negative Zero.
976 bool isKnownNeverZero(SDValue Op) const;
978 /// isEqualTo - Test whether two SDValues are known to compare equal. This
979 /// is true if they are the same value, or if one is negative zero and the
980 /// other positive zero.
981 bool isEqualTo(SDValue A, SDValue B) const;
983 /// isVerifiedDebugInfoDesc - Returns true if the specified SDValue has
984 /// been verified as a debug information descriptor.
985 bool isVerifiedDebugInfoDesc(SDValue Op) const;
987 /// UnrollVectorOp - Utility function used by legalize and lowering to
988 /// "unroll" a vector operation by splitting out the scalars and operating
989 /// on each element individually. If the ResNE is 0, fully unroll the vector
990 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
991 /// If the ResNE is greater than the width of the vector op, unroll the
992 /// vector op and fill the end of the resulting vector with UNDEFS.
993 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
995 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
996 /// location that is 'Dist' units away from the location that the 'Base' load
998 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
999 unsigned Bytes, int Dist) const;
1001 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1002 /// it cannot be inferred.
1003 unsigned InferPtrAlignment(SDValue Ptr) const;
1006 bool RemoveNodeFromCSEMaps(SDNode *N);
1007 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener);
1008 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1009 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1011 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1014 void DeleteNodeNotInCSEMaps(SDNode *N);
1015 void DeallocateNode(SDNode *N);
1017 unsigned getEVTAlignment(EVT MemoryVT) const;
1019 void allnodes_clear();
1021 /// VTList - List of non-single value types.
1022 std::vector<SDVTList> VTList;
1024 /// CondCodeNodes - Maps to auto-CSE operations.
1025 std::vector<CondCodeSDNode*> CondCodeNodes;
1027 std::vector<SDNode*> ValueTypeNodes;
1028 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1029 StringMap<SDNode*> ExternalSymbols;
1031 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1034 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1035 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1036 static nodes_iterator nodes_begin(SelectionDAG *G) {
1037 return G->allnodes_begin();
1039 static nodes_iterator nodes_end(SelectionDAG *G) {
1040 return G->allnodes_end();
1044 } // end namespace llvm