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 llvm_unreachable("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.
181 /// DAGUpdateListener - Clients of various APIs that cause global effects on
182 /// the DAG can optionally implement this interface. This allows the clients
183 /// to handle the various sorts of updates that happen.
185 /// A DAGUpdateListener automatically registers itself with DAG when it is
186 /// constructed, and removes itself when destroyed in RAII fashion.
187 struct DAGUpdateListener {
188 DAGUpdateListener *const Next;
191 explicit DAGUpdateListener(SelectionDAG &D)
192 : Next(D.UpdateListeners), DAG(D) {
193 DAG.UpdateListeners = this;
196 virtual ~DAGUpdateListener() {
197 assert(DAG.UpdateListeners == this &&
198 "DAGUpdateListeners must be destroyed in LIFO order");
199 DAG.UpdateListeners = Next;
202 /// NodeDeleted - The node N that was deleted and, if E is not null, an
203 /// equivalent node E that replaced it.
204 virtual void NodeDeleted(SDNode *N, SDNode *E);
206 /// NodeUpdated - The node N that was updated.
207 virtual void NodeUpdated(SDNode *N);
211 /// DAGUpdateListener is a friend so it can manipulate the listener stack.
212 friend struct DAGUpdateListener;
214 /// UpdateListeners - Linked list of registered DAGUpdateListener instances.
215 /// This stack is maintained by DAGUpdateListener RAII.
216 DAGUpdateListener *UpdateListeners;
218 /// setGraphColorHelper - Implementation of setSubgraphColor.
219 /// Return whether we had to truncate the search.
221 bool setSubgraphColorHelper(SDNode *N, const char *Color,
222 DenseSet<SDNode *> &visited,
223 int level, bool &printed);
225 void operator=(const SelectionDAG&); // Do not implement.
226 SelectionDAG(const SelectionDAG&); // Do not implement.
229 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level);
232 /// init - Prepare this SelectionDAG to process code in the given
235 void init(MachineFunction &mf);
237 /// clear - Clear state and free memory necessary to make this
238 /// SelectionDAG ready to process a new block.
242 MachineFunction &getMachineFunction() const { return *MF; }
243 const TargetMachine &getTarget() const { return TM; }
244 const TargetLowering &getTargetLoweringInfo() const { return TLI; }
245 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
246 LLVMContext *getContext() const {return Context; }
248 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
250 void viewGraph(const std::string &Title);
254 std::map<const SDNode *, std::string> NodeGraphAttrs;
257 /// clearGraphAttrs - Clear all previously defined node graph attributes.
258 /// Intended to be used from a debugging tool (eg. gdb).
259 void clearGraphAttrs();
261 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
263 void setGraphAttrs(const SDNode *N, const char *Attrs);
265 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
266 /// Used from getNodeAttributes.
267 const std::string getGraphAttrs(const SDNode *N) const;
269 /// setGraphColor - Convenience for setting node color attribute.
271 void setGraphColor(const SDNode *N, const char *Color);
273 /// setGraphColor - Convenience for setting subgraph color attribute.
275 void setSubgraphColor(SDNode *N, const char *Color);
277 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
278 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
279 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
280 typedef ilist<SDNode>::iterator allnodes_iterator;
281 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
282 allnodes_iterator allnodes_end() { return AllNodes.end(); }
283 ilist<SDNode>::size_type allnodes_size() const {
284 return AllNodes.size();
287 /// getRoot - Return the root tag of the SelectionDAG.
289 const SDValue &getRoot() const { return Root; }
291 /// getEntryNode - Return the token chain corresponding to the entry of the
293 SDValue getEntryNode() const {
294 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
297 /// setRoot - Set the current root tag of the SelectionDAG.
299 const SDValue &setRoot(SDValue N) {
300 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
301 "DAG root value is not a chain!");
303 checkForCycles(N.getNode());
306 checkForCycles(this);
310 /// Combine - This iterates over the nodes in the SelectionDAG, folding
311 /// certain types of nodes together, or eliminating superfluous nodes. The
312 /// Level argument controls whether Combine is allowed to produce nodes and
313 /// types that are illegal on the target.
314 void Combine(CombineLevel Level, AliasAnalysis &AA,
315 CodeGenOpt::Level OptLevel);
317 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
318 /// only uses types natively supported by the target. Returns "true" if it
319 /// made any changes.
321 /// Note that this is an involved process that may invalidate pointers into
323 bool LegalizeTypes();
325 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
326 /// compatible with the target instruction selector, as indicated by the
327 /// TargetLowering object.
329 /// Note that this is an involved process that may invalidate pointers into
333 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
334 /// that only uses vector math operations supported by the target. This is
335 /// necessary as a separate step from Legalize because unrolling a vector
336 /// operation can introduce illegal types, which requires running
337 /// LegalizeTypes again.
339 /// This returns true if it made any changes; in that case, LegalizeTypes
340 /// is called again before Legalize.
342 /// Note that this is an involved process that may invalidate pointers into
344 bool LegalizeVectors();
346 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
348 void RemoveDeadNodes();
350 /// DeleteNode - Remove the specified node from the system. This node must
351 /// have no referrers.
352 void DeleteNode(SDNode *N);
354 /// getVTList - Return an SDVTList that represents the list of values
356 SDVTList getVTList(EVT VT);
357 SDVTList getVTList(EVT VT1, EVT VT2);
358 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
359 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
360 SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
362 //===--------------------------------------------------------------------===//
363 // Node creation methods.
365 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
366 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
367 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
368 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
369 SDValue getTargetConstant(uint64_t Val, EVT VT) {
370 return getConstant(Val, VT, true);
372 SDValue getTargetConstant(const APInt &Val, EVT VT) {
373 return getConstant(Val, VT, true);
375 SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
376 return getConstant(Val, VT, true);
378 // The forms below that take a double should only be used for simple
379 // constants that can be exactly represented in VT. No checks are made.
380 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
381 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
382 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
383 SDValue getTargetConstantFP(double Val, EVT VT) {
384 return getConstantFP(Val, VT, true);
386 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
387 return getConstantFP(Val, VT, true);
389 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
390 return getConstantFP(Val, VT, true);
392 SDValue getGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
393 int64_t offset = 0, bool isTargetGA = false,
394 unsigned char TargetFlags = 0);
395 SDValue getTargetGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
397 unsigned char TargetFlags = 0) {
398 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
400 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
401 SDValue getTargetFrameIndex(int FI, EVT VT) {
402 return getFrameIndex(FI, VT, true);
404 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
405 unsigned char TargetFlags = 0);
406 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
407 return getJumpTable(JTI, VT, true, TargetFlags);
409 SDValue getConstantPool(const Constant *C, EVT VT,
410 unsigned Align = 0, int Offs = 0, bool isT=false,
411 unsigned char TargetFlags = 0);
412 SDValue getTargetConstantPool(const Constant *C, EVT VT,
413 unsigned Align = 0, int Offset = 0,
414 unsigned char TargetFlags = 0) {
415 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
417 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
418 unsigned Align = 0, int Offs = 0, bool isT=false,
419 unsigned char TargetFlags = 0);
420 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
421 EVT VT, unsigned Align = 0,
422 int Offset = 0, unsigned char TargetFlags=0) {
423 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
425 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
426 unsigned char TargetFlags = 0);
427 // When generating a branch to a BB, we don't in general know enough
428 // to provide debug info for the BB at that time, so keep this one around.
429 SDValue getBasicBlock(MachineBasicBlock *MBB);
430 SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl);
431 SDValue getExternalSymbol(const char *Sym, EVT VT);
432 SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT);
433 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
434 unsigned char TargetFlags = 0);
435 SDValue getValueType(EVT);
436 SDValue getRegister(unsigned Reg, EVT VT);
437 SDValue getRegisterMask(const uint32_t *RegMask);
438 SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label);
439 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
440 bool isTarget = false, unsigned char TargetFlags = 0);
442 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) {
443 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
444 getRegister(Reg, N.getValueType()), N);
447 // This version of the getCopyToReg method takes an extra operand, which
448 // indicates that there is potentially an incoming glue value (if Glue is not
449 // null) and that there should be a glue result.
450 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N,
452 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
453 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
454 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
457 // Similar to last getCopyToReg() except parameter Reg is a SDValue
458 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N,
460 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
461 SDValue Ops[] = { Chain, Reg, N, Glue };
462 return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3);
465 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) {
466 SDVTList VTs = getVTList(VT, MVT::Other);
467 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
468 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
471 // This version of the getCopyFromReg method takes an extra operand, which
472 // indicates that there is potentially an incoming glue value (if Glue is not
473 // null) and that there should be a glue result.
474 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT,
476 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
477 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
478 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Glue.getNode() ? 3 : 2);
481 SDValue getCondCode(ISD::CondCode Cond);
483 /// Returns the ConvertRndSat Note: Avoid using this node because it may
484 /// disappear in the future and most targets don't support it.
485 SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy,
487 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
489 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
490 /// elements in VT, which must be a vector type, must match the number of
491 /// mask elements NumElts. A integer mask element equal to -1 is treated as
493 SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2,
494 const int *MaskElts);
496 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the
497 /// integer type VT, by either any-extending or truncating it.
498 SDValue getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
500 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
501 /// integer type VT, by either sign-extending or truncating it.
502 SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
504 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
505 /// integer type VT, by either zero-extending or truncating it.
506 SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
508 /// getZeroExtendInReg - Return the expression required to zero extend the Op
509 /// value assuming it was the smaller SrcTy value.
510 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy);
512 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
513 SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT);
515 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
516 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a
518 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) {
519 SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
520 SDValue Ops[] = { Chain, Op };
521 return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2);
524 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
525 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have
526 /// a useful DebugLoc.
527 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
529 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
530 SmallVector<SDValue, 4> Ops;
531 Ops.push_back(Chain);
534 Ops.push_back(InGlue);
535 return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0],
536 (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0));
539 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc.
540 SDValue getUNDEF(EVT VT) {
541 return getNode(ISD::UNDEF, DebugLoc(), VT);
544 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
545 /// not have a useful DebugLoc.
546 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
547 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc(), VT);
550 /// getNode - Gets or creates the specified node.
552 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT);
553 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N);
554 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2);
555 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
556 SDValue N1, SDValue N2, SDValue N3);
557 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
558 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
559 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
560 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
562 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
563 const SDUse *Ops, unsigned NumOps);
564 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
565 const SDValue *Ops, unsigned NumOps);
566 SDValue getNode(unsigned Opcode, DebugLoc DL,
567 const std::vector<EVT> &ResultTys,
568 const SDValue *Ops, unsigned NumOps);
569 SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs,
570 const SDValue *Ops, unsigned NumOps);
571 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
572 const SDValue *Ops, unsigned NumOps);
573 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs);
574 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N);
575 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
576 SDValue N1, SDValue N2);
577 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
578 SDValue N1, SDValue N2, SDValue N3);
579 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
580 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
581 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
582 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
585 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
586 /// the incoming stack arguments to be loaded from the stack. This is
587 /// used in tail call lowering to protect stack arguments from being
589 SDValue getStackArgumentTokenFactor(SDValue Chain);
591 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
592 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
593 MachinePointerInfo DstPtrInfo,
594 MachinePointerInfo SrcPtrInfo);
596 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
597 SDValue Size, unsigned Align, bool isVol,
598 MachinePointerInfo DstPtrInfo,
599 MachinePointerInfo SrcPtrInfo);
601 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
602 SDValue Size, unsigned Align, bool isVol,
603 MachinePointerInfo DstPtrInfo);
605 /// getSetCC - Helper function to make it easier to build SetCC's if you just
606 /// have an ISD::CondCode instead of an SDValue.
608 SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
609 ISD::CondCode Cond) {
610 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
611 "Cannot compare scalars to vectors");
612 assert(LHS.getValueType().isVector() == VT.isVector() &&
613 "Cannot compare scalars to vectors");
614 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
617 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
618 /// just have an ISD::CondCode instead of an SDValue.
620 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS,
621 SDValue True, SDValue False, ISD::CondCode Cond) {
622 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
623 LHS, RHS, True, False, getCondCode(Cond));
626 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
627 /// and a source value as input.
628 SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
629 SDValue SV, unsigned Align);
631 /// getAtomic - Gets a node for an atomic op, produces result and chain and
633 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
634 SDValue Ptr, SDValue Cmp, SDValue Swp,
635 MachinePointerInfo PtrInfo, unsigned Alignment,
636 AtomicOrdering Ordering,
637 SynchronizationScope SynchScope);
638 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
639 SDValue Ptr, SDValue Cmp, SDValue Swp,
640 MachineMemOperand *MMO,
641 AtomicOrdering Ordering,
642 SynchronizationScope SynchScope);
644 /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
645 /// and chain and takes 2 operands.
646 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
647 SDValue Ptr, SDValue Val, const Value* PtrVal,
648 unsigned Alignment, AtomicOrdering Ordering,
649 SynchronizationScope SynchScope);
650 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
651 SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
652 AtomicOrdering Ordering,
653 SynchronizationScope SynchScope);
655 /// getAtomic - Gets a node for an atomic op, produces result and chain and
657 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
658 SDValue Chain, SDValue Ptr, const Value* PtrVal,
660 AtomicOrdering Ordering,
661 SynchronizationScope SynchScope);
662 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT,
663 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
664 AtomicOrdering Ordering,
665 SynchronizationScope SynchScope);
667 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
668 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
669 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
670 /// less than FIRST_TARGET_MEMORY_OPCODE.
671 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
672 const EVT *VTs, unsigned NumVTs,
673 const SDValue *Ops, unsigned NumOps,
674 EVT MemVT, MachinePointerInfo PtrInfo,
675 unsigned Align = 0, bool Vol = false,
676 bool ReadMem = true, bool WriteMem = true);
678 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
679 const SDValue *Ops, unsigned NumOps,
680 EVT MemVT, MachinePointerInfo PtrInfo,
681 unsigned Align = 0, bool Vol = false,
682 bool ReadMem = true, bool WriteMem = true);
684 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
685 const SDValue *Ops, unsigned NumOps,
686 EVT MemVT, MachineMemOperand *MMO);
688 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
689 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl);
691 /// getLoad - Loads are not normal binary operators: their result type is not
692 /// determined by their operands, and they produce a value AND a token chain.
694 SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
695 MachinePointerInfo PtrInfo, bool isVolatile,
696 bool isNonTemporal, bool isInvariant, unsigned Alignment,
697 const MDNode *TBAAInfo = 0, const MDNode *Ranges = 0);
698 SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
699 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
700 EVT MemVT, bool isVolatile,
701 bool isNonTemporal, unsigned Alignment,
702 const MDNode *TBAAInfo = 0);
703 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
704 SDValue Offset, ISD::MemIndexedMode AM);
705 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
707 SDValue Chain, SDValue Ptr, SDValue Offset,
708 MachinePointerInfo PtrInfo, EVT MemVT,
709 bool isVolatile, bool isNonTemporal, bool isInvariant,
710 unsigned Alignment, const MDNode *TBAAInfo = 0,
711 const MDNode *Ranges = 0);
712 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
714 SDValue Chain, SDValue Ptr, SDValue Offset,
715 EVT MemVT, MachineMemOperand *MMO);
717 /// getStore - Helper function to build ISD::STORE nodes.
719 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
720 MachinePointerInfo PtrInfo, bool isVolatile,
721 bool isNonTemporal, unsigned Alignment,
722 const MDNode *TBAAInfo = 0);
723 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
724 MachineMemOperand *MMO);
725 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
726 MachinePointerInfo PtrInfo, EVT TVT,
727 bool isNonTemporal, bool isVolatile,
729 const MDNode *TBAAInfo = 0);
730 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
731 EVT TVT, MachineMemOperand *MMO);
732 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base,
733 SDValue Offset, ISD::MemIndexedMode AM);
735 /// getSrcValue - Construct a node to track a Value* through the backend.
736 SDValue getSrcValue(const Value *v);
738 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
739 SDValue getMDNode(const MDNode *MD);
741 /// getShiftAmountOperand - Return the specified value casted to
742 /// the target's desired shift amount type.
743 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
745 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
746 /// specified operands. If the resultant node already exists in the DAG,
747 /// this does not modify the specified node, instead it returns the node that
748 /// already exists. If the resultant node does not exist in the DAG, the
749 /// input node is returned. As a degenerate case, if you specify the same
750 /// input operands as the node already has, the input node is returned.
751 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
752 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
753 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
755 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
756 SDValue Op3, SDValue Op4);
757 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
758 SDValue Op3, SDValue Op4, SDValue Op5);
759 SDNode *UpdateNodeOperands(SDNode *N,
760 const SDValue *Ops, unsigned NumOps);
762 /// SelectNodeTo - These are used for target selectors to *mutate* the
763 /// specified node to have the specified return type, Target opcode, and
764 /// operands. Note that target opcodes are stored as
765 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
766 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
767 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
768 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
769 SDValue Op1, SDValue Op2);
770 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
771 SDValue Op1, SDValue Op2, SDValue Op3);
772 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
773 const SDValue *Ops, unsigned NumOps);
774 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
775 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
776 EVT VT2, const SDValue *Ops, unsigned NumOps);
777 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
778 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
779 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
780 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
782 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
783 EVT VT2, SDValue Op1);
784 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
785 EVT VT2, SDValue Op1, SDValue Op2);
786 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
787 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
788 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
789 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
790 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
791 const SDValue *Ops, unsigned NumOps);
793 /// MorphNodeTo - This *mutates* the specified node to have the specified
794 /// return type, opcode, and operands.
795 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
796 const SDValue *Ops, unsigned NumOps);
798 /// getMachineNode - These are used for target selectors to create a new node
799 /// with specified return type(s), MachineInstr opcode, and operands.
801 /// Note that getMachineNode returns the resultant node. If there is already
802 /// a node of the specified opcode and operands, it returns that node instead
803 /// of the current one.
804 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
805 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
807 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
808 SDValue Op1, SDValue Op2);
809 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
810 SDValue Op1, SDValue Op2, SDValue Op3);
811 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
812 const SDValue *Ops, unsigned NumOps);
813 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2);
814 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
816 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
817 EVT VT2, SDValue Op1, SDValue Op2);
818 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
819 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
820 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
821 const SDValue *Ops, unsigned NumOps);
822 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
823 EVT VT3, SDValue Op1, SDValue Op2);
824 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
825 EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
826 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
827 EVT VT3, const SDValue *Ops, unsigned NumOps);
828 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
829 EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
830 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
831 const std::vector<EVT> &ResultTys, const SDValue *Ops,
833 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
834 const SDValue *Ops, unsigned NumOps);
836 /// getTargetExtractSubreg - A convenience function for creating
837 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
838 SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
841 /// getTargetInsertSubreg - A convenience function for creating
842 /// TargetInstrInfo::INSERT_SUBREG nodes.
843 SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
844 SDValue Operand, SDValue Subreg);
846 /// getNodeIfExists - Get the specified node if it's already available, or
847 /// else return NULL.
848 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
849 const SDValue *Ops, unsigned NumOps);
851 /// getDbgValue - Creates a SDDbgValue node.
853 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
854 DebugLoc DL, unsigned O);
855 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
856 DebugLoc DL, unsigned O);
857 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
858 DebugLoc DL, unsigned O);
860 /// RemoveDeadNode - Remove the specified node from the system. If any of its
861 /// operands then becomes dead, remove them as well. Inform UpdateListener
862 /// for each node deleted.
863 void RemoveDeadNode(SDNode *N);
865 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
866 /// given list, and any nodes that become unreachable as a result.
867 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
869 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
870 /// This can cause recursive merging of nodes in the DAG. Use the first
871 /// version if 'From' is known to have a single result, use the second
872 /// if you have two nodes with identical results (or if 'To' has a superset
873 /// of the results of 'From'), use the third otherwise.
875 /// These methods all take an optional UpdateListener, which (if not null) is
876 /// informed about nodes that are deleted and modified due to recursive
877 /// changes in the dag.
879 /// These functions only replace all existing uses. It's possible that as
880 /// these replacements are being performed, CSE may cause the From node
881 /// to be given new uses. These new uses of From are left in place, and
882 /// not automatically transferred to To.
884 void ReplaceAllUsesWith(SDValue From, SDValue Op);
885 void ReplaceAllUsesWith(SDNode *From, SDNode *To);
886 void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
888 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
889 /// uses of other values produced by From.Val alone.
890 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
892 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
893 /// for multiple values at once. This correctly handles the case where
894 /// there is an overlap between the From values and the To values.
895 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
898 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
899 /// assign a unique node id for each node in the DAG based on their
900 /// topological order. Returns the number of nodes.
901 unsigned AssignTopologicalOrder();
903 /// RepositionNode - Move node N in the AllNodes list to be immediately
904 /// before the given iterator Position. This may be used to update the
905 /// topological ordering when the list of nodes is modified.
906 void RepositionNode(allnodes_iterator Position, SDNode *N) {
907 AllNodes.insert(Position, AllNodes.remove(N));
910 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
912 static bool isCommutativeBinOp(unsigned Opcode) {
913 // FIXME: This should get its info from the td file, so that we can include
930 case ISD::ADDE: return true;
931 default: return false;
935 /// AssignOrdering - Assign an order to the SDNode.
936 void AssignOrdering(const SDNode *SD, unsigned Order);
938 /// GetOrdering - Get the order for the SDNode.
939 unsigned GetOrdering(const SDNode *SD) const;
941 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
942 /// value is produced by SD.
943 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
945 /// GetDbgValues - Get the debug values which reference the given SDNode.
946 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
947 return DbgInfo->getSDDbgValues(SD);
950 /// TransferDbgValues - Transfer SDDbgValues.
951 void TransferDbgValues(SDValue From, SDValue To);
953 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
954 /// with this SelectionDAG.
955 bool hasDebugValues() const { return !DbgInfo->empty(); }
957 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
958 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
959 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
960 return DbgInfo->ByvalParmDbgBegin();
962 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
963 return DbgInfo->ByvalParmDbgEnd();
968 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
969 /// specified value type. If minAlign is specified, the slot size will have
970 /// at least that alignment.
971 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
973 /// CreateStackTemporary - Create a stack temporary suitable for holding
974 /// either of the specified value types.
975 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
977 /// FoldConstantArithmetic -
978 SDValue FoldConstantArithmetic(unsigned Opcode,
980 ConstantSDNode *Cst1,
981 ConstantSDNode *Cst2);
983 /// FoldSetCC - Constant fold a setcc to true or false.
984 SDValue FoldSetCC(EVT VT, SDValue N1,
985 SDValue N2, ISD::CondCode Cond, DebugLoc dl);
987 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
988 /// use this predicate to simplify operations downstream.
989 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
991 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
992 /// use this predicate to simplify operations downstream. Op and Mask are
993 /// known to be the same type.
994 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
997 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
998 /// known to be either zero or one and return them in the KnownZero/KnownOne
999 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1000 /// processing. Targets can implement the computeMaskedBitsForTargetNode
1001 /// method in the TargetLowering class to allow target nodes to be understood.
1002 void ComputeMaskedBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1003 unsigned Depth = 0) const;
1005 /// ComputeNumSignBits - Return the number of times the sign bit of the
1006 /// register is replicated into the other bits. We know that at least 1 bit
1007 /// is always equal to the sign bit (itself), but other cases can give us
1008 /// information. For example, immediately after an "SRA X, 2", we know that
1009 /// the top 3 bits are all equal to each other, so we return 3. Targets can
1010 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1011 /// class to allow target nodes to be understood.
1012 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1014 /// isBaseWithConstantOffset - Return true if the specified operand is an
1015 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1016 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1017 /// semantics as an ADD. This handles the equivalence:
1018 /// X|Cst == X+Cst iff X&Cst = 0.
1019 bool isBaseWithConstantOffset(SDValue Op) const;
1021 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1022 bool isKnownNeverNaN(SDValue Op) const;
1024 /// isKnownNeverZero - Test whether the given SDValue is known to never be
1025 /// positive or negative Zero.
1026 bool isKnownNeverZero(SDValue Op) const;
1028 /// isEqualTo - Test whether two SDValues are known to compare equal. This
1029 /// is true if they are the same value, or if one is negative zero and the
1030 /// other positive zero.
1031 bool isEqualTo(SDValue A, SDValue B) const;
1033 /// UnrollVectorOp - Utility function used by legalize and lowering to
1034 /// "unroll" a vector operation by splitting out the scalars and operating
1035 /// on each element individually. If the ResNE is 0, fully unroll the vector
1036 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1037 /// If the ResNE is greater than the width of the vector op, unroll the
1038 /// vector op and fill the end of the resulting vector with UNDEFS.
1039 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1041 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1042 /// location that is 'Dist' units away from the location that the 'Base' load
1043 /// is loading from.
1044 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1045 unsigned Bytes, int Dist) const;
1047 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1048 /// it cannot be inferred.
1049 unsigned InferPtrAlignment(SDValue Ptr) const;
1052 bool RemoveNodeFromCSEMaps(SDNode *N);
1053 void AddModifiedNodeToCSEMaps(SDNode *N);
1054 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1055 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1057 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1059 SDNode *UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc loc);
1061 void DeleteNodeNotInCSEMaps(SDNode *N);
1062 void DeallocateNode(SDNode *N);
1064 unsigned getEVTAlignment(EVT MemoryVT) const;
1066 void allnodes_clear();
1068 /// VTList - List of non-single value types.
1069 std::vector<SDVTList> VTList;
1071 /// CondCodeNodes - Maps to auto-CSE operations.
1072 std::vector<CondCodeSDNode*> CondCodeNodes;
1074 std::vector<SDNode*> ValueTypeNodes;
1075 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1076 StringMap<SDNode*> ExternalSymbols;
1078 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1081 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1082 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1083 static nodes_iterator nodes_begin(SelectionDAG *G) {
1084 return G->allnodes_begin();
1086 static nodes_iterator nodes_end(SelectionDAG *G) {
1087 return G->allnodes_end();
1091 } // end namespace llvm