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