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 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the 454 /// integer type VT, by either sign-extending or truncating it. 455 SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT); 456 457 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the 458 /// integer type VT, by either zero-extending or truncating it. 459 SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT); 460 461 /// getZeroExtendInReg - Return the expression required to zero extend the Op 462 /// value assuming it was the smaller SrcTy value. 463 SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy); 464 465 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). 466 SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT); 467 468 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 469 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a 470 /// useful DebugLoc. 471 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) { 472 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 473 SDValue Ops[] = { Chain, Op }; 474 return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2); 475 } 476 477 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a 478 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have 479 /// a useful DebugLoc. 480 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, 481 SDValue InGlue) { 482 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue); 483 SmallVector<SDValue, 4> Ops; 484 Ops.push_back(Chain); 485 Ops.push_back(Op1); 486 Ops.push_back(Op2); 487 Ops.push_back(InGlue); 488 return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0], 489 (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0)); 490 } 491 492 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc. 493 SDValue getUNDEF(EVT VT) { 494 return getNode(ISD::UNDEF, DebugLoc(), VT); 495 } 496 497 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does 498 /// not have a useful DebugLoc. 499 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) { 500 return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc(), VT); 501 } 502 503 /// getNode - Gets or creates the specified node. 504 /// 505 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT); 506 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N); 507 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2); 508 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 509 SDValue N1, SDValue N2, SDValue N3); 510 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 511 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 512 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 513 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 514 SDValue N5); 515 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 516 const SDUse *Ops, unsigned NumOps); 517 SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, 518 const SDValue *Ops, unsigned NumOps); 519 SDValue getNode(unsigned Opcode, DebugLoc DL, 520 const std::vector<EVT> &ResultTys, 521 const SDValue *Ops, unsigned NumOps); 522 SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs, 523 const SDValue *Ops, unsigned NumOps); 524 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 525 const SDValue *Ops, unsigned NumOps); 526 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs); 527 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N); 528 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 529 SDValue N1, SDValue N2); 530 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 531 SDValue N1, SDValue N2, SDValue N3); 532 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 533 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 534 SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 535 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 536 SDValue N5); 537 538 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all 539 /// the incoming stack arguments to be loaded from the stack. This is 540 /// used in tail call lowering to protect stack arguments from being 541 /// clobbered. 542 SDValue getStackArgumentTokenFactor(SDValue Chain); 543 544 SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 545 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline, 546 MachinePointerInfo DstPtrInfo, 547 MachinePointerInfo SrcPtrInfo); 548 549 SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 550 SDValue Size, unsigned Align, bool isVol, 551 MachinePointerInfo DstPtrInfo, 552 MachinePointerInfo SrcPtrInfo); 553 554 SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, 555 SDValue Size, unsigned Align, bool isVol, 556 MachinePointerInfo DstPtrInfo); 557 558 /// getSetCC - Helper function to make it easier to build SetCC's if you just 559 /// have an ISD::CondCode instead of an SDValue. 560 /// 561 SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS, 562 ISD::CondCode Cond) { 563 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 564 } 565 566 /// getVSetCC - Helper function to make it easier to build VSetCC's nodes 567 /// if you just have an ISD::CondCode instead of an SDValue. 568 /// 569 SDValue getVSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS, 570 ISD::CondCode Cond) { 571 return getNode(ISD::VSETCC, 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=0); 593 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, 594 SDValue Ptr, SDValue Cmp, SDValue Swp, 595 MachineMemOperand *MMO); 596 597 /// getAtomic - Gets a node for an atomic op, produces result and chain and 598 /// takes 2 operands. 599 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, 600 SDValue Ptr, SDValue Val, const Value* PtrVal, 601 unsigned Alignment = 0); 602 SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, 603 SDValue Ptr, SDValue Val, 604 MachineMemOperand *MMO); 605 606 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a 607 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID, 608 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not 609 /// less than FIRST_TARGET_MEMORY_OPCODE. 610 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, 611 const EVT *VTs, unsigned NumVTs, 612 const SDValue *Ops, unsigned NumOps, 613 EVT MemVT, MachinePointerInfo PtrInfo, 614 unsigned Align = 0, bool Vol = false, 615 bool ReadMem = true, bool WriteMem = true); 616 617 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 618 const SDValue *Ops, unsigned NumOps, 619 EVT MemVT, MachinePointerInfo PtrInfo, 620 unsigned Align = 0, bool Vol = false, 621 bool ReadMem = true, bool WriteMem = true); 622 623 SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 624 const SDValue *Ops, unsigned NumOps, 625 EVT MemVT, MachineMemOperand *MMO); 626 627 /// getMergeValues - Create a MERGE_VALUES node from the given operands. 628 SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl); 629 630 /// getLoad - Loads are not normal binary operators: their result type is not 631 /// determined by their operands, and they produce a value AND a token chain. 632 /// 633 SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, 634 MachinePointerInfo PtrInfo, bool isVolatile, 635 bool isNonTemporal, unsigned Alignment, 636 const MDNode *TBAAInfo = 0); 637 SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT, 638 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, 639 EVT MemVT, bool isVolatile, 640 bool isNonTemporal, unsigned Alignment, 641 const MDNode *TBAAInfo = 0); 642 SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, 643 SDValue Offset, ISD::MemIndexedMode AM); 644 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 645 EVT VT, DebugLoc dl, 646 SDValue Chain, SDValue Ptr, SDValue Offset, 647 MachinePointerInfo PtrInfo, EVT MemVT, 648 bool isVolatile, bool isNonTemporal, unsigned Alignment, 649 const MDNode *TBAAInfo = 0); 650 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 651 EVT VT, DebugLoc dl, 652 SDValue Chain, SDValue Ptr, SDValue Offset, 653 EVT MemVT, MachineMemOperand *MMO); 654 655 /// getStore - Helper function to build ISD::STORE nodes. 656 /// 657 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 658 MachinePointerInfo PtrInfo, bool isVolatile, 659 bool isNonTemporal, unsigned Alignment, 660 const MDNode *TBAAInfo = 0); 661 SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 662 MachineMemOperand *MMO); 663 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 664 MachinePointerInfo PtrInfo, EVT TVT, 665 bool isNonTemporal, bool isVolatile, 666 unsigned Alignment, 667 const MDNode *TBAAInfo = 0); 668 SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, 669 EVT TVT, MachineMemOperand *MMO); 670 SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base, 671 SDValue Offset, ISD::MemIndexedMode AM); 672 673 /// getSrcValue - Construct a node to track a Value* through the backend. 674 SDValue getSrcValue(const Value *v); 675 676 /// getMDNode - Return an MDNodeSDNode which holds an MDNode. 677 SDValue getMDNode(const MDNode *MD); 678 679 /// getShiftAmountOperand - Return the specified value casted to 680 /// the target's desired shift amount type. 681 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op); 682 683 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 684 /// specified operands. If the resultant node already exists in the DAG, 685 /// this does not modify the specified node, instead it returns the node that 686 /// already exists. If the resultant node does not exist in the DAG, the 687 /// input node is returned. As a degenerate case, if you specify the same 688 /// input operands as the node already has, the input node is returned. 689 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op); 690 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2); 691 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 692 SDValue Op3); 693 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 694 SDValue Op3, SDValue Op4); 695 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 696 SDValue Op3, SDValue Op4, SDValue Op5); 697 SDNode *UpdateNodeOperands(SDNode *N, 698 const SDValue *Ops, unsigned NumOps); 699 700 /// SelectNodeTo - These are used for target selectors to *mutate* the 701 /// specified node to have the specified return type, Target opcode, and 702 /// operands. Note that target opcodes are stored as 703 /// ~TargetOpcode in the node opcode field. The resultant node is returned. 704 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT); 705 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1); 706 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 707 SDValue Op1, SDValue Op2); 708 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 709 SDValue Op1, SDValue Op2, SDValue Op3); 710 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 711 const SDValue *Ops, unsigned NumOps); 712 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2); 713 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 714 EVT VT2, const SDValue *Ops, unsigned NumOps); 715 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 716 EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps); 717 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 718 EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops, 719 unsigned NumOps); 720 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 721 EVT VT2, SDValue Op1); 722 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 723 EVT VT2, SDValue Op1, SDValue Op2); 724 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 725 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 726 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 727 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); 728 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs, 729 const SDValue *Ops, unsigned NumOps); 730 731 /// MorphNodeTo - This *mutates* the specified node to have the specified 732 /// return type, opcode, and operands. 733 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, 734 const SDValue *Ops, unsigned NumOps); 735 736 /// getMachineNode - These are used for target selectors to create a new node 737 /// with specified return type(s), MachineInstr opcode, and operands. 738 /// 739 /// Note that getMachineNode returns the resultant node. If there is already 740 /// a node of the specified opcode and operands, it returns that node instead 741 /// of the current one. 742 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT); 743 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 744 SDValue Op1); 745 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 746 SDValue Op1, SDValue Op2); 747 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 748 SDValue Op1, SDValue Op2, SDValue Op3); 749 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 750 const SDValue *Ops, unsigned NumOps); 751 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2); 752 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, 753 SDValue Op1); 754 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, 755 EVT VT2, SDValue Op1, SDValue Op2); 756 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, 757 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 758 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, 759 const SDValue *Ops, unsigned NumOps); 760 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, 761 EVT VT3, SDValue Op1, SDValue Op2); 762 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, 763 EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); 764 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, 765 EVT VT3, const SDValue *Ops, unsigned NumOps); 766 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, 767 EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps); 768 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, 769 const std::vector<EVT> &ResultTys, const SDValue *Ops, 770 unsigned NumOps); 771 MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs, 772 const SDValue *Ops, unsigned NumOps); 773 774 /// getTargetExtractSubreg - A convenience function for creating 775 /// TargetInstrInfo::EXTRACT_SUBREG nodes. 776 SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT, 777 SDValue Operand); 778 779 /// getTargetInsertSubreg - A convenience function for creating 780 /// TargetInstrInfo::INSERT_SUBREG nodes. 781 SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT, 782 SDValue Operand, SDValue Subreg); 783 784 /// getNodeIfExists - Get the specified node if it's already available, or 785 /// else return NULL. 786 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, 787 const SDValue *Ops, unsigned NumOps); 788 789 /// getDbgValue - Creates a SDDbgValue node. 790 /// 791 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off, 792 DebugLoc DL, unsigned O); 793 SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off, 794 DebugLoc DL, unsigned O); 795 SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off, 796 DebugLoc DL, unsigned O); 797 798 /// DAGUpdateListener - Clients of various APIs that cause global effects on 799 /// the DAG can optionally implement this interface. This allows the clients 800 /// to handle the various sorts of updates that happen. 801 class DAGUpdateListener { 802 public: 803 virtual ~DAGUpdateListener(); 804 805 /// NodeDeleted - The node N that was deleted and, if E is not null, an 806 /// equivalent node E that replaced it. 807 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0; 808 809 /// NodeUpdated - The node N that was updated. 810 virtual void NodeUpdated(SDNode *N) = 0; 811 }; 812 813 /// RemoveDeadNode - Remove the specified node from the system. If any of its 814 /// operands then becomes dead, remove them as well. Inform UpdateListener 815 /// for each node deleted. 816 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0); 817 818 /// RemoveDeadNodes - This method deletes the unreachable nodes in the 819 /// given list, and any nodes that become unreachable as a result. 820 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes, 821 DAGUpdateListener *UpdateListener = 0); 822 823 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 824 /// This can cause recursive merging of nodes in the DAG. Use the first 825 /// version if 'From' is known to have a single result, use the second 826 /// if you have two nodes with identical results (or if 'To' has a superset 827 /// of the results of 'From'), use the third otherwise. 828 /// 829 /// These methods all take an optional UpdateListener, which (if not null) is 830 /// informed about nodes that are deleted and modified due to recursive 831 /// changes in the dag. 832 /// 833 /// These functions only replace all existing uses. It's possible that as 834 /// these replacements are being performed, CSE may cause the From node 835 /// to be given new uses. These new uses of From are left in place, and 836 /// not automatically transferred to To. 837 /// 838 void ReplaceAllUsesWith(SDValue From, SDValue Op, 839 DAGUpdateListener *UpdateListener = 0); 840 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 841 DAGUpdateListener *UpdateListener = 0); 842 void ReplaceAllUsesWith(SDNode *From, const SDValue *To, 843 DAGUpdateListener *UpdateListener = 0); 844 845 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 846 /// uses of other values produced by From.Val alone. 847 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To, 848 DAGUpdateListener *UpdateListener = 0); 849 850 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but 851 /// for multiple values at once. This correctly handles the case where 852 /// there is an overlap between the From values and the To values. 853 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, 854 unsigned Num, 855 DAGUpdateListener *UpdateListener = 0); 856 857 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a 858 /// assign a unique node id for each node in the DAG based on their 859 /// topological order. Returns the number of nodes. 860 unsigned AssignTopologicalOrder(); 861 862 /// RepositionNode - Move node N in the AllNodes list to be immediately 863 /// before the given iterator Position. This may be used to update the 864 /// topological ordering when the list of nodes is modified. 865 void RepositionNode(allnodes_iterator Position, SDNode *N) { 866 AllNodes.insert(Position, AllNodes.remove(N)); 867 } 868 869 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 870 /// operation. 871 static bool isCommutativeBinOp(unsigned Opcode) { 872 // FIXME: This should get its info from the td file, so that we can include 873 // target info. 874 switch (Opcode) { 875 case ISD::ADD: 876 case ISD::MUL: 877 case ISD::MULHU: 878 case ISD::MULHS: 879 case ISD::SMUL_LOHI: 880 case ISD::UMUL_LOHI: 881 case ISD::FADD: 882 case ISD::FMUL: 883 case ISD::AND: 884 case ISD::OR: 885 case ISD::XOR: 886 case ISD::SADDO: 887 case ISD::UADDO: 888 case ISD::ADDC: 889 case ISD::ADDE: return true; 890 default: return false; 891 } 892 } 893 894 /// AssignOrdering - Assign an order to the SDNode. 895 void AssignOrdering(const SDNode *SD, unsigned Order); 896 897 /// GetOrdering - Get the order for the SDNode. 898 unsigned GetOrdering(const SDNode *SD) const; 899 900 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the 901 /// value is produced by SD. 902 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter); 903 904 /// GetDbgValues - Get the debug values which reference the given SDNode. 905 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) { 906 return DbgInfo->getSDDbgValues(SD); 907 } 908 909 /// TransferDbgValues - Transfer SDDbgValues. 910 void TransferDbgValues(SDValue From, SDValue To); 911 912 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated 913 /// with this SelectionDAG. 914 bool hasDebugValues() const { return !DbgInfo->empty(); } 915 916 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); } 917 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); } 918 SDDbgInfo::DbgIterator ByvalParmDbgBegin() { 919 return DbgInfo->ByvalParmDbgBegin(); 920 } 921 SDDbgInfo::DbgIterator ByvalParmDbgEnd() { 922 return DbgInfo->ByvalParmDbgEnd(); 923 } 924 925 void dump() const; 926 927 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 928 /// specified value type. If minAlign is specified, the slot size will have 929 /// at least that alignment. 930 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1); 931 932 /// CreateStackTemporary - Create a stack temporary suitable for holding 933 /// either of the specified value types. 934 SDValue CreateStackTemporary(EVT VT1, EVT VT2); 935 936 /// FoldConstantArithmetic - 937 SDValue FoldConstantArithmetic(unsigned Opcode, 938 EVT VT, 939 ConstantSDNode *Cst1, 940 ConstantSDNode *Cst2); 941 942 /// FoldSetCC - Constant fold a setcc to true or false. 943 SDValue FoldSetCC(EVT VT, SDValue N1, 944 SDValue N2, ISD::CondCode Cond, DebugLoc dl); 945 946 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 947 /// use this predicate to simplify operations downstream. 948 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const; 949 950 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 951 /// use this predicate to simplify operations downstream. Op and Mask are 952 /// known to be the same type. 953 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0) 954 const; 955 956 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 957 /// known to be either zero or one and return them in the KnownZero/KnownOne 958 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 959 /// processing. Targets can implement the computeMaskedBitsForTargetNode 960 /// method in the TargetLowering class to allow target nodes to be understood. 961 void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero, 962 APInt &KnownOne, unsigned Depth = 0) const; 963 964 /// ComputeNumSignBits - Return the number of times the sign bit of the 965 /// register is replicated into the other bits. We know that at least 1 bit 966 /// is always equal to the sign bit (itself), but other cases can give us 967 /// information. For example, immediately after an "SRA X, 2", we know that 968 /// the top 3 bits are all equal to each other, so we return 3. Targets can 969 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 970 /// class to allow target nodes to be understood. 971 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; 972 973 /// isBaseWithConstantOffset - Return true if the specified operand is an 974 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an 975 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same 976 /// semantics as an ADD. This handles the equivalence: 977 /// X|Cst == X+Cst iff X&Cst = 0. 978 bool isBaseWithConstantOffset(SDValue Op) const; 979 980 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN. 981 bool isKnownNeverNaN(SDValue Op) const; 982 983 /// isKnownNeverZero - Test whether the given SDValue is known to never be 984 /// positive or negative Zero. 985 bool isKnownNeverZero(SDValue Op) const; 986 987 /// isEqualTo - Test whether two SDValues are known to compare equal. This 988 /// is true if they are the same value, or if one is negative zero and the 989 /// other positive zero. 990 bool isEqualTo(SDValue A, SDValue B) const; 991 992 /// UnrollVectorOp - Utility function used by legalize and lowering to 993 /// "unroll" a vector operation by splitting out the scalars and operating 994 /// on each element individually. If the ResNE is 0, fully unroll the vector 995 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE. 996 /// If the ResNE is greater than the width of the vector op, unroll the 997 /// vector op and fill the end of the resulting vector with UNDEFS. 998 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0); 999 1000 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a 1001 /// location that is 'Dist' units away from the location that the 'Base' load 1002 /// is loading from. 1003 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base, 1004 unsigned Bytes, int Dist) const; 1005 1006 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if 1007 /// it cannot be inferred. 1008 unsigned InferPtrAlignment(SDValue Ptr) const; 1009 1010 private: 1011 bool RemoveNodeFromCSEMaps(SDNode *N); 1012 void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener); 1013 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); 1014 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, 1015 void *&InsertPos); 1016 SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps, 1017 void *&InsertPos); 1018 1019 void DeleteNodeNotInCSEMaps(SDNode *N); 1020 void DeallocateNode(SDNode *N); 1021 1022 unsigned getEVTAlignment(EVT MemoryVT) const; 1023 1024 void allnodes_clear(); 1025 1026 /// VTList - List of non-single value types. 1027 std::vector<SDVTList> VTList; 1028 1029 /// CondCodeNodes - Maps to auto-CSE operations. 1030 std::vector<CondCodeSDNode*> CondCodeNodes; 1031 1032 std::vector<SDNode*> ValueTypeNodes; 1033 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes; 1034 StringMap<SDNode*> ExternalSymbols; 1035 1036 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols; 1037 }; 1038 1039 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 1040 typedef SelectionDAG::allnodes_iterator nodes_iterator; 1041 static nodes_iterator nodes_begin(SelectionDAG *G) { 1042 return G->allnodes_begin(); 1043 } 1044 static nodes_iterator nodes_end(SelectionDAG *G) { 1045 return G->allnodes_end(); 1046 } 1047 }; 1048 1049 } // end namespace llvm 1050 1051 #endif 1052
