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 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
100 DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> >::iterator I =
101 DbgValMap.find(Node);
102 if (I != DbgValMap.end())
104 return ArrayRef<SDDbgValue*>();
107 typedef SmallVector<SDDbgValue*,32>::iterator DbgIterator;
108 DbgIterator DbgBegin() { return DbgValues.begin(); }
109 DbgIterator DbgEnd() { return DbgValues.end(); }
110 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
111 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
115 Unrestricted, // Combine may create illegal operations and illegal types.
116 NoIllegalTypes, // Combine may create illegal operations but no illegal types.
117 NoIllegalOperations // Combine may only create legal operations and types.
121 void checkForCycles(const SDNode *N);
122 void checkForCycles(const SelectionDAG *DAG);
124 /// SelectionDAG class - This is used to represent a portion of an LLVM function
125 /// in a low-level Data Dependence DAG representation suitable for instruction
126 /// selection. This DAG is constructed as the first step of instruction
127 /// selection in order to allow implementation of machine specific optimizations
128 /// and code simplifications.
130 /// The representation used by the SelectionDAG is a target-independent
131 /// representation, which has some similarities to the GCC RTL representation,
132 /// but is significantly more simple, powerful, and is a graph form instead of a
136 const TargetMachine &TM;
137 const TargetLowering &TLI;
138 const TargetSelectionDAGInfo &TSI;
140 LLVMContext *Context;
142 /// EntryNode - The starting token.
145 /// Root - The root of the entire DAG.
148 /// AllNodes - A linked list of nodes in the current DAG.
149 ilist<SDNode> AllNodes;
151 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
152 /// pool allocation with recycling.
153 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
154 AlignOf<MostAlignedSDNode>::Alignment>
157 /// NodeAllocator - Pool allocation for nodes.
158 NodeAllocatorType NodeAllocator;
160 /// CSEMap - This structure is used to memoize nodes, automatically performing
161 /// CSE with existing nodes when a duplicate is requested.
162 FoldingSet<SDNode> CSEMap;
164 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
165 BumpPtrAllocator OperandAllocator;
167 /// Allocator - Pool allocation for misc. objects that are created once per
169 BumpPtrAllocator Allocator;
171 /// SDNodeOrdering - The ordering of the SDNodes. It roughly corresponds to
172 /// the ordering of the original LLVM instructions.
173 SDNodeOrdering *Ordering;
175 /// DbgInfo - Tracks dbg_value information through SDISel.
178 /// setGraphColorHelper - Implementation of setSubgraphColor.
179 /// Return whether we had to truncate the search.
181 bool setSubgraphColorHelper(SDNode *N, const char *Color,
182 DenseSet<SDNode *> &visited,
183 int level, bool &printed);
185 void operator=(const SelectionDAG&); // Do not implement.
186 SelectionDAG(const SelectionDAG&); // Do not implement.
189 explicit SelectionDAG(const TargetMachine &TM);
192 /// init - Prepare this SelectionDAG to process code in the given
195 void init(MachineFunction &mf);
197 /// clear - Clear state and free memory necessary to make this
198 /// SelectionDAG ready to process a new block.
202 MachineFunction &getMachineFunction() const { return *MF; }
203 const TargetMachine &getTarget() const { return TM; }
204 const TargetLowering &getTargetLoweringInfo() const { return TLI; }
205 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
206 LLVMContext *getContext() const {return Context; }
208 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
210 void viewGraph(const std::string &Title);
214 std::map<const SDNode *, std::string> NodeGraphAttrs;
217 /// clearGraphAttrs - Clear all previously defined node graph attributes.
218 /// Intended to be used from a debugging tool (eg. gdb).
219 void clearGraphAttrs();
221 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
223 void setGraphAttrs(const SDNode *N, const char *Attrs);
225 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
226 /// Used from getNodeAttributes.
227 const std::string getGraphAttrs(const SDNode *N) const;
229 /// setGraphColor - Convenience for setting node color attribute.
231 void setGraphColor(const SDNode *N, const char *Color);
233 /// setGraphColor - Convenience for setting subgraph color attribute.
235 void setSubgraphColor(SDNode *N, const char *Color);
237 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
238 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
239 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
240 typedef ilist<SDNode>::iterator allnodes_iterator;
241 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
242 allnodes_iterator allnodes_end() { return AllNodes.end(); }
243 ilist<SDNode>::size_type allnodes_size() const {
244 return AllNodes.size();
247 /// getRoot - Return the root tag of the SelectionDAG.
249 const SDValue &getRoot() const { return Root; }
251 /// getEntryNode - Return the token chain corresponding to the entry of the
253 SDValue getEntryNode() const {
254 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
257 /// setRoot - Set the current root tag of the SelectionDAG.
259 const SDValue &setRoot(SDValue N) {
260 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
261 "DAG root value is not a chain!");
263 checkForCycles(N.getNode());
266 checkForCycles(this);
270 /// Combine - This iterates over the nodes in the SelectionDAG, folding
271 /// certain types of nodes together, or eliminating superfluous nodes. The
272 /// Level argument controls whether Combine is allowed to produce nodes and
273 /// types that are illegal on the target.
274 void Combine(CombineLevel Level, AliasAnalysis &AA,
275 CodeGenOpt::Level OptLevel);
277 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
278 /// only uses types natively supported by the target. Returns "true" if it
279 /// made any changes.
281 /// Note that this is an involved process that may invalidate pointers into
283 bool LegalizeTypes();
285 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
286 /// compatible with the target instruction selector, as indicated by the
287 /// TargetLowering object.
289 /// Note that this is an involved process that may invalidate pointers into
293 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
294 /// that only uses vector math operations supported by the target. This is
295 /// necessary as a separate step from Legalize because unrolling a vector
296 /// operation can introduce illegal types, which requires running
297 /// LegalizeTypes again.
299 /// This returns true if it made any changes; in that case, LegalizeTypes
300 /// is called again before Legalize.
302 /// Note that this is an involved process that may invalidate pointers into
304 bool LegalizeVectors();
306 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
308 void RemoveDeadNodes();
310 /// DeleteNode - Remove the specified node from the system. This node must
311 /// have no referrers.
312 void DeleteNode(SDNode *N);
314 /// getVTList - Return an SDVTList that represents the list of values
316 SDVTList getVTList(EVT VT);
317 SDVTList getVTList(EVT VT1, EVT VT2);
318 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
319 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
320 SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
322 //===--------------------------------------------------------------------===//
323 // Node creation methods.
325 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
326 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
327 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
328 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
329 SDValue getTargetConstant(uint64_t Val, EVT VT) {
330 return getConstant(Val, VT, true);
332 SDValue getTargetConstant(const APInt &Val, EVT VT) {
333 return getConstant(Val, VT, true);
335 SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
336 return getConstant(Val, VT, true);
338 // The forms below that take a double should only be used for simple
339 // constants that can be exactly represented in VT. No checks are made.
340 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
341 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
342 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
343 SDValue getTargetConstantFP(double Val, EVT VT) {
344 return getConstantFP(Val, VT, true);
346 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
347 return getConstantFP(Val, VT, true);
349 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
350 return getConstantFP(Val, VT, true);
352 SDValue getGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
353 int64_t offset = 0, bool isTargetGA = false,
354 unsigned char TargetFlags = 0);
355 SDValue getTargetGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
357 unsigned char TargetFlags = 0) {
358 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
360 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
361 SDValue getTargetFrameIndex(int FI, EVT VT) {
362 return getFrameIndex(FI, VT, true);
364 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
365 unsigned char TargetFlags = 0);
366 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
367 return getJumpTable(JTI, VT, true, TargetFlags);
369 SDValue getConstantPool(const Constant *C, EVT VT,
370 unsigned Align = 0, int Offs = 0, bool isT=false,
371 unsigned char TargetFlags = 0);
372 SDValue getTargetConstantPool(const Constant *C, EVT VT,
373 unsigned Align = 0, int Offset = 0,
374 unsigned char TargetFlags = 0) {
375 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
377 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
378 unsigned Align = 0, int Offs = 0, bool isT=false,
379 unsigned char TargetFlags = 0);
380 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
381 EVT VT, unsigned Align = 0,
382 int Offset = 0, unsigned char TargetFlags=0) {
383 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
385 // When generating a branch to a BB, we don't in general know enough
386 // to provide debug info for the BB at that time, so keep this one around.
387 SDValue getBasicBlock(MachineBasicBlock *MBB);
388 SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl);
389 SDValue getExternalSymbol(const char *Sym, EVT VT);
390 SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT);
391 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
392 unsigned char TargetFlags = 0);
393 SDValue getValueType(EVT);
394 SDValue getRegister(unsigned Reg, EVT VT);
395 SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label);
396 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
397 bool isTarget = false, unsigned char TargetFlags = 0);
399 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) {
400 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
401 getRegister(Reg, N.getValueType()), N);
404 // This version of the getCopyToReg method takes an extra operand, which
405 // indicates that there is potentially an incoming glue value (if Glue is not
406 // null) and that there should be a glue result.
407 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N,
409 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
410 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
411 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
414 // Similar to last getCopyToReg() except parameter Reg is a SDValue
415 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N,
417 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
418 SDValue Ops[] = { Chain, Reg, N, Glue };
419 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
422 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) {
423 SDVTList VTs = getVTList(VT, MVT::Other);
424 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
425 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
428 // This version of the getCopyFromReg method takes an extra operand, which
429 // indicates that there is potentially an incoming glue value (if Glue is not
430 // null) and that there should be a glue result.
431 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT,
433 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
434 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
435 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Glue.getNode() ? 3 : 2);
438 SDValue getCondCode(ISD::CondCode Cond);
440 /// Returns the ConvertRndSat Note: Avoid using this node because it may
441 /// disappear in the future and most targets don't support it.
442 SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy,
444 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
446 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
447 /// elements in VT, which must be a vector type, must match the number of
448 /// mask elements NumElts. A integer mask element equal to -1 is treated as
450 SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2,
451 const int *MaskElts);
453 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
454 /// integer type VT, by either any-extending or truncating it.
455 SDValue getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
457 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
458 /// integer type VT, by either sign-extending or truncating it.
459 SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
461 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
462 /// integer type VT, by either zero-extending or truncating it.
463 SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
465 /// getZeroExtendInReg - Return the expression required to zero extend the Op
466 /// value assuming it was the smaller SrcTy value.
467 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy);
469 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
470 SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT);
472 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
473 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a
475 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) {
476 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
477 SDValue Ops[] = { Chain, Op };
478 return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2);
481 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
482 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have
483 /// a useful DebugLoc.
484 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
486 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
487 SmallVector<SDValue, 4> Ops;
488 Ops.push_back(Chain);
491 Ops.push_back(InGlue);
492 return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0],
493 (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0));
496 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc.
497 SDValue getUNDEF(EVT VT) {
498 return getNode(ISD::UNDEF, DebugLoc(), VT);
501 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
502 /// not have a useful DebugLoc.
503 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
504 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc(), VT);
507 /// getNode - Gets or creates the specified node.
509 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT);
510 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N);
511 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2);
512 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
513 SDValue N1, SDValue N2, SDValue N3);
514 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
515 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
516 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
517 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
519 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
520 const SDUse *Ops, unsigned NumOps);
521 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
522 const SDValue *Ops, unsigned NumOps);
523 SDValue getNode(unsigned Opcode, DebugLoc DL,
524 const std::vector<EVT> &ResultTys,
525 const SDValue *Ops, unsigned NumOps);
526 SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs,
527 const SDValue *Ops, unsigned NumOps);
528 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
529 const SDValue *Ops, unsigned NumOps);
530 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs);
531 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N);
532 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
533 SDValue N1, SDValue N2);
534 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
535 SDValue N1, SDValue N2, SDValue N3);
536 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
537 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
538 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
539 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
542 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
543 /// the incoming stack arguments to be loaded from the stack. This is
544 /// used in tail call lowering to protect stack arguments from being
546 SDValue getStackArgumentTokenFactor(SDValue Chain);
548 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
549 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
550 MachinePointerInfo DstPtrInfo,
551 MachinePointerInfo SrcPtrInfo);
553 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
554 SDValue Size, unsigned Align, bool isVol,
555 MachinePointerInfo DstPtrInfo,
556 MachinePointerInfo SrcPtrInfo);
558 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
559 SDValue Size, unsigned Align, bool isVol,
560 MachinePointerInfo DstPtrInfo);
562 /// getSetCC - Helper function to make it easier to build SetCC's if you just
563 /// have an ISD::CondCode instead of an SDValue.
565 SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
566 ISD::CondCode Cond) {
567 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
568 "Cannot compare scalars to vectors");
569 assert(LHS.getValueType().isVector() == VT.isVector() &&
570 "Cannot compare scalars to vectors");
571 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
574 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
575 /// just have an ISD::CondCode instead of an SDValue.
577 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS,
578 SDValue True, SDValue False, ISD::CondCode Cond) {
579 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
580 LHS, RHS, True, False, getCondCode(Cond));
583 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
584 /// and a source value as input.
585 SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
586 SDValue SV, unsigned Align);
588 /// getAtomic - Gets a node for an atomic op, produces result and chain and
590 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
591 SDValue Ptr, SDValue Cmp, SDValue Swp,
592 MachinePointerInfo PtrInfo, unsigned Alignment,
593 AtomicOrdering Ordering,
594 SynchronizationScope SynchScope);
595 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
596 SDValue Ptr, SDValue Cmp, SDValue Swp,
597 MachineMemOperand *MMO,
598 AtomicOrdering Ordering,
599 SynchronizationScope SynchScope);
601 /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
602 /// and chain and takes 2 operands.
603 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
604 SDValue Ptr, SDValue Val, const Value* PtrVal,
605 unsigned Alignment, AtomicOrdering Ordering,
606 SynchronizationScope SynchScope);
607 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
608 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
609 AtomicOrdering Ordering,
610 SynchronizationScope SynchScope);
612 /// getAtomic - Gets a node for an atomic op, produces result and chain and
614 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
615 SDValue Chain, SDValue Ptr, const Value* PtrVal,
617 AtomicOrdering Ordering,
618 SynchronizationScope SynchScope);
619 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
620 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
621 AtomicOrdering Ordering,
622 SynchronizationScope SynchScope);
624 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
625 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
626 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
627 /// less than FIRST_TARGET_MEMORY_OPCODE.
628 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
629 const EVT *VTs, unsigned NumVTs,
630 const SDValue *Ops, unsigned NumOps,
631 EVT MemVT, MachinePointerInfo PtrInfo,
632 unsigned Align = 0, bool Vol = false,
633 bool ReadMem = true, bool WriteMem = true);
635 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
636 const SDValue *Ops, unsigned NumOps,
637 EVT MemVT, MachinePointerInfo PtrInfo,
638 unsigned Align = 0, bool Vol = false,
639 bool ReadMem = true, bool WriteMem = true);
641 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
642 const SDValue *Ops, unsigned NumOps,
643 EVT MemVT, MachineMemOperand *MMO);
645 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
646 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl);
648 /// getLoad - Loads are not normal binary operators: their result type is not
649 /// determined by their operands, and they produce a value AND a token chain.
651 SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
652 MachinePointerInfo PtrInfo, bool isVolatile,
653 bool isNonTemporal, bool isInvariant, unsigned Alignment,
654 const MDNode *TBAAInfo = 0);
655 SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
656 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
657 EVT MemVT, bool isVolatile,
658 bool isNonTemporal, unsigned Alignment,
659 const MDNode *TBAAInfo = 0);
660 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
661 SDValue Offset, ISD::MemIndexedMode AM);
662 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
664 SDValue Chain, SDValue Ptr, SDValue Offset,
665 MachinePointerInfo PtrInfo, EVT MemVT,
666 bool isVolatile, bool isNonTemporal, bool isInvariant,
667 unsigned Alignment, const MDNode *TBAAInfo = 0);
668 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
670 SDValue Chain, SDValue Ptr, SDValue Offset,
671 EVT MemVT, MachineMemOperand *MMO);
673 /// getStore - Helper function to build ISD::STORE nodes.
675 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
676 MachinePointerInfo PtrInfo, bool isVolatile,
677 bool isNonTemporal, unsigned Alignment,
678 const MDNode *TBAAInfo = 0);
679 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
680 MachineMemOperand *MMO);
681 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
682 MachinePointerInfo PtrInfo, EVT TVT,
683 bool isNonTemporal, bool isVolatile,
685 const MDNode *TBAAInfo = 0);
686 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
687 EVT TVT, MachineMemOperand *MMO);
688 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base,
689 SDValue Offset, ISD::MemIndexedMode AM);
691 /// getSrcValue - Construct a node to track a Value* through the backend.
692 SDValue getSrcValue(const Value *v);
694 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
695 SDValue getMDNode(const MDNode *MD);
697 /// getShiftAmountOperand - Return the specified value casted to
698 /// the target's desired shift amount type.
699 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
701 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
702 /// specified operands. If the resultant node already exists in the DAG,
703 /// this does not modify the specified node, instead it returns the node that
704 /// already exists. If the resultant node does not exist in the DAG, the
705 /// input node is returned. As a degenerate case, if you specify the same
706 /// input operands as the node already has, the input node is returned.
707 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
708 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
709 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
711 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
712 SDValue Op3, SDValue Op4);
713 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
714 SDValue Op3, SDValue Op4, SDValue Op5);
715 SDNode *UpdateNodeOperands(SDNode *N,
716 const SDValue *Ops, unsigned NumOps);
718 /// SelectNodeTo - These are used for target selectors to *mutate* the
719 /// specified node to have the specified return type, Target opcode, and
720 /// operands. Note that target opcodes are stored as
721 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
722 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
723 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
724 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
725 SDValue Op1, SDValue Op2);
726 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
727 SDValue Op1, SDValue Op2, SDValue Op3);
728 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
729 const SDValue *Ops, unsigned NumOps);
730 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
731 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
732 EVT VT2, const SDValue *Ops, unsigned NumOps);
733 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
734 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
735 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
736 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
738 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
739 EVT VT2, SDValue Op1);
740 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
741 EVT VT2, SDValue Op1, SDValue Op2);
742 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
743 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
744 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
745 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
746 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
747 const SDValue *Ops, unsigned NumOps);
749 /// MorphNodeTo - This *mutates* the specified node to have the specified
750 /// return type, opcode, and operands.
751 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
752 const SDValue *Ops, unsigned NumOps);
754 /// getMachineNode - These are used for target selectors to create a new node
755 /// with specified return type(s), MachineInstr opcode, and operands.
757 /// Note that getMachineNode returns the resultant node. If there is already
758 /// a node of the specified opcode and operands, it returns that node instead
759 /// of the current one.
760 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
761 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
763 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
764 SDValue Op1, SDValue Op2);
765 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
766 SDValue Op1, SDValue Op2, SDValue Op3);
767 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
768 const SDValue *Ops, unsigned NumOps);
769 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2);
770 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
772 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
773 EVT VT2, SDValue Op1, SDValue Op2);
774 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
775 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
776 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
777 const SDValue *Ops, unsigned NumOps);
778 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
779 EVT VT3, SDValue Op1, SDValue Op2);
780 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
781 EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
782 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
783 EVT VT3, const SDValue *Ops, unsigned NumOps);
784 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
785 EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
786 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
787 const std::vector<EVT> &ResultTys, const SDValue *Ops,
789 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
790 const SDValue *Ops, unsigned NumOps);
792 /// getTargetExtractSubreg - A convenience function for creating
793 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
794 SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
797 /// getTargetInsertSubreg - A convenience function for creating
798 /// TargetInstrInfo::INSERT_SUBREG nodes.
799 SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
800 SDValue Operand, SDValue Subreg);
802 /// getNodeIfExists - Get the specified node if it's already available, or
803 /// else return NULL.
804 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
805 const SDValue *Ops, unsigned NumOps);
807 /// getDbgValue - Creates a SDDbgValue node.
809 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
810 DebugLoc DL, unsigned O);
811 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
812 DebugLoc DL, unsigned O);
813 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
814 DebugLoc DL, unsigned O);
816 /// DAGUpdateListener - Clients of various APIs that cause global effects on
817 /// the DAG can optionally implement this interface. This allows the clients
818 /// to handle the various sorts of updates that happen.
819 class DAGUpdateListener {
821 virtual ~DAGUpdateListener();
823 /// NodeDeleted - The node N that was deleted and, if E is not null, an
824 /// equivalent node E that replaced it.
825 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0;
827 /// NodeUpdated - The node N that was updated.
828 virtual void NodeUpdated(SDNode *N) = 0;
831 /// RemoveDeadNode - Remove the specified node from the system. If any of its
832 /// operands then becomes dead, remove them as well. Inform UpdateListener
833 /// for each node deleted.
834 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0);
836 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
837 /// given list, and any nodes that become unreachable as a result.
838 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
839 DAGUpdateListener *UpdateListener = 0);
841 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
842 /// This can cause recursive merging of nodes in the DAG. Use the first
843 /// version if 'From' is known to have a single result, use the second
844 /// if you have two nodes with identical results (or if 'To' has a superset
845 /// of the results of 'From'), use the third otherwise.
847 /// These methods all take an optional UpdateListener, which (if not null) is
848 /// informed about nodes that are deleted and modified due to recursive
849 /// changes in the dag.
851 /// These functions only replace all existing uses. It's possible that as
852 /// these replacements are being performed, CSE may cause the From node
853 /// to be given new uses. These new uses of From are left in place, and
854 /// not automatically transferred to To.
856 void ReplaceAllUsesWith(SDValue From, SDValue Op,
857 DAGUpdateListener *UpdateListener = 0);
858 void ReplaceAllUsesWith(SDNode *From, SDNode *To,
859 DAGUpdateListener *UpdateListener = 0);
860 void ReplaceAllUsesWith(SDNode *From, const SDValue *To,
861 DAGUpdateListener *UpdateListener = 0);
863 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
864 /// uses of other values produced by From.Val alone.
865 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
866 DAGUpdateListener *UpdateListener = 0);
868 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
869 /// for multiple values at once. This correctly handles the case where
870 /// there is an overlap between the From values and the To values.
871 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
873 DAGUpdateListener *UpdateListener = 0);
875 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
876 /// assign a unique node id for each node in the DAG based on their
877 /// topological order. Returns the number of nodes.
878 unsigned AssignTopologicalOrder();
880 /// RepositionNode - Move node N in the AllNodes list to be immediately
881 /// before the given iterator Position. This may be used to update the
882 /// topological ordering when the list of nodes is modified.
883 void RepositionNode(allnodes_iterator Position, SDNode *N) {
884 AllNodes.insert(Position, AllNodes.remove(N));
887 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
889 static bool isCommutativeBinOp(unsigned Opcode) {
890 // FIXME: This should get its info from the td file, so that we can include
907 case ISD::ADDE: return true;
908 default: return false;
912 /// AssignOrdering - Assign an order to the SDNode.
913 void AssignOrdering(const SDNode *SD, unsigned Order);
915 /// GetOrdering - Get the order for the SDNode.
916 unsigned GetOrdering(const SDNode *SD) const;
918 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
919 /// value is produced by SD.
920 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
922 /// GetDbgValues - Get the debug values which reference the given SDNode.
923 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
924 return DbgInfo->getSDDbgValues(SD);
927 /// TransferDbgValues - Transfer SDDbgValues.
928 void TransferDbgValues(SDValue From, SDValue To);
930 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
931 /// with this SelectionDAG.
932 bool hasDebugValues() const { return !DbgInfo->empty(); }
934 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
935 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
936 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
937 return DbgInfo->ByvalParmDbgBegin();
939 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
940 return DbgInfo->ByvalParmDbgEnd();
945 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
946 /// specified value type. If minAlign is specified, the slot size will have
947 /// at least that alignment.
948 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
950 /// CreateStackTemporary - Create a stack temporary suitable for holding
951 /// either of the specified value types.
952 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
954 /// FoldConstantArithmetic -
955 SDValue FoldConstantArithmetic(unsigned Opcode,
957 ConstantSDNode *Cst1,
958 ConstantSDNode *Cst2);
960 /// FoldSetCC - Constant fold a setcc to true or false.
961 SDValue FoldSetCC(EVT VT, SDValue N1,
962 SDValue N2, ISD::CondCode Cond, DebugLoc dl);
964 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
965 /// use this predicate to simplify operations downstream.
966 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
968 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
969 /// use this predicate to simplify operations downstream. Op and Mask are
970 /// known to be the same type.
971 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
974 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
975 /// known to be either zero or one and return them in the KnownZero/KnownOne
976 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
977 /// processing. Targets can implement the computeMaskedBitsForTargetNode
978 /// method in the TargetLowering class to allow target nodes to be understood.
979 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero,
980 APInt &KnownOne, unsigned Depth = 0) const;
982 /// ComputeNumSignBits - Return the number of times the sign bit of the
983 /// register is replicated into the other bits. We know that at least 1 bit
984 /// is always equal to the sign bit (itself), but other cases can give us
985 /// information. For example, immediately after an "SRA X, 2", we know that
986 /// the top 3 bits are all equal to each other, so we return 3. Targets can
987 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
988 /// class to allow target nodes to be understood.
989 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
991 /// isBaseWithConstantOffset - Return true if the specified operand is an
992 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
993 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
994 /// semantics as an ADD. This handles the equivalence:
995 /// X|Cst == X+Cst iff X&Cst = 0.
996 bool isBaseWithConstantOffset(SDValue Op) const;
998 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
999 bool isKnownNeverNaN(SDValue Op) const;
1001 /// isKnownNeverZero - Test whether the given SDValue is known to never be
1002 /// positive or negative Zero.
1003 bool isKnownNeverZero(SDValue Op) const;
1005 /// isEqualTo - Test whether two SDValues are known to compare equal. This
1006 /// is true if they are the same value, or if one is negative zero and the
1007 /// other positive zero.
1008 bool isEqualTo(SDValue A, SDValue B) const;
1010 /// UnrollVectorOp - Utility function used by legalize and lowering to
1011 /// "unroll" a vector operation by splitting out the scalars and operating
1012 /// on each element individually. If the ResNE is 0, fully unroll the vector
1013 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1014 /// If the ResNE is greater than the width of the vector op, unroll the
1015 /// vector op and fill the end of the resulting vector with UNDEFS.
1016 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1018 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1019 /// location that is 'Dist' units away from the location that the 'Base' load
1020 /// is loading from.
1021 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1022 unsigned Bytes, int Dist) const;
1024 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1025 /// it cannot be inferred.
1026 unsigned InferPtrAlignment(SDValue Ptr) const;
1029 bool RemoveNodeFromCSEMaps(SDNode *N);
1030 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener);
1031 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1032 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1034 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1037 void DeleteNodeNotInCSEMaps(SDNode *N);
1038 void DeallocateNode(SDNode *N);
1040 unsigned getEVTAlignment(EVT MemoryVT) const;
1042 void allnodes_clear();
1044 /// VTList - List of non-single value types.
1045 std::vector<SDVTList> VTList;
1047 /// CondCodeNodes - Maps to auto-CSE operations.
1048 std::vector<CondCodeSDNode*> CondCodeNodes;
1050 std::vector<SDNode*> ValueTypeNodes;
1051 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1052 StringMap<SDNode*> ExternalSymbols;
1054 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1057 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1058 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1059 static nodes_iterator nodes_begin(SelectionDAG *G) {
1060 return G->allnodes_begin();
1062 static nodes_iterator nodes_end(SelectionDAG *G) {
1063 return G->allnodes_end();
1067 } // end namespace llvm