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