1 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file declares the SelectionDAG class, and transitively defines the
11 // SDNode class and subclasses.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
16 #define LLVM_CODEGEN_SELECTIONDAG_H
18 #include "llvm/ADT/ilist.h"
19 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/ADT/StringMap.h"
21 #include "llvm/CodeGen/SelectionDAGNodes.h"
22 #include "llvm/Support/RecyclingAllocator.h"
23 #include "llvm/Target/TargetMachine.h"
32 class MachineConstantPoolValue;
33 class MachineFunction;
38 class TargetSelectionDAGInfo;
40 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
42 mutable ilist_half_node<SDNode> Sentinel;
44 SDNode *createSentinel() const {
45 return static_cast<SDNode*>(&Sentinel);
47 static void destroySentinel(SDNode *) {}
49 SDNode *provideInitialHead() const { return createSentinel(); }
50 SDNode *ensureHead(SDNode*) const { return createSentinel(); }
51 static void noteHead(SDNode*, SDNode*) {}
53 static void deleteNode(SDNode *) {
54 assert(0 && "ilist_traits<SDNode> shouldn't see a deleteNode call!");
57 static void createNode(const SDNode &);
60 /// SDDbgInfo - Keeps track of dbg_value information through SDISel. We do
61 /// not build SDNodes for these so as not to perturb the generated code;
62 /// instead the info is kept off to the side in this structure. Each SDNode may
63 /// have one or more associated dbg_value entries. This information is kept in
65 /// Byval parameters are handled separately because they don't use alloca's,
66 /// which busts the normal mechanism. There is good reason for handling all
67 /// parameters separately: they may not have code generated for them, they
68 /// should always go at the beginning of the function regardless of other code
69 /// motion, and debug info for them is potentially useful even if the parameter
70 /// is unused. Right now only byval parameters are handled separately.
72 SmallVector<SDDbgValue*, 32> DbgValues;
73 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
74 DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMap;
76 void operator=(const SDDbgInfo&); // Do not implement.
77 SDDbgInfo(const SDDbgInfo&); // Do not implement.
81 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
83 ByvalParmDbgValues.push_back(V);
84 } else DbgValues.push_back(V);
86 DbgValMap[Node].push_back(V);
92 ByvalParmDbgValues.clear();
96 return DbgValues.empty() && ByvalParmDbgValues.empty();
99 SmallVector<SDDbgValue*,2> &getSDDbgValues(const SDNode *Node) {
100 return DbgValMap[Node];
103 typedef SmallVector<SDDbgValue*,32>::iterator DbgIterator;
104 DbgIterator DbgBegin() { return DbgValues.begin(); }
105 DbgIterator DbgEnd() { return DbgValues.end(); }
106 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
107 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
111 Unrestricted, // Combine may create illegal operations and illegal types.
112 NoIllegalTypes, // Combine may create illegal operations but no illegal types.
113 NoIllegalOperations // Combine may only create legal operations and types.
117 void checkForCycles(const SDNode *N);
118 void checkForCycles(const SelectionDAG *DAG);
120 /// SelectionDAG class - This is used to represent a portion of an LLVM function
121 /// in a low-level Data Dependence DAG representation suitable for instruction
122 /// selection. This DAG is constructed as the first step of instruction
123 /// selection in order to allow implementation of machine specific optimizations
124 /// and code simplifications.
126 /// The representation used by the SelectionDAG is a target-independent
127 /// representation, which has some similarities to the GCC RTL representation,
128 /// but is significantly more simple, powerful, and is a graph form instead of a
132 const TargetMachine &TM;
133 const TargetLowering &TLI;
134 const TargetSelectionDAGInfo &TSI;
136 LLVMContext *Context;
138 /// EntryNode - The starting token.
141 /// Root - The root of the entire DAG.
144 /// AllNodes - A linked list of nodes in the current DAG.
145 ilist<SDNode> AllNodes;
147 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
148 /// pool allocation with recycling.
149 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
150 AlignOf<MostAlignedSDNode>::Alignment>
153 /// NodeAllocator - Pool allocation for nodes.
154 NodeAllocatorType NodeAllocator;
156 /// CSEMap - This structure is used to memoize nodes, automatically performing
157 /// CSE with existing nodes when a duplicate is requested.
158 FoldingSet<SDNode> CSEMap;
160 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
161 BumpPtrAllocator OperandAllocator;
163 /// Allocator - Pool allocation for misc. objects that are created once per
165 BumpPtrAllocator Allocator;
167 /// SDNodeOrdering - The ordering of the SDNodes. It roughly corresponds to
168 /// the ordering of the original LLVM instructions.
169 SDNodeOrdering *Ordering;
171 /// DbgInfo - Tracks dbg_value information through SDISel.
174 /// VerifyNode - Sanity check the given node. Aborts if it is invalid.
175 void VerifyNode(SDNode *N);
177 /// setGraphColorHelper - Implementation of setSubgraphColor.
178 /// Return whether we had to truncate the search.
180 bool setSubgraphColorHelper(SDNode *N, const char *Color,
181 DenseSet<SDNode *> &visited,
182 int level, bool &printed);
184 void operator=(const SelectionDAG&); // Do not implement.
185 SelectionDAG(const SelectionDAG&); // Do not implement.
188 explicit SelectionDAG(const TargetMachine &TM);
191 /// init - Prepare this SelectionDAG to process code in the given
194 void init(MachineFunction &mf);
196 /// clear - Clear state and free memory necessary to make this
197 /// SelectionDAG ready to process a new block.
201 MachineFunction &getMachineFunction() const { return *MF; }
202 const TargetMachine &getTarget() const { return TM; }
203 const TargetLowering &getTargetLoweringInfo() const { return TLI; }
204 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; }
205 LLVMContext *getContext() const {return Context; }
207 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
209 void viewGraph(const std::string &Title);
213 std::map<const SDNode *, std::string> NodeGraphAttrs;
216 /// clearGraphAttrs - Clear all previously defined node graph attributes.
217 /// Intended to be used from a debugging tool (eg. gdb).
218 void clearGraphAttrs();
220 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
222 void setGraphAttrs(const SDNode *N, const char *Attrs);
224 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
225 /// Used from getNodeAttributes.
226 const std::string getGraphAttrs(const SDNode *N) const;
228 /// setGraphColor - Convenience for setting node color attribute.
230 void setGraphColor(const SDNode *N, const char *Color);
232 /// setGraphColor - Convenience for setting subgraph color attribute.
234 void setSubgraphColor(SDNode *N, const char *Color);
236 typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
237 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
238 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
239 typedef ilist<SDNode>::iterator allnodes_iterator;
240 allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
241 allnodes_iterator allnodes_end() { return AllNodes.end(); }
242 ilist<SDNode>::size_type allnodes_size() const {
243 return AllNodes.size();
246 /// getRoot - Return the root tag of the SelectionDAG.
248 const SDValue &getRoot() const { return Root; }
250 /// getEntryNode - Return the token chain corresponding to the entry of the
252 SDValue getEntryNode() const {
253 return SDValue(const_cast<SDNode *>(&EntryNode), 0);
256 /// setRoot - Set the current root tag of the SelectionDAG.
258 const SDValue &setRoot(SDValue N) {
259 assert((!N.getNode() || N.getValueType() == MVT::Other) &&
260 "DAG root value is not a chain!");
262 checkForCycles(N.getNode());
265 checkForCycles(this);
269 /// Combine - This iterates over the nodes in the SelectionDAG, folding
270 /// certain types of nodes together, or eliminating superfluous nodes. The
271 /// Level argument controls whether Combine is allowed to produce nodes and
272 /// types that are illegal on the target.
273 void Combine(CombineLevel Level, AliasAnalysis &AA,
274 CodeGenOpt::Level OptLevel);
276 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
277 /// only uses types natively supported by the target. Returns "true" if it
278 /// made any changes.
280 /// Note that this is an involved process that may invalidate pointers into
282 bool LegalizeTypes();
284 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
285 /// compatible with the target instruction selector, as indicated by the
286 /// TargetLowering object.
288 /// Note that this is an involved process that may invalidate pointers into
290 void Legalize(CodeGenOpt::Level OptLevel);
292 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
293 /// that only uses vector math operations supported by the target. This is
294 /// necessary as a separate step from Legalize because unrolling a vector
295 /// operation can introduce illegal types, which requires running
296 /// LegalizeTypes again.
298 /// This returns true if it made any changes; in that case, LegalizeTypes
299 /// is called again before Legalize.
301 /// Note that this is an involved process that may invalidate pointers into
303 bool LegalizeVectors();
305 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
307 void RemoveDeadNodes();
309 /// DeleteNode - Remove the specified node from the system. This node must
310 /// have no referrers.
311 void DeleteNode(SDNode *N);
313 /// getVTList - Return an SDVTList that represents the list of values
315 SDVTList getVTList(EVT VT);
316 SDVTList getVTList(EVT VT1, EVT VT2);
317 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
318 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
319 SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
321 //===--------------------------------------------------------------------===//
322 // Node creation methods.
324 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
325 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
326 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
327 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
328 SDValue getTargetConstant(uint64_t Val, EVT VT) {
329 return getConstant(Val, VT, true);
331 SDValue getTargetConstant(const APInt &Val, EVT VT) {
332 return getConstant(Val, VT, true);
334 SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
335 return getConstant(Val, VT, true);
337 // The forms below that take a double should only be used for simple
338 // constants that can be exactly represented in VT. No checks are made.
339 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
340 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
341 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
342 SDValue getTargetConstantFP(double Val, EVT VT) {
343 return getConstantFP(Val, VT, true);
345 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
346 return getConstantFP(Val, VT, true);
348 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
349 return getConstantFP(Val, VT, true);
351 SDValue getGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
352 int64_t offset = 0, bool isTargetGA = false,
353 unsigned char TargetFlags = 0);
354 SDValue getTargetGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT,
356 unsigned char TargetFlags = 0) {
357 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
359 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
360 SDValue getTargetFrameIndex(int FI, EVT VT) {
361 return getFrameIndex(FI, VT, true);
363 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
364 unsigned char TargetFlags = 0);
365 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
366 return getJumpTable(JTI, VT, true, TargetFlags);
368 SDValue getConstantPool(const Constant *C, EVT VT,
369 unsigned Align = 0, int Offs = 0, bool isT=false,
370 unsigned char TargetFlags = 0);
371 SDValue getTargetConstantPool(const Constant *C, EVT VT,
372 unsigned Align = 0, int Offset = 0,
373 unsigned char TargetFlags = 0) {
374 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
376 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
377 unsigned Align = 0, int Offs = 0, bool isT=false,
378 unsigned char TargetFlags = 0);
379 SDValue getTargetConstantPool(MachineConstantPoolValue *C,
380 EVT VT, unsigned Align = 0,
381 int Offset = 0, unsigned char TargetFlags=0) {
382 return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
384 // When generating a branch to a BB, we don't in general know enough
385 // to provide debug info for the BB at that time, so keep this one around.
386 SDValue getBasicBlock(MachineBasicBlock *MBB);
387 SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl);
388 SDValue getExternalSymbol(const char *Sym, EVT VT);
389 SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT);
390 SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
391 unsigned char TargetFlags = 0);
392 SDValue getValueType(EVT);
393 SDValue getRegister(unsigned Reg, EVT VT);
394 SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label);
395 SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
396 bool isTarget = false, unsigned char TargetFlags = 0);
398 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) {
399 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
400 getRegister(Reg, N.getValueType()), N);
403 // This version of the getCopyToReg method takes an extra operand, which
404 // indicates that there is potentially an incoming flag value (if Flag is not
405 // null) and that there should be a flag result.
406 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N,
408 SDVTList VTs = getVTList(MVT::Other, MVT::Flag);
409 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag };
410 return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3);
413 // Similar to last getCopyToReg() except parameter Reg is a SDValue
414 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N,
416 SDVTList VTs = getVTList(MVT::Other, MVT::Flag);
417 SDValue Ops[] = { Chain, Reg, N, Flag };
418 return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3);
421 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) {
422 SDVTList VTs = getVTList(VT, MVT::Other);
423 SDValue Ops[] = { Chain, getRegister(Reg, VT) };
424 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
427 // This version of the getCopyFromReg method takes an extra operand, which
428 // indicates that there is potentially an incoming flag value (if Flag is not
429 // null) and that there should be a flag result.
430 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT,
432 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Flag);
433 SDValue Ops[] = { Chain, getRegister(Reg, VT), Flag };
434 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Flag.getNode() ? 3 : 2);
437 SDValue getCondCode(ISD::CondCode Cond);
439 /// Returns the ConvertRndSat Note: Avoid using this node because it may
440 /// disappear in the future and most targets don't support it.
441 SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy,
443 SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
445 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of
446 /// elements in VT, which must be a vector type, must match the number of
447 /// mask elements NumElts. A integer mask element equal to -1 is treated as
449 SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2,
450 const int *MaskElts);
452 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
453 /// integer type VT, by either sign-extending or truncating it.
454 SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
456 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
457 /// integer type VT, by either zero-extending or truncating it.
458 SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
460 /// getZeroExtendInReg - Return the expression required to zero extend the Op
461 /// value assuming it was the smaller SrcTy value.
462 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy);
464 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
465 SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT);
467 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
468 /// a flag result (to ensure it's not CSE'd). CALLSEQ_START does not have a
470 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) {
471 SDVTList VTs = getVTList(MVT::Other, MVT::Flag);
472 SDValue Ops[] = { Chain, Op };
473 return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2);
476 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
477 /// flag result (to ensure it's not CSE'd). CALLSEQ_END does not have
478 /// a useful DebugLoc.
479 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
481 SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag);
482 SmallVector<SDValue, 4> Ops;
483 Ops.push_back(Chain);
486 Ops.push_back(InFlag);
487 return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0],
488 (unsigned)Ops.size() - (InFlag.getNode() == 0 ? 1 : 0));
491 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc.
492 SDValue getUNDEF(EVT VT) {
493 return getNode(ISD::UNDEF, DebugLoc(), VT);
496 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does
497 /// not have a useful DebugLoc.
498 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
499 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc(), VT);
502 /// getNode - Gets or creates the specified node.
504 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT);
505 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N);
506 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2);
507 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
508 SDValue N1, SDValue N2, SDValue N3);
509 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
510 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
511 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
512 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
514 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
515 const SDUse *Ops, unsigned NumOps);
516 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
517 const SDValue *Ops, unsigned NumOps);
518 SDValue getNode(unsigned Opcode, DebugLoc DL,
519 const std::vector<EVT> &ResultTys,
520 const SDValue *Ops, unsigned NumOps);
521 SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs,
522 const SDValue *Ops, unsigned NumOps);
523 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
524 const SDValue *Ops, unsigned NumOps);
525 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs);
526 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N);
527 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
528 SDValue N1, SDValue N2);
529 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
530 SDValue N1, SDValue N2, SDValue N3);
531 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
532 SDValue N1, SDValue N2, SDValue N3, SDValue N4);
533 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
534 SDValue N1, SDValue N2, SDValue N3, SDValue N4,
537 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
538 /// the incoming stack arguments to be loaded from the stack. This is
539 /// used in tail call lowering to protect stack arguments from being
541 SDValue getStackArgumentTokenFactor(SDValue Chain);
543 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
544 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
545 MachinePointerInfo DstPtrInfo,
546 MachinePointerInfo SrcPtrInfo);
548 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
549 SDValue Size, unsigned Align, bool isVol,
550 MachinePointerInfo DstPtrInfo,
551 MachinePointerInfo SrcPtrInfo);
553 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
554 SDValue Size, unsigned Align, bool isVol,
555 MachinePointerInfo DstPtrInfo);
557 /// getSetCC - Helper function to make it easier to build SetCC's if you just
558 /// have an ISD::CondCode instead of an SDValue.
560 SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
561 ISD::CondCode Cond) {
562 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
565 /// getVSetCC - Helper function to make it easier to build VSetCC's nodes
566 /// if you just have an ISD::CondCode instead of an SDValue.
568 SDValue getVSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
569 ISD::CondCode Cond) {
570 return getNode(ISD::VSETCC, DL, VT, LHS, RHS, getCondCode(Cond));
573 /// getSelectCC - Helper function to make it easier to build SelectCC's if you
574 /// just have an ISD::CondCode instead of an SDValue.
576 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS,
577 SDValue True, SDValue False, ISD::CondCode Cond) {
578 return getNode(ISD::SELECT_CC, DL, True.getValueType(),
579 LHS, RHS, True, False, getCondCode(Cond));
582 /// getVAArg - VAArg produces a result and token chain, and takes a pointer
583 /// and a source value as input.
584 SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
585 SDValue SV, unsigned Align);
587 /// getAtomic - Gets a node for an atomic op, produces result and chain and
589 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
590 SDValue Ptr, SDValue Cmp, SDValue Swp,
591 MachinePointerInfo PtrInfo, unsigned Alignment=0);
592 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
593 SDValue Ptr, SDValue Cmp, SDValue Swp,
594 MachineMemOperand *MMO);
596 /// getAtomic - Gets a node for an atomic op, produces result and chain and
597 /// takes 2 operands.
598 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
599 SDValue Ptr, SDValue Val, const Value* PtrVal,
600 unsigned Alignment = 0);
601 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
602 SDValue Ptr, SDValue Val,
603 MachineMemOperand *MMO);
605 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
606 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
607 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
608 /// less than FIRST_TARGET_MEMORY_OPCODE.
609 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
610 const EVT *VTs, unsigned NumVTs,
611 const SDValue *Ops, unsigned NumOps,
612 EVT MemVT, MachinePointerInfo PtrInfo,
613 unsigned Align = 0, bool Vol = false,
614 bool ReadMem = true, bool WriteMem = true);
616 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
617 const SDValue *Ops, unsigned NumOps,
618 EVT MemVT, MachinePointerInfo PtrInfo,
619 unsigned Align = 0, bool Vol = false,
620 bool ReadMem = true, bool WriteMem = true);
622 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
623 const SDValue *Ops, unsigned NumOps,
624 EVT MemVT, MachineMemOperand *MMO);
626 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
627 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl);
629 /// getLoad - Loads are not normal binary operators: their result type is not
630 /// determined by their operands, and they produce a value AND a token chain.
632 SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
633 MachinePointerInfo PtrInfo, bool isVolatile,
634 bool isNonTemporal, unsigned Alignment);
635 SDValue getExtLoad(ISD::LoadExtType ExtType, EVT VT, DebugLoc dl,
636 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
637 EVT MemVT, bool isVolatile,
638 bool isNonTemporal, unsigned Alignment);
639 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
640 SDValue Offset, ISD::MemIndexedMode AM);
641 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
643 SDValue Chain, SDValue Ptr, SDValue Offset,
644 MachinePointerInfo PtrInfo, EVT MemVT,
645 bool isVolatile, bool isNonTemporal, unsigned Alignment);
646 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
648 SDValue Chain, SDValue Ptr, SDValue Offset,
649 EVT MemVT, MachineMemOperand *MMO);
651 /// getStore - Helper function to build ISD::STORE nodes.
653 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
654 MachinePointerInfo PtrInfo, bool isVolatile,
655 bool isNonTemporal, unsigned Alignment);
656 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
657 MachineMemOperand *MMO);
658 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
659 MachinePointerInfo PtrInfo, EVT TVT,
660 bool isNonTemporal, bool isVolatile,
662 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
663 EVT TVT, MachineMemOperand *MMO);
664 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base,
665 SDValue Offset, ISD::MemIndexedMode AM);
667 /// getSrcValue - Construct a node to track a Value* through the backend.
668 SDValue getSrcValue(const Value *v);
670 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
671 SDValue getMDNode(const MDNode *MD);
673 /// getShiftAmountOperand - Return the specified value casted to
674 /// the target's desired shift amount type.
675 SDValue getShiftAmountOperand(SDValue Op);
677 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
678 /// specified operands. If the resultant node already exists in the DAG,
679 /// this does not modify the specified node, instead it returns the node that
680 /// already exists. If the resultant node does not exist in the DAG, the
681 /// input node is returned. As a degenerate case, if you specify the same
682 /// input operands as the node already has, the input node is returned.
683 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
684 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
685 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
687 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
688 SDValue Op3, SDValue Op4);
689 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
690 SDValue Op3, SDValue Op4, SDValue Op5);
691 SDNode *UpdateNodeOperands(SDNode *N,
692 const SDValue *Ops, unsigned NumOps);
694 /// SelectNodeTo - These are used for target selectors to *mutate* the
695 /// specified node to have the specified return type, Target opcode, and
696 /// operands. Note that target opcodes are stored as
697 /// ~TargetOpcode in the node opcode field. The resultant node is returned.
698 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
699 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
700 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
701 SDValue Op1, SDValue Op2);
702 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
703 SDValue Op1, SDValue Op2, SDValue Op3);
704 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
705 const SDValue *Ops, unsigned NumOps);
706 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
707 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
708 EVT VT2, const SDValue *Ops, unsigned NumOps);
709 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
710 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
711 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
712 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
714 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
715 EVT VT2, SDValue Op1);
716 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
717 EVT VT2, SDValue Op1, SDValue Op2);
718 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
719 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
720 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
721 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
722 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
723 const SDValue *Ops, unsigned NumOps);
725 /// MorphNodeTo - This *mutates* the specified node to have the specified
726 /// return type, opcode, and operands.
727 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
728 const SDValue *Ops, unsigned NumOps);
730 /// getMachineNode - These are used for target selectors to create a new node
731 /// with specified return type(s), MachineInstr opcode, and operands.
733 /// Note that getMachineNode returns the resultant node. If there is already
734 /// a node of the specified opcode and operands, it returns that node instead
735 /// of the current one.
736 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
737 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
739 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
740 SDValue Op1, SDValue Op2);
741 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
742 SDValue Op1, SDValue Op2, SDValue Op3);
743 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
744 const SDValue *Ops, unsigned NumOps);
745 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2);
746 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
748 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
749 EVT VT2, SDValue Op1, SDValue Op2);
750 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
751 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
752 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
753 const SDValue *Ops, unsigned NumOps);
754 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
755 EVT VT3, SDValue Op1, SDValue Op2);
756 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
757 EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
758 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
759 EVT VT3, const SDValue *Ops, unsigned NumOps);
760 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
761 EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
762 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
763 const std::vector<EVT> &ResultTys, const SDValue *Ops,
765 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
766 const SDValue *Ops, unsigned NumOps);
768 /// getTargetExtractSubreg - A convenience function for creating
769 /// TargetInstrInfo::EXTRACT_SUBREG nodes.
770 SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
773 /// getTargetInsertSubreg - A convenience function for creating
774 /// TargetInstrInfo::INSERT_SUBREG nodes.
775 SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
776 SDValue Operand, SDValue Subreg);
778 /// getNodeIfExists - Get the specified node if it's already available, or
779 /// else return NULL.
780 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
781 const SDValue *Ops, unsigned NumOps);
783 /// getDbgValue - Creates a SDDbgValue node.
785 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
786 DebugLoc DL, unsigned O);
787 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
788 DebugLoc DL, unsigned O);
789 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
790 DebugLoc DL, unsigned O);
792 /// DAGUpdateListener - Clients of various APIs that cause global effects on
793 /// the DAG can optionally implement this interface. This allows the clients
794 /// to handle the various sorts of updates that happen.
795 class DAGUpdateListener {
797 virtual ~DAGUpdateListener();
799 /// NodeDeleted - The node N that was deleted and, if E is not null, an
800 /// equivalent node E that replaced it.
801 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0;
803 /// NodeUpdated - The node N that was updated.
804 virtual void NodeUpdated(SDNode *N) = 0;
807 /// RemoveDeadNode - Remove the specified node from the system. If any of its
808 /// operands then becomes dead, remove them as well. Inform UpdateListener
809 /// for each node deleted.
810 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0);
812 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
813 /// given list, and any nodes that become unreachable as a result.
814 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
815 DAGUpdateListener *UpdateListener = 0);
817 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
818 /// This can cause recursive merging of nodes in the DAG. Use the first
819 /// version if 'From' is known to have a single result, use the second
820 /// if you have two nodes with identical results (or if 'To' has a superset
821 /// of the results of 'From'), use the third otherwise.
823 /// These methods all take an optional UpdateListener, which (if not null) is
824 /// informed about nodes that are deleted and modified due to recursive
825 /// changes in the dag.
827 /// These functions only replace all existing uses. It's possible that as
828 /// these replacements are being performed, CSE may cause the From node
829 /// to be given new uses. These new uses of From are left in place, and
830 /// not automatically transfered to To.
832 void ReplaceAllUsesWith(SDValue From, SDValue Op,
833 DAGUpdateListener *UpdateListener = 0);
834 void ReplaceAllUsesWith(SDNode *From, SDNode *To,
835 DAGUpdateListener *UpdateListener = 0);
836 void ReplaceAllUsesWith(SDNode *From, const SDValue *To,
837 DAGUpdateListener *UpdateListener = 0);
839 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
840 /// uses of other values produced by From.Val alone.
841 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
842 DAGUpdateListener *UpdateListener = 0);
844 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
845 /// for multiple values at once. This correctly handles the case where
846 /// there is an overlap between the From values and the To values.
847 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
849 DAGUpdateListener *UpdateListener = 0);
851 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
852 /// assign a unique node id for each node in the DAG based on their
853 /// topological order. Returns the number of nodes.
854 unsigned AssignTopologicalOrder();
856 /// RepositionNode - Move node N in the AllNodes list to be immediately
857 /// before the given iterator Position. This may be used to update the
858 /// topological ordering when the list of nodes is modified.
859 void RepositionNode(allnodes_iterator Position, SDNode *N) {
860 AllNodes.insert(Position, AllNodes.remove(N));
863 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
865 static bool isCommutativeBinOp(unsigned Opcode) {
866 // FIXME: This should get its info from the td file, so that we can include
883 case ISD::ADDE: return true;
884 default: return false;
888 /// AssignOrdering - Assign an order to the SDNode.
889 void AssignOrdering(const SDNode *SD, unsigned Order);
891 /// GetOrdering - Get the order for the SDNode.
892 unsigned GetOrdering(const SDNode *SD) const;
894 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
895 /// value is produced by SD.
896 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
898 /// GetDbgValues - Get the debug values which reference the given SDNode.
899 SmallVector<SDDbgValue*,2> &GetDbgValues(const SDNode* SD) {
900 return DbgInfo->getSDDbgValues(SD);
903 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
904 /// with this SelectionDAG.
905 bool hasDebugValues() const { return !DbgInfo->empty(); }
907 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
908 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
909 SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
910 return DbgInfo->ByvalParmDbgBegin();
912 SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
913 return DbgInfo->ByvalParmDbgEnd();
918 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
919 /// specified value type. If minAlign is specified, the slot size will have
920 /// at least that alignment.
921 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
923 /// CreateStackTemporary - Create a stack temporary suitable for holding
924 /// either of the specified value types.
925 SDValue CreateStackTemporary(EVT VT1, EVT VT2);
927 /// FoldConstantArithmetic -
928 SDValue FoldConstantArithmetic(unsigned Opcode,
930 ConstantSDNode *Cst1,
931 ConstantSDNode *Cst2);
933 /// FoldSetCC - Constant fold a setcc to true or false.
934 SDValue FoldSetCC(EVT VT, SDValue N1,
935 SDValue N2, ISD::CondCode Cond, DebugLoc dl);
937 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
938 /// use this predicate to simplify operations downstream.
939 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
941 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We
942 /// use this predicate to simplify operations downstream. Op and Mask are
943 /// known to be the same type.
944 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
947 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
948 /// known to be either zero or one and return them in the KnownZero/KnownOne
949 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
950 /// processing. Targets can implement the computeMaskedBitsForTargetNode
951 /// method in the TargetLowering class to allow target nodes to be understood.
952 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero,
953 APInt &KnownOne, unsigned Depth = 0) const;
955 /// ComputeNumSignBits - Return the number of times the sign bit of the
956 /// register is replicated into the other bits. We know that at least 1 bit
957 /// is always equal to the sign bit (itself), but other cases can give us
958 /// information. For example, immediately after an "SRA X, 2", we know that
959 /// the top 3 bits are all equal to each other, so we return 3. Targets can
960 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
961 /// class to allow target nodes to be understood.
962 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
964 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
965 bool isKnownNeverNaN(SDValue Op) const;
967 /// isKnownNeverZero - Test whether the given SDValue is known to never be
968 /// positive or negative Zero.
969 bool isKnownNeverZero(SDValue Op) const;
971 /// isEqualTo - Test whether two SDValues are known to compare equal. This
972 /// is true if they are the same value, or if one is negative zero and the
973 /// other positive zero.
974 bool isEqualTo(SDValue A, SDValue B) const;
976 /// isVerifiedDebugInfoDesc - Returns true if the specified SDValue has
977 /// been verified as a debug information descriptor.
978 bool isVerifiedDebugInfoDesc(SDValue Op) const;
980 /// UnrollVectorOp - Utility function used by legalize and lowering to
981 /// "unroll" a vector operation by splitting out the scalars and operating
982 /// on each element individually. If the ResNE is 0, fully unroll the vector
983 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
984 /// If the ResNE is greater than the width of the vector op, unroll the
985 /// vector op and fill the end of the resulting vector with UNDEFS.
986 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
988 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
989 /// location that is 'Dist' units away from the location that the 'Base' load
991 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
992 unsigned Bytes, int Dist) const;
994 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
995 /// it cannot be inferred.
996 unsigned InferPtrAlignment(SDValue Ptr) const;
999 bool RemoveNodeFromCSEMaps(SDNode *N);
1000 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener);
1001 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1002 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1004 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1007 void DeleteNodeNotInCSEMaps(SDNode *N);
1008 void DeallocateNode(SDNode *N);
1010 unsigned getEVTAlignment(EVT MemoryVT) const;
1012 void allnodes_clear();
1014 /// VTList - List of non-single value types.
1015 std::vector<SDVTList> VTList;
1017 /// CondCodeNodes - Maps to auto-CSE operations.
1018 std::vector<CondCodeSDNode*> CondCodeNodes;
1020 std::vector<SDNode*> ValueTypeNodes;
1021 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1022 StringMap<SDNode*> ExternalSymbols;
1024 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1027 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1028 typedef SelectionDAG::allnodes_iterator nodes_iterator;
1029 static nodes_iterator nodes_begin(SelectionDAG *G) {
1030 return G->allnodes_begin();
1032 static nodes_iterator nodes_end(SelectionDAG *G) {
1033 return G->allnodes_end();
1037 } // end namespace llvm