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 getExtLoad(ISD::LoadExtType ExtType, EVT VT, DebugLoc dl,
640 SDValue Chain, SDValue Ptr, const Value *SV,
641 int SVOffset, EVT MemVT, bool isVolatile,
642 bool isNonTemporal, unsigned Alignment);*/
643 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
644 SDValue Offset, ISD::MemIndexedMode AM);
645 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
647 SDValue Chain, SDValue Ptr, SDValue Offset,
648 const Value *SV, int SVOffset, EVT MemVT,
649 bool isVolatile, bool isNonTemporal, unsigned Alignment);
650 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
652 SDValue Chain, SDValue Ptr, SDValue Offset,
653 MachinePointerInfo PtrInfo, EVT MemVT,
654 bool isVolatile, bool isNonTemporal, unsigned Alignment);
655 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
657 SDValue Chain, SDValue Ptr, SDValue Offset,
658 EVT MemVT, MachineMemOperand *MMO);
660 /// getStore - Helper function to build ISD::STORE nodes.
662 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
663 MachinePointerInfo PtrInfo, bool isVolatile,
664 bool isNonTemporal, unsigned Alignment);
665 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
666 const Value *V, int SVOffset, bool isVolatile,
667 bool isNonTemporal, unsigned Alignment);
668 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
669 MachineMemOperand *MMO);
670 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
671 MachinePointerInfo PtrInfo, EVT TVT,
672 bool isNonTemporal, bool isVolatile,
674 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
675 const Value *SV, int SVOffset, EVT TVT,
676 bool isNonTemporal, bool isVolatile,
678 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
679 EVT TVT, MachineMemOperand *MMO);
680 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base,
681 SDValue Offset, ISD::MemIndexedMode AM);
683 /// getSrcValue - Construct a node to track a Value* through the backend.
684 SDValue getSrcValue(const Value *v);
686 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
687 SDValue getMDNode(const MDNode *MD);
689 /// getShiftAmountOperand - Return the specified value casted to
690 /// the target's desired shift amount type.
691 SDValue getShiftAmountOperand(SDValue Op);
693 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
694 /// specified operands. If the resultant node already exists in the DAG,
695 /// this does not modify the specified node, instead it returns the node that
696 /// already exists. If the resultant node does not exist in the DAG, the
697 /// input node is returned. As a degenerate case, if you specify the same
698 /// input operands as the node already has, the input node is returned.
699 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
700 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
701 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
703 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
704 SDValue Op3, SDValue Op4);
705 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
706 SDValue Op3, SDValue Op4, SDValue Op5);
707 SDNode *UpdateNodeOperands(SDNode *N,
708 const SDValue *Ops, unsigned NumOps);
710 /// SelectNodeTo - These are used for target selectors to *mutate* the
711 /// specified node to have the specified return type, Target opcode, and
712 /// operands. Note that target opcodes are stored as
713 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
714 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
715 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
716 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
717 SDValue Op1, SDValue Op2);
718 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
719 SDValue Op1, SDValue Op2, SDValue Op3);
720 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
721 const SDValue *Ops, unsigned NumOps);
722 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
723 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
724 EVT VT2, const SDValue *Ops, unsigned NumOps);
725 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
726 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
727 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
728 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
730 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
731 EVT VT2, SDValue Op1);
732 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
733 EVT VT2, SDValue Op1, SDValue Op2);
734 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
735 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
736 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
737 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
738 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
739 const SDValue *Ops, unsigned NumOps);
741 /// MorphNodeTo - This *mutates* the specified node to have the specified
742 /// return type, opcode, and operands.
743 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
744 const SDValue *Ops, unsigned NumOps);
746 /// getMachineNode - These are used for target selectors to create a new node
747 /// with specified return type(s), MachineInstr opcode, and operands.
749 /// Note that getMachineNode returns the resultant node. If there is already
750 /// a node of the specified opcode and operands, it returns that node instead
751 /// of the current one.
752 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
753 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
755 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
756 SDValue Op1, SDValue Op2);
757 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
758 SDValue Op1, SDValue Op2, SDValue Op3);
759 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
760 const SDValue *Ops, unsigned NumOps);
761 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2);
762 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
764 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
765 EVT VT2, SDValue Op1, SDValue Op2);
766 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
767 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
768 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
769 const SDValue *Ops, unsigned NumOps);
770 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
771 EVT VT3, SDValue Op1, SDValue Op2);
772 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
773 EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
774 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
775 EVT VT3, const SDValue *Ops, unsigned NumOps);
776 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
777 EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
778 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
779 const std::vector<EVT> &ResultTys, const SDValue *Ops,
781 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
782 const SDValue *Ops, unsigned NumOps);
784 /// getTargetExtractSubreg - A convenience function for creating
785 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
786 SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
789 /// getTargetInsertSubreg - A convenience function for creating
790 /// TargetInstrInfo::INSERT_SUBREG nodes.
791 SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
792 SDValue Operand, SDValue Subreg);
794 /// getNodeIfExists - Get the specified node if it's already available, or
795 /// else return NULL.
796 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
797 const SDValue *Ops, unsigned NumOps);
799 /// getDbgValue - Creates a SDDbgValue node.
801 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
802 DebugLoc DL, unsigned O);
803 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
804 DebugLoc DL, unsigned O);
805 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
806 DebugLoc DL, unsigned O);
808 /// DAGUpdateListener - Clients of various APIs that cause global effects on
809 /// the DAG can optionally implement this interface. This allows the clients
810 /// to handle the various sorts of updates that happen.
811 class DAGUpdateListener {
813 virtual ~DAGUpdateListener();
815 /// NodeDeleted - The node N that was deleted and, if E is not null, an
816 /// equivalent node E that replaced it.
817 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0;
819 /// NodeUpdated - The node N that was updated.
820 virtual void NodeUpdated(SDNode *N) = 0;
823 /// RemoveDeadNode - Remove the specified node from the system. If any of its
824 /// operands then becomes dead, remove them as well. Inform UpdateListener
825 /// for each node deleted.
826 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0);
828 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
829 /// given list, and any nodes that become unreachable as a result.
830 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
831 DAGUpdateListener *UpdateListener = 0);
833 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
834 /// This can cause recursive merging of nodes in the DAG. Use the first
835 /// version if 'From' is known to have a single result, use the second
836 /// if you have two nodes with identical results (or if 'To' has a superset
837 /// of the results of 'From'), use the third otherwise.
839 /// These methods all take an optional UpdateListener, which (if not null) is
840 /// informed about nodes that are deleted and modified due to recursive
841 /// changes in the dag.
843 /// These functions only replace all existing uses. It's possible that as
844 /// these replacements are being performed, CSE may cause the From node
845 /// to be given new uses. These new uses of From are left in place, and
846 /// not automatically transfered to To.
848 void ReplaceAllUsesWith(SDValue From, SDValue Op,
849 DAGUpdateListener *UpdateListener = 0);
850 void ReplaceAllUsesWith(SDNode *From, SDNode *To,
851 DAGUpdateListener *UpdateListener = 0);
852 void ReplaceAllUsesWith(SDNode *From, const SDValue *To,
853 DAGUpdateListener *UpdateListener = 0);
855 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
856 /// uses of other values produced by From.Val alone.
857 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
858 DAGUpdateListener *UpdateListener = 0);
860 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
861 /// for multiple values at once. This correctly handles the case where
862 /// there is an overlap between the From values and the To values.
863 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
865 DAGUpdateListener *UpdateListener = 0);
867 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
868 /// assign a unique node id for each node in the DAG based on their
869 /// topological order. Returns the number of nodes.
870 unsigned AssignTopologicalOrder();
872 /// RepositionNode - Move node N in the AllNodes list to be immediately
873 /// before the given iterator Position. This may be used to update the
874 /// topological ordering when the list of nodes is modified.
875 void RepositionNode(allnodes_iterator Position, SDNode *N) {
876 AllNodes.insert(Position, AllNodes.remove(N));
879 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
881 static bool isCommutativeBinOp(unsigned Opcode) {
882 // FIXME: This should get its info from the td file, so that we can include
899 case ISD::ADDE: return true;
900 default: return false;
904 /// AssignOrdering - Assign an order to the SDNode.
905 void AssignOrdering(const SDNode *SD, unsigned Order);
907 /// GetOrdering - Get the order for the SDNode.
908 unsigned GetOrdering(const SDNode *SD) const;
910 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
911 /// value is produced by SD.
912 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
914 /// GetDbgValues - Get the debug values which reference the given SDNode.
915 SmallVector<SDDbgValue*,2> &GetDbgValues(const SDNode* SD) {
916 return DbgInfo->getSDDbgValues(SD);
919 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
920 /// with this SelectionDAG.
921 bool hasDebugValues() const { return !DbgInfo->empty(); }
923 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
924 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
925 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
926 return DbgInfo->ByvalParmDbgBegin();
928 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
929 return DbgInfo->ByvalParmDbgEnd();
934 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
935 /// specified value type. If minAlign is specified, the slot size will have
936 /// at least that alignment.
937 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
939 /// CreateStackTemporary - Create a stack temporary suitable for holding
940 /// either of the specified value types.
941 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
943 /// FoldConstantArithmetic -
944 SDValue FoldConstantArithmetic(unsigned Opcode,
946 ConstantSDNode *Cst1,
947 ConstantSDNode *Cst2);
949 /// FoldSetCC - Constant fold a setcc to true or false.
950 SDValue FoldSetCC(EVT VT, SDValue N1,
951 SDValue N2, ISD::CondCode Cond, DebugLoc dl);
953 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
954 /// use this predicate to simplify operations downstream.
955 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
957 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
958 /// use this predicate to simplify operations downstream. Op and Mask are
959 /// known to be the same type.
960 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
963 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
964 /// known to be either zero or one and return them in the KnownZero/KnownOne
965 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
966 /// processing. Targets can implement the computeMaskedBitsForTargetNode
967 /// method in the TargetLowering class to allow target nodes to be understood.
968 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero,
969 APInt &KnownOne, unsigned Depth = 0) const;
971 /// ComputeNumSignBits - Return the number of times the sign bit of the
972 /// register is replicated into the other bits. We know that at least 1 bit
973 /// is always equal to the sign bit (itself), but other cases can give us
974 /// information. For example, immediately after an "SRA X, 2", we know that
975 /// the top 3 bits are all equal to each other, so we return 3. Targets can
976 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
977 /// class to allow target nodes to be understood.
978 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
980 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
981 bool isKnownNeverNaN(SDValue Op) const;
983 /// isKnownNeverZero - Test whether the given SDValue is known to never be
984 /// positive or negative Zero.
985 bool isKnownNeverZero(SDValue Op) const;
987 /// isEqualTo - Test whether two SDValues are known to compare equal. This
988 /// is true if they are the same value, or if one is negative zero and the
989 /// other positive zero.
990 bool isEqualTo(SDValue A, SDValue B) const;
992 /// isVerifiedDebugInfoDesc - Returns true if the specified SDValue has
993 /// been verified as a debug information descriptor.
994 bool isVerifiedDebugInfoDesc(SDValue Op) const;
996 /// UnrollVectorOp - Utility function used by legalize and lowering to
997 /// "unroll" a vector operation by splitting out the scalars and operating
998 /// on each element individually. If the ResNE is 0, fully unroll the vector
999 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1000 /// If the ResNE is greater than the width of the vector op, unroll the
1001 /// vector op and fill the end of the resulting vector with UNDEFS.
1002 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1004 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1005 /// location that is 'Dist' units away from the location that the 'Base' load
1006 /// is loading from.
1007 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1008 unsigned Bytes, int Dist) const;
1010 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1011 /// it cannot be inferred.
1012 unsigned InferPtrAlignment(SDValue Ptr) const;
1015 bool RemoveNodeFromCSEMaps(SDNode *N);
1016 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener);
1017 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1018 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1020 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1023 void DeleteNodeNotInCSEMaps(SDNode *N);
1024 void DeallocateNode(SDNode *N);
1026 unsigned getEVTAlignment(EVT MemoryVT) const;
1028 void allnodes_clear();
1030 /// VTList - List of non-single value types.
1031 std::vector<SDVTList> VTList;
1033 /// CondCodeNodes - Maps to auto-CSE operations.
1034 std::vector<CondCodeSDNode*> CondCodeNodes;
1036 std::vector<SDNode*> ValueTypeNodes;
1037 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1038 StringMap<SDNode*> ExternalSymbols;
1040 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1043 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1044 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1045 static nodes_iterator nodes_begin(SelectionDAG *G) {
1046 return G->allnodes_begin();
1048 static nodes_iterator nodes_end(SelectionDAG *G) {
1049 return G->allnodes_end();
1053 } // end namespace llvm