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