LLVM API Documentation
00001 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file declares the SelectionDAG class, and transitively defines the 00011 // SDNode class and subclasses. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_CODEGEN_SELECTIONDAG_H 00016 #define LLVM_CODEGEN_SELECTIONDAG_H 00017 00018 #include "llvm/ADT/ilist.h" 00019 #include "llvm/ADT/DenseSet.h" 00020 #include "llvm/ADT/StringMap.h" 00021 #include "llvm/CodeGen/SelectionDAGNodes.h" 00022 #include "llvm/Target/TargetMachine.h" 00023 #include <cassert> 00024 #include <vector> 00025 #include <map> 00026 #include <string> 00027 00028 namespace llvm { 00029 00030 class AliasAnalysis; 00031 class TargetLowering; 00032 class MachineModuleInfo; 00033 class DwarfWriter; 00034 class MachineFunction; 00035 class MachineConstantPoolValue; 00036 class FunctionLoweringInfo; 00037 00038 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> { 00039 private: 00040 mutable ilist_node<SDNode> Sentinel; 00041 public: 00042 SDNode *createSentinel() const { 00043 return static_cast<SDNode*>(&Sentinel); 00044 } 00045 static void destroySentinel(SDNode *) {} 00046 00047 SDNode *provideInitialHead() const { return createSentinel(); } 00048 SDNode *ensureHead(SDNode*) const { return createSentinel(); } 00049 static void noteHead(SDNode*, SDNode*) {} 00050 00051 static void deleteNode(SDNode *) { 00052 assert(0 && "ilist_traits<SDNode> shouldn't see a deleteNode call!"); 00053 } 00054 private: 00055 static void createNode(const SDNode &); 00056 }; 00057 00058 enum CombineLevel { 00059 Unrestricted, // Combine may create illegal operations and illegal types. 00060 NoIllegalTypes, // Combine may create illegal operations but no illegal types. 00061 NoIllegalOperations // Combine may only create legal operations and types. 00062 }; 00063 00064 /// SelectionDAG class - This is used to represent a portion of an LLVM function 00065 /// in a low-level Data Dependence DAG representation suitable for instruction 00066 /// selection. This DAG is constructed as the first step of instruction 00067 /// selection in order to allow implementation of machine specific optimizations 00068 /// and code simplifications. 00069 /// 00070 /// The representation used by the SelectionDAG is a target-independent 00071 /// representation, which has some similarities to the GCC RTL representation, 00072 /// but is significantly more simple, powerful, and is a graph form instead of a 00073 /// linear form. 00074 /// 00075 class SelectionDAG { 00076 TargetLowering &TLI; 00077 MachineFunction *MF; 00078 FunctionLoweringInfo &FLI; 00079 MachineModuleInfo *MMI; 00080 DwarfWriter *DW; 00081 LLVMContext* Context; 00082 00083 /// EntryNode - The starting token. 00084 SDNode EntryNode; 00085 00086 /// Root - The root of the entire DAG. 00087 SDValue Root; 00088 00089 /// AllNodes - A linked list of nodes in the current DAG. 00090 ilist<SDNode> AllNodes; 00091 00092 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use 00093 /// pool allocation with recycling. 00094 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode), 00095 AlignOf<MostAlignedSDNode>::Alignment> 00096 NodeAllocatorType; 00097 00098 /// NodeAllocator - Pool allocation for nodes. 00099 NodeAllocatorType NodeAllocator; 00100 00101 /// CSEMap - This structure is used to memoize nodes, automatically performing 00102 /// CSE with existing nodes when a duplicate is requested. 00103 FoldingSet<SDNode> CSEMap; 00104 00105 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands. 00106 BumpPtrAllocator OperandAllocator; 00107 00108 /// Allocator - Pool allocation for misc. objects that are created once per 00109 /// SelectionDAG. 00110 BumpPtrAllocator Allocator; 00111 00112 /// VerifyNode - Sanity check the given node. Aborts if it is invalid. 00113 void VerifyNode(SDNode *N); 00114 00115 /// setGraphColorHelper - Implementation of setSubgraphColor. 00116 /// Return whether we had to truncate the search. 00117 /// 00118 bool setSubgraphColorHelper(SDNode *N, const char *Color, 00119 DenseSet<SDNode *> &visited, 00120 int level, bool &printed); 00121 00122 public: 00123 SelectionDAG(TargetLowering &tli, FunctionLoweringInfo &fli); 00124 ~SelectionDAG(); 00125 00126 /// init - Prepare this SelectionDAG to process code in the given 00127 /// MachineFunction. 00128 /// 00129 void init(MachineFunction &mf, MachineModuleInfo *mmi, DwarfWriter *dw); 00130 00131 /// clear - Clear state and free memory necessary to make this 00132 /// SelectionDAG ready to process a new block. 00133 /// 00134 void clear(); 00135 00136 MachineFunction &getMachineFunction() const { return *MF; } 00137 const TargetMachine &getTarget() const; 00138 TargetLowering &getTargetLoweringInfo() const { return TLI; } 00139 FunctionLoweringInfo &getFunctionLoweringInfo() const { return FLI; } 00140 MachineModuleInfo *getMachineModuleInfo() const { return MMI; } 00141 DwarfWriter *getDwarfWriter() const { return DW; } 00142 LLVMContext *getContext() const {return Context; } 00143 00144 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 00145 /// 00146 void viewGraph(const std::string &Title); 00147 void viewGraph(); 00148 00149 #ifndef NDEBUG 00150 std::map<const SDNode *, std::string> NodeGraphAttrs; 00151 #endif 00152 00153 /// clearGraphAttrs - Clear all previously defined node graph attributes. 00154 /// Intended to be used from a debugging tool (eg. gdb). 00155 void clearGraphAttrs(); 00156 00157 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".) 00158 /// 00159 void setGraphAttrs(const SDNode *N, const char *Attrs); 00160 00161 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".) 00162 /// Used from getNodeAttributes. 00163 const std::string getGraphAttrs(const SDNode *N) const; 00164 00165 /// setGraphColor - Convenience for setting node color attribute. 00166 /// 00167 void setGraphColor(const SDNode *N, const char *Color); 00168 00169 /// setGraphColor - Convenience for setting subgraph color attribute. 00170 /// 00171 void setSubgraphColor(SDNode *N, const char *Color); 00172 00173 typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 00174 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 00175 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 00176 typedef ilist<SDNode>::iterator allnodes_iterator; 00177 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 00178 allnodes_iterator allnodes_end() { return AllNodes.end(); } 00179 ilist<SDNode>::size_type allnodes_size() const { 00180 return AllNodes.size(); 00181 } 00182 00183 /// getRoot - Return the root tag of the SelectionDAG. 00184 /// 00185 const SDValue &getRoot() const { return Root; } 00186 00187 /// getEntryNode - Return the token chain corresponding to the entry of the 00188 /// function. 00189 SDValue getEntryNode() const { 00190 return SDValue(const_cast<SDNode *>(&EntryNode), 0); 00191 } 00192 00193 /// setRoot - Set the current root tag of the SelectionDAG. 00194 /// 00195 const SDValue &setRoot(SDValue N) { 00196 assert((!N.getNode() || N.getValueType() == MVT::Other) && 00197 "DAG root value is not a chain!"); 00198 return Root = N; 00199 } 00200 00201 /// Combine - This iterates over the nodes in the SelectionDAG, folding 00202 /// certain types of nodes together, or eliminating superfluous nodes. The 00203 /// Level argument controls whether Combine is allowed to produce nodes and 00204 /// types that are illegal on the target. 00205 void Combine(CombineLevel Level, AliasAnalysis &AA, 00206 CodeGenOpt::Level OptLevel); 00207 00208 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 00209 /// only uses types natively supported by the target. Returns "true" if it 00210 /// made any changes. 00211 /// 00212 /// Note that this is an involved process that may invalidate pointers into 00213 /// the graph. 00214 bool LegalizeTypes(); 00215 00216 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 00217 /// compatible with the target instruction selector, as indicated by the 00218 /// TargetLowering object. 00219 /// 00220 /// Note that this is an involved process that may invalidate pointers into 00221 /// the graph. 00222 void Legalize(bool TypesNeedLegalizing, CodeGenOpt::Level OptLevel); 00223 00224 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG 00225 /// that only uses vector math operations supported by the target. This is 00226 /// necessary as a separate step from Legalize because unrolling a vector 00227 /// operation can introduce illegal types, which requires running 00228 /// LegalizeTypes again. 00229 /// 00230 /// This returns true if it made any changes; in that case, LegalizeTypes 00231 /// is called again before Legalize. 00232 /// 00233 /// Note that this is an involved process that may invalidate pointers into 00234 /// the graph. 00235 bool LegalizeVectors(); 00236 00237 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 00238 /// SelectionDAG. 00239 void RemoveDeadNodes(); 00240 00241 /// DeleteNode - Remove the specified node from the system. This node must 00242 /// have no referrers. 00243 void DeleteNode(SDNode *N); 00244 00245 /// getVTList - Return an SDVTList that represents the list of values 00246 /// specified. 00247 SDVTList getVTList(EVT VT); 00248 SDVTList getVTList(EVT VT1, EVT VT2); 00249 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3); 00250 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4); 00251 SDVTList getVTList(const EVT *VTs, unsigned NumVTs); 00252 00253 //===--------------------------------------------------------------------===// 00254 // Node creation methods. 00255 // 00256 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false); 00257 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false); 00258 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false); 00259 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false); 00260 SDValue getTargetConstant(uint64_t Val, EVT VT) { 00261 return getConstant(Val, VT, true); 00262 } 00263 SDValue getTargetConstant(const APInt &Val, EVT VT) { 00264 return getConstant(Val, VT, true); 00265 } 00266 SDValue getTargetConstant(const ConstantInt &Val, EVT VT) { 00267 return getConstant(Val, VT, true); 00268 } 00269 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false); 00270 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false); 00271 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false); 00272 SDValue getTargetConstantFP(double Val, EVT VT) { 00273 return getConstantFP(Val, VT, true); 00274 } 00275 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) { 00276 return getConstantFP(Val, VT, true); 00277 } 00278 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) { 00279 return getConstantFP(Val, VT, true); 00280 } 00281 SDValue getGlobalAddress(const GlobalValue *GV, EVT VT, 00282 int64_t offset = 0, bool isTargetGA = false, 00283 unsigned char TargetFlags = 0); 00284 SDValue getTargetGlobalAddress(const GlobalValue *GV, EVT VT, 00285 int64_t offset = 0, 00286 unsigned char TargetFlags = 0) { 00287 return getGlobalAddress(GV, VT, offset, true, TargetFlags); 00288 } 00289 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false); 00290 SDValue getTargetFrameIndex(int FI, EVT VT) { 00291 return getFrameIndex(FI, VT, true); 00292 } 00293 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false, 00294 unsigned char TargetFlags = 0); 00295 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) { 00296 return getJumpTable(JTI, VT, true, TargetFlags); 00297 } 00298 SDValue getConstantPool(Constant *C, EVT VT, 00299 unsigned Align = 0, int Offs = 0, bool isT=false, 00300 unsigned char TargetFlags = 0); 00301 SDValue getTargetConstantPool(Constant *C, EVT VT, 00302 unsigned Align = 0, int Offset = 0, 00303 unsigned char TargetFlags = 0) { 00304 return getConstantPool(C, VT, Align, Offset, true, TargetFlags); 00305 } 00306 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT, 00307 unsigned Align = 0, int Offs = 0, bool isT=false, 00308 unsigned char TargetFlags = 0); 00309 SDValue getTargetConstantPool(MachineConstantPoolValue *C, 00310 EVT VT, unsigned Align = 0, 00311 int Offset = 0, unsigned char TargetFlags=0) { 00312 return getConstantPool(C, VT, Align, Offset, true, TargetFlags); 00313 } 00314 // When generating a branch to a BB, we don't in general know enough 00315 // to provide debug info for the BB at that time, so keep this one around. 00316 SDValue getBasicBlock(MachineBasicBlock *MBB); 00317 SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl); 00318 SDValue getExternalSymbol(const char *Sym, EVT VT); 00319 SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT); 00320 SDValue getTargetExternalSymbol(const char *Sym, EVT VT, 00321 unsigned char TargetFlags = 0); 00322 SDValue getValueType(EVT); 00323 SDValue getRegister(unsigned Reg, EVT VT); 00324 SDValue getDbgStopPoint(DebugLoc DL, SDValue Root, 00325 unsigned Line, unsigned Col, Value *CU); 00326 SDValue getLabel(unsigned Opcode, DebugLoc dl, SDValue Root, 00327 unsigned LabelID); 00328 00329 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) { 00330 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, 00331 getRegister(Reg, N.getValueType()), N); 00332 } 00333 00334 // This version of the getCopyToReg method takes an extra operand, which 00335 // indicates that there is potentially an incoming flag value (if Flag is not 00336 // null) and that there should be a flag result. 00337 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N, 00338 SDValue Flag) { 00339 SDVTList VTs = getVTList(MVT::Other, MVT::Flag); 00340 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; 00341 return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3); 00342 } 00343 00344 // Similar to last getCopyToReg() except parameter Reg is a SDValue 00345 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N, 00346 SDValue Flag) { 00347 SDVTList VTs = getVTList(MVT::Other, MVT::Flag); 00348 SDValue Ops[] = { Chain, Reg, N, Flag }; 00349 return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3); 00350 } 00351 00352 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) { 00353 SDVTList VTs = getVTList(VT, MVT::Other); 00354 SDValue Ops[] = { Chain, getRegister(Reg, VT) }; 00355 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2); 00356 } 00357 00358 // This version of the getCopyFromReg method takes an extra operand, which 00359 // indicates that there is potentially an incoming flag value (if Flag is not 00360 // null) and that there should be a flag result. 00361 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT, 00362 SDValue Flag) { 00363 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Flag); 00364 SDValue Ops[] = { Chain, getRegister(Reg, VT), Flag }; 00365 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Flag.getNode() ? 3 : 2); 00366 } 00367 00368 SDValue getCondCode(ISD::CondCode Cond); 00369 00370 /// Returns the ConvertRndSat Note: Avoid using this node because it may 00371 /// disappear in the future and most targets don't support it. 00372 SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy, 00373 SDValue STy, 00374 SDValue Rnd, SDValue Sat, ISD::CvtCode Code); 00375 00376 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of 00377 /// elements in VT, which must be a vector type, must match the number of 00378 /// mask elements NumElts. A integer mask element equal to -1 is treated as 00379 /// undefined. 00380 SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2, 00381 const int *MaskElts); 00382 00383 /// getZeroExtendInReg - Return the expression required to zero extend the Op 00384 /// value assuming it was the smaller SrcTy value. 00385 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy); 00386 00387 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). 00388 SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT); 00389 00390 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 00391 /// a flag result (to ensure it's not CSE'd). CALLSEQ_START does not have a 00392 /// useful DebugLoc. 00393 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) { 00394 SDVTList VTs = getVTList(MVT::Other, MVT::Flag); 00395 SDValue Ops[] = { Chain, Op }; 00396 return getNode(ISD::CALLSEQ_START, DebugLoc::getUnknownLoc(), 00397 VTs, Ops, 2); 00398 } 00399 00400 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a 00401 /// flag result (to ensure it's not CSE'd). CALLSEQ_END does not have 00402 /// a useful DebugLoc. 00403 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, 00404 SDValue InFlag) { 00405 SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag); 00406 SmallVector<SDValue, 4> Ops; 00407 Ops.push_back(Chain); 00408 Ops.push_back(Op1); 00409 Ops.push_back(Op2); 00410 Ops.push_back(InFlag); 00411 return getNode(ISD::CALLSEQ_END, DebugLoc::getUnknownLoc(), NodeTys, 00412 &Ops[0], 00413 (unsigned)Ops.size() - (InFlag.getNode() == 0 ? 1 : 0)); 00414 } 00415 00416 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc. 00417 SDValue getUNDEF(EVT VT) { 00418 return getNode(ISD::UNDEF, DebugLoc::getUnknownLoc(), VT); 00419 } 00420 00421 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does 00422 /// not have a useful DebugLoc. 00423 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) { 00424 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc::getUnknownLoc(), VT); 00425 } 00426 00427 /// getNode - Gets or creates the specified node. 00428 /// 00429 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT); 00430 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N); 00431 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2); 00432 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 00433 SDValue N1, SDValue N2, SDValue N3); 00434 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 00435 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 00436 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 00437 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 00438 SDValue N5); 00439 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 00440 const SDUse *Ops, unsigned NumOps); 00441 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 00442 const SDValue *Ops, unsigned NumOps); 00443 SDValue getNode(unsigned Opcode, DebugLoc DL, 00444 const std::vector<EVT> &ResultTys, 00445 const SDValue *Ops, unsigned NumOps); 00446 SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs, 00447 const SDValue *Ops, unsigned NumOps); 00448 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 00449 const SDValue *Ops, unsigned NumOps); 00450 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs); 00451 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N); 00452 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 00453 SDValue N1, SDValue N2); 00454 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 00455 SDValue N1, SDValue N2, SDValue N3); 00456 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 00457 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 00458 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 00459 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 00460 SDValue N5); 00461 00462 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all 00463 /// the incoming stack arguments to be loaded from the stack. This is 00464 /// used in tail call lowering to protect stack arguments from being 00465 /// clobbered. 00466 SDValue getStackArgumentTokenFactor(SDValue Chain); 00467 00468 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 00469 SDValue Size, unsigned Align, bool AlwaysInline, 00470 const Value *DstSV, uint64_t DstSVOff, 00471 const Value *SrcSV, uint64_t SrcSVOff); 00472 00473 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 00474 SDValue Size, unsigned Align, 00475 const Value *DstSV, uint64_t DstOSVff, 00476 const Value *SrcSV, uint64_t SrcSVOff); 00477 00478 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 00479 SDValue Size, unsigned Align, 00480 const Value *DstSV, uint64_t DstSVOff); 00481 00482 /// getSetCC - Helper function to make it easier to build SetCC's if you just 00483 /// have an ISD::CondCode instead of an SDValue. 00484 /// 00485 SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS, 00486 ISD::CondCode Cond) { 00487 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 00488 } 00489 00490 /// getVSetCC - Helper function to make it easier to build VSetCC's nodes 00491 /// if you just have an ISD::CondCode instead of an SDValue. 00492 /// 00493 SDValue getVSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS, 00494 ISD::CondCode Cond) { 00495 return getNode(ISD::VSETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 00496 } 00497 00498 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 00499 /// just have an ISD::CondCode instead of an SDValue. 00500 /// 00501 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS, 00502 SDValue True, SDValue False, ISD::CondCode Cond) { 00503 return getNode(ISD::SELECT_CC, DL, True.getValueType(), 00504 LHS, RHS, True, False, getCondCode(Cond)); 00505 } 00506 00507 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 00508 /// and a source value as input. 00509 SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, 00510 SDValue SV); 00511 00512 /// getAtomic - Gets a node for an atomic op, produces result and chain and 00513 /// takes 3 operands 00514 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, 00515 SDValue Ptr, SDValue Cmp, SDValue Swp, const Value* PtrVal, 00516 unsigned Alignment=0); 00517 00518 /// getAtomic - Gets a node for an atomic op, produces result and chain and 00519 /// takes 2 operands. 00520 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, 00521 SDValue Ptr, SDValue Val, const Value* PtrVal, 00522 unsigned Alignment = 0); 00523 00524 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a 00525 /// result and takes a list of operands. 00526 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, 00527 const EVT *VTs, unsigned NumVTs, 00528 const SDValue *Ops, unsigned NumOps, 00529 EVT MemVT, const Value *srcValue, int SVOff, 00530 unsigned Align = 0, bool Vol = false, 00531 bool ReadMem = true, bool WriteMem = true); 00532 00533 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 00534 const SDValue *Ops, unsigned NumOps, 00535 EVT MemVT, const Value *srcValue, int SVOff, 00536 unsigned Align = 0, bool Vol = false, 00537 bool ReadMem = true, bool WriteMem = true); 00538 00539 /// getMergeValues - Create a MERGE_VALUES node from the given operands. 00540 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl); 00541 00542 /// getLoad - Loads are not normal binary operators: their result type is not 00543 /// determined by their operands, and they produce a value AND a token chain. 00544 /// 00545 SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, 00546 const Value *SV, int SVOffset, bool isVolatile=false, 00547 unsigned Alignment=0); 00548 SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT, 00549 SDValue Chain, SDValue Ptr, const Value *SV, 00550 int SVOffset, EVT EVT, bool isVolatile=false, 00551 unsigned Alignment=0); 00552 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, 00553 SDValue Offset, ISD::MemIndexedMode AM); 00554 SDValue getLoad(ISD::MemIndexedMode AM, DebugLoc dl, ISD::LoadExtType ExtType, 00555 EVT VT, SDValue Chain, 00556 SDValue Ptr, SDValue Offset, 00557 const Value *SV, int SVOffset, EVT EVT, 00558 bool isVolatile=false, unsigned Alignment=0); 00559 00560 /// getStore - Helper function to build ISD::STORE nodes. 00561 /// 00562 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 00563 const Value *SV, int SVOffset, bool isVolatile=false, 00564 unsigned Alignment=0); 00565 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 00566 const Value *SV, int SVOffset, EVT TVT, 00567 bool isVolatile=false, unsigned Alignment=0); 00568 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base, 00569 SDValue Offset, ISD::MemIndexedMode AM); 00570 00571 /// getSrcValue - Construct a node to track a Value* through the backend. 00572 SDValue getSrcValue(const Value *v); 00573 00574 /// getMemOperand - Construct a node to track a memory reference 00575 /// through the backend. 00576 SDValue getMemOperand(const MachineMemOperand &MO); 00577 00578 /// getShiftAmountOperand - Return the specified value casted to 00579 /// the target's desired shift amount type. 00580 SDValue getShiftAmountOperand(SDValue Op); 00581 00582 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 00583 /// specified operands. If the resultant node already exists in the DAG, 00584 /// this does not modify the specified node, instead it returns the node that 00585 /// already exists. If the resultant node does not exist in the DAG, the 00586 /// input node is returned. As a degenerate case, if you specify the same 00587 /// input operands as the node already has, the input node is returned. 00588 SDValue UpdateNodeOperands(SDValue N, SDValue Op); 00589 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2); 00590 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 00591 SDValue Op3); 00592 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 00593 SDValue Op3, SDValue Op4); 00594 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 00595 SDValue Op3, SDValue Op4, SDValue Op5); 00596 SDValue UpdateNodeOperands(SDValue N, 00597 const SDValue *Ops, unsigned NumOps); 00598 00599 /// SelectNodeTo - These are used for target selectors to *mutate* the 00600 /// specified node to have the specified return type, Target opcode, and 00601 /// operands. Note that target opcodes are stored as 00602 /// ~TargetOpcode in the node opcode field. The resultant node is returned. 00603 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT); 00604 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1); 00605 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 00606 SDValue Op1, SDValue Op2); 00607 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 00608 SDValue Op1, SDValue Op2, SDValue Op3); 00609 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 00610 const SDValue *Ops, unsigned NumOps); 00611 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2); 00612 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 00613 EVT VT2, const SDValue *Ops, unsigned NumOps); 00614 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 00615 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps); 00616 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 00617 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops, 00618 unsigned NumOps); 00619 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 00620 EVT VT2, SDValue Op1); 00621 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 00622 EVT VT2, SDValue Op1, SDValue Op2); 00623 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 00624 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 00625 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 00626 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); 00627 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs, 00628 const SDValue *Ops, unsigned NumOps); 00629 00630 /// MorphNodeTo - These *mutate* the specified node to have the specified 00631 /// return type, opcode, and operands. 00632 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT); 00633 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT, SDValue Op1); 00634 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT, 00635 SDValue Op1, SDValue Op2); 00636 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT, 00637 SDValue Op1, SDValue Op2, SDValue Op3); 00638 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT, 00639 const SDValue *Ops, unsigned NumOps); 00640 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1, EVT VT2); 00641 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1, 00642 EVT VT2, const SDValue *Ops, unsigned NumOps); 00643 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1, 00644 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps); 00645 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1, 00646 EVT VT2, SDValue Op1); 00647 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1, 00648 EVT VT2, SDValue Op1, SDValue Op2); 00649 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1, 00650 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 00651 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, 00652 const SDValue *Ops, unsigned NumOps); 00653 00654 /// getTargetNode - These are used for target selectors to create a new node 00655 /// with specified return type(s), target opcode, and operands. 00656 /// 00657 /// Note that getTargetNode returns the resultant node. If there is already a 00658 /// node of the specified opcode and operands, it returns that node instead of 00659 /// the current one. 00660 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT); 00661 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1); 00662 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1, 00663 SDValue Op2); 00664 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT, 00665 SDValue Op1, SDValue Op2, SDValue Op3); 00666 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT, 00667 const SDValue *Ops, unsigned NumOps); 00668 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2); 00669 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, 00670 SDValue Op1); 00671 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, 00672 EVT VT2, SDValue Op1, SDValue Op2); 00673 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, 00674 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 00675 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, 00676 const SDValue *Ops, unsigned NumOps); 00677 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, EVT VT3, 00678 SDValue Op1, SDValue Op2); 00679 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, EVT VT3, 00680 SDValue Op1, SDValue Op2, SDValue Op3); 00681 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, EVT VT3, 00682 const SDValue *Ops, unsigned NumOps); 00683 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, EVT VT3, 00684 EVT VT4, const SDValue *Ops, unsigned NumOps); 00685 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, 00686 const std::vector<EVT> &ResultTys, const SDValue *Ops, 00687 unsigned NumOps); 00688 00689 /// getTargetExtractSubreg - A convenience function for creating 00690 /// TargetInstrInfo::EXTRACT_SUBREG nodes. 00691 SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT, 00692 SDValue Operand); 00693 00694 /// getNodeIfExists - Get the specified node if it's already available, or 00695 /// else return NULL. 00696 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, 00697 const SDValue *Ops, unsigned NumOps); 00698 00699 /// DAGUpdateListener - Clients of various APIs that cause global effects on 00700 /// the DAG can optionally implement this interface. This allows the clients 00701 /// to handle the various sorts of updates that happen. 00702 class DAGUpdateListener { 00703 public: 00704 virtual ~DAGUpdateListener(); 00705 00706 /// NodeDeleted - The node N that was deleted and, if E is not null, an 00707 /// equivalent node E that replaced it. 00708 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0; 00709 00710 /// NodeUpdated - The node N that was updated. 00711 virtual void NodeUpdated(SDNode *N) = 0; 00712 }; 00713 00714 /// RemoveDeadNode - Remove the specified node from the system. If any of its 00715 /// operands then becomes dead, remove them as well. Inform UpdateListener 00716 /// for each node deleted. 00717 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0); 00718 00719 /// RemoveDeadNodes - This method deletes the unreachable nodes in the 00720 /// given list, and any nodes that become unreachable as a result. 00721 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes, 00722 DAGUpdateListener *UpdateListener = 0); 00723 00724 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 00725 /// This can cause recursive merging of nodes in the DAG. Use the first 00726 /// version if 'From' is known to have a single result, use the second 00727 /// if you have two nodes with identical results (or if 'To' has a superset 00728 /// of the results of 'From'), use the third otherwise. 00729 /// 00730 /// These methods all take an optional UpdateListener, which (if not null) is 00731 /// informed about nodes that are deleted and modified due to recursive 00732 /// changes in the dag. 00733 /// 00734 /// These functions only replace all existing uses. It's possible that as 00735 /// these replacements are being performed, CSE may cause the From node 00736 /// to be given new uses. These new uses of From are left in place, and 00737 /// not automatically transfered to To. 00738 /// 00739 void ReplaceAllUsesWith(SDValue From, SDValue Op, 00740 DAGUpdateListener *UpdateListener = 0); 00741 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 00742 DAGUpdateListener *UpdateListener = 0); 00743 void ReplaceAllUsesWith(SDNode *From, const SDValue *To, 00744 DAGUpdateListener *UpdateListener = 0); 00745 00746 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 00747 /// uses of other values produced by From.Val alone. 00748 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To, 00749 DAGUpdateListener *UpdateListener = 0); 00750 00751 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but 00752 /// for multiple values at once. This correctly handles the case where 00753 /// there is an overlap between the From values and the To values. 00754 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, 00755 unsigned Num, 00756 DAGUpdateListener *UpdateListener = 0); 00757 00758 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a 00759 /// assign a unique node id for each node in the DAG based on their 00760 /// topological order. Returns the number of nodes. 00761 unsigned AssignTopologicalOrder(); 00762 00763 /// RepositionNode - Move node N in the AllNodes list to be immediately 00764 /// before the given iterator Position. This may be used to update the 00765 /// topological ordering when the list of nodes is modified. 00766 void RepositionNode(allnodes_iterator Position, SDNode *N) { 00767 AllNodes.insert(Position, AllNodes.remove(N)); 00768 } 00769 00770 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 00771 /// operation. 00772 static bool isCommutativeBinOp(unsigned Opcode) { 00773 // FIXME: This should get its info from the td file, so that we can include 00774 // target info. 00775 switch (Opcode) { 00776 case ISD::ADD: 00777 case ISD::MUL: 00778 case ISD::MULHU: 00779 case ISD::MULHS: 00780 case ISD::SMUL_LOHI: 00781 case ISD::UMUL_LOHI: 00782 case ISD::FADD: 00783 case ISD::FMUL: 00784 case ISD::AND: 00785 case ISD::OR: 00786 case ISD::XOR: 00787 case ISD::SADDO: 00788 case ISD::UADDO: 00789 case ISD::ADDC: 00790 case ISD::ADDE: return true; 00791 default: return false; 00792 } 00793 } 00794 00795 void dump() const; 00796 00797 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 00798 /// specified value type. If minAlign is specified, the slot size will have 00799 /// at least that alignment. 00800 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1); 00801 00802 /// CreateStackTemporary - Create a stack temporary suitable for holding 00803 /// either of the specified value types. 00804 SDValue CreateStackTemporary(EVT VT1, EVT VT2); 00805 00806 /// FoldConstantArithmetic - 00807 SDValue FoldConstantArithmetic(unsigned Opcode, 00808 EVT VT, 00809 ConstantSDNode *Cst1, 00810 ConstantSDNode *Cst2); 00811 00812 /// FoldSetCC - Constant fold a setcc to true or false. 00813 SDValue FoldSetCC(EVT VT, SDValue N1, 00814 SDValue N2, ISD::CondCode Cond, DebugLoc dl); 00815 00816 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 00817 /// use this predicate to simplify operations downstream. 00818 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const; 00819 00820 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 00821 /// use this predicate to simplify operations downstream. Op and Mask are 00822 /// known to be the same type. 00823 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0) 00824 const; 00825 00826 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 00827 /// known to be either zero or one and return them in the KnownZero/KnownOne 00828 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 00829 /// processing. Targets can implement the computeMaskedBitsForTargetNode 00830 /// method in the TargetLowering class to allow target nodes to be understood. 00831 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero, 00832 APInt &KnownOne, unsigned Depth = 0) const; 00833 00834 /// ComputeNumSignBits - Return the number of times the sign bit of the 00835 /// register is replicated into the other bits. We know that at least 1 bit 00836 /// is always equal to the sign bit (itself), but other cases can give us 00837 /// information. For example, immediately after an "SRA X, 2", we know that 00838 /// the top 3 bits are all equal to each other, so we return 3. Targets can 00839 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 00840 /// class to allow target nodes to be understood. 00841 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; 00842 00843 /// isVerifiedDebugInfoDesc - Returns true if the specified SDValue has 00844 /// been verified as a debug information descriptor. 00845 bool isVerifiedDebugInfoDesc(SDValue Op) const; 00846 00847 /// getShuffleScalarElt - Returns the scalar element that will make up the ith 00848 /// element of the result of the vector shuffle. 00849 SDValue getShuffleScalarElt(const ShuffleVectorSDNode *N, unsigned Idx); 00850 00851 private: 00852 bool RemoveNodeFromCSEMaps(SDNode *N); 00853 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener); 00854 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); 00855 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, 00856 void *&InsertPos); 00857 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps, 00858 void *&InsertPos); 00859 00860 void DeleteNodeNotInCSEMaps(SDNode *N); 00861 void DeallocateNode(SDNode *N); 00862 00863 unsigned getEVTAlignment(EVT MemoryVT) const; 00864 00865 void allnodes_clear(); 00866 00867 /// VTList - List of non-single value types. 00868 std::vector<SDVTList> VTList; 00869 00870 /// CondCodeNodes - Maps to auto-CSE operations. 00871 std::vector<CondCodeSDNode*> CondCodeNodes; 00872 00873 std::vector<SDNode*> ValueTypeNodes; 00874 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes; 00875 StringMap<SDNode*> ExternalSymbols; 00876 00877 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols; 00878 }; 00879 00880 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 00881 typedef SelectionDAG::allnodes_iterator nodes_iterator; 00882 static nodes_iterator nodes_begin(SelectionDAG *G) { 00883 return G->allnodes_begin(); 00884 } 00885 static nodes_iterator nodes_end(SelectionDAG *G) { 00886 return G->allnodes_end(); 00887 } 00888 }; 00889 00890 } // end namespace llvm 00891 00892 #endif