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