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(); }
117 AfterLegalizeVectorOps,
122 void checkForCycles(const SDNode *N);
123 void checkForCycles(const SelectionDAG *DAG);
125 /// SelectionDAG class - This is used to represent a portion of an LLVM function
126 /// in a low-level Data Dependence DAG representation suitable for instruction
127 /// selection. This DAG is constructed as the first step of instruction
128 /// selection in order to allow implementation of machine specific optimizations
129 /// and code simplifications.
131 /// The representation used by the SelectionDAG is a target-independent
132 /// representation, which has some similarities to the GCC RTL representation,
133 /// but is significantly more simple, powerful, and is a graph form instead of a
137 const TargetMachine &TM;
138 const TargetLowering &TLI;
139 const TargetSelectionDAGInfo &TSI;
141 LLVMContext *Context;
143 /// EntryNode - The starting token.
146 /// Root - The root of the entire DAG.
149 /// AllNodes - A linked list of nodes in the current DAG.
150 ilist<SDNode> AllNodes;
152 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
153 /// pool allocation with recycling.
154 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
155 AlignOf<MostAlignedSDNode>::Alignment>
158 /// NodeAllocator - Pool allocation for nodes.
159 NodeAllocatorType NodeAllocator;
161 /// CSEMap - This structure is used to memoize nodes, automatically performing
162 /// CSE with existing nodes when a duplicate is requested.
163 FoldingSet<SDNode> CSEMap;
165 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
166 BumpPtrAllocator OperandAllocator;
168 /// Allocator - Pool allocation for misc. objects that are created once per
170 BumpPtrAllocator Allocator;
172 /// SDNodeOrdering - The ordering of the SDNodes. It roughly corresponds to
173 /// the ordering of the original LLVM instructions.
174 SDNodeOrdering *Ordering;
176 /// DbgInfo - Tracks dbg_value information through SDISel.
179 /// setGraphColorHelper - Implementation of setSubgraphColor.
180 /// Return whether we had to truncate the search.
182 bool setSubgraphColorHelper(SDNode *N, const char *Color,
183 DenseSet<SDNode *> &visited,
184 int level, bool &printed);
186 void operator=(const SelectionDAG&); // Do not implement.
187 SelectionDAG(const SelectionDAG&); // Do not implement.
190 explicit SelectionDAG(const TargetMachine &TM);
193 /// init - Prepare this SelectionDAG to process code in the given
196 void init(MachineFunction &mf);
198 /// clear - Clear state and free memory necessary to make this
199 /// SelectionDAG ready to process a new block.
203 MachineFunction &getMachineFunction() const { return *MF; }
204 const TargetMachine &getTarget() const { return TM; }
205 const TargetLowering &getTargetLoweringInfo() const { return TLI; }
206 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
207 LLVMContext *getContext() const {return Context; }
209 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
211 void viewGraph(const std::string &Title);
215 std::map<const SDNode *, std::string> NodeGraphAttrs;
218 /// clearGraphAttrs - Clear all previously defined node graph attributes.
219 /// Intended to be used from a debugging tool (eg. gdb).
220 void clearGraphAttrs();
222 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
224 void setGraphAttrs(const SDNode *N, const char *Attrs);
226 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
227 /// Used from getNodeAttributes.
228 const std::string getGraphAttrs(const SDNode *N) const;
230 /// setGraphColor - Convenience for setting node color attribute.
232 void setGraphColor(const SDNode *N, const char *Color);
234 /// setGraphColor - Convenience for setting subgraph color attribute.
236 void setSubgraphColor(SDNode *N, const char *Color);
238 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
239 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
240 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
241 typedef ilist<SDNode>::iterator allnodes_iterator;
242 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
243 allnodes_iterator allnodes_end() { return AllNodes.end(); }
244 ilist<SDNode>::size_type allnodes_size() const {
245 return AllNodes.size();
248 /// getRoot - Return the root tag of the SelectionDAG.
250 const SDValue &getRoot() const { return Root; }
252 /// getEntryNode - Return the token chain corresponding to the entry of the
254 SDValue getEntryNode() const {
255 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
258 /// setRoot - Set the current root tag of the SelectionDAG.
260 const SDValue &setRoot(SDValue N) {
261 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
262 "DAG root value is not a chain!");
264 checkForCycles(N.getNode());
267 checkForCycles(this);
271 /// Combine - This iterates over the nodes in the SelectionDAG, folding
272 /// certain types of nodes together, or eliminating superfluous nodes. The
273 /// Level argument controls whether Combine is allowed to produce nodes and
274 /// types that are illegal on the target.
275 void Combine(CombineLevel Level, AliasAnalysis &AA,
276 CodeGenOpt::Level OptLevel);
278 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
279 /// only uses types natively supported by the target. Returns "true" if it
280 /// made any changes.
282 /// Note that this is an involved process that may invalidate pointers into
284 bool LegalizeTypes();
286 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
287 /// compatible with the target instruction selector, as indicated by the
288 /// TargetLowering object.
290 /// Note that this is an involved process that may invalidate pointers into
294 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
295 /// that only uses vector math operations supported by the target. This is
296 /// necessary as a separate step from Legalize because unrolling a vector
297 /// operation can introduce illegal types, which requires running
298 /// LegalizeTypes again.
300 /// This returns true if it made any changes; in that case, LegalizeTypes
301 /// is called again before Legalize.
303 /// Note that this is an involved process that may invalidate pointers into
305 bool LegalizeVectors();
307 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
309 void RemoveDeadNodes();
311 /// DeleteNode - Remove the specified node from the system. This node must
312 /// have no referrers.
313 void DeleteNode(SDNode *N);
315 /// getVTList - Return an SDVTList that represents the list of values
317 SDVTList getVTList(EVT VT);
318 SDVTList getVTList(EVT VT1, EVT VT2);
319 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
320 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
321 SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
323 //===--------------------------------------------------------------------===//
324 // Node creation methods.
326 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
327 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
328 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
329 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
330 SDValue getTargetConstant(uint64_t Val, EVT VT) {
331 return getConstant(Val, VT, true);
333 SDValue getTargetConstant(const APInt &Val, EVT VT) {
334 return getConstant(Val, VT, true);
336 SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
337 return getConstant(Val, VT, true);
339 // The forms below that take a double should only be used for simple
340 // constants that can be exactly represented in VT. No checks are made.
341 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
342 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
343 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
344 SDValue getTargetConstantFP(double Val, EVT VT) {
345 return getConstantFP(Val, VT, true);
347 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
348 return getConstantFP(Val, VT, true);
350 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
351 return getConstantFP(Val, VT, true);
353 SDValue getGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
354 int64_t offset = 0, bool isTargetGA = false,
355 unsigned char TargetFlags = 0);
356 SDValue getTargetGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
358 unsigned char TargetFlags = 0) {
359 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
361 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
362 SDValue getTargetFrameIndex(int FI, EVT VT) {
363 return getFrameIndex(FI, VT, true);
365 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
366 unsigned char TargetFlags = 0);
367 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
368 return getJumpTable(JTI, VT, true, TargetFlags);
370 SDValue getConstantPool(const Constant *C, EVT VT,
371 unsigned Align = 0, int Offs = 0, bool isT=false,
372 unsigned char TargetFlags = 0);
373 SDValue getTargetConstantPool(const Constant *C, EVT VT,
374 unsigned Align = 0, int Offset = 0,
375 unsigned char TargetFlags = 0) {
376 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
378 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
379 unsigned Align = 0, int Offs = 0, bool isT=false,
380 unsigned char TargetFlags = 0);
381 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
382 EVT VT, unsigned Align = 0,
383 int Offset = 0, unsigned char TargetFlags=0) {
384 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
386 // When generating a branch to a BB, we don't in general know enough
387 // to provide debug info for the BB at that time, so keep this one around.
388 SDValue getBasicBlock(MachineBasicBlock *MBB);
389 SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl);
390 SDValue getExternalSymbol(const char *Sym, EVT VT);
391 SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT);
392 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
393 unsigned char TargetFlags = 0);
394 SDValue getValueType(EVT);
395 SDValue getRegister(unsigned Reg, EVT VT);
396 SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label);
397 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
398 bool isTarget = false, unsigned char TargetFlags = 0);
400 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) {
401 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
402 getRegister(Reg, N.getValueType()), N);
405 // This version of the getCopyToReg method takes an extra operand, which
406 // indicates that there is potentially an incoming glue value (if Glue is not
407 // null) and that there should be a glue result.
408 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N,
410 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
411 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
412 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
415 // Similar to last getCopyToReg() except parameter Reg is a SDValue
416 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N,
418 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
419 SDValue Ops[] = { Chain, Reg, N, Glue };
420 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
423 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) {
424 SDVTList VTs = getVTList(VT, MVT::Other);
425 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
426 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
429 // This version of the getCopyFromReg method takes an extra operand, which
430 // indicates that there is potentially an incoming glue value (if Glue is not
431 // null) and that there should be a glue result.
432 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT,
434 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
435 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
436 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Glue.getNode() ? 3 : 2);
439 SDValue getCondCode(ISD::CondCode Cond);
441 /// Returns the ConvertRndSat Note: Avoid using this node because it may
442 /// disappear in the future and most targets don't support it.
443 SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy,
445 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
447 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
448 /// elements in VT, which must be a vector type, must match the number of
449 /// mask elements NumElts. A integer mask element equal to -1 is treated as
451 SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2,
452 const int *MaskElts);
454 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
455 /// integer type VT, by either any-extending or truncating it.
456 SDValue getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
458 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
459 /// integer type VT, by either sign-extending or truncating it.
460 SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
462 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
463 /// integer type VT, by either zero-extending or truncating it.
464 SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
466 /// getZeroExtendInReg - Return the expression required to zero extend the Op
467 /// value assuming it was the smaller SrcTy value.
468 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy);
470 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
471 SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT);
473 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
474 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a
476 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) {
477 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
478 SDValue Ops[] = { Chain, Op };
479 return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2);
482 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
483 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have
484 /// a useful DebugLoc.
485 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
487 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
488 SmallVector<SDValue, 4> Ops;
489 Ops.push_back(Chain);
492 Ops.push_back(InGlue);
493 return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0],
494 (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0));
497 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc.
498 SDValue getUNDEF(EVT VT) {
499 return getNode(ISD::UNDEF, DebugLoc(), VT);
502 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
503 /// not have a useful DebugLoc.
504 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
505 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc(), VT);
508 /// getNode - Gets or creates the specified node.
510 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT);
511 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N);
512 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2);
513 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
514 SDValue N1, SDValue N2, SDValue N3);
515 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
516 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
517 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
518 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
520 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
521 const SDUse *Ops, unsigned NumOps);
522 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
523 const SDValue *Ops, unsigned NumOps);
524 SDValue getNode(unsigned Opcode, DebugLoc DL,
525 const std::vector<EVT> &ResultTys,
526 const SDValue *Ops, unsigned NumOps);
527 SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs,
528 const SDValue *Ops, unsigned NumOps);
529 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
530 const SDValue *Ops, unsigned NumOps);
531 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs);
532 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N);
533 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
534 SDValue N1, SDValue N2);
535 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
536 SDValue N1, SDValue N2, SDValue N3);
537 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
538 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
539 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
540 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
543 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
544 /// the incoming stack arguments to be loaded from the stack. This is
545 /// used in tail call lowering to protect stack arguments from being
547 SDValue getStackArgumentTokenFactor(SDValue Chain);
549 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
550 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
551 MachinePointerInfo DstPtrInfo,
552 MachinePointerInfo SrcPtrInfo);
554 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
555 SDValue Size, unsigned Align, bool isVol,
556 MachinePointerInfo DstPtrInfo,
557 MachinePointerInfo SrcPtrInfo);
559 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
560 SDValue Size, unsigned Align, bool isVol,
561 MachinePointerInfo DstPtrInfo);
563 /// getSetCC - Helper function to make it easier to build SetCC's if you just
564 /// have an ISD::CondCode instead of an SDValue.
566 SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
567 ISD::CondCode Cond) {
568 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
569 "Cannot compare scalars to vectors");
570 assert(LHS.getValueType().isVector() == VT.isVector() &&
571 "Cannot compare scalars to vectors");
572 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
575 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
576 /// just have an ISD::CondCode instead of an SDValue.
578 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS,
579 SDValue True, SDValue False, ISD::CondCode Cond) {
580 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
581 LHS, RHS, True, False, getCondCode(Cond));
584 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
585 /// and a source value as input.
586 SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
587 SDValue SV, unsigned Align);
589 /// getAtomic - Gets a node for an atomic op, produces result and chain and
591 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
592 SDValue Ptr, SDValue Cmp, SDValue Swp,
593 MachinePointerInfo PtrInfo, unsigned Alignment,
594 AtomicOrdering Ordering,
595 SynchronizationScope SynchScope);
596 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
597 SDValue Ptr, SDValue Cmp, SDValue Swp,
598 MachineMemOperand *MMO,
599 AtomicOrdering Ordering,
600 SynchronizationScope SynchScope);
602 /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
603 /// and chain and takes 2 operands.
604 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
605 SDValue Ptr, SDValue Val, const Value* PtrVal,
606 unsigned Alignment, AtomicOrdering Ordering,
607 SynchronizationScope SynchScope);
608 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
609 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
610 AtomicOrdering Ordering,
611 SynchronizationScope SynchScope);
613 /// getAtomic - Gets a node for an atomic op, produces result and chain and
615 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
616 SDValue Chain, SDValue Ptr, const Value* PtrVal,
618 AtomicOrdering Ordering,
619 SynchronizationScope SynchScope);
620 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
621 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
622 AtomicOrdering Ordering,
623 SynchronizationScope SynchScope);
625 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
626 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
627 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
628 /// less than FIRST_TARGET_MEMORY_OPCODE.
629 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
630 const EVT *VTs, unsigned NumVTs,
631 const SDValue *Ops, unsigned NumOps,
632 EVT MemVT, MachinePointerInfo PtrInfo,
633 unsigned Align = 0, bool Vol = false,
634 bool ReadMem = true, bool WriteMem = true);
636 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
637 const SDValue *Ops, unsigned NumOps,
638 EVT MemVT, MachinePointerInfo PtrInfo,
639 unsigned Align = 0, bool Vol = false,
640 bool ReadMem = true, bool WriteMem = true);
642 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
643 const SDValue *Ops, unsigned NumOps,
644 EVT MemVT, MachineMemOperand *MMO);
646 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
647 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl);
649 /// getLoad - Loads are not normal binary operators: their result type is not
650 /// determined by their operands, and they produce a value AND a token chain.
652 SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
653 MachinePointerInfo PtrInfo, bool isVolatile,
654 bool isNonTemporal, bool isInvariant, unsigned Alignment,
655 const MDNode *TBAAInfo = 0);
656 SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
657 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
658 EVT MemVT, bool isVolatile,
659 bool isNonTemporal, unsigned Alignment,
660 const MDNode *TBAAInfo = 0);
661 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
662 SDValue Offset, ISD::MemIndexedMode AM);
663 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
665 SDValue Chain, SDValue Ptr, SDValue Offset,
666 MachinePointerInfo PtrInfo, EVT MemVT,
667 bool isVolatile, bool isNonTemporal, bool isInvariant,
668 unsigned Alignment, const MDNode *TBAAInfo = 0);
669 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
671 SDValue Chain, SDValue Ptr, SDValue Offset,
672 EVT MemVT, MachineMemOperand *MMO);
674 /// getStore - Helper function to build ISD::STORE nodes.
676 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
677 MachinePointerInfo PtrInfo, bool isVolatile,
678 bool isNonTemporal, unsigned Alignment,
679 const MDNode *TBAAInfo = 0);
680 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
681 MachineMemOperand *MMO);
682 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
683 MachinePointerInfo PtrInfo, EVT TVT,
684 bool isNonTemporal, bool isVolatile,
686 const MDNode *TBAAInfo = 0);
687 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
688 EVT TVT, MachineMemOperand *MMO);
689 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base,
690 SDValue Offset, ISD::MemIndexedMode AM);
692 /// getSrcValue - Construct a node to track a Value* through the backend.
693 SDValue getSrcValue(const Value *v);
695 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
696 SDValue getMDNode(const MDNode *MD);
698 /// getShiftAmountOperand - Return the specified value casted to
699 /// the target's desired shift amount type.
700 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
702 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
703 /// specified operands. If the resultant node already exists in the DAG,
704 /// this does not modify the specified node, instead it returns the node that
705 /// already exists. If the resultant node does not exist in the DAG, the
706 /// input node is returned. As a degenerate case, if you specify the same
707 /// input operands as the node already has, the input node is returned.
708 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
709 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
710 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
712 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
713 SDValue Op3, SDValue Op4);
714 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
715 SDValue Op3, SDValue Op4, SDValue Op5);
716 SDNode *UpdateNodeOperands(SDNode *N,
717 const SDValue *Ops, unsigned NumOps);
719 /// SelectNodeTo - These are used for target selectors to *mutate* the
720 /// specified node to have the specified return type, Target opcode, and
721 /// operands. Note that target opcodes are stored as
722 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
723 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
724 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
725 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
726 SDValue Op1, SDValue Op2);
727 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
728 SDValue Op1, SDValue Op2, SDValue Op3);
729 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
730 const SDValue *Ops, unsigned NumOps);
731 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
732 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
733 EVT VT2, const SDValue *Ops, unsigned NumOps);
734 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
735 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
736 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
737 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
739 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
740 EVT VT2, SDValue Op1);
741 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
742 EVT VT2, SDValue Op1, SDValue Op2);
743 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
744 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
745 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
746 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
747 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
748 const SDValue *Ops, unsigned NumOps);
750 /// MorphNodeTo - This *mutates* the specified node to have the specified
751 /// return type, opcode, and operands.
752 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
753 const SDValue *Ops, unsigned NumOps);
755 /// getMachineNode - These are used for target selectors to create a new node
756 /// with specified return type(s), MachineInstr opcode, and operands.
758 /// Note that getMachineNode returns the resultant node. If there is already
759 /// a node of the specified opcode and operands, it returns that node instead
760 /// of the current one.
761 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
762 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
764 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
765 SDValue Op1, SDValue Op2);
766 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
767 SDValue Op1, SDValue Op2, SDValue Op3);
768 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
769 const SDValue *Ops, unsigned NumOps);
770 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2);
771 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
773 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
774 EVT VT2, SDValue Op1, SDValue Op2);
775 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
776 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
777 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
778 const SDValue *Ops, unsigned NumOps);
779 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
780 EVT VT3, SDValue Op1, SDValue Op2);
781 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
782 EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
783 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
784 EVT VT3, const SDValue *Ops, unsigned NumOps);
785 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
786 EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
787 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
788 const std::vector<EVT> &ResultTys, const SDValue *Ops,
790 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
791 const SDValue *Ops, unsigned NumOps);
793 /// getTargetExtractSubreg - A convenience function for creating
794 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
795 SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
798 /// getTargetInsertSubreg - A convenience function for creating
799 /// TargetInstrInfo::INSERT_SUBREG nodes.
800 SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
801 SDValue Operand, SDValue Subreg);
803 /// getNodeIfExists - Get the specified node if it's already available, or
804 /// else return NULL.
805 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
806 const SDValue *Ops, unsigned NumOps);
808 /// getDbgValue - Creates a SDDbgValue node.
810 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
811 DebugLoc DL, unsigned O);
812 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
813 DebugLoc DL, unsigned O);
814 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
815 DebugLoc DL, unsigned O);
817 /// DAGUpdateListener - Clients of various APIs that cause global effects on
818 /// the DAG can optionally implement this interface. This allows the clients
819 /// to handle the various sorts of updates that happen.
820 class DAGUpdateListener {
822 virtual ~DAGUpdateListener();
824 /// NodeDeleted - The node N that was deleted and, if E is not null, an
825 /// equivalent node E that replaced it.
826 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0;
828 /// NodeUpdated - The node N that was updated.
829 virtual void NodeUpdated(SDNode *N) = 0;
832 /// RemoveDeadNode - Remove the specified node from the system. If any of its
833 /// operands then becomes dead, remove them as well. Inform UpdateListener
834 /// for each node deleted.
835 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0);
837 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
838 /// given list, and any nodes that become unreachable as a result.
839 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
840 DAGUpdateListener *UpdateListener = 0);
842 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
843 /// This can cause recursive merging of nodes in the DAG. Use the first
844 /// version if 'From' is known to have a single result, use the second
845 /// if you have two nodes with identical results (or if 'To' has a superset
846 /// of the results of 'From'), use the third otherwise.
848 /// These methods all take an optional UpdateListener, which (if not null) is
849 /// informed about nodes that are deleted and modified due to recursive
850 /// changes in the dag.
852 /// These functions only replace all existing uses. It's possible that as
853 /// these replacements are being performed, CSE may cause the From node
854 /// to be given new uses. These new uses of From are left in place, and
855 /// not automatically transferred to To.
857 void ReplaceAllUsesWith(SDValue From, SDValue Op,
858 DAGUpdateListener *UpdateListener = 0);
859 void ReplaceAllUsesWith(SDNode *From, SDNode *To,
860 DAGUpdateListener *UpdateListener = 0);
861 void ReplaceAllUsesWith(SDNode *From, const SDValue *To,
862 DAGUpdateListener *UpdateListener = 0);
864 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
865 /// uses of other values produced by From.Val alone.
866 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
867 DAGUpdateListener *UpdateListener = 0);
869 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
870 /// for multiple values at once. This correctly handles the case where
871 /// there is an overlap between the From values and the To values.
872 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
874 DAGUpdateListener *UpdateListener = 0);
876 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
877 /// assign a unique node id for each node in the DAG based on their
878 /// topological order. Returns the number of nodes.
879 unsigned AssignTopologicalOrder();
881 /// RepositionNode - Move node N in the AllNodes list to be immediately
882 /// before the given iterator Position. This may be used to update the
883 /// topological ordering when the list of nodes is modified.
884 void RepositionNode(allnodes_iterator Position, SDNode *N) {
885 AllNodes.insert(Position, AllNodes.remove(N));
888 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
890 static bool isCommutativeBinOp(unsigned Opcode) {
891 // FIXME: This should get its info from the td file, so that we can include
908 case ISD::ADDE: return true;
909 default: return false;
913 /// AssignOrdering - Assign an order to the SDNode.
914 void AssignOrdering(const SDNode *SD, unsigned Order);
916 /// GetOrdering - Get the order for the SDNode.
917 unsigned GetOrdering(const SDNode *SD) const;
919 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
920 /// value is produced by SD.
921 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
923 /// GetDbgValues - Get the debug values which reference the given SDNode.
924 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
925 return DbgInfo->getSDDbgValues(SD);
928 /// TransferDbgValues - Transfer SDDbgValues.
929 void TransferDbgValues(SDValue From, SDValue To);
931 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
932 /// with this SelectionDAG.
933 bool hasDebugValues() const { return !DbgInfo->empty(); }
935 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
936 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
937 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
938 return DbgInfo->ByvalParmDbgBegin();
940 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
941 return DbgInfo->ByvalParmDbgEnd();
946 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
947 /// specified value type. If minAlign is specified, the slot size will have
948 /// at least that alignment.
949 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
951 /// CreateStackTemporary - Create a stack temporary suitable for holding
952 /// either of the specified value types.
953 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
955 /// FoldConstantArithmetic -
956 SDValue FoldConstantArithmetic(unsigned Opcode,
958 ConstantSDNode *Cst1,
959 ConstantSDNode *Cst2);
961 /// FoldSetCC - Constant fold a setcc to true or false.
962 SDValue FoldSetCC(EVT VT, SDValue N1,
963 SDValue N2, ISD::CondCode Cond, DebugLoc dl);
965 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
966 /// use this predicate to simplify operations downstream.
967 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
969 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
970 /// use this predicate to simplify operations downstream. Op and Mask are
971 /// known to be the same type.
972 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
975 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
976 /// known to be either zero or one and return them in the KnownZero/KnownOne
977 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
978 /// processing. Targets can implement the computeMaskedBitsForTargetNode
979 /// method in the TargetLowering class to allow target nodes to be understood.
980 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero,
981 APInt &KnownOne, unsigned Depth = 0) const;
983 /// ComputeNumSignBits - Return the number of times the sign bit of the
984 /// register is replicated into the other bits. We know that at least 1 bit
985 /// is always equal to the sign bit (itself), but other cases can give us
986 /// information. For example, immediately after an "SRA X, 2", we know that
987 /// the top 3 bits are all equal to each other, so we return 3. Targets can
988 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
989 /// class to allow target nodes to be understood.
990 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
992 /// isBaseWithConstantOffset - Return true if the specified operand is an
993 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
994 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
995 /// semantics as an ADD. This handles the equivalence:
996 /// X|Cst == X+Cst iff X&Cst = 0.
997 bool isBaseWithConstantOffset(SDValue Op) const;
999 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1000 bool isKnownNeverNaN(SDValue Op) const;
1002 /// isKnownNeverZero - Test whether the given SDValue is known to never be
1003 /// positive or negative Zero.
1004 bool isKnownNeverZero(SDValue Op) const;
1006 /// isEqualTo - Test whether two SDValues are known to compare equal. This
1007 /// is true if they are the same value, or if one is negative zero and the
1008 /// other positive zero.
1009 bool isEqualTo(SDValue A, SDValue B) const;
1011 /// UnrollVectorOp - Utility function used by legalize and lowering to
1012 /// "unroll" a vector operation by splitting out the scalars and operating
1013 /// on each element individually. If the ResNE is 0, fully unroll the vector
1014 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1015 /// If the ResNE is greater than the width of the vector op, unroll the
1016 /// vector op and fill the end of the resulting vector with UNDEFS.
1017 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1019 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1020 /// location that is 'Dist' units away from the location that the 'Base' load
1021 /// is loading from.
1022 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1023 unsigned Bytes, int Dist) const;
1025 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1026 /// it cannot be inferred.
1027 unsigned InferPtrAlignment(SDValue Ptr) const;
1030 bool RemoveNodeFromCSEMaps(SDNode *N);
1031 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener);
1032 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1033 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1035 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1038 void DeleteNodeNotInCSEMaps(SDNode *N);
1039 void DeallocateNode(SDNode *N);
1041 unsigned getEVTAlignment(EVT MemoryVT) const;
1043 void allnodes_clear();
1045 /// VTList - List of non-single value types.
1046 std::vector<SDVTList> VTList;
1048 /// CondCodeNodes - Maps to auto-CSE operations.
1049 std::vector<CondCodeSDNode*> CondCodeNodes;
1051 std::vector<SDNode*> ValueTypeNodes;
1052 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1053 StringMap<SDNode*> ExternalSymbols;
1055 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1058 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1059 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1060 static nodes_iterator nodes_begin(SelectionDAG *G) {
1061 return G->allnodes_begin();
1063 static nodes_iterator nodes_end(SelectionDAG *G) {
1064 return G->allnodes_end();
1068 } // end namespace llvm