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;
142 CodeGenOpt::Level OptLevel;
144 /// EntryNode - The starting token.
147 /// Root - The root of the entire DAG.
150 /// AllNodes - A linked list of nodes in the current DAG.
151 ilist<SDNode> AllNodes;
153 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
154 /// pool allocation with recycling.
155 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
156 AlignOf<MostAlignedSDNode>::Alignment>
159 /// NodeAllocator - Pool allocation for nodes.
160 NodeAllocatorType NodeAllocator;
162 /// CSEMap - This structure is used to memoize nodes, automatically performing
163 /// CSE with existing nodes when a duplicate is requested.
164 FoldingSet<SDNode> CSEMap;
166 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
167 BumpPtrAllocator OperandAllocator;
169 /// Allocator - Pool allocation for misc. objects that are created once per
171 BumpPtrAllocator Allocator;
173 /// SDNodeOrdering - The ordering of the SDNodes. It roughly corresponds to
174 /// the ordering of the original LLVM instructions.
175 SDNodeOrdering *Ordering;
177 /// DbgInfo - Tracks dbg_value information through SDISel.
180 /// setGraphColorHelper - Implementation of setSubgraphColor.
181 /// Return whether we had to truncate the search.
183 bool setSubgraphColorHelper(SDNode *N, const char *Color,
184 DenseSet<SDNode *> &visited,
185 int level, bool &printed);
187 void operator=(const SelectionDAG&); // Do not implement.
188 SelectionDAG(const SelectionDAG&); // Do not implement.
191 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
194 /// init - Prepare this SelectionDAG to process code in the given
197 void init(MachineFunction &mf);
199 /// clear - Clear state and free memory necessary to make this
200 /// SelectionDAG ready to process a new block.
204 MachineFunction &getMachineFunction() const { return *MF; }
205 const TargetMachine &getTarget() const { return TM; }
206 const TargetLowering &getTargetLoweringInfo() const { return TLI; }
207 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
208 LLVMContext *getContext() const {return Context; }
210 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
212 void viewGraph(const std::string &Title);
216 std::map<const SDNode *, std::string> NodeGraphAttrs;
219 /// clearGraphAttrs - Clear all previously defined node graph attributes.
220 /// Intended to be used from a debugging tool (eg. gdb).
221 void clearGraphAttrs();
223 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
225 void setGraphAttrs(const SDNode *N, const char *Attrs);
227 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
228 /// Used from getNodeAttributes.
229 const std::string getGraphAttrs(const SDNode *N) const;
231 /// setGraphColor - Convenience for setting node color attribute.
233 void setGraphColor(const SDNode *N, const char *Color);
235 /// setGraphColor - Convenience for setting subgraph color attribute.
237 void setSubgraphColor(SDNode *N, const char *Color);
239 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
240 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
241 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
242 typedef ilist<SDNode>::iterator allnodes_iterator;
243 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
244 allnodes_iterator allnodes_end() { return AllNodes.end(); }
245 ilist<SDNode>::size_type allnodes_size() const {
246 return AllNodes.size();
249 /// getRoot - Return the root tag of the SelectionDAG.
251 const SDValue &getRoot() const { return Root; }
253 /// getEntryNode - Return the token chain corresponding to the entry of the
255 SDValue getEntryNode() const {
256 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
259 /// setRoot - Set the current root tag of the SelectionDAG.
261 const SDValue &setRoot(SDValue N) {
262 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
263 "DAG root value is not a chain!");
265 checkForCycles(N.getNode());
268 checkForCycles(this);
272 /// Combine - This iterates over the nodes in the SelectionDAG, folding
273 /// certain types of nodes together, or eliminating superfluous nodes. The
274 /// Level argument controls whether Combine is allowed to produce nodes and
275 /// types that are illegal on the target.
276 void Combine(CombineLevel Level, AliasAnalysis &AA,
277 CodeGenOpt::Level OptLevel);
279 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
280 /// only uses types natively supported by the target. Returns "true" if it
281 /// made any changes.
283 /// Note that this is an involved process that may invalidate pointers into
285 bool LegalizeTypes();
287 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
288 /// compatible with the target instruction selector, as indicated by the
289 /// TargetLowering object.
291 /// Note that this is an involved process that may invalidate pointers into
295 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
296 /// that only uses vector math operations supported by the target. This is
297 /// necessary as a separate step from Legalize because unrolling a vector
298 /// operation can introduce illegal types, which requires running
299 /// LegalizeTypes again.
301 /// This returns true if it made any changes; in that case, LegalizeTypes
302 /// is called again before Legalize.
304 /// Note that this is an involved process that may invalidate pointers into
306 bool LegalizeVectors();
308 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
310 void RemoveDeadNodes();
312 /// DeleteNode - Remove the specified node from the system. This node must
313 /// have no referrers.
314 void DeleteNode(SDNode *N);
316 /// getVTList - Return an SDVTList that represents the list of values
318 SDVTList getVTList(EVT VT);
319 SDVTList getVTList(EVT VT1, EVT VT2);
320 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
321 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
322 SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
324 //===--------------------------------------------------------------------===//
325 // Node creation methods.
327 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
328 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
329 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
330 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
331 SDValue getTargetConstant(uint64_t Val, EVT VT) {
332 return getConstant(Val, VT, true);
334 SDValue getTargetConstant(const APInt &Val, EVT VT) {
335 return getConstant(Val, VT, true);
337 SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
338 return getConstant(Val, VT, true);
340 // The forms below that take a double should only be used for simple
341 // constants that can be exactly represented in VT. No checks are made.
342 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
343 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
344 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
345 SDValue getTargetConstantFP(double Val, EVT VT) {
346 return getConstantFP(Val, VT, true);
348 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
349 return getConstantFP(Val, VT, true);
351 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
352 return getConstantFP(Val, VT, true);
354 SDValue getGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
355 int64_t offset = 0, bool isTargetGA = false,
356 unsigned char TargetFlags = 0);
357 SDValue getTargetGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
359 unsigned char TargetFlags = 0) {
360 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
362 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
363 SDValue getTargetFrameIndex(int FI, EVT VT) {
364 return getFrameIndex(FI, VT, true);
366 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
367 unsigned char TargetFlags = 0);
368 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
369 return getJumpTable(JTI, VT, true, TargetFlags);
371 SDValue getConstantPool(const Constant *C, EVT VT,
372 unsigned Align = 0, int Offs = 0, bool isT=false,
373 unsigned char TargetFlags = 0);
374 SDValue getTargetConstantPool(const Constant *C, EVT VT,
375 unsigned Align = 0, int Offset = 0,
376 unsigned char TargetFlags = 0) {
377 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
379 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
380 unsigned Align = 0, int Offs = 0, bool isT=false,
381 unsigned char TargetFlags = 0);
382 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
383 EVT VT, unsigned Align = 0,
384 int Offset = 0, unsigned char TargetFlags=0) {
385 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
387 // When generating a branch to a BB, we don't in general know enough
388 // to provide debug info for the BB at that time, so keep this one around.
389 SDValue getBasicBlock(MachineBasicBlock *MBB);
390 SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl);
391 SDValue getExternalSymbol(const char *Sym, EVT VT);
392 SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT);
393 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
394 unsigned char TargetFlags = 0);
395 SDValue getValueType(EVT);
396 SDValue getRegister(unsigned Reg, EVT VT);
397 SDValue getRegisterMask(const uint32_t *RegMask);
398 SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label);
399 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
400 bool isTarget = false, unsigned char TargetFlags = 0);
402 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) {
403 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
404 getRegister(Reg, N.getValueType()), N);
407 // This version of the getCopyToReg method takes an extra operand, which
408 // indicates that there is potentially an incoming glue value (if Glue is not
409 // null) and that there should be a glue result.
410 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N,
412 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
413 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
414 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
417 // Similar to last getCopyToReg() except parameter Reg is a SDValue
418 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N,
420 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
421 SDValue Ops[] = { Chain, Reg, N, Glue };
422 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
425 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) {
426 SDVTList VTs = getVTList(VT, MVT::Other);
427 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
428 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
431 // This version of the getCopyFromReg method takes an extra operand, which
432 // indicates that there is potentially an incoming glue value (if Glue is not
433 // null) and that there should be a glue result.
434 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT,
436 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
437 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
438 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Glue.getNode() ? 3 : 2);
441 SDValue getCondCode(ISD::CondCode Cond);
443 /// Returns the ConvertRndSat Note: Avoid using this node because it may
444 /// disappear in the future and most targets don't support it.
445 SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy,
447 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
449 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
450 /// elements in VT, which must be a vector type, must match the number of
451 /// mask elements NumElts. A integer mask element equal to -1 is treated as
453 SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2,
454 const int *MaskElts);
456 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
457 /// integer type VT, by either any-extending or truncating it.
458 SDValue getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
460 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
461 /// integer type VT, by either sign-extending or truncating it.
462 SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
464 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
465 /// integer type VT, by either zero-extending or truncating it.
466 SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
468 /// getZeroExtendInReg - Return the expression required to zero extend the Op
469 /// value assuming it was the smaller SrcTy value.
470 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy);
472 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
473 SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT);
475 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
476 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a
478 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) {
479 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
480 SDValue Ops[] = { Chain, Op };
481 return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2);
484 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
485 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have
486 /// a useful DebugLoc.
487 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
489 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
490 SmallVector<SDValue, 4> Ops;
491 Ops.push_back(Chain);
494 Ops.push_back(InGlue);
495 return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0],
496 (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0));
499 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc.
500 SDValue getUNDEF(EVT VT) {
501 return getNode(ISD::UNDEF, DebugLoc(), VT);
504 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
505 /// not have a useful DebugLoc.
506 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
507 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc(), VT);
510 /// getNode - Gets or creates the specified node.
512 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT);
513 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N);
514 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2);
515 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
516 SDValue N1, SDValue N2, SDValue N3);
517 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
518 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
519 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
520 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
522 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
523 const SDUse *Ops, unsigned NumOps);
524 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
525 const SDValue *Ops, unsigned NumOps);
526 SDValue getNode(unsigned Opcode, DebugLoc DL,
527 const std::vector<EVT> &ResultTys,
528 const SDValue *Ops, unsigned NumOps);
529 SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs,
530 const SDValue *Ops, unsigned NumOps);
531 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
532 const SDValue *Ops, unsigned NumOps);
533 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs);
534 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N);
535 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
536 SDValue N1, SDValue N2);
537 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
538 SDValue N1, SDValue N2, SDValue N3);
539 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
540 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
541 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
542 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
545 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
546 /// the incoming stack arguments to be loaded from the stack. This is
547 /// used in tail call lowering to protect stack arguments from being
549 SDValue getStackArgumentTokenFactor(SDValue Chain);
551 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
552 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
553 MachinePointerInfo DstPtrInfo,
554 MachinePointerInfo SrcPtrInfo);
556 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
557 SDValue Size, unsigned Align, bool isVol,
558 MachinePointerInfo DstPtrInfo,
559 MachinePointerInfo SrcPtrInfo);
561 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
562 SDValue Size, unsigned Align, bool isVol,
563 MachinePointerInfo DstPtrInfo);
565 /// getSetCC - Helper function to make it easier to build SetCC's if you just
566 /// have an ISD::CondCode instead of an SDValue.
568 SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
569 ISD::CondCode Cond) {
570 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
571 "Cannot compare scalars to vectors");
572 assert(LHS.getValueType().isVector() == VT.isVector() &&
573 "Cannot compare scalars to vectors");
574 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
577 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
578 /// just have an ISD::CondCode instead of an SDValue.
580 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS,
581 SDValue True, SDValue False, ISD::CondCode Cond) {
582 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
583 LHS, RHS, True, False, getCondCode(Cond));
586 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
587 /// and a source value as input.
588 SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
589 SDValue SV, unsigned Align);
591 /// getAtomic - Gets a node for an atomic op, produces result and chain and
593 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
594 SDValue Ptr, SDValue Cmp, SDValue Swp,
595 MachinePointerInfo PtrInfo, unsigned Alignment,
596 AtomicOrdering Ordering,
597 SynchronizationScope SynchScope);
598 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
599 SDValue Ptr, SDValue Cmp, SDValue Swp,
600 MachineMemOperand *MMO,
601 AtomicOrdering Ordering,
602 SynchronizationScope SynchScope);
604 /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
605 /// and chain and takes 2 operands.
606 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
607 SDValue Ptr, SDValue Val, const Value* PtrVal,
608 unsigned Alignment, AtomicOrdering Ordering,
609 SynchronizationScope SynchScope);
610 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
611 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
612 AtomicOrdering Ordering,
613 SynchronizationScope SynchScope);
615 /// getAtomic - Gets a node for an atomic op, produces result and chain and
617 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
618 SDValue Chain, SDValue Ptr, const Value* PtrVal,
620 AtomicOrdering Ordering,
621 SynchronizationScope SynchScope);
622 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
623 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
624 AtomicOrdering Ordering,
625 SynchronizationScope SynchScope);
627 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
628 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
629 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
630 /// less than FIRST_TARGET_MEMORY_OPCODE.
631 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
632 const EVT *VTs, unsigned NumVTs,
633 const SDValue *Ops, unsigned NumOps,
634 EVT MemVT, MachinePointerInfo PtrInfo,
635 unsigned Align = 0, bool Vol = false,
636 bool ReadMem = true, bool WriteMem = true);
638 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
639 const SDValue *Ops, unsigned NumOps,
640 EVT MemVT, MachinePointerInfo PtrInfo,
641 unsigned Align = 0, bool Vol = false,
642 bool ReadMem = true, bool WriteMem = true);
644 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
645 const SDValue *Ops, unsigned NumOps,
646 EVT MemVT, MachineMemOperand *MMO);
648 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
649 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl);
651 /// getLoad - Loads are not normal binary operators: their result type is not
652 /// determined by their operands, and they produce a value AND a token chain.
654 SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
655 MachinePointerInfo PtrInfo, bool isVolatile,
656 bool isNonTemporal, bool isInvariant, unsigned Alignment,
657 const MDNode *TBAAInfo = 0);
658 SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
659 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
660 EVT MemVT, bool isVolatile,
661 bool isNonTemporal, unsigned Alignment,
662 const MDNode *TBAAInfo = 0);
663 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
664 SDValue Offset, ISD::MemIndexedMode AM);
665 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
667 SDValue Chain, SDValue Ptr, SDValue Offset,
668 MachinePointerInfo PtrInfo, EVT MemVT,
669 bool isVolatile, bool isNonTemporal, bool isInvariant,
670 unsigned Alignment, const MDNode *TBAAInfo = 0);
671 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
673 SDValue Chain, SDValue Ptr, SDValue Offset,
674 EVT MemVT, MachineMemOperand *MMO);
676 /// getStore - Helper function to build ISD::STORE nodes.
678 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
679 MachinePointerInfo PtrInfo, bool isVolatile,
680 bool isNonTemporal, unsigned Alignment,
681 const MDNode *TBAAInfo = 0);
682 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
683 MachineMemOperand *MMO);
684 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
685 MachinePointerInfo PtrInfo, EVT TVT,
686 bool isNonTemporal, bool isVolatile,
688 const MDNode *TBAAInfo = 0);
689 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
690 EVT TVT, MachineMemOperand *MMO);
691 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base,
692 SDValue Offset, ISD::MemIndexedMode AM);
694 /// getSrcValue - Construct a node to track a Value* through the backend.
695 SDValue getSrcValue(const Value *v);
697 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
698 SDValue getMDNode(const MDNode *MD);
700 /// getShiftAmountOperand - Return the specified value casted to
701 /// the target's desired shift amount type.
702 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
704 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
705 /// specified operands. If the resultant node already exists in the DAG,
706 /// this does not modify the specified node, instead it returns the node that
707 /// already exists. If the resultant node does not exist in the DAG, the
708 /// input node is returned. As a degenerate case, if you specify the same
709 /// input operands as the node already has, the input node is returned.
710 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
711 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
712 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
714 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
715 SDValue Op3, SDValue Op4);
716 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
717 SDValue Op3, SDValue Op4, SDValue Op5);
718 SDNode *UpdateNodeOperands(SDNode *N,
719 const SDValue *Ops, unsigned NumOps);
721 /// SelectNodeTo - These are used for target selectors to *mutate* the
722 /// specified node to have the specified return type, Target opcode, and
723 /// operands. Note that target opcodes are stored as
724 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
725 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
726 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
727 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
728 SDValue Op1, SDValue Op2);
729 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
730 SDValue Op1, SDValue Op2, SDValue Op3);
731 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
732 const SDValue *Ops, unsigned NumOps);
733 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
734 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
735 EVT VT2, const SDValue *Ops, unsigned NumOps);
736 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
737 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
738 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
739 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
741 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
742 EVT VT2, SDValue Op1);
743 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
744 EVT VT2, SDValue Op1, SDValue Op2);
745 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
746 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
747 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
748 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
749 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
750 const SDValue *Ops, unsigned NumOps);
752 /// MorphNodeTo - This *mutates* the specified node to have the specified
753 /// return type, opcode, and operands.
754 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
755 const SDValue *Ops, unsigned NumOps);
757 /// getMachineNode - These are used for target selectors to create a new node
758 /// with specified return type(s), MachineInstr opcode, and operands.
760 /// Note that getMachineNode returns the resultant node. If there is already
761 /// a node of the specified opcode and operands, it returns that node instead
762 /// of the current one.
763 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
764 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
766 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
767 SDValue Op1, SDValue Op2);
768 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
769 SDValue Op1, SDValue Op2, SDValue Op3);
770 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
771 const SDValue *Ops, unsigned NumOps);
772 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2);
773 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
775 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
776 EVT VT2, SDValue Op1, SDValue Op2);
777 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
778 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
779 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
780 const SDValue *Ops, unsigned NumOps);
781 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
782 EVT VT3, SDValue Op1, SDValue Op2);
783 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
784 EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
785 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
786 EVT VT3, const SDValue *Ops, unsigned NumOps);
787 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
788 EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
789 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
790 const std::vector<EVT> &ResultTys, const SDValue *Ops,
792 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
793 const SDValue *Ops, unsigned NumOps);
795 /// getTargetExtractSubreg - A convenience function for creating
796 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
797 SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
800 /// getTargetInsertSubreg - A convenience function for creating
801 /// TargetInstrInfo::INSERT_SUBREG nodes.
802 SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
803 SDValue Operand, SDValue Subreg);
805 /// getNodeIfExists - Get the specified node if it's already available, or
806 /// else return NULL.
807 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
808 const SDValue *Ops, unsigned NumOps);
810 /// getDbgValue - Creates a SDDbgValue node.
812 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
813 DebugLoc DL, unsigned O);
814 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
815 DebugLoc DL, unsigned O);
816 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
817 DebugLoc DL, unsigned O);
819 /// DAGUpdateListener - Clients of various APIs that cause global effects on
820 /// the DAG can optionally implement this interface. This allows the clients
821 /// to handle the various sorts of updates that happen.
822 class DAGUpdateListener {
824 virtual ~DAGUpdateListener();
826 /// NodeDeleted - The node N that was deleted and, if E is not null, an
827 /// equivalent node E that replaced it.
828 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0;
830 /// NodeUpdated - The node N that was updated.
831 virtual void NodeUpdated(SDNode *N) = 0;
834 /// RemoveDeadNode - Remove the specified node from the system. If any of its
835 /// operands then becomes dead, remove them as well. Inform UpdateListener
836 /// for each node deleted.
837 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0);
839 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
840 /// given list, and any nodes that become unreachable as a result.
841 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
842 DAGUpdateListener *UpdateListener = 0);
844 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
845 /// This can cause recursive merging of nodes in the DAG. Use the first
846 /// version if 'From' is known to have a single result, use the second
847 /// if you have two nodes with identical results (or if 'To' has a superset
848 /// of the results of 'From'), use the third otherwise.
850 /// These methods all take an optional UpdateListener, which (if not null) is
851 /// informed about nodes that are deleted and modified due to recursive
852 /// changes in the dag.
854 /// These functions only replace all existing uses. It's possible that as
855 /// these replacements are being performed, CSE may cause the From node
856 /// to be given new uses. These new uses of From are left in place, and
857 /// not automatically transferred to To.
859 void ReplaceAllUsesWith(SDValue From, SDValue Op,
860 DAGUpdateListener *UpdateListener = 0);
861 void ReplaceAllUsesWith(SDNode *From, SDNode *To,
862 DAGUpdateListener *UpdateListener = 0);
863 void ReplaceAllUsesWith(SDNode *From, const SDValue *To,
864 DAGUpdateListener *UpdateListener = 0);
866 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
867 /// uses of other values produced by From.Val alone.
868 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
869 DAGUpdateListener *UpdateListener = 0);
871 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
872 /// for multiple values at once. This correctly handles the case where
873 /// there is an overlap between the From values and the To values.
874 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
876 DAGUpdateListener *UpdateListener = 0);
878 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
879 /// assign a unique node id for each node in the DAG based on their
880 /// topological order. Returns the number of nodes.
881 unsigned AssignTopologicalOrder();
883 /// RepositionNode - Move node N in the AllNodes list to be immediately
884 /// before the given iterator Position. This may be used to update the
885 /// topological ordering when the list of nodes is modified.
886 void RepositionNode(allnodes_iterator Position, SDNode *N) {
887 AllNodes.insert(Position, AllNodes.remove(N));
890 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
892 static bool isCommutativeBinOp(unsigned Opcode) {
893 // FIXME: This should get its info from the td file, so that we can include
910 case ISD::ADDE: return true;
911 default: return false;
915 /// AssignOrdering - Assign an order to the SDNode.
916 void AssignOrdering(const SDNode *SD, unsigned Order);
918 /// GetOrdering - Get the order for the SDNode.
919 unsigned GetOrdering(const SDNode *SD) const;
921 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
922 /// value is produced by SD.
923 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
925 /// GetDbgValues - Get the debug values which reference the given SDNode.
926 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
927 return DbgInfo->getSDDbgValues(SD);
930 /// TransferDbgValues - Transfer SDDbgValues.
931 void TransferDbgValues(SDValue From, SDValue To);
933 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
934 /// with this SelectionDAG.
935 bool hasDebugValues() const { return !DbgInfo->empty(); }
937 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
938 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
939 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
940 return DbgInfo->ByvalParmDbgBegin();
942 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
943 return DbgInfo->ByvalParmDbgEnd();
948 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
949 /// specified value type. If minAlign is specified, the slot size will have
950 /// at least that alignment.
951 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
953 /// CreateStackTemporary - Create a stack temporary suitable for holding
954 /// either of the specified value types.
955 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
957 /// FoldConstantArithmetic -
958 SDValue FoldConstantArithmetic(unsigned Opcode,
960 ConstantSDNode *Cst1,
961 ConstantSDNode *Cst2);
963 /// FoldSetCC - Constant fold a setcc to true or false.
964 SDValue FoldSetCC(EVT VT, SDValue N1,
965 SDValue N2, ISD::CondCode Cond, DebugLoc dl);
967 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
968 /// use this predicate to simplify operations downstream.
969 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
971 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
972 /// use this predicate to simplify operations downstream. Op and Mask are
973 /// known to be the same type.
974 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
977 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
978 /// known to be either zero or one and return them in the KnownZero/KnownOne
979 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
980 /// processing. Targets can implement the computeMaskedBitsForTargetNode
981 /// method in the TargetLowering class to allow target nodes to be understood.
982 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero,
983 APInt &KnownOne, unsigned Depth = 0) const;
985 /// ComputeNumSignBits - Return the number of times the sign bit of the
986 /// register is replicated into the other bits. We know that at least 1 bit
987 /// is always equal to the sign bit (itself), but other cases can give us
988 /// information. For example, immediately after an "SRA X, 2", we know that
989 /// the top 3 bits are all equal to each other, so we return 3. Targets can
990 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
991 /// class to allow target nodes to be understood.
992 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
994 /// isBaseWithConstantOffset - Return true if the specified operand is an
995 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
996 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
997 /// semantics as an ADD. This handles the equivalence:
998 /// X|Cst == X+Cst iff X&Cst = 0.
999 bool isBaseWithConstantOffset(SDValue Op) const;
1001 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1002 bool isKnownNeverNaN(SDValue Op) const;
1004 /// isKnownNeverZero - Test whether the given SDValue is known to never be
1005 /// positive or negative Zero.
1006 bool isKnownNeverZero(SDValue Op) const;
1008 /// isEqualTo - Test whether two SDValues are known to compare equal. This
1009 /// is true if they are the same value, or if one is negative zero and the
1010 /// other positive zero.
1011 bool isEqualTo(SDValue A, SDValue B) const;
1013 /// UnrollVectorOp - Utility function used by legalize and lowering to
1014 /// "unroll" a vector operation by splitting out the scalars and operating
1015 /// on each element individually. If the ResNE is 0, fully unroll the vector
1016 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1017 /// If the ResNE is greater than the width of the vector op, unroll the
1018 /// vector op and fill the end of the resulting vector with UNDEFS.
1019 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1021 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1022 /// location that is 'Dist' units away from the location that the 'Base' load
1023 /// is loading from.
1024 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1025 unsigned Bytes, int Dist) const;
1027 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1028 /// it cannot be inferred.
1029 unsigned InferPtrAlignment(SDValue Ptr) const;
1032 bool RemoveNodeFromCSEMaps(SDNode *N);
1033 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener);
1034 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1035 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1037 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1039 SDNode *UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc loc);
1041 void DeleteNodeNotInCSEMaps(SDNode *N);
1042 void DeallocateNode(SDNode *N);
1044 unsigned getEVTAlignment(EVT MemoryVT) const;
1046 void allnodes_clear();
1048 /// VTList - List of non-single value types.
1049 std::vector<SDVTList> VTList;
1051 /// CondCodeNodes - Maps to auto-CSE operations.
1052 std::vector<CondCodeSDNode*> CondCodeNodes;
1054 std::vector<SDNode*> ValueTypeNodes;
1055 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1056 StringMap<SDNode*> ExternalSymbols;
1058 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1061 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1062 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1063 static nodes_iterator nodes_begin(SelectionDAG *G) {
1064 return G->allnodes_begin();
1066 static nodes_iterator nodes_end(SelectionDAG *G) {
1067 return G->allnodes_end();
1071 } // end namespace llvm