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/SetVector.h" 20 #include "llvm/ADT/StringMap.h" 21 #include "llvm/ADT/ilist.h" 22 #include "llvm/Analysis/AliasAnalysis.h" 23 #include "llvm/CodeGen/DAGCombine.h" 24 #include "llvm/CodeGen/MachineFunction.h" 25 #include "llvm/CodeGen/SelectionDAGNodes.h" 26 #include "llvm/Support/ArrayRecycler.h" 27 #include "llvm/Support/RecyclingAllocator.h" 28 #include "llvm/Target/TargetMachine.h" 29 #include <cassert> 30 #include <map> 31 #include <string> 32 #include <vector> 33 34 namespace llvm { 35 36 class MachineConstantPoolValue; 37 class MachineFunction; 38 class MDNode; 39 class SDDbgValue; 40 class TargetLowering; 41 class SelectionDAGTargetInfo; 42 43 class SDVTListNode : public FoldingSetNode { 44 friend struct FoldingSetTrait<SDVTListNode>; 45 /// A reference to an Interned FoldingSetNodeID for this node. 46 /// The Allocator in SelectionDAG holds the data. 47 /// SDVTList contains all types which are frequently accessed in SelectionDAG. 48 /// The size of this list is not expected to be big so it won't introduce 49 /// a memory penalty. 50 FoldingSetNodeIDRef FastID; 51 const EVT *VTs; 52 unsigned int NumVTs; 53 /// The hash value for SDVTList is fixed, so cache it to avoid 54 /// hash calculation. 55 unsigned HashValue; 56 public: 57 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) : 58 FastID(ID), VTs(VT), NumVTs(Num) { 59 HashValue = ID.ComputeHash(); 60 } 61 SDVTList getSDVTList() { 62 SDVTList result = {VTs, NumVTs}; 63 return result; 64 } 65 }; 66 67 /// Specialize FoldingSetTrait for SDVTListNode 68 /// to avoid computing temp FoldingSetNodeID and hash value. 69 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> { 70 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) { 71 ID = X.FastID; 72 } 73 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID, 74 unsigned IDHash, FoldingSetNodeID &TempID) { 75 if (X.HashValue != IDHash) 76 return false; 77 return ID == X.FastID; 78 } 79 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) { 80 return X.HashValue; 81 } 82 }; 83 84 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> { 85 private: 86 mutable ilist_half_node<SDNode> Sentinel; 87 public: 88 SDNode *createSentinel() const { 89 return static_cast<SDNode*>(&Sentinel); 90 } 91 static void destroySentinel(SDNode *) {} 92 93 SDNode *provideInitialHead() const { return createSentinel(); } 94 SDNode *ensureHead(SDNode*) const { return createSentinel(); } 95 static void noteHead(SDNode*, SDNode*) {} 96 97 static void deleteNode(SDNode *) { 98 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!"); 99 } 100 private: 101 static void createNode(const SDNode &); 102 }; 103 104 /// Keeps track of dbg_value information through SDISel. We do 105 /// not build SDNodes for these so as not to perturb the generated code; 106 /// instead the info is kept off to the side in this structure. Each SDNode may 107 /// have one or more associated dbg_value entries. This information is kept in 108 /// DbgValMap. 109 /// Byval parameters are handled separately because they don't use alloca's, 110 /// which busts the normal mechanism. There is good reason for handling all 111 /// parameters separately: they may not have code generated for them, they 112 /// should always go at the beginning of the function regardless of other code 113 /// motion, and debug info for them is potentially useful even if the parameter 114 /// is unused. Right now only byval parameters are handled separately. 115 class SDDbgInfo { 116 BumpPtrAllocator Alloc; 117 SmallVector<SDDbgValue*, 32> DbgValues; 118 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues; 119 typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType; 120 DbgValMapType DbgValMap; 121 122 void operator=(const SDDbgInfo&) = delete; 123 SDDbgInfo(const SDDbgInfo&) = delete; 124 public: 125 SDDbgInfo() {} 126 127 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) { 128 if (isParameter) { 129 ByvalParmDbgValues.push_back(V); 130 } else DbgValues.push_back(V); 131 if (Node) 132 DbgValMap[Node].push_back(V); 133 } 134 135 /// \brief Invalidate all DbgValues attached to the node and remove 136 /// it from the Node-to-DbgValues map. 137 void erase(const SDNode *Node); 138 139 void clear() { 140 DbgValMap.clear(); 141 DbgValues.clear(); 142 ByvalParmDbgValues.clear(); 143 Alloc.Reset(); 144 } 145 146 BumpPtrAllocator &getAlloc() { return Alloc; } 147 148 bool empty() const { 149 return DbgValues.empty() && ByvalParmDbgValues.empty(); 150 } 151 152 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) { 153 DbgValMapType::iterator I = DbgValMap.find(Node); 154 if (I != DbgValMap.end()) 155 return I->second; 156 return ArrayRef<SDDbgValue*>(); 157 } 158 159 typedef SmallVectorImpl<SDDbgValue*>::iterator DbgIterator; 160 DbgIterator DbgBegin() { return DbgValues.begin(); } 161 DbgIterator DbgEnd() { return DbgValues.end(); } 162 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); } 163 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); } 164 }; 165 166 class SelectionDAG; 167 void checkForCycles(const SelectionDAG *DAG, bool force = false); 168 169 /// This is used to represent a portion of an LLVM function in a low-level 170 /// Data Dependence DAG representation suitable for instruction selection. 171 /// This DAG is constructed as the first step of instruction selection in order 172 /// to allow implementation of machine specific optimizations 173 /// and code simplifications. 174 /// 175 /// The representation used by the SelectionDAG is a target-independent 176 /// representation, which has some similarities to the GCC RTL representation, 177 /// but is significantly more simple, powerful, and is a graph form instead of a 178 /// linear form. 179 /// 180 class SelectionDAG { 181 const TargetMachine &TM; 182 const SelectionDAGTargetInfo *TSI; 183 const TargetLowering *TLI; 184 MachineFunction *MF; 185 LLVMContext *Context; 186 CodeGenOpt::Level OptLevel; 187 188 /// The starting token. 189 SDNode EntryNode; 190 191 /// The root of the entire DAG. 192 SDValue Root; 193 194 /// A linked list of nodes in the current DAG. 195 ilist<SDNode> AllNodes; 196 197 /// The AllocatorType for allocating SDNodes. We use 198 /// pool allocation with recycling. 199 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode), 200 AlignOf<MostAlignedSDNode>::Alignment> 201 NodeAllocatorType; 202 203 /// Pool allocation for nodes. 204 NodeAllocatorType NodeAllocator; 205 206 /// This structure is used to memoize nodes, automatically performing 207 /// CSE with existing nodes when a duplicate is requested. 208 FoldingSet<SDNode> CSEMap; 209 210 /// Pool allocation for machine-opcode SDNode operands. 211 BumpPtrAllocator OperandAllocator; 212 ArrayRecycler<SDUse> OperandRecycler; 213 214 /// Pool allocation for misc. objects that are created once per SelectionDAG. 215 BumpPtrAllocator Allocator; 216 217 /// Tracks dbg_value information through SDISel. 218 SDDbgInfo *DbgInfo; 219 220 uint16_t NextPersistentId = 0; 221 222 public: 223 /// Clients of various APIs that cause global effects on 224 /// the DAG can optionally implement this interface. This allows the clients 225 /// to handle the various sorts of updates that happen. 226 /// 227 /// A DAGUpdateListener automatically registers itself with DAG when it is 228 /// constructed, and removes itself when destroyed in RAII fashion. 229 struct DAGUpdateListener { 230 DAGUpdateListener *const Next; 231 SelectionDAG &DAG; 232 233 explicit DAGUpdateListener(SelectionDAG &D) 234 : Next(D.UpdateListeners), DAG(D) { 235 DAG.UpdateListeners = this; 236 } 237 238 virtual ~DAGUpdateListener() { 239 assert(DAG.UpdateListeners == this && 240 "DAGUpdateListeners must be destroyed in LIFO order"); 241 DAG.UpdateListeners = Next; 242 } 243 244 /// The node N that was deleted and, if E is not null, an 245 /// equivalent node E that replaced it. 246 virtual void NodeDeleted(SDNode *N, SDNode *E); 247 248 /// The node N that was updated. 249 virtual void NodeUpdated(SDNode *N); 250 }; 251 252 struct DAGNodeDeletedListener : public DAGUpdateListener { 253 std::function<void(SDNode *, SDNode *)> Callback; 254 DAGNodeDeletedListener(SelectionDAG &DAG, 255 std::function<void(SDNode *, SDNode *)> Callback) 256 : DAGUpdateListener(DAG), Callback(Callback) {} 257 void NodeDeleted(SDNode *N, SDNode *E) override { Callback(N, E); } 258 }; 259 260 /// When true, additional steps are taken to 261 /// ensure that getConstant() and similar functions return DAG nodes that 262 /// have legal types. This is important after type legalization since 263 /// any illegally typed nodes generated after this point will not experience 264 /// type legalization. 265 bool NewNodesMustHaveLegalTypes; 266 267 private: 268 /// DAGUpdateListener is a friend so it can manipulate the listener stack. 269 friend struct DAGUpdateListener; 270 271 /// Linked list of registered DAGUpdateListener instances. 272 /// This stack is maintained by DAGUpdateListener RAII. 273 DAGUpdateListener *UpdateListeners; 274 275 /// Implementation of setSubgraphColor. 276 /// Return whether we had to truncate the search. 277 bool setSubgraphColorHelper(SDNode *N, const char *Color, 278 DenseSet<SDNode *> &visited, 279 int level, bool &printed); 280 281 template <typename SDNodeT, typename... ArgTypes> 282 SDNodeT *newSDNode(ArgTypes &&... Args) { 283 return new (NodeAllocator.template Allocate<SDNodeT>()) 284 SDNodeT(std::forward<ArgTypes>(Args)...); 285 } 286 287 void createOperands(SDNode *Node, ArrayRef<SDValue> Vals) { 288 assert(!Node->OperandList && "Node already has operands"); 289 SDUse *Ops = OperandRecycler.allocate( 290 ArrayRecycler<SDUse>::Capacity::get(Vals.size()), OperandAllocator); 291 292 for (unsigned I = 0; I != Vals.size(); ++I) { 293 Ops[I].setUser(Node); 294 Ops[I].setInitial(Vals[I]); 295 } 296 Node->NumOperands = Vals.size(); 297 Node->OperandList = Ops; 298 checkForCycles(Node); 299 } 300 301 void removeOperands(SDNode *Node) { 302 if (!Node->OperandList) 303 return; 304 OperandRecycler.deallocate( 305 ArrayRecycler<SDUse>::Capacity::get(Node->NumOperands), 306 Node->OperandList); 307 Node->NumOperands = 0; 308 Node->OperandList = nullptr; 309 } 310 311 void operator=(const SelectionDAG&) = delete; 312 SelectionDAG(const SelectionDAG&) = delete; 313 314 public: 315 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level); 316 ~SelectionDAG(); 317 318 /// Prepare this SelectionDAG to process code in the given MachineFunction. 319 void init(MachineFunction &mf); 320 321 /// Clear state and free memory necessary to make this 322 /// SelectionDAG ready to process a new block. 323 void clear(); 324 325 MachineFunction &getMachineFunction() const { return *MF; } 326 const DataLayout &getDataLayout() const { return MF->getDataLayout(); } 327 const TargetMachine &getTarget() const { return TM; } 328 const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); } 329 const TargetLowering &getTargetLoweringInfo() const { return *TLI; } 330 const SelectionDAGTargetInfo &getSelectionDAGInfo() const { return *TSI; } 331 LLVMContext *getContext() const {return Context; } 332 333 /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 334 void viewGraph(const std::string &Title); 335 void viewGraph(); 336 337 #ifndef NDEBUG 338 std::map<const SDNode *, std::string> NodeGraphAttrs; 339 #endif 340 341 /// Clear all previously defined node graph attributes. 342 /// Intended to be used from a debugging tool (eg. gdb). 343 void clearGraphAttrs(); 344 345 /// Set graph attributes for a node. (eg. "color=red".) 346 void setGraphAttrs(const SDNode *N, const char *Attrs); 347 348 /// Get graph attributes for a node. (eg. "color=red".) 349 /// Used from getNodeAttributes. 350 const std::string getGraphAttrs(const SDNode *N) const; 351 352 /// Convenience for setting node color attribute. 353 void setGraphColor(const SDNode *N, const char *Color); 354 355 /// Convenience for setting subgraph color attribute. 356 void setSubgraphColor(SDNode *N, const char *Color); 357 358 typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 359 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 360 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 361 typedef ilist<SDNode>::iterator allnodes_iterator; 362 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 363 allnodes_iterator allnodes_end() { return AllNodes.end(); } 364 ilist<SDNode>::size_type allnodes_size() const { 365 return AllNodes.size(); 366 } 367 368 iterator_range<allnodes_iterator> allnodes() { 369 return make_range(allnodes_begin(), allnodes_end()); 370 } 371 iterator_range<allnodes_const_iterator> allnodes() const { 372 return make_range(allnodes_begin(), allnodes_end()); 373 } 374 375 /// Return the root tag of the SelectionDAG. 376 const SDValue &getRoot() const { return Root; } 377 378 /// Return the token chain corresponding to the entry of the function. 379 SDValue getEntryNode() const { 380 return SDValue(const_cast<SDNode *>(&EntryNode), 0); 381 } 382 383 /// Set the current root tag of the SelectionDAG. 384 /// 385 const SDValue &setRoot(SDValue N) { 386 assert((!N.getNode() || N.getValueType() == MVT::Other) && 387 "DAG root value is not a chain!"); 388 if (N.getNode()) 389 checkForCycles(N.getNode(), this); 390 Root = N; 391 if (N.getNode()) 392 checkForCycles(this); 393 return Root; 394 } 395 396 /// This iterates over the nodes in the SelectionDAG, folding 397 /// certain types of nodes together, or eliminating superfluous nodes. The 398 /// Level argument controls whether Combine is allowed to produce nodes and 399 /// types that are illegal on the target. 400 void Combine(CombineLevel Level, AliasAnalysis &AA, 401 CodeGenOpt::Level OptLevel); 402 403 /// This transforms the SelectionDAG into a SelectionDAG that 404 /// only uses types natively supported by the target. 405 /// Returns "true" if it made any changes. 406 /// 407 /// Note that this is an involved process that may invalidate pointers into 408 /// the graph. 409 bool LegalizeTypes(); 410 411 /// This transforms the SelectionDAG into a SelectionDAG that is 412 /// compatible with the target instruction selector, as indicated by the 413 /// TargetLowering object. 414 /// 415 /// Note that this is an involved process that may invalidate pointers into 416 /// the graph. 417 void Legalize(); 418 419 /// \brief Transforms a SelectionDAG node and any operands to it into a node 420 /// that is compatible with the target instruction selector, as indicated by 421 /// the TargetLowering object. 422 /// 423 /// \returns true if \c N is a valid, legal node after calling this. 424 /// 425 /// This essentially runs a single recursive walk of the \c Legalize process 426 /// over the given node (and its operands). This can be used to incrementally 427 /// legalize the DAG. All of the nodes which are directly replaced, 428 /// potentially including N, are added to the output parameter \c 429 /// UpdatedNodes so that the delta to the DAG can be understood by the 430 /// caller. 431 /// 432 /// When this returns false, N has been legalized in a way that make the 433 /// pointer passed in no longer valid. It may have even been deleted from the 434 /// DAG, and so it shouldn't be used further. When this returns true, the 435 /// N passed in is a legal node, and can be immediately processed as such. 436 /// This may still have done some work on the DAG, and will still populate 437 /// UpdatedNodes with any new nodes replacing those originally in the DAG. 438 bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes); 439 440 /// This transforms the SelectionDAG into a SelectionDAG 441 /// that only uses vector math operations supported by the target. This is 442 /// necessary as a separate step from Legalize because unrolling a vector 443 /// operation can introduce illegal types, which requires running 444 /// LegalizeTypes again. 445 /// 446 /// This returns true if it made any changes; in that case, LegalizeTypes 447 /// is called again before Legalize. 448 /// 449 /// Note that this is an involved process that may invalidate pointers into 450 /// the graph. 451 bool LegalizeVectors(); 452 453 /// This method deletes all unreachable nodes in the SelectionDAG. 454 void RemoveDeadNodes(); 455 456 /// Remove the specified node from the system. This node must 457 /// have no referrers. 458 void DeleteNode(SDNode *N); 459 460 /// Return an SDVTList that represents the list of values specified. 461 SDVTList getVTList(EVT VT); 462 SDVTList getVTList(EVT VT1, EVT VT2); 463 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3); 464 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4); 465 SDVTList getVTList(ArrayRef<EVT> VTs); 466 467 //===--------------------------------------------------------------------===// 468 // Node creation methods. 469 // 470 471 /// \brief Create a ConstantSDNode wrapping a constant value. 472 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR. 473 /// 474 /// If only legal types can be produced, this does the necessary 475 /// transformations (e.g., if the vector element type is illegal). 476 /// @{ 477 SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT, 478 bool isTarget = false, bool isOpaque = false); 479 SDValue getConstant(const APInt &Val, const SDLoc &DL, EVT VT, 480 bool isTarget = false, bool isOpaque = false); 481 SDValue getConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT, 482 bool isTarget = false, bool isOpaque = false); 483 SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL, 484 bool isTarget = false); 485 SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT, 486 bool isOpaque = false) { 487 return getConstant(Val, DL, VT, true, isOpaque); 488 } 489 SDValue getTargetConstant(const APInt &Val, const SDLoc &DL, EVT VT, 490 bool isOpaque = false) { 491 return getConstant(Val, DL, VT, true, isOpaque); 492 } 493 SDValue getTargetConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT, 494 bool isOpaque = false) { 495 return getConstant(Val, DL, VT, true, isOpaque); 496 } 497 /// @} 498 499 /// \brief Create a ConstantFPSDNode wrapping a constant value. 500 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR. 501 /// 502 /// If only legal types can be produced, this does the necessary 503 /// transformations (e.g., if the vector element type is illegal). 504 /// The forms that take a double should only be used for simple constants 505 /// that can be exactly represented in VT. No checks are made. 506 /// @{ 507 SDValue getConstantFP(double Val, const SDLoc &DL, EVT VT, 508 bool isTarget = false); 509 SDValue getConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT, 510 bool isTarget = false); 511 SDValue getConstantFP(const ConstantFP &CF, const SDLoc &DL, EVT VT, 512 bool isTarget = false); 513 SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT) { 514 return getConstantFP(Val, DL, VT, true); 515 } 516 SDValue getTargetConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT) { 517 return getConstantFP(Val, DL, VT, true); 518 } 519 SDValue getTargetConstantFP(const ConstantFP &Val, const SDLoc &DL, EVT VT) { 520 return getConstantFP(Val, DL, VT, true); 521 } 522 /// @} 523 524 SDValue getGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT, 525 int64_t offset = 0, bool isTargetGA = false, 526 unsigned char TargetFlags = 0); 527 SDValue getTargetGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT, 528 int64_t offset = 0, 529 unsigned char TargetFlags = 0) { 530 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags); 531 } 532 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false); 533 SDValue getTargetFrameIndex(int FI, EVT VT) { 534 return getFrameIndex(FI, VT, true); 535 } 536 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false, 537 unsigned char TargetFlags = 0); 538 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) { 539 return getJumpTable(JTI, VT, true, TargetFlags); 540 } 541 SDValue getConstantPool(const Constant *C, EVT VT, 542 unsigned Align = 0, int Offs = 0, bool isT=false, 543 unsigned char TargetFlags = 0); 544 SDValue getTargetConstantPool(const Constant *C, EVT VT, 545 unsigned Align = 0, int Offset = 0, 546 unsigned char TargetFlags = 0) { 547 return getConstantPool(C, VT, Align, Offset, true, TargetFlags); 548 } 549 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT, 550 unsigned Align = 0, int Offs = 0, bool isT=false, 551 unsigned char TargetFlags = 0); 552 SDValue getTargetConstantPool(MachineConstantPoolValue *C, 553 EVT VT, unsigned Align = 0, 554 int Offset = 0, unsigned char TargetFlags=0) { 555 return getConstantPool(C, VT, Align, Offset, true, TargetFlags); 556 } 557 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0, 558 unsigned char TargetFlags = 0); 559 // When generating a branch to a BB, we don't in general know enough 560 // to provide debug info for the BB at that time, so keep this one around. 561 SDValue getBasicBlock(MachineBasicBlock *MBB); 562 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl); 563 SDValue getExternalSymbol(const char *Sym, EVT VT); 564 SDValue getExternalSymbol(const char *Sym, const SDLoc &dl, EVT VT); 565 SDValue getTargetExternalSymbol(const char *Sym, EVT VT, 566 unsigned char TargetFlags = 0); 567 SDValue getMCSymbol(MCSymbol *Sym, EVT VT); 568 569 SDValue getValueType(EVT); 570 SDValue getRegister(unsigned Reg, EVT VT); 571 SDValue getRegisterMask(const uint32_t *RegMask); 572 SDValue getEHLabel(const SDLoc &dl, SDValue Root, MCSymbol *Label); 573 SDValue getBlockAddress(const BlockAddress *BA, EVT VT, 574 int64_t Offset = 0, bool isTarget = false, 575 unsigned char TargetFlags = 0); 576 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT, 577 int64_t Offset = 0, 578 unsigned char TargetFlags = 0) { 579 return getBlockAddress(BA, VT, Offset, true, TargetFlags); 580 } 581 582 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, 583 SDValue N) { 584 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, 585 getRegister(Reg, N.getValueType()), N); 586 } 587 588 // This version of the getCopyToReg method takes an extra operand, which 589 // indicates that there is potentially an incoming glue value (if Glue is not 590 // null) and that there should be a glue result. 591 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N, 592 SDValue Glue) { 593 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 594 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue }; 595 return getNode(ISD::CopyToReg, dl, VTs, 596 makeArrayRef(Ops, Glue.getNode() ? 4 : 3)); 597 } 598 599 // Similar to last getCopyToReg() except parameter Reg is a SDValue 600 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, SDValue Reg, SDValue N, 601 SDValue Glue) { 602 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 603 SDValue Ops[] = { Chain, Reg, N, Glue }; 604 return getNode(ISD::CopyToReg, dl, VTs, 605 makeArrayRef(Ops, Glue.getNode() ? 4 : 3)); 606 } 607 608 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT) { 609 SDVTList VTs = getVTList(VT, MVT::Other); 610 SDValue Ops[] = { Chain, getRegister(Reg, VT) }; 611 return getNode(ISD::CopyFromReg, dl, VTs, Ops); 612 } 613 614 // This version of the getCopyFromReg method takes an extra operand, which 615 // indicates that there is potentially an incoming glue value (if Glue is not 616 // null) and that there should be a glue result. 617 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT, 618 SDValue Glue) { 619 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue); 620 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue }; 621 return getNode(ISD::CopyFromReg, dl, VTs, 622 makeArrayRef(Ops, Glue.getNode() ? 3 : 2)); 623 } 624 625 SDValue getCondCode(ISD::CondCode Cond); 626 627 /// Returns the ConvertRndSat Note: Avoid using this node because it may 628 /// disappear in the future and most targets don't support it. 629 SDValue getConvertRndSat(EVT VT, const SDLoc &dl, SDValue Val, SDValue DTy, 630 SDValue STy, SDValue Rnd, SDValue Sat, 631 ISD::CvtCode Code); 632 633 /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT, 634 /// which must be a vector type, must match the number of mask elements 635 /// NumElts. An integer mask element equal to -1 is treated as undefined. 636 SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2, 637 ArrayRef<int> Mask); 638 639 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT, 640 /// which must be a vector type, must match the number of operands in Ops. 641 /// The operands must have the same type as (or, for integers, a type wider 642 /// than) VT's element type. 643 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDValue> Ops) { 644 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later. 645 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops); 646 } 647 648 /// Return a splat ISD::BUILD_VECTOR node, consisting of Op splatted to all 649 /// elements. VT must be a vector type. Op's type must be the same as (or, 650 /// for integers, a type wider than) VT's element type. 651 SDValue getSplatBuildVector(EVT VT, const SDLoc &DL, SDValue Op) { 652 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later. 653 if (Op.getOpcode() == ISD::UNDEF) { 654 assert((VT.getVectorElementType() == Op.getValueType() || 655 (VT.isInteger() && 656 VT.getVectorElementType().bitsLE(Op.getValueType()))) && 657 "A splatted value must have a width equal or (for integers) " 658 "greater than the vector element type!"); 659 return getNode(ISD::UNDEF, SDLoc(), VT); 660 } 661 662 SmallVector<SDValue, 16> Ops(VT.getVectorNumElements(), Op); 663 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops); 664 } 665 666 /// Return a splat ISD::BUILD_VECTOR node, but with Op's SDLoc. 667 SDValue getSplatBuildVector(EVT VT, SDValue Op) { 668 return getSplatBuildVector(VT, SDLoc(Op), Op); 669 } 670 671 /// \brief Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to 672 /// the shuffle node in input but with swapped operands. 673 /// 674 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3> 675 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV); 676 677 /// Convert Op, which must be of integer type, to the 678 /// integer type VT, by either any-extending or truncating it. 679 SDValue getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 680 681 /// Convert Op, which must be of integer type, to the 682 /// integer type VT, by either sign-extending or truncating it. 683 SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 684 685 /// Convert Op, which must be of integer type, to the 686 /// integer type VT, by either zero-extending or truncating it. 687 SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 688 689 /// Return the expression required to zero extend the Op 690 /// value assuming it was the smaller SrcTy value. 691 SDValue getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT SrcTy); 692 693 /// Return an operation which will any-extend the low lanes of the operand 694 /// into the specified vector type. For example, 695 /// this can convert a v16i8 into a v4i32 by any-extending the low four 696 /// lanes of the operand from i8 to i32. 697 SDValue getAnyExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT); 698 699 /// Return an operation which will sign extend the low lanes of the operand 700 /// into the specified vector type. For example, 701 /// this can convert a v16i8 into a v4i32 by sign extending the low four 702 /// lanes of the operand from i8 to i32. 703 SDValue getSignExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT); 704 705 /// Return an operation which will zero extend the low lanes of the operand 706 /// into the specified vector type. For example, 707 /// this can convert a v16i8 into a v4i32 by zero extending the low four 708 /// lanes of the operand from i8 to i32. 709 SDValue getZeroExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT); 710 711 /// Convert Op, which must be of integer type, to the integer type VT, 712 /// by using an extension appropriate for the target's 713 /// BooleanContent for type OpVT or truncating it. 714 SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT); 715 716 /// Create a bitwise NOT operation as (XOR Val, -1). 717 SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT); 718 719 /// \brief Create a logical NOT operation as (XOR Val, BooleanOne). 720 SDValue getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT); 721 722 /// Return a new CALLSEQ_START node, which always must have a glue result 723 /// (to ensure it's not CSE'd). CALLSEQ_START does not have a useful SDLoc. 724 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, const SDLoc &DL) { 725 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 726 SDValue Ops[] = { Chain, Op }; 727 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops); 728 } 729 730 /// Return a new CALLSEQ_END node, which always must have a 731 /// glue result (to ensure it's not CSE'd). 732 /// CALLSEQ_END does not have a useful SDLoc. 733 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, 734 SDValue InGlue, const SDLoc &DL) { 735 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue); 736 SmallVector<SDValue, 4> Ops; 737 Ops.push_back(Chain); 738 Ops.push_back(Op1); 739 Ops.push_back(Op2); 740 if (InGlue.getNode()) 741 Ops.push_back(InGlue); 742 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops); 743 } 744 745 /// Return an UNDEF node. UNDEF does not have a useful SDLoc. 746 SDValue getUNDEF(EVT VT) { 747 return getNode(ISD::UNDEF, SDLoc(), VT); 748 } 749 750 /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc. 751 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) { 752 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT); 753 } 754 755 /// Gets or creates the specified node. 756 /// 757 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, 758 ArrayRef<SDUse> Ops); 759 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, 760 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags = nullptr); 761 SDValue getNode(unsigned Opcode, const SDLoc &DL, ArrayRef<EVT> ResultTys, 762 ArrayRef<SDValue> Ops); 763 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, 764 ArrayRef<SDValue> Ops); 765 766 // Specialize based on number of operands. 767 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT); 768 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N); 769 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 770 SDValue N2, const SDNodeFlags *Flags = nullptr); 771 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 772 SDValue N2, SDValue N3); 773 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 774 SDValue N2, SDValue N3, SDValue N4); 775 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 776 SDValue N2, SDValue N3, SDValue N4, SDValue N5); 777 778 // Specialize again based on number of operands for nodes with a VTList 779 // rather than a single VT. 780 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs); 781 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N); 782 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1, 783 SDValue N2); 784 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1, 785 SDValue N2, SDValue N3); 786 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1, 787 SDValue N2, SDValue N3, SDValue N4); 788 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, SDValue N1, 789 SDValue N2, SDValue N3, SDValue N4, SDValue N5); 790 791 /// Compute a TokenFactor to force all the incoming stack arguments to be 792 /// loaded from the stack. This is used in tail call lowering to protect 793 /// stack arguments from being clobbered. 794 SDValue getStackArgumentTokenFactor(SDValue Chain); 795 796 SDValue getMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src, 797 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline, 798 bool isTailCall, MachinePointerInfo DstPtrInfo, 799 MachinePointerInfo SrcPtrInfo); 800 801 SDValue getMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src, 802 SDValue Size, unsigned Align, bool isVol, bool isTailCall, 803 MachinePointerInfo DstPtrInfo, 804 MachinePointerInfo SrcPtrInfo); 805 806 SDValue getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src, 807 SDValue Size, unsigned Align, bool isVol, bool isTailCall, 808 MachinePointerInfo DstPtrInfo); 809 810 /// Helper function to make it easier to build SetCC's if you just 811 /// have an ISD::CondCode instead of an SDValue. 812 /// 813 SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS, 814 ISD::CondCode Cond) { 815 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() && 816 "Cannot compare scalars to vectors"); 817 assert(LHS.getValueType().isVector() == VT.isVector() && 818 "Cannot compare scalars to vectors"); 819 assert(Cond != ISD::SETCC_INVALID && 820 "Cannot create a setCC of an invalid node."); 821 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 822 } 823 824 /// Helper function to make it easier to build Select's if you just 825 /// have operands and don't want to check for vector. 826 SDValue getSelect(const SDLoc &DL, EVT VT, SDValue Cond, SDValue LHS, 827 SDValue RHS) { 828 assert(LHS.getValueType() == RHS.getValueType() && 829 "Cannot use select on differing types"); 830 assert(VT.isVector() == LHS.getValueType().isVector() && 831 "Cannot mix vectors and scalars"); 832 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT, 833 Cond, LHS, RHS); 834 } 835 836 /// Helper function to make it easier to build SelectCC's if you 837 /// just have an ISD::CondCode instead of an SDValue. 838 /// 839 SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True, 840 SDValue False, ISD::CondCode Cond) { 841 return getNode(ISD::SELECT_CC, DL, True.getValueType(), 842 LHS, RHS, True, False, getCondCode(Cond)); 843 } 844 845 /// VAArg produces a result and token chain, and takes a pointer 846 /// and a source value as input. 847 SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 848 SDValue SV, unsigned Align); 849 850 /// Gets a node for an atomic cmpxchg op. There are two 851 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a 852 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded, 853 /// a success flag (initially i1), and a chain. 854 SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT, 855 SDVTList VTs, SDValue Chain, SDValue Ptr, 856 SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo, 857 unsigned Alignment, AtomicOrdering SuccessOrdering, 858 AtomicOrdering FailureOrdering, 859 SynchronizationScope SynchScope); 860 SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT, 861 SDVTList VTs, SDValue Chain, SDValue Ptr, 862 SDValue Cmp, SDValue Swp, MachineMemOperand *MMO, 863 AtomicOrdering SuccessOrdering, 864 AtomicOrdering FailureOrdering, 865 SynchronizationScope SynchScope); 866 867 /// Gets a node for an atomic op, produces result (if relevant) 868 /// and chain and takes 2 operands. 869 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain, 870 SDValue Ptr, SDValue Val, const Value *PtrVal, 871 unsigned Alignment, AtomicOrdering Ordering, 872 SynchronizationScope SynchScope); 873 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain, 874 SDValue Ptr, SDValue Val, MachineMemOperand *MMO, 875 AtomicOrdering Ordering, SynchronizationScope SynchScope); 876 877 /// Gets a node for an atomic op, produces result and chain and 878 /// takes 1 operand. 879 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, EVT VT, 880 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO, 881 AtomicOrdering Ordering, SynchronizationScope SynchScope); 882 883 /// Gets a node for an atomic op, produces result and chain and takes N 884 /// operands. 885 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, 886 SDVTList VTList, ArrayRef<SDValue> Ops, 887 MachineMemOperand *MMO, AtomicOrdering SuccessOrdering, 888 AtomicOrdering FailureOrdering, 889 SynchronizationScope SynchScope); 890 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, 891 SDVTList VTList, ArrayRef<SDValue> Ops, 892 MachineMemOperand *MMO, AtomicOrdering Ordering, 893 SynchronizationScope SynchScope); 894 895 /// Creates a MemIntrinsicNode that may produce a 896 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID, 897 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not 898 /// less than FIRST_TARGET_MEMORY_OPCODE. 899 SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList, 900 ArrayRef<SDValue> Ops, EVT MemVT, 901 MachinePointerInfo PtrInfo, unsigned Align = 0, 902 bool Vol = false, bool ReadMem = true, 903 bool WriteMem = true, unsigned Size = 0); 904 905 SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList, 906 ArrayRef<SDValue> Ops, EVT MemVT, 907 MachineMemOperand *MMO); 908 909 /// Create a MERGE_VALUES node from the given operands. 910 SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl); 911 912 /// Loads are not normal binary operators: their result type is not 913 /// determined by their operands, and they produce a value AND a token chain. 914 /// 915 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 916 MachinePointerInfo PtrInfo, bool isVolatile, 917 bool isNonTemporal, bool isInvariant, unsigned Alignment, 918 const AAMDNodes &AAInfo = AAMDNodes(), 919 const MDNode *Ranges = nullptr); 920 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 921 MachineMemOperand *MMO); 922 SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, 923 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, 924 EVT MemVT, bool isVolatile, bool isNonTemporal, 925 bool isInvariant, unsigned Alignment, 926 const AAMDNodes &AAInfo = AAMDNodes()); 927 SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, 928 SDValue Chain, SDValue Ptr, EVT MemVT, 929 MachineMemOperand *MMO); 930 SDValue getIndexedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base, 931 SDValue Offset, ISD::MemIndexedMode AM); 932 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 933 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 934 MachinePointerInfo PtrInfo, EVT MemVT, bool isVolatile, 935 bool isNonTemporal, bool isInvariant, unsigned Alignment, 936 const AAMDNodes &AAInfo = AAMDNodes(), 937 const MDNode *Ranges = nullptr); 938 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 939 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 940 EVT MemVT, MachineMemOperand *MMO); 941 942 /// Helper function to build ISD::STORE nodes. 943 SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 944 MachinePointerInfo PtrInfo, bool isVolatile, 945 bool isNonTemporal, unsigned Alignment, 946 const AAMDNodes &AAInfo = AAMDNodes()); 947 SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 948 MachineMemOperand *MMO); 949 SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, 950 SDValue Ptr, MachinePointerInfo PtrInfo, EVT TVT, 951 bool isNonTemporal, bool isVolatile, unsigned Alignment, 952 const AAMDNodes &AAInfo = AAMDNodes()); 953 SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, 954 SDValue Ptr, EVT TVT, MachineMemOperand *MMO); 955 SDValue getIndexedStore(SDValue OrigStoe, const SDLoc &dl, SDValue Base, 956 SDValue Offset, ISD::MemIndexedMode AM); 957 958 /// Returns sum of the base pointer and offset. 959 SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, const SDLoc &DL); 960 961 SDValue getMaskedLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 962 SDValue Mask, SDValue Src0, EVT MemVT, 963 MachineMemOperand *MMO, ISD::LoadExtType); 964 SDValue getMaskedStore(SDValue Chain, const SDLoc &dl, SDValue Val, 965 SDValue Ptr, SDValue Mask, EVT MemVT, 966 MachineMemOperand *MMO, bool IsTrunc); 967 SDValue getMaskedGather(SDVTList VTs, EVT VT, const SDLoc &dl, 968 ArrayRef<SDValue> Ops, MachineMemOperand *MMO); 969 SDValue getMaskedScatter(SDVTList VTs, EVT VT, const SDLoc &dl, 970 ArrayRef<SDValue> Ops, MachineMemOperand *MMO); 971 /// Construct a node to track a Value* through the backend. 972 SDValue getSrcValue(const Value *v); 973 974 /// Return an MDNodeSDNode which holds an MDNode. 975 SDValue getMDNode(const MDNode *MD); 976 977 /// Return a bitcast using the SDLoc of the value operand, and casting to the 978 /// provided type. Use getNode to set a custom SDLoc. 979 SDValue getBitcast(EVT VT, SDValue V); 980 981 /// Return an AddrSpaceCastSDNode. 982 SDValue getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr, unsigned SrcAS, 983 unsigned DestAS); 984 985 /// Return the specified value casted to 986 /// the target's desired shift amount type. 987 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op); 988 989 /// Expand the specified \c ISD::VAARG node as the Legalize pass would. 990 SDValue expandVAArg(SDNode *Node); 991 992 /// Expand the specified \c ISD::VACOPY node as the Legalize pass would. 993 SDValue expandVACopy(SDNode *Node); 994 995 /// *Mutate* the specified node in-place to have the 996 /// specified operands. If the resultant node already exists in the DAG, 997 /// this does not modify the specified node, instead it returns the node that 998 /// already exists. If the resultant node does not exist in the DAG, the 999 /// input node is returned. As a degenerate case, if you specify the same 1000 /// input operands as the node already has, the input node is returned. 1001 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op); 1002 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2); 1003 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 1004 SDValue Op3); 1005 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 1006 SDValue Op3, SDValue Op4); 1007 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 1008 SDValue Op3, SDValue Op4, SDValue Op5); 1009 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops); 1010 1011 /// These are used for target selectors to *mutate* the 1012 /// specified node to have the specified return type, Target opcode, and 1013 /// operands. Note that target opcodes are stored as 1014 /// ~TargetOpcode in the node opcode field. The resultant node is returned. 1015 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT); 1016 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1); 1017 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 1018 SDValue Op1, SDValue Op2); 1019 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 1020 SDValue Op1, SDValue Op2, SDValue Op3); 1021 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 1022 ArrayRef<SDValue> Ops); 1023 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2); 1024 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 1025 EVT VT2, ArrayRef<SDValue> Ops); 1026 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 1027 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops); 1028 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 1029 EVT VT2, EVT VT3, EVT VT4, ArrayRef<SDValue> Ops); 1030 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 1031 EVT VT2, SDValue Op1); 1032 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 1033 EVT VT2, SDValue Op1, SDValue Op2); 1034 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 1035 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 1036 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 1037 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); 1038 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs, 1039 ArrayRef<SDValue> Ops); 1040 1041 /// This *mutates* the specified node to have the specified 1042 /// return type, opcode, and operands. 1043 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, 1044 ArrayRef<SDValue> Ops); 1045 1046 /// These are used for target selectors to create a new node 1047 /// with specified return type(s), MachineInstr opcode, and operands. 1048 /// 1049 /// Note that getMachineNode returns the resultant node. If there is already 1050 /// a node of the specified opcode and operands, it returns that node instead 1051 /// of the current one. 1052 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT); 1053 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1054 SDValue Op1); 1055 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1056 SDValue Op1, SDValue Op2); 1057 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1058 SDValue Op1, SDValue Op2, SDValue Op3); 1059 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1060 ArrayRef<SDValue> Ops); 1061 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1062 EVT VT2); 1063 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1064 EVT VT2, SDValue Op1); 1065 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1066 EVT VT2, SDValue Op1, SDValue Op2); 1067 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1068 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 1069 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1070 EVT VT2, ArrayRef<SDValue> Ops); 1071 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1072 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2); 1073 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1074 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, 1075 SDValue Op3); 1076 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1077 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops); 1078 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1079 EVT VT2, EVT VT3, EVT VT4, 1080 ArrayRef<SDValue> Ops); 1081 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, 1082 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops); 1083 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, SDVTList VTs, 1084 ArrayRef<SDValue> Ops); 1085 1086 /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes. 1087 SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT, 1088 SDValue Operand); 1089 1090 /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes. 1091 SDValue getTargetInsertSubreg(int SRIdx, const SDLoc &DL, EVT VT, 1092 SDValue Operand, SDValue Subreg); 1093 1094 /// Get the specified node if it's already available, or else return NULL. 1095 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops, 1096 const SDNodeFlags *Flags = nullptr); 1097 1098 /// Creates a SDDbgValue node. 1099 SDDbgValue *getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N, unsigned R, 1100 bool IsIndirect, uint64_t Off, const DebugLoc &DL, 1101 unsigned O); 1102 1103 /// Constant 1104 SDDbgValue *getConstantDbgValue(MDNode *Var, MDNode *Expr, const Value *C, 1105 uint64_t Off, const DebugLoc &DL, unsigned O); 1106 1107 /// FrameIndex 1108 SDDbgValue *getFrameIndexDbgValue(MDNode *Var, MDNode *Expr, unsigned FI, 1109 uint64_t Off, const DebugLoc &DL, 1110 unsigned O); 1111 1112 /// Remove the specified node from the system. If any of its 1113 /// operands then becomes dead, remove them as well. Inform UpdateListener 1114 /// for each node deleted. 1115 void RemoveDeadNode(SDNode *N); 1116 1117 /// This method deletes the unreachable nodes in the 1118 /// given list, and any nodes that become unreachable as a result. 1119 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes); 1120 1121 /// Modify anything using 'From' to use 'To' instead. 1122 /// This can cause recursive merging of nodes in the DAG. Use the first 1123 /// version if 'From' is known to have a single result, use the second 1124 /// if you have two nodes with identical results (or if 'To' has a superset 1125 /// of the results of 'From'), use the third otherwise. 1126 /// 1127 /// These methods all take an optional UpdateListener, which (if not null) is 1128 /// informed about nodes that are deleted and modified due to recursive 1129 /// changes in the dag. 1130 /// 1131 /// These functions only replace all existing uses. It's possible that as 1132 /// these replacements are being performed, CSE may cause the From node 1133 /// to be given new uses. These new uses of From are left in place, and 1134 /// not automatically transferred to To. 1135 /// 1136 void ReplaceAllUsesWith(SDValue From, SDValue Op); 1137 void ReplaceAllUsesWith(SDNode *From, SDNode *To); 1138 void ReplaceAllUsesWith(SDNode *From, const SDValue *To); 1139 1140 /// Replace any uses of From with To, leaving 1141 /// uses of other values produced by From.Val alone. 1142 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To); 1143 1144 /// Like ReplaceAllUsesOfValueWith, but for multiple values at once. 1145 /// This correctly handles the case where 1146 /// there is an overlap between the From values and the To values. 1147 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, 1148 unsigned Num); 1149 1150 /// Topological-sort the AllNodes list and a 1151 /// assign a unique node id for each node in the DAG based on their 1152 /// topological order. Returns the number of nodes. 1153 unsigned AssignTopologicalOrder(); 1154 1155 /// Move node N in the AllNodes list to be immediately 1156 /// before the given iterator Position. This may be used to update the 1157 /// topological ordering when the list of nodes is modified. 1158 void RepositionNode(allnodes_iterator Position, SDNode *N) { 1159 AllNodes.insert(Position, AllNodes.remove(N)); 1160 } 1161 1162 /// Returns true if the opcode is a commutative binary operation. 1163 static bool isCommutativeBinOp(unsigned Opcode) { 1164 // FIXME: This should get its info from the td file, so that we can include 1165 // target info. 1166 switch (Opcode) { 1167 case ISD::ADD: 1168 case ISD::SMIN: 1169 case ISD::SMAX: 1170 case ISD::UMIN: 1171 case ISD::UMAX: 1172 case ISD::MUL: 1173 case ISD::MULHU: 1174 case ISD::MULHS: 1175 case ISD::SMUL_LOHI: 1176 case ISD::UMUL_LOHI: 1177 case ISD::FADD: 1178 case ISD::FMUL: 1179 case ISD::AND: 1180 case ISD::OR: 1181 case ISD::XOR: 1182 case ISD::SADDO: 1183 case ISD::UADDO: 1184 case ISD::ADDC: 1185 case ISD::ADDE: 1186 case ISD::FMINNUM: 1187 case ISD::FMAXNUM: 1188 case ISD::FMINNAN: 1189 case ISD::FMAXNAN: 1190 return true; 1191 default: return false; 1192 } 1193 } 1194 1195 /// Returns an APFloat semantics tag appropriate for the given type. If VT is 1196 /// a vector type, the element semantics are returned. 1197 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) { 1198 switch (VT.getScalarType().getSimpleVT().SimpleTy) { 1199 default: llvm_unreachable("Unknown FP format"); 1200 case MVT::f16: return APFloat::IEEEhalf; 1201 case MVT::f32: return APFloat::IEEEsingle; 1202 case MVT::f64: return APFloat::IEEEdouble; 1203 case MVT::f80: return APFloat::x87DoubleExtended; 1204 case MVT::f128: return APFloat::IEEEquad; 1205 case MVT::ppcf128: return APFloat::PPCDoubleDouble; 1206 } 1207 } 1208 1209 /// Add a dbg_value SDNode. If SD is non-null that means the 1210 /// value is produced by SD. 1211 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter); 1212 1213 /// Get the debug values which reference the given SDNode. 1214 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) { 1215 return DbgInfo->getSDDbgValues(SD); 1216 } 1217 1218 private: 1219 /// Transfer SDDbgValues. Called via ReplaceAllUses{OfValue}?With 1220 void TransferDbgValues(SDValue From, SDValue To); 1221 1222 public: 1223 /// Return true if there are any SDDbgValue nodes associated 1224 /// with this SelectionDAG. 1225 bool hasDebugValues() const { return !DbgInfo->empty(); } 1226 1227 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); } 1228 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); } 1229 SDDbgInfo::DbgIterator ByvalParmDbgBegin() { 1230 return DbgInfo->ByvalParmDbgBegin(); 1231 } 1232 SDDbgInfo::DbgIterator ByvalParmDbgEnd() { 1233 return DbgInfo->ByvalParmDbgEnd(); 1234 } 1235 1236 void dump() const; 1237 1238 /// Create a stack temporary, suitable for holding the specified value type. 1239 /// If minAlign is specified, the slot size will have at least that alignment. 1240 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1); 1241 1242 /// Create a stack temporary suitable for holding either of the specified 1243 /// value types. 1244 SDValue CreateStackTemporary(EVT VT1, EVT VT2); 1245 1246 SDValue FoldSymbolOffset(unsigned Opcode, EVT VT, 1247 const GlobalAddressSDNode *GA, 1248 const SDNode *N2); 1249 1250 SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT, 1251 SDNode *Cst1, SDNode *Cst2); 1252 1253 SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT, 1254 const ConstantSDNode *Cst1, 1255 const ConstantSDNode *Cst2); 1256 1257 SDValue FoldConstantVectorArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT, 1258 ArrayRef<SDValue> Ops, 1259 const SDNodeFlags *Flags = nullptr); 1260 1261 /// Constant fold a setcc to true or false. 1262 SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond, 1263 const SDLoc &dl); 1264 1265 /// Return true if the sign bit of Op is known to be zero. 1266 /// We use this predicate to simplify operations downstream. 1267 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const; 1268 1269 /// Return true if 'Op & Mask' is known to be zero. We 1270 /// use this predicate to simplify operations downstream. Op and Mask are 1271 /// known to be the same type. 1272 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0) 1273 const; 1274 1275 /// Determine which bits of Op are known to be either zero or one and return 1276 /// them in the KnownZero/KnownOne bitsets. Targets can implement the 1277 /// computeKnownBitsForTargetNode method in the TargetLowering class to allow 1278 /// target nodes to be understood. 1279 void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne, 1280 unsigned Depth = 0) const; 1281 1282 /// Test if the given value is known to have exactly one bit set. This differs 1283 /// from computeKnownBits in that it doesn't necessarily determine which bit 1284 /// is set. 1285 bool isKnownToBeAPowerOfTwo(SDValue Val) const; 1286 1287 /// Return the number of times the sign bit of the register is replicated into 1288 /// the other bits. We know that at least 1 bit is always equal to the sign 1289 /// bit (itself), but other cases can give us information. For example, 1290 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal 1291 /// to each other, so we return 3. Targets can implement the 1292 /// ComputeNumSignBitsForTarget method in the TargetLowering class to allow 1293 /// target nodes to be understood. 1294 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; 1295 1296 /// Return true if the specified operand is an ISD::ADD with a ConstantSDNode 1297 /// on the right-hand side, or if it is an ISD::OR with a ConstantSDNode that 1298 /// is guaranteed to have the same semantics as an ADD. This handles the 1299 /// equivalence: 1300 /// X|Cst == X+Cst iff X&Cst = 0. 1301 bool isBaseWithConstantOffset(SDValue Op) const; 1302 1303 /// Test whether the given SDValue is known to never be NaN. 1304 bool isKnownNeverNaN(SDValue Op) const; 1305 1306 /// Test whether the given SDValue is known to never be positive or negative 1307 /// zero. 1308 bool isKnownNeverZero(SDValue Op) const; 1309 1310 /// Test whether two SDValues are known to compare equal. This 1311 /// is true if they are the same value, or if one is negative zero and the 1312 /// other positive zero. 1313 bool isEqualTo(SDValue A, SDValue B) const; 1314 1315 /// Return true if A and B have no common bits set. As an example, this can 1316 /// allow an 'add' to be transformed into an 'or'. 1317 bool haveNoCommonBitsSet(SDValue A, SDValue B) const; 1318 1319 /// Utility function used by legalize and lowering to 1320 /// "unroll" a vector operation by splitting out the scalars and operating 1321 /// on each element individually. If the ResNE is 0, fully unroll the vector 1322 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE. 1323 /// If the ResNE is greater than the width of the vector op, unroll the 1324 /// vector op and fill the end of the resulting vector with UNDEFS. 1325 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0); 1326 1327 /// Return true if loads are next to each other and can be 1328 /// merged. Check that both are nonvolatile and if LD is loading 1329 /// 'Bytes' bytes from a location that is 'Dist' units away from the 1330 /// location that the 'Base' load is loading from. 1331 bool areNonVolatileConsecutiveLoads(LoadSDNode *LD, LoadSDNode *Base, 1332 unsigned Bytes, int Dist) const; 1333 1334 /// Infer alignment of a load / store address. Return 0 if 1335 /// it cannot be inferred. 1336 unsigned InferPtrAlignment(SDValue Ptr) const; 1337 1338 /// Compute the VTs needed for the low/hi parts of a type 1339 /// which is split (or expanded) into two not necessarily identical pieces. 1340 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const; 1341 1342 /// Split the vector with EXTRACT_SUBVECTOR using the provides 1343 /// VTs and return the low/high part. 1344 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL, 1345 const EVT &LoVT, const EVT &HiVT); 1346 1347 /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part. 1348 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) { 1349 EVT LoVT, HiVT; 1350 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType()); 1351 return SplitVector(N, DL, LoVT, HiVT); 1352 } 1353 1354 /// Split the node's operand with EXTRACT_SUBVECTOR and 1355 /// return the low/high part. 1356 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo) 1357 { 1358 return SplitVector(N->getOperand(OpNo), SDLoc(N)); 1359 } 1360 1361 /// Append the extracted elements from Start to Count out of the vector Op 1362 /// in Args. If Count is 0, all of the elements will be extracted. 1363 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args, 1364 unsigned Start = 0, unsigned Count = 0); 1365 1366 /// Compute the default alignment value for the given type. 1367 unsigned getEVTAlignment(EVT MemoryVT) const; 1368 1369 /// Test whether the given value is a constant int or similar node. 1370 SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N); 1371 1372 private: 1373 void InsertNode(SDNode *N); 1374 bool RemoveNodeFromCSEMaps(SDNode *N); 1375 void AddModifiedNodeToCSEMaps(SDNode *N); 1376 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); 1377 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, 1378 void *&InsertPos); 1379 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops, 1380 void *&InsertPos); 1381 SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, const SDLoc &loc); 1382 1383 void DeleteNodeNotInCSEMaps(SDNode *N); 1384 void DeallocateNode(SDNode *N); 1385 1386 void allnodes_clear(); 1387 1388 SDNode *GetBinarySDNode(unsigned Opcode, const SDLoc &DL, SDVTList VTs, 1389 SDValue N1, SDValue N2, 1390 const SDNodeFlags *Flags = nullptr); 1391 1392 /// Look up the node specified by ID in CSEMap. If it exists, return it. If 1393 /// not, return the insertion token that will make insertion faster. This 1394 /// overload is for nodes other than Constant or ConstantFP, use the other one 1395 /// for those. 1396 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos); 1397 1398 /// Look up the node specified by ID in CSEMap. If it exists, return it. If 1399 /// not, return the insertion token that will make insertion faster. Performs 1400 /// additional processing for constant nodes. 1401 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, const SDLoc &DL, 1402 void *&InsertPos); 1403 1404 /// List of non-single value types. 1405 FoldingSet<SDVTListNode> VTListMap; 1406 1407 /// Maps to auto-CSE operations. 1408 std::vector<CondCodeSDNode*> CondCodeNodes; 1409 1410 std::vector<SDNode*> ValueTypeNodes; 1411 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes; 1412 StringMap<SDNode*> ExternalSymbols; 1413 1414 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols; 1415 DenseMap<MCSymbol *, SDNode *> MCSymbols; 1416 }; 1417 1418 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 1419 typedef SelectionDAG::allnodes_iterator nodes_iterator; 1420 static nodes_iterator nodes_begin(SelectionDAG *G) { 1421 return G->allnodes_begin(); 1422 } 1423 static nodes_iterator nodes_end(SelectionDAG *G) { 1424 return G->allnodes_end(); 1425 } 1426 }; 1427 1428 } // end namespace llvm 1429 1430 #endif 1431