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