SelectionDAG.h revision 2a4ed82ce2ba4a02f2a02eb4ed8ce5186f3f93da
1//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file declares the SelectionDAG class, and transitively defines the 11// SDNode class and subclasses. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CODEGEN_SELECTIONDAG_H 16#define LLVM_CODEGEN_SELECTIONDAG_H 17 18#include "llvm/ADT/ilist.h" 19#include "llvm/ADT/DenseSet.h" 20#include "llvm/ADT/FoldingSet.h" 21#include "llvm/ADT/StringMap.h" 22#include "llvm/CodeGen/SelectionDAGNodes.h" 23#include "llvm/Target/TargetMachine.h" 24#include <cassert> 25#include <vector> 26#include <map> 27#include <string> 28 29namespace llvm { 30 31class AliasAnalysis; 32class TargetLowering; 33class MachineModuleInfo; 34class DwarfWriter; 35class MachineFunction; 36class MachineConstantPoolValue; 37class FunctionLoweringInfo; 38 39template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> { 40private: 41 mutable ilist_node<SDNode> Sentinel; 42public: 43 SDNode *createSentinel() const { 44 return static_cast<SDNode*>(&Sentinel); 45 } 46 static void destroySentinel(SDNode *) {} 47 48 SDNode *provideInitialHead() const { return createSentinel(); } 49 SDNode *ensureHead(SDNode*) const { return createSentinel(); } 50 static void noteHead(SDNode*, SDNode*) {} 51 52 static void deleteNode(SDNode *) { 53 assert(0 && "ilist_traits<SDNode> shouldn't see a deleteNode call!"); 54 } 55private: 56 static void createNode(const SDNode &); 57}; 58 59enum CombineLevel { 60 Unrestricted, // Combine may create illegal operations and illegal types. 61 NoIllegalTypes, // Combine may create illegal operations but no illegal types. 62 NoIllegalOperations // Combine may only create legal operations and types. 63}; 64 65/// SelectionDAG class - This is used to represent a portion of an LLVM function 66/// in a low-level Data Dependence DAG representation suitable for instruction 67/// selection. This DAG is constructed as the first step of instruction 68/// selection in order to allow implementation of machine specific optimizations 69/// and code simplifications. 70/// 71/// The representation used by the SelectionDAG is a target-independent 72/// representation, which has some similarities to the GCC RTL representation, 73/// but is significantly more simple, powerful, and is a graph form instead of a 74/// linear form. 75/// 76class SelectionDAG { 77 TargetLowering &TLI; 78 MachineFunction *MF; 79 FunctionLoweringInfo &FLI; 80 MachineModuleInfo *MMI; 81 DwarfWriter *DW; 82 83 /// EntryNode - The starting token. 84 SDNode EntryNode; 85 86 /// Root - The root of the entire DAG. 87 SDValue Root; 88 89 /// AllNodes - A linked list of nodes in the current DAG. 90 ilist<SDNode> AllNodes; 91 92 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use 93 /// pool allocation with recycling. 94 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode), 95 AlignOf<MostAlignedSDNode>::Alignment> 96 NodeAllocatorType; 97 98 /// NodeAllocator - Pool allocation for nodes. 99 NodeAllocatorType NodeAllocator; 100 101 /// CSEMap - This structure is used to memoize nodes, automatically performing 102 /// CSE with existing nodes with a duplicate is requested. 103 FoldingSet<SDNode> CSEMap; 104 105 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands. 106 BumpPtrAllocator OperandAllocator; 107 108 /// Allocator - Pool allocation for misc. objects that are created once per 109 /// SelectionDAG. 110 BumpPtrAllocator Allocator; 111 112 /// VerifyNode - Sanity check the given node. Aborts if it is invalid. 113 void VerifyNode(SDNode *N); 114 115 /// setGraphColorHelper - Implementation of setSubgraphColor. 116 /// Return whether we had to truncate the search. 117 /// 118 bool setSubgraphColorHelper(SDNode *N, const char *Color, 119 DenseSet<SDNode *> &visited, 120 int level, bool &printed); 121 122public: 123 SelectionDAG(TargetLowering &tli, FunctionLoweringInfo &fli); 124 ~SelectionDAG(); 125 126 /// init - Prepare this SelectionDAG to process code in the given 127 /// MachineFunction. 128 /// 129 void init(MachineFunction &mf, MachineModuleInfo *mmi, DwarfWriter *dw); 130 131 /// clear - Clear state and free memory necessary to make this 132 /// SelectionDAG ready to process a new block. 133 /// 134 void clear(); 135 136 MachineFunction &getMachineFunction() const { return *MF; } 137 const TargetMachine &getTarget() const; 138 TargetLowering &getTargetLoweringInfo() const { return TLI; } 139 FunctionLoweringInfo &getFunctionLoweringInfo() const { return FLI; } 140 MachineModuleInfo *getMachineModuleInfo() const { return MMI; } 141 DwarfWriter *getDwarfWriter() const { return DW; } 142 143 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 144 /// 145 void viewGraph(const std::string &Title); 146 void viewGraph(); 147 148#ifndef NDEBUG 149 std::map<const SDNode *, std::string> NodeGraphAttrs; 150#endif 151 152 /// clearGraphAttrs - Clear all previously defined node graph attributes. 153 /// Intended to be used from a debugging tool (eg. gdb). 154 void clearGraphAttrs(); 155 156 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".) 157 /// 158 void setGraphAttrs(const SDNode *N, const char *Attrs); 159 160 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".) 161 /// Used from getNodeAttributes. 162 const std::string getGraphAttrs(const SDNode *N) const; 163 164 /// setGraphColor - Convenience for setting node color attribute. 165 /// 166 void setGraphColor(const SDNode *N, const char *Color); 167 168 /// setGraphColor - Convenience for setting subgraph color attribute. 169 /// 170 void setSubgraphColor(SDNode *N, const char *Color); 171 172 typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 173 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 174 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 175 typedef ilist<SDNode>::iterator allnodes_iterator; 176 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 177 allnodes_iterator allnodes_end() { return AllNodes.end(); } 178 ilist<SDNode>::size_type allnodes_size() const { 179 return AllNodes.size(); 180 } 181 182 /// getRoot - Return the root tag of the SelectionDAG. 183 /// 184 const SDValue &getRoot() const { return Root; } 185 186 /// getEntryNode - Return the token chain corresponding to the entry of the 187 /// function. 188 SDValue getEntryNode() const { 189 return SDValue(const_cast<SDNode *>(&EntryNode), 0); 190 } 191 192 /// setRoot - Set the current root tag of the SelectionDAG. 193 /// 194 const SDValue &setRoot(SDValue N) { 195 assert((!N.getNode() || N.getValueType() == MVT::Other) && 196 "DAG root value is not a chain!"); 197 return Root = N; 198 } 199 200 /// Combine - This iterates over the nodes in the SelectionDAG, folding 201 /// certain types of nodes together, or eliminating superfluous nodes. The 202 /// Level argument controls whether Combine is allowed to produce nodes and 203 /// types that are illegal on the target. 204 void Combine(CombineLevel Level, AliasAnalysis &AA, 205 CodeGenOpt::Level OptLevel); 206 207 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 208 /// only uses types natively supported by the target. Returns "true" if it 209 /// made any changes. 210 /// 211 /// Note that this is an involved process that may invalidate pointers into 212 /// the graph. 213 bool LegalizeTypes(); 214 215 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 216 /// compatible with the target instruction selector, as indicated by the 217 /// TargetLowering object. 218 /// 219 /// Note that this is an involved process that may invalidate pointers into 220 /// the graph. 221 void Legalize(bool TypesNeedLegalizing, CodeGenOpt::Level OptLevel); 222 223 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG 224 /// that only uses vector math operations supported by the target. This is 225 /// necessary as a separate step from Legalize because unrolling a vector 226 /// operation can introduce illegal types, which requires running 227 /// LegalizeTypes again. 228 /// 229 /// This returns true if it made any changes; in that case, LegalizeTypes 230 /// is called again before Legalize. 231 /// 232 /// Note that this is an involved process that may invalidate pointers into 233 /// the graph. 234 bool LegalizeVectors(); 235 236 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 237 /// SelectionDAG. 238 void RemoveDeadNodes(); 239 240 /// DeleteNode - Remove the specified node from the system. This node must 241 /// have no referrers. 242 void DeleteNode(SDNode *N); 243 244 /// getVTList - Return an SDVTList that represents the list of values 245 /// specified. 246 SDVTList getVTList(MVT VT); 247 SDVTList getVTList(MVT VT1, MVT VT2); 248 SDVTList getVTList(MVT VT1, MVT VT2, MVT VT3); 249 SDVTList getVTList(MVT VT1, MVT VT2, MVT VT3, MVT VT4); 250 SDVTList getVTList(const MVT *VTs, unsigned NumVTs); 251 252 //===--------------------------------------------------------------------===// 253 // Node creation methods. 254 // 255 SDValue getConstant(uint64_t Val, MVT VT, bool isTarget = false); 256 SDValue getConstant(const APInt &Val, MVT VT, bool isTarget = false); 257 SDValue getConstant(const ConstantInt &Val, MVT VT, bool isTarget = false); 258 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false); 259 SDValue getTargetConstant(uint64_t Val, MVT VT) { 260 return getConstant(Val, VT, true); 261 } 262 SDValue getTargetConstant(const APInt &Val, MVT VT) { 263 return getConstant(Val, VT, true); 264 } 265 SDValue getTargetConstant(const ConstantInt &Val, MVT VT) { 266 return getConstant(Val, VT, true); 267 } 268 SDValue getConstantFP(double Val, MVT VT, bool isTarget = false); 269 SDValue getConstantFP(const APFloat& Val, MVT VT, bool isTarget = false); 270 SDValue getConstantFP(const ConstantFP &CF, MVT VT, bool isTarget = false); 271 SDValue getTargetConstantFP(double Val, MVT VT) { 272 return getConstantFP(Val, VT, true); 273 } 274 SDValue getTargetConstantFP(const APFloat& Val, MVT VT) { 275 return getConstantFP(Val, VT, true); 276 } 277 SDValue getTargetConstantFP(const ConstantFP &Val, MVT VT) { 278 return getConstantFP(Val, VT, true); 279 } 280 SDValue getGlobalAddress(const GlobalValue *GV, MVT VT, 281 int64_t offset = 0, bool isTargetGA = false, 282 unsigned char TargetFlags = 0); 283 SDValue getTargetGlobalAddress(const GlobalValue *GV, MVT VT, 284 int64_t offset = 0, 285 unsigned char TargetFlags = 0) { 286 return getGlobalAddress(GV, VT, offset, true, TargetFlags); 287 } 288 SDValue getFrameIndex(int FI, MVT VT, bool isTarget = false); 289 SDValue getTargetFrameIndex(int FI, MVT VT) { 290 return getFrameIndex(FI, VT, true); 291 } 292 SDValue getJumpTable(int JTI, MVT VT, bool isTarget = false); 293 SDValue getTargetJumpTable(int JTI, MVT VT) { 294 return getJumpTable(JTI, VT, true); 295 } 296 SDValue getConstantPool(Constant *C, MVT VT, 297 unsigned Align = 0, int Offs = 0, bool isT=false); 298 SDValue getTargetConstantPool(Constant *C, MVT VT, 299 unsigned Align = 0, int Offset = 0) { 300 return getConstantPool(C, VT, Align, Offset, true); 301 } 302 SDValue getConstantPool(MachineConstantPoolValue *C, MVT VT, 303 unsigned Align = 0, int Offs = 0, bool isT=false); 304 SDValue getTargetConstantPool(MachineConstantPoolValue *C, 305 MVT VT, unsigned Align = 0, 306 int Offset = 0) { 307 return getConstantPool(C, VT, Align, Offset, true); 308 } 309 // When generating a branch to a BB, we don't in general know enough 310 // to provide debug info for the BB at that time, so keep this one around. 311 SDValue getBasicBlock(MachineBasicBlock *MBB); 312 SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl); 313 SDValue getExternalSymbol(const char *Sym, MVT VT); 314 SDValue getExternalSymbol(const char *Sym, DebugLoc dl, MVT VT); 315 SDValue getTargetExternalSymbol(const char *Sym, MVT VT, 316 unsigned char TargetFlags = 0); 317 SDValue getArgFlags(ISD::ArgFlagsTy Flags); 318 SDValue getValueType(MVT); 319 SDValue getRegister(unsigned Reg, MVT VT); 320 SDValue getDbgStopPoint(DebugLoc DL, SDValue Root, 321 unsigned Line, unsigned Col, Value *CU); 322 SDValue getLabel(unsigned Opcode, DebugLoc dl, SDValue Root, 323 unsigned LabelID); 324 325 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) { 326 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, 327 getRegister(Reg, N.getValueType()), N); 328 } 329 330 // This version of the getCopyToReg method takes an extra operand, which 331 // indicates that there is potentially an incoming flag value (if Flag is not 332 // null) and that there should be a flag result. 333 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N, 334 SDValue Flag) { 335 SDVTList VTs = getVTList(MVT::Other, MVT::Flag); 336 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; 337 return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3); 338 } 339 340 // Similar to last getCopyToReg() except parameter Reg is a SDValue 341 SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N, 342 SDValue Flag) { 343 SDVTList VTs = getVTList(MVT::Other, MVT::Flag); 344 SDValue Ops[] = { Chain, Reg, N, Flag }; 345 return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3); 346 } 347 348 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, MVT VT) { 349 SDVTList VTs = getVTList(VT, MVT::Other); 350 SDValue Ops[] = { Chain, getRegister(Reg, VT) }; 351 return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2); 352 } 353 354 // This version of the getCopyFromReg method takes an extra operand, which 355 // indicates that there is potentially an incoming flag value (if Flag is not 356 // null) and that there should be a flag result. 357 SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, MVT VT, 358 SDValue Flag) { 359 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Flag); 360 SDValue Ops[] = { Chain, getRegister(Reg, VT), Flag }; 361 return getNode(ISD::CopyFromReg, dl, VTs, Ops, Flag.getNode() ? 3 : 2); 362 } 363 364 SDValue getCondCode(ISD::CondCode Cond); 365 366 /// Returns the ConvertRndSat Note: Avoid using this node because it may 367 /// disappear in the future and most targets don't support it. 368 SDValue getConvertRndSat(MVT VT, DebugLoc dl, SDValue Val, SDValue DTy, 369 SDValue STy, 370 SDValue Rnd, SDValue Sat, ISD::CvtCode Code); 371 372 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of 373 /// elements in VT, which must be a vector type, must match the number of 374 /// mask elements NumElts. A integer mask element equal to -1 is treated as 375 /// undefined. 376 SDValue getVectorShuffle(MVT VT, DebugLoc dl, SDValue N1, SDValue N2, 377 const int *MaskElts); 378 379 /// getZeroExtendInReg - Return the expression required to zero extend the Op 380 /// value assuming it was the smaller SrcTy value. 381 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, MVT SrcTy); 382 383 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). 384 SDValue getNOT(DebugLoc DL, SDValue Val, MVT VT); 385 386 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 387 /// a flag result (to ensure it's not CSE'd). CALLSEQ_START does not have a 388 /// useful DebugLoc. 389 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) { 390 SDVTList VTs = getVTList(MVT::Other, MVT::Flag); 391 SDValue Ops[] = { Chain, Op }; 392 return getNode(ISD::CALLSEQ_START, DebugLoc::getUnknownLoc(), 393 VTs, Ops, 2); 394 } 395 396 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a 397 /// flag result (to ensure it's not CSE'd). CALLSEQ_END does not have 398 /// a useful DebugLoc. 399 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, 400 SDValue InFlag) { 401 SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag); 402 SmallVector<SDValue, 4> Ops; 403 Ops.push_back(Chain); 404 Ops.push_back(Op1); 405 Ops.push_back(Op2); 406 Ops.push_back(InFlag); 407 return getNode(ISD::CALLSEQ_END, DebugLoc::getUnknownLoc(), NodeTys, 408 &Ops[0], 409 (unsigned)Ops.size() - (InFlag.getNode() == 0 ? 1 : 0)); 410 } 411 412 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc. 413 SDValue getUNDEF(MVT VT) { 414 return getNode(ISD::UNDEF, DebugLoc::getUnknownLoc(), VT); 415 } 416 417 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does 418 /// not have a useful DebugLoc. 419 SDValue getGLOBAL_OFFSET_TABLE(MVT VT) { 420 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc::getUnknownLoc(), VT); 421 } 422 423 /// getNode - Gets or creates the specified node. 424 /// 425 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT); 426 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, SDValue N); 427 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, SDValue N1, SDValue N2); 428 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 429 SDValue N1, SDValue N2, SDValue N3); 430 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 431 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 432 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 433 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 434 SDValue N5); 435 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 436 const SDUse *Ops, unsigned NumOps); 437 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 438 const SDValue *Ops, unsigned NumOps); 439 SDValue getNode(unsigned Opcode, DebugLoc DL, 440 const std::vector<MVT> &ResultTys, 441 const SDValue *Ops, unsigned NumOps); 442 SDValue getNode(unsigned Opcode, DebugLoc DL, const MVT *VTs, unsigned NumVTs, 443 const SDValue *Ops, unsigned NumOps); 444 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 445 const SDValue *Ops, unsigned NumOps); 446 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs); 447 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N); 448 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 449 SDValue N1, SDValue N2); 450 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 451 SDValue N1, SDValue N2, SDValue N3); 452 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 453 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 454 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 455 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 456 SDValue N5); 457 458 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 459 SDValue Size, unsigned Align, bool AlwaysInline, 460 const Value *DstSV, uint64_t DstSVOff, 461 const Value *SrcSV, uint64_t SrcSVOff); 462 463 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 464 SDValue Size, unsigned Align, 465 const Value *DstSV, uint64_t DstOSVff, 466 const Value *SrcSV, uint64_t SrcSVOff); 467 468 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 469 SDValue Size, unsigned Align, 470 const Value *DstSV, uint64_t DstSVOff); 471 472 /// getSetCC - Helper function to make it easier to build SetCC's if you just 473 /// have an ISD::CondCode instead of an SDValue. 474 /// 475 SDValue getSetCC(DebugLoc DL, MVT VT, SDValue LHS, SDValue RHS, 476 ISD::CondCode Cond) { 477 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 478 } 479 480 /// getVSetCC - Helper function to make it easier to build VSetCC's nodes 481 /// if you just have an ISD::CondCode instead of an SDValue. 482 /// 483 SDValue getVSetCC(DebugLoc DL, MVT VT, SDValue LHS, SDValue RHS, 484 ISD::CondCode Cond) { 485 return getNode(ISD::VSETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 486 } 487 488 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 489 /// just have an ISD::CondCode instead of an SDValue. 490 /// 491 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS, 492 SDValue True, SDValue False, ISD::CondCode Cond) { 493 return getNode(ISD::SELECT_CC, DL, True.getValueType(), 494 LHS, RHS, True, False, getCondCode(Cond)); 495 } 496 497 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 498 /// and a source value as input. 499 SDValue getVAArg(MVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, 500 SDValue SV); 501 502 /// getAtomic - Gets a node for an atomic op, produces result and chain and 503 /// takes 3 operands 504 SDValue getAtomic(unsigned Opcode, DebugLoc dl, MVT MemVT, SDValue Chain, 505 SDValue Ptr, SDValue Cmp, SDValue Swp, const Value* PtrVal, 506 unsigned Alignment=0); 507 508 /// getAtomic - Gets a node for an atomic op, produces result and chain and 509 /// takes 2 operands. 510 SDValue getAtomic(unsigned Opcode, DebugLoc dl, MVT MemVT, SDValue Chain, 511 SDValue Ptr, SDValue Val, const Value* PtrVal, 512 unsigned Alignment = 0); 513 514 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a 515 /// result and takes a list of operands. 516 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, 517 const MVT *VTs, unsigned NumVTs, 518 const SDValue *Ops, unsigned NumOps, 519 MVT MemVT, const Value *srcValue, int SVOff, 520 unsigned Align = 0, bool Vol = false, 521 bool ReadMem = true, bool WriteMem = true); 522 523 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 524 const SDValue *Ops, unsigned NumOps, 525 MVT MemVT, const Value *srcValue, int SVOff, 526 unsigned Align = 0, bool Vol = false, 527 bool ReadMem = true, bool WriteMem = true); 528 529 /// getMergeValues - Create a MERGE_VALUES node from the given operands. 530 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl); 531 532 /// getCall - Create a CALL node from the given information. 533 /// 534 SDValue getCall(unsigned CallingConv, DebugLoc dl, bool IsVarArgs, 535 bool IsTailCall, bool isInreg, SDVTList VTs, 536 const SDValue *Operands, unsigned NumOperands); 537 538 /// getLoad - Loads are not normal binary operators: their result type is not 539 /// determined by their operands, and they produce a value AND a token chain. 540 /// 541 SDValue getLoad(MVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, 542 const Value *SV, int SVOffset, bool isVolatile=false, 543 unsigned Alignment=0); 544 SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, MVT VT, 545 SDValue Chain, SDValue Ptr, const Value *SV, 546 int SVOffset, MVT EVT, bool isVolatile=false, 547 unsigned Alignment=0); 548 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, 549 SDValue Offset, ISD::MemIndexedMode AM); 550 SDValue getLoad(ISD::MemIndexedMode AM, DebugLoc dl, ISD::LoadExtType ExtType, 551 MVT VT, SDValue Chain, 552 SDValue Ptr, SDValue Offset, 553 const Value *SV, int SVOffset, MVT EVT, 554 bool isVolatile=false, unsigned Alignment=0); 555 556 /// getStore - Helper function to build ISD::STORE nodes. 557 /// 558 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 559 const Value *SV, int SVOffset, bool isVolatile=false, 560 unsigned Alignment=0); 561 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 562 const Value *SV, int SVOffset, MVT TVT, 563 bool isVolatile=false, unsigned Alignment=0); 564 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base, 565 SDValue Offset, ISD::MemIndexedMode AM); 566 567 /// getSrcValue - Construct a node to track a Value* through the backend. 568 SDValue getSrcValue(const Value *v); 569 570 /// getMemOperand - Construct a node to track a memory reference 571 /// through the backend. 572 SDValue getMemOperand(const MachineMemOperand &MO); 573 574 /// getShiftAmountOperand - Return the specified value casted to 575 /// the target's desired shift amount type. 576 SDValue getShiftAmountOperand(SDValue Op); 577 578 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 579 /// specified operands. If the resultant node already exists in the DAG, 580 /// this does not modify the specified node, instead it returns the node that 581 /// already exists. If the resultant node does not exist in the DAG, the 582 /// input node is returned. As a degenerate case, if you specify the same 583 /// input operands as the node already has, the input node is returned. 584 SDValue UpdateNodeOperands(SDValue N, SDValue Op); 585 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2); 586 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 587 SDValue Op3); 588 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 589 SDValue Op3, SDValue Op4); 590 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 591 SDValue Op3, SDValue Op4, SDValue Op5); 592 SDValue UpdateNodeOperands(SDValue N, 593 const SDValue *Ops, unsigned NumOps); 594 595 /// SelectNodeTo - These are used for target selectors to *mutate* the 596 /// specified node to have the specified return type, Target opcode, and 597 /// operands. Note that target opcodes are stored as 598 /// ~TargetOpcode in the node opcode field. The resultant node is returned. 599 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT); 600 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, SDValue Op1); 601 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 602 SDValue Op1, SDValue Op2); 603 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 604 SDValue Op1, SDValue Op2, SDValue Op3); 605 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 606 const SDValue *Ops, unsigned NumOps); 607 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, MVT VT2); 608 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 609 MVT VT2, const SDValue *Ops, unsigned NumOps); 610 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 611 MVT VT2, MVT VT3, const SDValue *Ops, unsigned NumOps); 612 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, MVT VT1, 613 MVT VT2, MVT VT3, MVT VT4, const SDValue *Ops, 614 unsigned NumOps); 615 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 616 MVT VT2, SDValue Op1); 617 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 618 MVT VT2, SDValue Op1, SDValue Op2); 619 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 620 MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 621 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 622 MVT VT2, MVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); 623 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs, 624 const SDValue *Ops, unsigned NumOps); 625 626 /// MorphNodeTo - These *mutate* the specified node to have the specified 627 /// return type, opcode, and operands. 628 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT); 629 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, SDValue Op1); 630 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, 631 SDValue Op1, SDValue Op2); 632 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, 633 SDValue Op1, SDValue Op2, SDValue Op3); 634 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, 635 const SDValue *Ops, unsigned NumOps); 636 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, MVT VT2); 637 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 638 MVT VT2, const SDValue *Ops, unsigned NumOps); 639 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 640 MVT VT2, MVT VT3, const SDValue *Ops, unsigned NumOps); 641 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 642 MVT VT2, SDValue Op1); 643 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 644 MVT VT2, SDValue Op1, SDValue Op2); 645 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 646 MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 647 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, 648 const SDValue *Ops, unsigned NumOps); 649 650 /// getTargetNode - These are used for target selectors to create a new node 651 /// with specified return type(s), target opcode, and operands. 652 /// 653 /// Note that getTargetNode returns the resultant node. If there is already a 654 /// node of the specified opcode and operands, it returns that node instead of 655 /// the current one. 656 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT); 657 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, SDValue Op1); 658 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, SDValue Op1, 659 SDValue Op2); 660 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, 661 SDValue Op1, SDValue Op2, SDValue Op3); 662 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, 663 const SDValue *Ops, unsigned NumOps); 664 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2); 665 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, 666 SDValue Op1); 667 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, 668 MVT VT2, SDValue Op1, SDValue Op2); 669 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, 670 MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 671 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, 672 const SDValue *Ops, unsigned NumOps); 673 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 674 SDValue Op1, SDValue Op2); 675 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 676 SDValue Op1, SDValue Op2, SDValue Op3); 677 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 678 const SDValue *Ops, unsigned NumOps); 679 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 680 MVT VT4, const SDValue *Ops, unsigned NumOps); 681 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, 682 const std::vector<MVT> &ResultTys, const SDValue *Ops, 683 unsigned NumOps); 684 685 /// getNodeIfExists - Get the specified node if it's already available, or 686 /// else return NULL. 687 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, 688 const SDValue *Ops, unsigned NumOps); 689 690 /// DAGUpdateListener - Clients of various APIs that cause global effects on 691 /// the DAG can optionally implement this interface. This allows the clients 692 /// to handle the various sorts of updates that happen. 693 class DAGUpdateListener { 694 public: 695 virtual ~DAGUpdateListener(); 696 697 /// NodeDeleted - The node N that was deleted and, if E is not null, an 698 /// equivalent node E that replaced it. 699 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0; 700 701 /// NodeUpdated - The node N that was updated. 702 virtual void NodeUpdated(SDNode *N) = 0; 703 }; 704 705 /// RemoveDeadNode - Remove the specified node from the system. If any of its 706 /// operands then becomes dead, remove them as well. Inform UpdateListener 707 /// for each node deleted. 708 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0); 709 710 /// RemoveDeadNodes - This method deletes the unreachable nodes in the 711 /// given list, and any nodes that become unreachable as a result. 712 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes, 713 DAGUpdateListener *UpdateListener = 0); 714 715 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 716 /// This can cause recursive merging of nodes in the DAG. Use the first 717 /// version if 'From' is known to have a single result, use the second 718 /// if you have two nodes with identical results (or if 'To' has a superset 719 /// of the results of 'From'), use the third otherwise. 720 /// 721 /// These methods all take an optional UpdateListener, which (if not null) is 722 /// informed about nodes that are deleted and modified due to recursive 723 /// changes in the dag. 724 /// 725 /// These functions only replace all existing uses. It's possible that as 726 /// these replacements are being performed, CSE may cause the From node 727 /// to be given new uses. These new uses of From are left in place, and 728 /// not automatically transfered to To. 729 /// 730 void ReplaceAllUsesWith(SDValue From, SDValue Op, 731 DAGUpdateListener *UpdateListener = 0); 732 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 733 DAGUpdateListener *UpdateListener = 0); 734 void ReplaceAllUsesWith(SDNode *From, const SDValue *To, 735 DAGUpdateListener *UpdateListener = 0); 736 737 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 738 /// uses of other values produced by From.Val alone. 739 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To, 740 DAGUpdateListener *UpdateListener = 0); 741 742 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but 743 /// for multiple values at once. This correctly handles the case where 744 /// there is an overlap between the From values and the To values. 745 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, 746 unsigned Num, 747 DAGUpdateListener *UpdateListener = 0); 748 749 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a 750 /// assign a unique node id for each node in the DAG based on their 751 /// topological order. Returns the number of nodes. 752 unsigned AssignTopologicalOrder(); 753 754 /// RepositionNode - Move node N in the AllNodes list to be immediately 755 /// before the given iterator Position. This may be used to update the 756 /// topological ordering when the list of nodes is modified. 757 void RepositionNode(allnodes_iterator Position, SDNode *N) { 758 AllNodes.insert(Position, AllNodes.remove(N)); 759 } 760 761 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 762 /// operation. 763 static bool isCommutativeBinOp(unsigned Opcode) { 764 // FIXME: This should get its info from the td file, so that we can include 765 // target info. 766 switch (Opcode) { 767 case ISD::ADD: 768 case ISD::MUL: 769 case ISD::MULHU: 770 case ISD::MULHS: 771 case ISD::SMUL_LOHI: 772 case ISD::UMUL_LOHI: 773 case ISD::FADD: 774 case ISD::FMUL: 775 case ISD::AND: 776 case ISD::OR: 777 case ISD::XOR: 778 case ISD::SADDO: 779 case ISD::UADDO: 780 case ISD::ADDC: 781 case ISD::ADDE: return true; 782 default: return false; 783 } 784 } 785 786 void dump() const; 787 788 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 789 /// specified value type. If minAlign is specified, the slot size will have 790 /// at least that alignment. 791 SDValue CreateStackTemporary(MVT VT, unsigned minAlign = 1); 792 793 /// CreateStackTemporary - Create a stack temporary suitable for holding 794 /// either of the specified value types. 795 SDValue CreateStackTemporary(MVT VT1, MVT VT2); 796 797 /// FoldConstantArithmetic - 798 SDValue FoldConstantArithmetic(unsigned Opcode, 799 MVT VT, 800 ConstantSDNode *Cst1, 801 ConstantSDNode *Cst2); 802 803 /// FoldSetCC - Constant fold a setcc to true or false. 804 SDValue FoldSetCC(MVT VT, SDValue N1, 805 SDValue N2, ISD::CondCode Cond, DebugLoc dl); 806 807 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 808 /// use this predicate to simplify operations downstream. 809 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const; 810 811 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 812 /// use this predicate to simplify operations downstream. Op and Mask are 813 /// known to be the same type. 814 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0) 815 const; 816 817 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 818 /// known to be either zero or one and return them in the KnownZero/KnownOne 819 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 820 /// processing. Targets can implement the computeMaskedBitsForTargetNode 821 /// method in the TargetLowering class to allow target nodes to be understood. 822 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero, 823 APInt &KnownOne, unsigned Depth = 0) const; 824 825 /// ComputeNumSignBits - Return the number of times the sign bit of the 826 /// register is replicated into the other bits. We know that at least 1 bit 827 /// is always equal to the sign bit (itself), but other cases can give us 828 /// information. For example, immediately after an "SRA X, 2", we know that 829 /// the top 3 bits are all equal to each other, so we return 3. Targets can 830 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 831 /// class to allow target nodes to be understood. 832 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; 833 834 /// isVerifiedDebugInfoDesc - Returns true if the specified SDValue has 835 /// been verified as a debug information descriptor. 836 bool isVerifiedDebugInfoDesc(SDValue Op) const; 837 838 /// getShuffleScalarElt - Returns the scalar element that will make up the ith 839 /// element of the result of the vector shuffle. 840 SDValue getShuffleScalarElt(const ShuffleVectorSDNode *N, unsigned Idx); 841 842private: 843 bool RemoveNodeFromCSEMaps(SDNode *N); 844 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener); 845 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); 846 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, 847 void *&InsertPos); 848 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps, 849 void *&InsertPos); 850 851 void DeleteNodeNotInCSEMaps(SDNode *N); 852 void DeallocateNode(SDNode *N); 853 854 unsigned getMVTAlignment(MVT MemoryVT) const; 855 856 void allnodes_clear(); 857 858 /// VTList - List of non-single value types. 859 std::vector<SDVTList> VTList; 860 861 /// CondCodeNodes - Maps to auto-CSE operations. 862 std::vector<CondCodeSDNode*> CondCodeNodes; 863 864 std::vector<SDNode*> ValueTypeNodes; 865 std::map<MVT, SDNode*, MVT::compareRawBits> ExtendedValueTypeNodes; 866 StringMap<SDNode*> ExternalSymbols; 867 868 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols; 869}; 870 871template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 872 typedef SelectionDAG::allnodes_iterator nodes_iterator; 873 static nodes_iterator nodes_begin(SelectionDAG *G) { 874 return G->allnodes_begin(); 875 } 876 static nodes_iterator nodes_end(SelectionDAG *G) { 877 return G->allnodes_end(); 878 } 879}; 880 881} // end namespace llvm 882 883#endif 884