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