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