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