SelectionDAG.h revision c23e4968790395053f3f52aeb3342637fcaafdbf
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, bool Fast); 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, bool Fast); 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 /// getZeroExtendInReg - Return the expression required to zero extend the Op 358 /// value assuming it was the smaller SrcTy value. 359 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, MVT SrcTy); 360 361 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). 362 SDValue getNOT(DebugLoc DL, SDValue Val, MVT VT); 363 364 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 365 /// a flag result (to ensure it's not CSE'd). CALLSEQ_START does not have a 366 /// useful DebugLoc. 367 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) { 368 SDVTList VTs = getVTList(MVT::Other, MVT::Flag); 369 SDValue Ops[] = { Chain, Op }; 370 return getNode(ISD::CALLSEQ_START, DebugLoc::getUnknownLoc(), 371 VTs, Ops, 2); 372 } 373 374 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a 375 /// flag result (to ensure it's not CSE'd). CALLSEQ_END does not have 376 /// a useful DebugLoc. 377 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, 378 SDValue InFlag) { 379 SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag); 380 SmallVector<SDValue, 4> Ops; 381 Ops.push_back(Chain); 382 Ops.push_back(Op1); 383 Ops.push_back(Op2); 384 Ops.push_back(InFlag); 385 return getNode(ISD::CALLSEQ_END, DebugLoc::getUnknownLoc(), NodeTys, 386 &Ops[0], 387 (unsigned)Ops.size() - (InFlag.getNode() == 0 ? 1 : 0)); 388 } 389 390 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc. 391 SDValue getUNDEF(MVT VT) { 392 return getNode(ISD::UNDEF, DebugLoc::getUnknownLoc(), VT); 393 } 394 395 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does 396 /// not have a useful DebugLoc. 397 SDValue getGLOBAL_OFFSET_TABLE(MVT VT) { 398 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc::getUnknownLoc(), VT); 399 } 400 401 /// getNode - Gets or creates the specified node. 402 /// 403 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT); 404 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, SDValue N); 405 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, SDValue N1, SDValue N2); 406 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 407 SDValue N1, SDValue N2, SDValue N3); 408 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 409 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 410 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 411 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 412 SDValue N5); 413 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 414 const SDUse *Ops, unsigned NumOps); 415 SDValue getNode(unsigned Opcode, DebugLoc DL, MVT VT, 416 const SDValue *Ops, unsigned NumOps); 417 SDValue getNode(unsigned Opcode, DebugLoc DL, 418 const std::vector<MVT> &ResultTys, 419 const SDValue *Ops, unsigned NumOps); 420 SDValue getNode(unsigned Opcode, DebugLoc DL, const MVT *VTs, unsigned NumVTs, 421 const SDValue *Ops, unsigned NumOps); 422 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 423 const SDValue *Ops, unsigned NumOps); 424 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs); 425 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N); 426 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 427 SDValue N1, SDValue N2); 428 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 429 SDValue N1, SDValue N2, SDValue N3); 430 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 431 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 432 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 433 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 434 SDValue N5); 435 436 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 437 SDValue Size, unsigned Align, bool AlwaysInline, 438 const Value *DstSV, uint64_t DstSVOff, 439 const Value *SrcSV, uint64_t SrcSVOff); 440 441 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 442 SDValue Size, unsigned Align, 443 const Value *DstSV, uint64_t DstOSVff, 444 const Value *SrcSV, uint64_t SrcSVOff); 445 446 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 447 SDValue Size, unsigned Align, 448 const Value *DstSV, uint64_t DstSVOff); 449 450 /// getSetCC - Helper function to make it easier to build SetCC's if you just 451 /// have an ISD::CondCode instead of an SDValue. 452 /// 453 SDValue getSetCC(DebugLoc DL, MVT VT, SDValue LHS, SDValue RHS, 454 ISD::CondCode Cond) { 455 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 456 } 457 458 /// getVSetCC - Helper function to make it easier to build VSetCC's nodes 459 /// if you just have an ISD::CondCode instead of an SDValue. 460 /// 461 SDValue getVSetCC(DebugLoc DL, MVT VT, SDValue LHS, SDValue RHS, 462 ISD::CondCode Cond) { 463 return getNode(ISD::VSETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 464 } 465 466 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 467 /// just have an ISD::CondCode instead of an SDValue. 468 /// 469 SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS, 470 SDValue True, SDValue False, ISD::CondCode Cond) { 471 return getNode(ISD::SELECT_CC, DL, True.getValueType(), 472 LHS, RHS, True, False, getCondCode(Cond)); 473 } 474 475 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 476 /// and a source value as input. 477 SDValue getVAArg(MVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, 478 SDValue SV); 479 480 /// getAtomic - Gets a node for an atomic op, produces result and chain and 481 /// takes 3 operands 482 SDValue getAtomic(unsigned Opcode, DebugLoc dl, MVT MemVT, SDValue Chain, 483 SDValue Ptr, SDValue Cmp, SDValue Swp, const Value* PtrVal, 484 unsigned Alignment=0); 485 486 /// getAtomic - Gets a node for an atomic op, produces result and chain and 487 /// takes 2 operands. 488 SDValue getAtomic(unsigned Opcode, DebugLoc dl, MVT MemVT, SDValue Chain, 489 SDValue Ptr, SDValue Val, const Value* PtrVal, 490 unsigned Alignment = 0); 491 492 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a 493 /// result and takes a list of operands. 494 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, 495 const MVT *VTs, unsigned NumVTs, 496 const SDValue *Ops, unsigned NumOps, 497 MVT MemVT, const Value *srcValue, int SVOff, 498 unsigned Align = 0, bool Vol = false, 499 bool ReadMem = true, bool WriteMem = true); 500 501 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 502 const SDValue *Ops, unsigned NumOps, 503 MVT MemVT, const Value *srcValue, int SVOff, 504 unsigned Align = 0, bool Vol = false, 505 bool ReadMem = true, bool WriteMem = true); 506 507 /// getMergeValues - Create a MERGE_VALUES node from the given operands. 508 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl); 509 510 /// getCall - Create a CALL node from the given information. 511 /// 512 SDValue getCall(unsigned CallingConv, DebugLoc dl, bool IsVarArgs, 513 bool IsTailCall, bool isInreg, SDVTList VTs, 514 const SDValue *Operands, unsigned NumOperands); 515 516 /// getLoad - Loads are not normal binary operators: their result type is not 517 /// determined by their operands, and they produce a value AND a token chain. 518 /// 519 SDValue getLoad(MVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, 520 const Value *SV, int SVOffset, bool isVolatile=false, 521 unsigned Alignment=0); 522 SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, MVT VT, 523 SDValue Chain, SDValue Ptr, const Value *SV, 524 int SVOffset, MVT EVT, bool isVolatile=false, 525 unsigned Alignment=0); 526 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, 527 SDValue Offset, ISD::MemIndexedMode AM); 528 SDValue getLoad(ISD::MemIndexedMode AM, DebugLoc dl, ISD::LoadExtType ExtType, 529 MVT VT, SDValue Chain, 530 SDValue Ptr, SDValue Offset, 531 const Value *SV, int SVOffset, MVT EVT, 532 bool isVolatile=false, unsigned Alignment=0); 533 534 /// getStore - Helper function to build ISD::STORE nodes. 535 /// 536 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 537 const Value *SV, int SVOffset, bool isVolatile=false, 538 unsigned Alignment=0); 539 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 540 const Value *SV, int SVOffset, MVT TVT, 541 bool isVolatile=false, unsigned Alignment=0); 542 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base, 543 SDValue Offset, ISD::MemIndexedMode AM); 544 545 /// getSrcValue - Construct a node to track a Value* through the backend. 546 SDValue getSrcValue(const Value *v); 547 548 /// getMemOperand - Construct a node to track a memory reference 549 /// through the backend. 550 SDValue getMemOperand(const MachineMemOperand &MO); 551 552 /// getShiftAmountOperand - Return the specified value casted to 553 /// the target's desired shift amount type. 554 SDValue getShiftAmountOperand(SDValue Op); 555 556 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 557 /// specified operands. If the resultant node already exists in the DAG, 558 /// this does not modify the specified node, instead it returns the node that 559 /// already exists. If the resultant node does not exist in the DAG, the 560 /// input node is returned. As a degenerate case, if you specify the same 561 /// input operands as the node already has, the input node is returned. 562 SDValue UpdateNodeOperands(SDValue N, SDValue Op); 563 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2); 564 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 565 SDValue Op3); 566 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 567 SDValue Op3, SDValue Op4); 568 SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 569 SDValue Op3, SDValue Op4, SDValue Op5); 570 SDValue UpdateNodeOperands(SDValue N, 571 const SDValue *Ops, unsigned NumOps); 572 573 /// SelectNodeTo - These are used for target selectors to *mutate* the 574 /// specified node to have the specified return type, Target opcode, and 575 /// operands. Note that target opcodes are stored as 576 /// ~TargetOpcode in the node opcode field. The resultant node is returned. 577 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT); 578 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, SDValue Op1); 579 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 580 SDValue Op1, SDValue Op2); 581 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 582 SDValue Op1, SDValue Op2, SDValue Op3); 583 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 584 const SDValue *Ops, unsigned NumOps); 585 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, MVT VT2); 586 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 587 MVT VT2, const SDValue *Ops, unsigned NumOps); 588 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 589 MVT VT2, MVT VT3, const SDValue *Ops, unsigned NumOps); 590 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, MVT VT1, 591 MVT VT2, MVT VT3, MVT VT4, const SDValue *Ops, 592 unsigned NumOps); 593 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 594 MVT VT2, SDValue Op1); 595 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 596 MVT VT2, SDValue Op1, SDValue Op2); 597 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 598 MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 599 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 600 MVT VT2, MVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); 601 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs, 602 const SDValue *Ops, unsigned NumOps); 603 604 /// MorphNodeTo - These *mutate* the specified node to have the specified 605 /// return type, opcode, and operands. 606 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT); 607 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, SDValue Op1); 608 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, 609 SDValue Op1, SDValue Op2); 610 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, 611 SDValue Op1, SDValue Op2, SDValue Op3); 612 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, 613 const SDValue *Ops, unsigned NumOps); 614 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, MVT VT2); 615 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 616 MVT VT2, const SDValue *Ops, unsigned NumOps); 617 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 618 MVT VT2, MVT VT3, const SDValue *Ops, unsigned NumOps); 619 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 620 MVT VT2, SDValue Op1); 621 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 622 MVT VT2, SDValue Op1, SDValue Op2); 623 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, 624 MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 625 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, 626 const SDValue *Ops, unsigned NumOps); 627 628 /// getTargetNode - These are used for target selectors to create a new node 629 /// with specified return type(s), target opcode, and operands. 630 /// 631 /// Note that getTargetNode returns the resultant node. If there is already a 632 /// node of the specified opcode and operands, it returns that node instead of 633 /// the current one. 634 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT); 635 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, SDValue Op1); 636 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, SDValue Op1, 637 SDValue Op2); 638 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, 639 SDValue Op1, SDValue Op2, SDValue Op3); 640 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT, 641 const SDValue *Ops, unsigned NumOps); 642 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2); 643 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, 644 SDValue Op1); 645 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, 646 MVT VT2, SDValue Op1, SDValue Op2); 647 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, 648 MVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 649 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, 650 const SDValue *Ops, unsigned NumOps); 651 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 652 SDValue Op1, SDValue Op2); 653 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 654 SDValue Op1, SDValue Op2, SDValue Op3); 655 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 656 const SDValue *Ops, unsigned NumOps); 657 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, MVT VT1, MVT VT2, MVT VT3, 658 MVT VT4, const SDValue *Ops, unsigned NumOps); 659 SDNode *getTargetNode(unsigned Opcode, DebugLoc dl, 660 const std::vector<MVT> &ResultTys, const SDValue *Ops, 661 unsigned NumOps); 662 663 /// getNodeIfExists - Get the specified node if it's already available, or 664 /// else return NULL. 665 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, 666 const SDValue *Ops, unsigned NumOps); 667 668 /// DAGUpdateListener - Clients of various APIs that cause global effects on 669 /// the DAG can optionally implement this interface. This allows the clients 670 /// to handle the various sorts of updates that happen. 671 class DAGUpdateListener { 672 public: 673 virtual ~DAGUpdateListener(); 674 675 /// NodeDeleted - The node N that was deleted and, if E is not null, an 676 /// equivalent node E that replaced it. 677 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0; 678 679 /// NodeUpdated - The node N that was updated. 680 virtual void NodeUpdated(SDNode *N) = 0; 681 }; 682 683 /// RemoveDeadNode - Remove the specified node from the system. If any of its 684 /// operands then becomes dead, remove them as well. Inform UpdateListener 685 /// for each node deleted. 686 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0); 687 688 /// RemoveDeadNodes - This method deletes the unreachable nodes in the 689 /// given list, and any nodes that become unreachable as a result. 690 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes, 691 DAGUpdateListener *UpdateListener = 0); 692 693 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 694 /// This can cause recursive merging of nodes in the DAG. Use the first 695 /// version if 'From' is known to have a single result, use the second 696 /// if you have two nodes with identical results (or if 'To' has a superset 697 /// of the results of 'From'), use the third otherwise. 698 /// 699 /// These methods all take an optional UpdateListener, which (if not null) is 700 /// informed about nodes that are deleted and modified due to recursive 701 /// changes in the dag. 702 /// 703 /// These functions only replace all existing uses. It's possible that as 704 /// these replacements are being performed, CSE may cause the From node 705 /// to be given new uses. These new uses of From are left in place, and 706 /// not automatically transfered to To. 707 /// 708 void ReplaceAllUsesWith(SDValue From, SDValue Op, 709 DAGUpdateListener *UpdateListener = 0); 710 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 711 DAGUpdateListener *UpdateListener = 0); 712 void ReplaceAllUsesWith(SDNode *From, const SDValue *To, 713 DAGUpdateListener *UpdateListener = 0); 714 715 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 716 /// uses of other values produced by From.Val alone. 717 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To, 718 DAGUpdateListener *UpdateListener = 0); 719 720 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but 721 /// for multiple values at once. This correctly handles the case where 722 /// there is an overlap between the From values and the To values. 723 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, 724 unsigned Num, 725 DAGUpdateListener *UpdateListener = 0); 726 727 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a 728 /// assign a unique node id for each node in the DAG based on their 729 /// topological order. Returns the number of nodes. 730 unsigned AssignTopologicalOrder(); 731 732 /// RepositionNode - Move node N in the AllNodes list to be immediately 733 /// before the given iterator Position. This may be used to update the 734 /// topological ordering when the list of nodes is modified. 735 void RepositionNode(allnodes_iterator Position, SDNode *N) { 736 AllNodes.insert(Position, AllNodes.remove(N)); 737 } 738 739 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 740 /// operation. 741 static bool isCommutativeBinOp(unsigned Opcode) { 742 // FIXME: This should get its info from the td file, so that we can include 743 // target info. 744 switch (Opcode) { 745 case ISD::ADD: 746 case ISD::MUL: 747 case ISD::MULHU: 748 case ISD::MULHS: 749 case ISD::SMUL_LOHI: 750 case ISD::UMUL_LOHI: 751 case ISD::FADD: 752 case ISD::FMUL: 753 case ISD::AND: 754 case ISD::OR: 755 case ISD::XOR: 756 case ISD::SADDO: 757 case ISD::UADDO: 758 case ISD::ADDC: 759 case ISD::ADDE: return true; 760 default: return false; 761 } 762 } 763 764 void dump() const; 765 766 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 767 /// specified value type. If minAlign is specified, the slot size will have 768 /// at least that alignment. 769 SDValue CreateStackTemporary(MVT VT, unsigned minAlign = 1); 770 771 /// CreateStackTemporary - Create a stack temporary suitable for holding 772 /// either of the specified value types. 773 SDValue CreateStackTemporary(MVT VT1, MVT VT2); 774 775 /// FoldConstantArithmetic - 776 SDValue FoldConstantArithmetic(unsigned Opcode, 777 MVT VT, 778 ConstantSDNode *Cst1, 779 ConstantSDNode *Cst2); 780 781 /// FoldSetCC - Constant fold a setcc to true or false. 782 SDValue FoldSetCC(MVT VT, SDValue N1, 783 SDValue N2, ISD::CondCode Cond, DebugLoc dl); 784 785 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 786 /// use this predicate to simplify operations downstream. 787 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const; 788 789 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 790 /// use this predicate to simplify operations downstream. Op and Mask are 791 /// known to be the same type. 792 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0) 793 const; 794 795 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 796 /// known to be either zero or one and return them in the KnownZero/KnownOne 797 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 798 /// processing. Targets can implement the computeMaskedBitsForTargetNode 799 /// method in the TargetLowering class to allow target nodes to be understood. 800 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero, 801 APInt &KnownOne, unsigned Depth = 0) const; 802 803 /// ComputeNumSignBits - Return the number of times the sign bit of the 804 /// register is replicated into the other bits. We know that at least 1 bit 805 /// is always equal to the sign bit (itself), but other cases can give us 806 /// information. For example, immediately after an "SRA X, 2", we know that 807 /// the top 3 bits are all equal to each other, so we return 3. Targets can 808 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 809 /// class to allow target nodes to be understood. 810 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; 811 812 /// isVerifiedDebugInfoDesc - Returns true if the specified SDValue has 813 /// been verified as a debug information descriptor. 814 bool isVerifiedDebugInfoDesc(SDValue Op) const; 815 816 /// getShuffleScalarElt - Returns the scalar element that will make up the ith 817 /// element of the result of the vector shuffle. 818 SDValue getShuffleScalarElt(const SDNode *N, unsigned Idx); 819 820private: 821 bool RemoveNodeFromCSEMaps(SDNode *N); 822 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener); 823 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); 824 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, 825 void *&InsertPos); 826 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps, 827 void *&InsertPos); 828 829 void DeleteNodeNotInCSEMaps(SDNode *N); 830 void DeallocateNode(SDNode *N); 831 832 unsigned getMVTAlignment(MVT MemoryVT) const; 833 834 void allnodes_clear(); 835 836 /// VTList - List of non-single value types. 837 std::vector<SDVTList> VTList; 838 839 /// CondCodeNodes - Maps to auto-CSE operations. 840 std::vector<CondCodeSDNode*> CondCodeNodes; 841 842 std::vector<SDNode*> ValueTypeNodes; 843 std::map<MVT, SDNode*, MVT::compareRawBits> ExtendedValueTypeNodes; 844 StringMap<SDNode*> ExternalSymbols; 845 StringMap<SDNode*> TargetExternalSymbols; 846}; 847 848template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 849 typedef SelectionDAG::allnodes_iterator nodes_iterator; 850 static nodes_iterator nodes_begin(SelectionDAG *G) { 851 return G->allnodes_begin(); 852 } 853 static nodes_iterator nodes_end(SelectionDAG *G) { 854 return G->allnodes_end(); 855 } 856}; 857 858} // end namespace llvm 859 860#endif 861