1 //===- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ----------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file declares the SelectionDAG class, and transitively defines the 10 // SDNode class and subclasses. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CODEGEN_SELECTIONDAG_H 15 #define LLVM_CODEGEN_SELECTIONDAG_H 16 17 #include "llvm/ADT/APFloat.h" 18 #include "llvm/ADT/APInt.h" 19 #include "llvm/ADT/ArrayRef.h" 20 #include "llvm/ADT/DenseMap.h" 21 #include "llvm/ADT/DenseSet.h" 22 #include "llvm/ADT/FoldingSet.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/ADT/StringMap.h" 25 #include "llvm/ADT/ilist.h" 26 #include "llvm/ADT/iterator.h" 27 #include "llvm/ADT/iterator_range.h" 28 #include "llvm/CodeGen/DAGCombine.h" 29 #include "llvm/CodeGen/ISDOpcodes.h" 30 #include "llvm/CodeGen/MachineFunction.h" 31 #include "llvm/CodeGen/MachineMemOperand.h" 32 #include "llvm/CodeGen/SelectionDAGNodes.h" 33 #include "llvm/CodeGen/ValueTypes.h" 34 #include "llvm/IR/DebugLoc.h" 35 #include "llvm/IR/Metadata.h" 36 #include "llvm/Support/Allocator.h" 37 #include "llvm/Support/ArrayRecycler.h" 38 #include "llvm/Support/CodeGen.h" 39 #include "llvm/Support/ErrorHandling.h" 40 #include "llvm/Support/MachineValueType.h" 41 #include "llvm/Support/RecyclingAllocator.h" 42 #include <cassert> 43 #include <cstdint> 44 #include <functional> 45 #include <map> 46 #include <string> 47 #include <tuple> 48 #include <utility> 49 #include <vector> 50 51 namespace llvm { 52 53 class DIExpression; 54 class DILabel; 55 class DIVariable; 56 class Function; 57 class Pass; 58 class Type; 59 template <class GraphType> struct GraphTraits; 60 template <typename T, unsigned int N> class SmallSetVector; 61 template <typename T, typename Enable> struct FoldingSetTrait; 62 class AAResults; 63 class BlockAddress; 64 class BlockFrequencyInfo; 65 class Constant; 66 class ConstantFP; 67 class ConstantInt; 68 class DataLayout; 69 struct fltSemantics; 70 class FunctionLoweringInfo; 71 class GlobalValue; 72 struct KnownBits; 73 class LegacyDivergenceAnalysis; 74 class LLVMContext; 75 class MachineBasicBlock; 76 class MachineConstantPoolValue; 77 class MCSymbol; 78 class OptimizationRemarkEmitter; 79 class ProfileSummaryInfo; 80 class SDDbgValue; 81 class SDDbgOperand; 82 class SDDbgLabel; 83 class SelectionDAG; 84 class SelectionDAGTargetInfo; 85 class TargetLibraryInfo; 86 class TargetLowering; 87 class TargetMachine; 88 class TargetSubtargetInfo; 89 class Value; 90 91 class SDVTListNode : public FoldingSetNode { 92 friend struct FoldingSetTrait<SDVTListNode>; 93 94 /// A reference to an Interned FoldingSetNodeID for this node. 95 /// The Allocator in SelectionDAG holds the data. 96 /// SDVTList contains all types which are frequently accessed in SelectionDAG. 97 /// The size of this list is not expected to be big so it won't introduce 98 /// a memory penalty. 99 FoldingSetNodeIDRef FastID; 100 const EVT *VTs; 101 unsigned int NumVTs; 102 /// The hash value for SDVTList is fixed, so cache it to avoid 103 /// hash calculation. 104 unsigned HashValue; 105 106 public: 107 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) : 108 FastID(ID), VTs(VT), NumVTs(Num) { 109 HashValue = ID.ComputeHash(); 110 } 111 112 SDVTList getSDVTList() { 113 SDVTList result = {VTs, NumVTs}; 114 return result; 115 } 116 }; 117 118 /// Specialize FoldingSetTrait for SDVTListNode 119 /// to avoid computing temp FoldingSetNodeID and hash value. 120 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> { 121 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) { 122 ID = X.FastID; 123 } 124 125 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID, 126 unsigned IDHash, FoldingSetNodeID &TempID) { 127 if (X.HashValue != IDHash) 128 return false; 129 return ID == X.FastID; 130 } 131 132 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) { 133 return X.HashValue; 134 } 135 }; 136 137 template <> struct ilist_alloc_traits<SDNode> { 138 static void deleteNode(SDNode *) { 139 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!"); 140 } 141 }; 142 143 /// Keeps track of dbg_value information through SDISel. We do 144 /// not build SDNodes for these so as not to perturb the generated code; 145 /// instead the info is kept off to the side in this structure. Each SDNode may 146 /// have one or more associated dbg_value entries. This information is kept in 147 /// DbgValMap. 148 /// Byval parameters are handled separately because they don't use alloca's, 149 /// which busts the normal mechanism. There is good reason for handling all 150 /// parameters separately: they may not have code generated for them, they 151 /// should always go at the beginning of the function regardless of other code 152 /// motion, and debug info for them is potentially useful even if the parameter 153 /// is unused. Right now only byval parameters are handled separately. 154 class SDDbgInfo { 155 BumpPtrAllocator Alloc; 156 SmallVector<SDDbgValue*, 32> DbgValues; 157 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues; 158 SmallVector<SDDbgLabel*, 4> DbgLabels; 159 using DbgValMapType = DenseMap<const SDNode *, SmallVector<SDDbgValue *, 2>>; 160 DbgValMapType DbgValMap; 161 162 public: 163 SDDbgInfo() = default; 164 SDDbgInfo(const SDDbgInfo &) = delete; 165 SDDbgInfo &operator=(const SDDbgInfo &) = delete; 166 167 void add(SDDbgValue *V, bool isParameter); 168 169 void add(SDDbgLabel *L) { DbgLabels.push_back(L); } 170 171 /// Invalidate all DbgValues attached to the node and remove 172 /// it from the Node-to-DbgValues map. 173 void erase(const SDNode *Node); 174 175 void clear() { 176 DbgValMap.clear(); 177 DbgValues.clear(); 178 ByvalParmDbgValues.clear(); 179 DbgLabels.clear(); 180 Alloc.Reset(); 181 } 182 183 BumpPtrAllocator &getAlloc() { return Alloc; } 184 185 bool empty() const { 186 return DbgValues.empty() && ByvalParmDbgValues.empty() && DbgLabels.empty(); 187 } 188 189 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) const { 190 auto I = DbgValMap.find(Node); 191 if (I != DbgValMap.end()) 192 return I->second; 193 return ArrayRef<SDDbgValue*>(); 194 } 195 196 using DbgIterator = SmallVectorImpl<SDDbgValue*>::iterator; 197 using DbgLabelIterator = SmallVectorImpl<SDDbgLabel*>::iterator; 198 199 DbgIterator DbgBegin() { return DbgValues.begin(); } 200 DbgIterator DbgEnd() { return DbgValues.end(); } 201 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); } 202 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); } 203 DbgLabelIterator DbgLabelBegin() { return DbgLabels.begin(); } 204 DbgLabelIterator DbgLabelEnd() { return DbgLabels.end(); } 205 }; 206 207 void checkForCycles(const SelectionDAG *DAG, bool force = false); 208 209 /// This is used to represent a portion of an LLVM function in a low-level 210 /// Data Dependence DAG representation suitable for instruction selection. 211 /// This DAG is constructed as the first step of instruction selection in order 212 /// to allow implementation of machine specific optimizations 213 /// and code simplifications. 214 /// 215 /// The representation used by the SelectionDAG is a target-independent 216 /// representation, which has some similarities to the GCC RTL representation, 217 /// but is significantly more simple, powerful, and is a graph form instead of a 218 /// linear form. 219 /// 220 class SelectionDAG { 221 const TargetMachine &TM; 222 const SelectionDAGTargetInfo *TSI = nullptr; 223 const TargetLowering *TLI = nullptr; 224 const TargetLibraryInfo *LibInfo = nullptr; 225 MachineFunction *MF; 226 Pass *SDAGISelPass = nullptr; 227 LLVMContext *Context; 228 CodeGenOpt::Level OptLevel; 229 230 LegacyDivergenceAnalysis * DA = nullptr; 231 FunctionLoweringInfo * FLI = nullptr; 232 233 /// The function-level optimization remark emitter. Used to emit remarks 234 /// whenever manipulating the DAG. 235 OptimizationRemarkEmitter *ORE; 236 237 ProfileSummaryInfo *PSI = nullptr; 238 BlockFrequencyInfo *BFI = nullptr; 239 240 /// The starting token. 241 SDNode EntryNode; 242 243 /// The root of the entire DAG. 244 SDValue Root; 245 246 /// A linked list of nodes in the current DAG. 247 ilist<SDNode> AllNodes; 248 249 /// The AllocatorType for allocating SDNodes. We use 250 /// pool allocation with recycling. 251 using NodeAllocatorType = RecyclingAllocator<BumpPtrAllocator, SDNode, 252 sizeof(LargestSDNode), 253 alignof(MostAlignedSDNode)>; 254 255 /// Pool allocation for nodes. 256 NodeAllocatorType NodeAllocator; 257 258 /// This structure is used to memoize nodes, automatically performing 259 /// CSE with existing nodes when a duplicate is requested. 260 FoldingSet<SDNode> CSEMap; 261 262 /// Pool allocation for machine-opcode SDNode operands. 263 BumpPtrAllocator OperandAllocator; 264 ArrayRecycler<SDUse> OperandRecycler; 265 266 /// Pool allocation for misc. objects that are created once per SelectionDAG. 267 BumpPtrAllocator Allocator; 268 269 /// Tracks dbg_value and dbg_label information through SDISel. 270 SDDbgInfo *DbgInfo; 271 272 using CallSiteInfo = MachineFunction::CallSiteInfo; 273 using CallSiteInfoImpl = MachineFunction::CallSiteInfoImpl; 274 275 struct CallSiteDbgInfo { 276 CallSiteInfo CSInfo; 277 MDNode *HeapAllocSite = nullptr; 278 bool NoMerge = false; 279 }; 280 281 DenseMap<const SDNode *, CallSiteDbgInfo> SDCallSiteDbgInfo; 282 283 /// PersistentId counter to be used when inserting the next 284 /// SDNode to this SelectionDAG. We do not place that under 285 /// `#if LLVM_ENABLE_ABI_BREAKING_CHECKS` intentionally because 286 /// it adds unneeded complexity without noticeable 287 /// benefits (see discussion with @thakis in D120714). 288 uint16_t NextPersistentId = 0; 289 290 /// Are instruction referencing variable locations desired for this function? 291 bool UseInstrRefDebugInfo = false; 292 293 public: 294 /// Clients of various APIs that cause global effects on 295 /// the DAG can optionally implement this interface. This allows the clients 296 /// to handle the various sorts of updates that happen. 297 /// 298 /// A DAGUpdateListener automatically registers itself with DAG when it is 299 /// constructed, and removes itself when destroyed in RAII fashion. 300 struct DAGUpdateListener { 301 DAGUpdateListener *const Next; 302 SelectionDAG &DAG; 303 304 explicit DAGUpdateListener(SelectionDAG &D) 305 : Next(D.UpdateListeners), DAG(D) { 306 DAG.UpdateListeners = this; 307 } 308 309 virtual ~DAGUpdateListener() { 310 assert(DAG.UpdateListeners == this && 311 "DAGUpdateListeners must be destroyed in LIFO order"); 312 DAG.UpdateListeners = Next; 313 } 314 315 /// The node N that was deleted and, if E is not null, an 316 /// equivalent node E that replaced it. 317 virtual void NodeDeleted(SDNode *N, SDNode *E); 318 319 /// The node N that was updated. 320 virtual void NodeUpdated(SDNode *N); 321 322 /// The node N that was inserted. 323 virtual void NodeInserted(SDNode *N); 324 }; 325 326 struct DAGNodeDeletedListener : public DAGUpdateListener { 327 std::function<void(SDNode *, SDNode *)> Callback; 328 329 DAGNodeDeletedListener(SelectionDAG &DAG, 330 std::function<void(SDNode *, SDNode *)> Callback) 331 : DAGUpdateListener(DAG), Callback(std::move(Callback)) {} 332 333 void NodeDeleted(SDNode *N, SDNode *E) override { Callback(N, E); } 334 335 private: 336 virtual void anchor(); 337 }; 338 339 /// Help to insert SDNodeFlags automatically in transforming. Use 340 /// RAII to save and resume flags in current scope. 341 class FlagInserter { 342 SelectionDAG &DAG; 343 SDNodeFlags Flags; 344 FlagInserter *LastInserter; 345 346 public: 347 FlagInserter(SelectionDAG &SDAG, SDNodeFlags Flags) 348 : DAG(SDAG), Flags(Flags), 349 LastInserter(SDAG.getFlagInserter()) { 350 SDAG.setFlagInserter(this); 351 } 352 FlagInserter(SelectionDAG &SDAG, SDNode *N) 353 : FlagInserter(SDAG, N->getFlags()) {} 354 355 FlagInserter(const FlagInserter &) = delete; 356 FlagInserter &operator=(const FlagInserter &) = delete; 357 ~FlagInserter() { DAG.setFlagInserter(LastInserter); } 358 359 SDNodeFlags getFlags() const { return Flags; } 360 }; 361 362 /// When true, additional steps are taken to 363 /// ensure that getConstant() and similar functions return DAG nodes that 364 /// have legal types. This is important after type legalization since 365 /// any illegally typed nodes generated after this point will not experience 366 /// type legalization. 367 bool NewNodesMustHaveLegalTypes = false; 368 369 private: 370 /// DAGUpdateListener is a friend so it can manipulate the listener stack. 371 friend struct DAGUpdateListener; 372 373 /// Linked list of registered DAGUpdateListener instances. 374 /// This stack is maintained by DAGUpdateListener RAII. 375 DAGUpdateListener *UpdateListeners = nullptr; 376 377 /// Implementation of setSubgraphColor. 378 /// Return whether we had to truncate the search. 379 bool setSubgraphColorHelper(SDNode *N, const char *Color, 380 DenseSet<SDNode *> &visited, 381 int level, bool &printed); 382 383 template <typename SDNodeT, typename... ArgTypes> 384 SDNodeT *newSDNode(ArgTypes &&... Args) { 385 return new (NodeAllocator.template Allocate<SDNodeT>()) 386 SDNodeT(std::forward<ArgTypes>(Args)...); 387 } 388 389 /// Build a synthetic SDNodeT with the given args and extract its subclass 390 /// data as an integer (e.g. for use in a folding set). 391 /// 392 /// The args to this function are the same as the args to SDNodeT's 393 /// constructor, except the second arg (assumed to be a const DebugLoc&) is 394 /// omitted. 395 template <typename SDNodeT, typename... ArgTypes> 396 static uint16_t getSyntheticNodeSubclassData(unsigned IROrder, 397 ArgTypes &&... Args) { 398 // The compiler can reduce this expression to a constant iff we pass an 399 // empty DebugLoc. Thankfully, the debug location doesn't have any bearing 400 // on the subclass data. 401 return SDNodeT(IROrder, DebugLoc(), std::forward<ArgTypes>(Args)...) 402 .getRawSubclassData(); 403 } 404 405 template <typename SDNodeTy> 406 static uint16_t getSyntheticNodeSubclassData(unsigned Opc, unsigned Order, 407 SDVTList VTs, EVT MemoryVT, 408 MachineMemOperand *MMO) { 409 return SDNodeTy(Opc, Order, DebugLoc(), VTs, MemoryVT, MMO) 410 .getRawSubclassData(); 411 } 412 413 void createOperands(SDNode *Node, ArrayRef<SDValue> Vals); 414 415 void removeOperands(SDNode *Node) { 416 if (!Node->OperandList) 417 return; 418 OperandRecycler.deallocate( 419 ArrayRecycler<SDUse>::Capacity::get(Node->NumOperands), 420 Node->OperandList); 421 Node->NumOperands = 0; 422 Node->OperandList = nullptr; 423 } 424 void CreateTopologicalOrder(std::vector<SDNode*>& Order); 425 426 public: 427 // Maximum depth for recursive analysis such as computeKnownBits, etc. 428 static constexpr unsigned MaxRecursionDepth = 6; 429 430 explicit SelectionDAG(const TargetMachine &TM, CodeGenOpt::Level); 431 SelectionDAG(const SelectionDAG &) = delete; 432 SelectionDAG &operator=(const SelectionDAG &) = delete; 433 ~SelectionDAG(); 434 435 /// Prepare this SelectionDAG to process code in the given MachineFunction. 436 void init(MachineFunction &NewMF, OptimizationRemarkEmitter &NewORE, 437 Pass *PassPtr, const TargetLibraryInfo *LibraryInfo, 438 LegacyDivergenceAnalysis * Divergence, 439 ProfileSummaryInfo *PSIin, BlockFrequencyInfo *BFIin); 440 441 void setFunctionLoweringInfo(FunctionLoweringInfo * FuncInfo) { 442 FLI = FuncInfo; 443 } 444 445 /// Clear state and free memory necessary to make this 446 /// SelectionDAG ready to process a new block. 447 void clear(); 448 449 MachineFunction &getMachineFunction() const { return *MF; } 450 const Pass *getPass() const { return SDAGISelPass; } 451 452 const DataLayout &getDataLayout() const { return MF->getDataLayout(); } 453 const TargetMachine &getTarget() const { return TM; } 454 const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); } 455 template <typename STC> const STC &getSubtarget() const { 456 return MF->getSubtarget<STC>(); 457 } 458 const TargetLowering &getTargetLoweringInfo() const { return *TLI; } 459 const TargetLibraryInfo &getLibInfo() const { return *LibInfo; } 460 const SelectionDAGTargetInfo &getSelectionDAGInfo() const { return *TSI; } 461 const LegacyDivergenceAnalysis *getDivergenceAnalysis() const { return DA; } 462 LLVMContext *getContext() const { return Context; } 463 OptimizationRemarkEmitter &getORE() const { return *ORE; } 464 ProfileSummaryInfo *getPSI() const { return PSI; } 465 BlockFrequencyInfo *getBFI() const { return BFI; } 466 467 FlagInserter *getFlagInserter() { return Inserter; } 468 void setFlagInserter(FlagInserter *FI) { Inserter = FI; } 469 470 /// Just dump dot graph to a user-provided path and title. 471 /// This doesn't open the dot viewer program and 472 /// helps visualization when outside debugging session. 473 /// FileName expects absolute path. If provided 474 /// without any path separators then the file 475 /// will be created in the current directory. 476 /// Error will be emitted if the path is insane. 477 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 478 LLVM_DUMP_METHOD void dumpDotGraph(const Twine &FileName, const Twine &Title); 479 #endif 480 481 /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 482 void viewGraph(const std::string &Title); 483 void viewGraph(); 484 485 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 486 std::map<const SDNode *, std::string> NodeGraphAttrs; 487 #endif 488 489 /// Clear all previously defined node graph attributes. 490 /// Intended to be used from a debugging tool (eg. gdb). 491 void clearGraphAttrs(); 492 493 /// Set graph attributes for a node. (eg. "color=red".) 494 void setGraphAttrs(const SDNode *N, const char *Attrs); 495 496 /// Get graph attributes for a node. (eg. "color=red".) 497 /// Used from getNodeAttributes. 498 std::string getGraphAttrs(const SDNode *N) const; 499 500 /// Convenience for setting node color attribute. 501 void setGraphColor(const SDNode *N, const char *Color); 502 503 /// Convenience for setting subgraph color attribute. 504 void setSubgraphColor(SDNode *N, const char *Color); 505 506 using allnodes_const_iterator = ilist<SDNode>::const_iterator; 507 508 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 509 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 510 511 using allnodes_iterator = ilist<SDNode>::iterator; 512 513 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 514 allnodes_iterator allnodes_end() { return AllNodes.end(); } 515 516 ilist<SDNode>::size_type allnodes_size() const { 517 return AllNodes.size(); 518 } 519 520 iterator_range<allnodes_iterator> allnodes() { 521 return make_range(allnodes_begin(), allnodes_end()); 522 } 523 iterator_range<allnodes_const_iterator> allnodes() const { 524 return make_range(allnodes_begin(), allnodes_end()); 525 } 526 527 /// Return the root tag of the SelectionDAG. 528 const SDValue &getRoot() const { return Root; } 529 530 /// Return the token chain corresponding to the entry of the function. 531 SDValue getEntryNode() const { 532 return SDValue(const_cast<SDNode *>(&EntryNode), 0); 533 } 534 535 /// Set the current root tag of the SelectionDAG. 536 /// 537 const SDValue &setRoot(SDValue N) { 538 assert((!N.getNode() || N.getValueType() == MVT::Other) && 539 "DAG root value is not a chain!"); 540 if (N.getNode()) 541 checkForCycles(N.getNode(), this); 542 Root = N; 543 if (N.getNode()) 544 checkForCycles(this); 545 return Root; 546 } 547 548 #ifndef NDEBUG 549 void VerifyDAGDivergence(); 550 #endif 551 552 /// This iterates over the nodes in the SelectionDAG, folding 553 /// certain types of nodes together, or eliminating superfluous nodes. The 554 /// Level argument controls whether Combine is allowed to produce nodes and 555 /// types that are illegal on the target. 556 void Combine(CombineLevel Level, AAResults *AA, 557 CodeGenOpt::Level OptLevel); 558 559 /// This transforms the SelectionDAG into a SelectionDAG that 560 /// only uses types natively supported by the target. 561 /// Returns "true" if it made any changes. 562 /// 563 /// Note that this is an involved process that may invalidate pointers into 564 /// the graph. 565 bool LegalizeTypes(); 566 567 /// This transforms the SelectionDAG into a SelectionDAG that is 568 /// compatible with the target instruction selector, as indicated by the 569 /// TargetLowering object. 570 /// 571 /// Note that this is an involved process that may invalidate pointers into 572 /// the graph. 573 void Legalize(); 574 575 /// Transforms a SelectionDAG node and any operands to it into a node 576 /// that is compatible with the target instruction selector, as indicated by 577 /// the TargetLowering object. 578 /// 579 /// \returns true if \c N is a valid, legal node after calling this. 580 /// 581 /// This essentially runs a single recursive walk of the \c Legalize process 582 /// over the given node (and its operands). This can be used to incrementally 583 /// legalize the DAG. All of the nodes which are directly replaced, 584 /// potentially including N, are added to the output parameter \c 585 /// UpdatedNodes so that the delta to the DAG can be understood by the 586 /// caller. 587 /// 588 /// When this returns false, N has been legalized in a way that make the 589 /// pointer passed in no longer valid. It may have even been deleted from the 590 /// DAG, and so it shouldn't be used further. When this returns true, the 591 /// N passed in is a legal node, and can be immediately processed as such. 592 /// This may still have done some work on the DAG, and will still populate 593 /// UpdatedNodes with any new nodes replacing those originally in the DAG. 594 bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes); 595 596 /// This transforms the SelectionDAG into a SelectionDAG 597 /// that only uses vector math operations supported by the target. This is 598 /// necessary as a separate step from Legalize because unrolling a vector 599 /// operation can introduce illegal types, which requires running 600 /// LegalizeTypes again. 601 /// 602 /// This returns true if it made any changes; in that case, LegalizeTypes 603 /// is called again before Legalize. 604 /// 605 /// Note that this is an involved process that may invalidate pointers into 606 /// the graph. 607 bool LegalizeVectors(); 608 609 /// This method deletes all unreachable nodes in the SelectionDAG. 610 void RemoveDeadNodes(); 611 612 /// Remove the specified node from the system. This node must 613 /// have no referrers. 614 void DeleteNode(SDNode *N); 615 616 /// Return an SDVTList that represents the list of values specified. 617 SDVTList getVTList(EVT VT); 618 SDVTList getVTList(EVT VT1, EVT VT2); 619 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3); 620 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4); 621 SDVTList getVTList(ArrayRef<EVT> VTs); 622 623 //===--------------------------------------------------------------------===// 624 // Node creation methods. 625 626 /// Create a ConstantSDNode wrapping a constant value. 627 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR. 628 /// 629 /// If only legal types can be produced, this does the necessary 630 /// transformations (e.g., if the vector element type is illegal). 631 /// @{ 632 SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT, 633 bool isTarget = false, bool isOpaque = false); 634 SDValue getConstant(const APInt &Val, const SDLoc &DL, EVT VT, 635 bool isTarget = false, bool isOpaque = false); 636 637 SDValue getAllOnesConstant(const SDLoc &DL, EVT VT, bool IsTarget = false, 638 bool IsOpaque = false) { 639 return getConstant(APInt::getAllOnes(VT.getScalarSizeInBits()), DL, VT, 640 IsTarget, IsOpaque); 641 } 642 643 SDValue getConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT, 644 bool isTarget = false, bool isOpaque = false); 645 SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL, 646 bool isTarget = false); 647 SDValue getShiftAmountConstant(uint64_t Val, EVT VT, const SDLoc &DL, 648 bool LegalTypes = true); 649 SDValue getVectorIdxConstant(uint64_t Val, const SDLoc &DL, 650 bool isTarget = false); 651 652 SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT, 653 bool isOpaque = false) { 654 return getConstant(Val, DL, VT, true, isOpaque); 655 } 656 SDValue getTargetConstant(const APInt &Val, const SDLoc &DL, EVT VT, 657 bool isOpaque = false) { 658 return getConstant(Val, DL, VT, true, isOpaque); 659 } 660 SDValue getTargetConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT, 661 bool isOpaque = false) { 662 return getConstant(Val, DL, VT, true, isOpaque); 663 } 664 665 /// Create a true or false constant of type \p VT using the target's 666 /// BooleanContent for type \p OpVT. 667 SDValue getBoolConstant(bool V, const SDLoc &DL, EVT VT, EVT OpVT); 668 /// @} 669 670 /// Create a ConstantFPSDNode wrapping a constant value. 671 /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR. 672 /// 673 /// If only legal types can be produced, this does the necessary 674 /// transformations (e.g., if the vector element type is illegal). 675 /// The forms that take a double should only be used for simple constants 676 /// that can be exactly represented in VT. No checks are made. 677 /// @{ 678 SDValue getConstantFP(double Val, const SDLoc &DL, EVT VT, 679 bool isTarget = false); 680 SDValue getConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT, 681 bool isTarget = false); 682 SDValue getConstantFP(const ConstantFP &V, const SDLoc &DL, EVT VT, 683 bool isTarget = false); 684 SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT) { 685 return getConstantFP(Val, DL, VT, true); 686 } 687 SDValue getTargetConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT) { 688 return getConstantFP(Val, DL, VT, true); 689 } 690 SDValue getTargetConstantFP(const ConstantFP &Val, const SDLoc &DL, EVT VT) { 691 return getConstantFP(Val, DL, VT, true); 692 } 693 /// @} 694 695 SDValue getGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT, 696 int64_t offset = 0, bool isTargetGA = false, 697 unsigned TargetFlags = 0); 698 SDValue getTargetGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT, 699 int64_t offset = 0, unsigned TargetFlags = 0) { 700 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags); 701 } 702 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false); 703 SDValue getTargetFrameIndex(int FI, EVT VT) { 704 return getFrameIndex(FI, VT, true); 705 } 706 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false, 707 unsigned TargetFlags = 0); 708 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned TargetFlags = 0) { 709 return getJumpTable(JTI, VT, true, TargetFlags); 710 } 711 SDValue getConstantPool(const Constant *C, EVT VT, MaybeAlign Align = None, 712 int Offs = 0, bool isT = false, 713 unsigned TargetFlags = 0); 714 SDValue getTargetConstantPool(const Constant *C, EVT VT, 715 MaybeAlign Align = None, int Offset = 0, 716 unsigned TargetFlags = 0) { 717 return getConstantPool(C, VT, Align, Offset, true, TargetFlags); 718 } 719 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT, 720 MaybeAlign Align = None, int Offs = 0, 721 bool isT = false, unsigned TargetFlags = 0); 722 SDValue getTargetConstantPool(MachineConstantPoolValue *C, EVT VT, 723 MaybeAlign Align = None, int Offset = 0, 724 unsigned TargetFlags = 0) { 725 return getConstantPool(C, VT, Align, Offset, true, TargetFlags); 726 } 727 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0, 728 unsigned TargetFlags = 0); 729 // When generating a branch to a BB, we don't in general know enough 730 // to provide debug info for the BB at that time, so keep this one around. 731 SDValue getBasicBlock(MachineBasicBlock *MBB); 732 SDValue getExternalSymbol(const char *Sym, EVT VT); 733 SDValue getTargetExternalSymbol(const char *Sym, EVT VT, 734 unsigned TargetFlags = 0); 735 SDValue getMCSymbol(MCSymbol *Sym, EVT VT); 736 737 SDValue getValueType(EVT); 738 SDValue getRegister(unsigned Reg, EVT VT); 739 SDValue getRegisterMask(const uint32_t *RegMask); 740 SDValue getEHLabel(const SDLoc &dl, SDValue Root, MCSymbol *Label); 741 SDValue getLabelNode(unsigned Opcode, const SDLoc &dl, SDValue Root, 742 MCSymbol *Label); 743 SDValue getBlockAddress(const BlockAddress *BA, EVT VT, int64_t Offset = 0, 744 bool isTarget = false, unsigned TargetFlags = 0); 745 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT, 746 int64_t Offset = 0, unsigned TargetFlags = 0) { 747 return getBlockAddress(BA, VT, Offset, true, TargetFlags); 748 } 749 750 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, 751 SDValue N) { 752 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, 753 getRegister(Reg, N.getValueType()), N); 754 } 755 756 // This version of the getCopyToReg method takes an extra operand, which 757 // indicates that there is potentially an incoming glue value (if Glue is not 758 // null) and that there should be a glue result. 759 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N, 760 SDValue Glue) { 761 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 762 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue }; 763 return getNode(ISD::CopyToReg, dl, VTs, 764 makeArrayRef(Ops, Glue.getNode() ? 4 : 3)); 765 } 766 767 // Similar to last getCopyToReg() except parameter Reg is a SDValue 768 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, SDValue Reg, SDValue N, 769 SDValue Glue) { 770 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 771 SDValue Ops[] = { Chain, Reg, N, Glue }; 772 return getNode(ISD::CopyToReg, dl, VTs, 773 makeArrayRef(Ops, Glue.getNode() ? 4 : 3)); 774 } 775 776 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT) { 777 SDVTList VTs = getVTList(VT, MVT::Other); 778 SDValue Ops[] = { Chain, getRegister(Reg, VT) }; 779 return getNode(ISD::CopyFromReg, dl, VTs, Ops); 780 } 781 782 // This version of the getCopyFromReg method takes an extra operand, which 783 // indicates that there is potentially an incoming glue value (if Glue is not 784 // null) and that there should be a glue result. 785 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT, 786 SDValue Glue) { 787 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue); 788 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue }; 789 return getNode(ISD::CopyFromReg, dl, VTs, 790 makeArrayRef(Ops, Glue.getNode() ? 3 : 2)); 791 } 792 793 SDValue getCondCode(ISD::CondCode Cond); 794 795 /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT, 796 /// which must be a vector type, must match the number of mask elements 797 /// NumElts. An integer mask element equal to -1 is treated as undefined. 798 SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2, 799 ArrayRef<int> Mask); 800 801 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT, 802 /// which must be a vector type, must match the number of operands in Ops. 803 /// The operands must have the same type as (or, for integers, a type wider 804 /// than) VT's element type. 805 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDValue> Ops) { 806 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later. 807 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops); 808 } 809 810 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT, 811 /// which must be a vector type, must match the number of operands in Ops. 812 /// The operands must have the same type as (or, for integers, a type wider 813 /// than) VT's element type. 814 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDUse> Ops) { 815 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later. 816 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops); 817 } 818 819 /// Return a splat ISD::BUILD_VECTOR node, consisting of Op splatted to all 820 /// elements. VT must be a vector type. Op's type must be the same as (or, 821 /// for integers, a type wider than) VT's element type. 822 SDValue getSplatBuildVector(EVT VT, const SDLoc &DL, SDValue Op) { 823 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later. 824 if (Op.getOpcode() == ISD::UNDEF) { 825 assert((VT.getVectorElementType() == Op.getValueType() || 826 (VT.isInteger() && 827 VT.getVectorElementType().bitsLE(Op.getValueType()))) && 828 "A splatted value must have a width equal or (for integers) " 829 "greater than the vector element type!"); 830 return getNode(ISD::UNDEF, SDLoc(), VT); 831 } 832 833 SmallVector<SDValue, 16> Ops(VT.getVectorNumElements(), Op); 834 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops); 835 } 836 837 // Return a splat ISD::SPLAT_VECTOR node, consisting of Op splatted to all 838 // elements. 839 SDValue getSplatVector(EVT VT, const SDLoc &DL, SDValue Op) { 840 if (Op.getOpcode() == ISD::UNDEF) { 841 assert((VT.getVectorElementType() == Op.getValueType() || 842 (VT.isInteger() && 843 VT.getVectorElementType().bitsLE(Op.getValueType()))) && 844 "A splatted value must have a width equal or (for integers) " 845 "greater than the vector element type!"); 846 return getNode(ISD::UNDEF, SDLoc(), VT); 847 } 848 return getNode(ISD::SPLAT_VECTOR, DL, VT, Op); 849 } 850 851 /// Returns a vector of type ResVT whose elements contain the linear sequence 852 /// <0, Step, Step * 2, Step * 3, ...> 853 SDValue getStepVector(const SDLoc &DL, EVT ResVT, APInt StepVal); 854 855 /// Returns a vector of type ResVT whose elements contain the linear sequence 856 /// <0, 1, 2, 3, ...> 857 SDValue getStepVector(const SDLoc &DL, EVT ResVT); 858 859 /// Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to 860 /// the shuffle node in input but with swapped operands. 861 /// 862 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3> 863 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV); 864 865 /// Convert Op, which must be of float type, to the 866 /// float type VT, by either extending or rounding (by truncation). 867 SDValue getFPExtendOrRound(SDValue Op, const SDLoc &DL, EVT VT); 868 869 /// Convert Op, which must be a STRICT operation of float type, to the 870 /// float type VT, by either extending or rounding (by truncation). 871 std::pair<SDValue, SDValue> 872 getStrictFPExtendOrRound(SDValue Op, SDValue Chain, const SDLoc &DL, EVT VT); 873 874 /// Convert Op, which must be of integer type, to the 875 /// integer type VT, by either any-extending or truncating it. 876 SDValue getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 877 878 /// Convert Op, which must be of integer type, to the 879 /// integer type VT, by either sign-extending or truncating it. 880 SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 881 882 /// Convert Op, which must be of integer type, to the 883 /// integer type VT, by either zero-extending or truncating it. 884 SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 885 886 /// Return the expression required to zero extend the Op 887 /// value assuming it was the smaller SrcTy value. 888 SDValue getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT VT); 889 890 /// Convert Op, which must be of integer type, to the integer type VT, by 891 /// either truncating it or performing either zero or sign extension as 892 /// appropriate extension for the pointer's semantics. 893 SDValue getPtrExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 894 895 /// Return the expression required to extend the Op as a pointer value 896 /// assuming it was the smaller SrcTy value. This may be either a zero extend 897 /// or a sign extend. 898 SDValue getPtrExtendInReg(SDValue Op, const SDLoc &DL, EVT VT); 899 900 /// Convert Op, which must be of integer type, to the integer type VT, 901 /// by using an extension appropriate for the target's 902 /// BooleanContent for type OpVT or truncating it. 903 SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT); 904 905 /// Create a bitwise NOT operation as (XOR Val, -1). 906 SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT); 907 908 /// Create a logical NOT operation as (XOR Val, BooleanOne). 909 SDValue getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT); 910 911 /// Create a vector-predicated logical NOT operation as (VP_XOR Val, 912 /// BooleanOne, Mask, EVL). 913 SDValue getVPLogicalNOT(const SDLoc &DL, SDValue Val, SDValue Mask, 914 SDValue EVL, EVT VT); 915 916 /// Returns sum of the base pointer and offset. 917 /// Unlike getObjectPtrOffset this does not set NoUnsignedWrap by default. 918 SDValue getMemBasePlusOffset(SDValue Base, TypeSize Offset, const SDLoc &DL, 919 const SDNodeFlags Flags = SDNodeFlags()); 920 SDValue getMemBasePlusOffset(SDValue Base, SDValue Offset, const SDLoc &DL, 921 const SDNodeFlags Flags = SDNodeFlags()); 922 923 /// Create an add instruction with appropriate flags when used for 924 /// addressing some offset of an object. i.e. if a load is split into multiple 925 /// components, create an add nuw from the base pointer to the offset. 926 SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Ptr, TypeSize Offset) { 927 SDNodeFlags Flags; 928 Flags.setNoUnsignedWrap(true); 929 return getMemBasePlusOffset(Ptr, Offset, SL, Flags); 930 } 931 932 SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Ptr, SDValue Offset) { 933 // The object itself can't wrap around the address space, so it shouldn't be 934 // possible for the adds of the offsets to the split parts to overflow. 935 SDNodeFlags Flags; 936 Flags.setNoUnsignedWrap(true); 937 return getMemBasePlusOffset(Ptr, Offset, SL, Flags); 938 } 939 940 /// Return a new CALLSEQ_START node, that starts new call frame, in which 941 /// InSize bytes are set up inside CALLSEQ_START..CALLSEQ_END sequence and 942 /// OutSize specifies part of the frame set up prior to the sequence. 943 SDValue getCALLSEQ_START(SDValue Chain, uint64_t InSize, uint64_t OutSize, 944 const SDLoc &DL) { 945 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 946 SDValue Ops[] = { Chain, 947 getIntPtrConstant(InSize, DL, true), 948 getIntPtrConstant(OutSize, DL, true) }; 949 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops); 950 } 951 952 /// Return a new CALLSEQ_END node, which always must have a 953 /// glue result (to ensure it's not CSE'd). 954 /// CALLSEQ_END does not have a useful SDLoc. 955 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, 956 SDValue InGlue, const SDLoc &DL) { 957 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue); 958 SmallVector<SDValue, 4> Ops; 959 Ops.push_back(Chain); 960 Ops.push_back(Op1); 961 Ops.push_back(Op2); 962 if (InGlue.getNode()) 963 Ops.push_back(InGlue); 964 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops); 965 } 966 967 /// Return true if the result of this operation is always undefined. 968 bool isUndef(unsigned Opcode, ArrayRef<SDValue> Ops); 969 970 /// Return an UNDEF node. UNDEF does not have a useful SDLoc. 971 SDValue getUNDEF(EVT VT) { 972 return getNode(ISD::UNDEF, SDLoc(), VT); 973 } 974 975 /// Return a node that represents the runtime scaling 'MulImm * RuntimeVL'. 976 SDValue getVScale(const SDLoc &DL, EVT VT, APInt MulImm) { 977 assert(MulImm.getMinSignedBits() <= VT.getSizeInBits() && 978 "Immediate does not fit VT"); 979 return getNode(ISD::VSCALE, DL, VT, 980 getConstant(MulImm.sextOrTrunc(VT.getSizeInBits()), DL, VT)); 981 } 982 983 /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc. 984 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) { 985 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT); 986 } 987 988 /// Gets or creates the specified node. 989 /// 990 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, 991 ArrayRef<SDUse> Ops); 992 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, 993 ArrayRef<SDValue> Ops, const SDNodeFlags Flags); 994 SDValue getNode(unsigned Opcode, const SDLoc &DL, ArrayRef<EVT> ResultTys, 995 ArrayRef<SDValue> Ops); 996 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, 997 ArrayRef<SDValue> Ops, const SDNodeFlags Flags); 998 999 // Use flags from current flag inserter. 1000 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, 1001 ArrayRef<SDValue> Ops); 1002 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, 1003 ArrayRef<SDValue> Ops); 1004 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue Operand); 1005 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 1006 SDValue N2); 1007 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 1008 SDValue N2, SDValue N3); 1009 1010 // Specialize based on number of operands. 1011 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT); 1012 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue Operand, 1013 const SDNodeFlags Flags); 1014 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 1015 SDValue N2, const SDNodeFlags Flags); 1016 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 1017 SDValue N2, SDValue N3, const SDNodeFlags Flags); 1018 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 1019 SDValue N2, SDValue N3, SDValue N4); 1020 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 1021 SDValue N2, SDValue N3, SDValue N4, SDValue N5); 1022 1023 // Specialize again based on number of operands for nodes with a VTList 1024 // rather than a single VT. 1025 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList); 1026 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N); 1027 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1, 1028 SDValue N2); 1029 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1, 1030 SDValue N2, SDValue N3); 1031 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1, 1032 SDValue N2, SDValue N3, SDValue N4); 1033 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1, 1034 SDValue N2, SDValue N3, SDValue N4, SDValue N5); 1035 1036 /// Compute a TokenFactor to force all the incoming stack arguments to be 1037 /// loaded from the stack. This is used in tail call lowering to protect 1038 /// stack arguments from being clobbered. 1039 SDValue getStackArgumentTokenFactor(SDValue Chain); 1040 1041 SDValue getMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src, 1042 SDValue Size, Align Alignment, bool isVol, 1043 bool AlwaysInline, bool isTailCall, 1044 MachinePointerInfo DstPtrInfo, 1045 MachinePointerInfo SrcPtrInfo, 1046 const AAMDNodes &AAInfo = AAMDNodes(), 1047 AAResults *AA = nullptr); 1048 1049 SDValue getMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src, 1050 SDValue Size, Align Alignment, bool isVol, bool isTailCall, 1051 MachinePointerInfo DstPtrInfo, 1052 MachinePointerInfo SrcPtrInfo, 1053 const AAMDNodes &AAInfo = AAMDNodes(), 1054 AAResults *AA = nullptr); 1055 1056 SDValue getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src, 1057 SDValue Size, Align Alignment, bool isVol, 1058 bool AlwaysInline, bool isTailCall, 1059 MachinePointerInfo DstPtrInfo, 1060 const AAMDNodes &AAInfo = AAMDNodes()); 1061 1062 SDValue getAtomicMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, 1063 SDValue Src, SDValue Size, Type *SizeTy, 1064 unsigned ElemSz, bool isTailCall, 1065 MachinePointerInfo DstPtrInfo, 1066 MachinePointerInfo SrcPtrInfo); 1067 1068 SDValue getAtomicMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, 1069 SDValue Src, SDValue Size, Type *SizeTy, 1070 unsigned ElemSz, bool isTailCall, 1071 MachinePointerInfo DstPtrInfo, 1072 MachinePointerInfo SrcPtrInfo); 1073 1074 SDValue getAtomicMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, 1075 SDValue Value, SDValue Size, Type *SizeTy, 1076 unsigned ElemSz, bool isTailCall, 1077 MachinePointerInfo DstPtrInfo); 1078 1079 /// Helper function to make it easier to build SetCC's if you just have an 1080 /// ISD::CondCode instead of an SDValue. 1081 SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS, 1082 ISD::CondCode Cond, SDValue Chain = SDValue(), 1083 bool IsSignaling = false) { 1084 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() && 1085 "Cannot compare scalars to vectors"); 1086 assert(LHS.getValueType().isVector() == VT.isVector() && 1087 "Cannot compare scalars to vectors"); 1088 assert(Cond != ISD::SETCC_INVALID && 1089 "Cannot create a setCC of an invalid node."); 1090 if (Chain) 1091 return getNode(IsSignaling ? ISD::STRICT_FSETCCS : ISD::STRICT_FSETCC, DL, 1092 {VT, MVT::Other}, {Chain, LHS, RHS, getCondCode(Cond)}); 1093 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 1094 } 1095 1096 /// Helper function to make it easier to build VP_SETCCs if you just have an 1097 /// ISD::CondCode instead of an SDValue. 1098 SDValue getSetCCVP(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS, 1099 ISD::CondCode Cond, SDValue Mask, SDValue EVL) { 1100 assert(LHS.getValueType().isVector() && RHS.getValueType().isVector() && 1101 "Cannot compare scalars"); 1102 assert(Cond != ISD::SETCC_INVALID && 1103 "Cannot create a setCC of an invalid node."); 1104 return getNode(ISD::VP_SETCC, DL, VT, LHS, RHS, getCondCode(Cond), Mask, 1105 EVL); 1106 } 1107 1108 /// Helper function to make it easier to build Select's if you just have 1109 /// operands and don't want to check for vector. 1110 SDValue getSelect(const SDLoc &DL, EVT VT, SDValue Cond, SDValue LHS, 1111 SDValue RHS) { 1112 assert(LHS.getValueType() == VT && RHS.getValueType() == VT && 1113 "Cannot use select on differing types"); 1114 auto Opcode = Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT; 1115 return getNode(Opcode, DL, VT, Cond, LHS, RHS); 1116 } 1117 1118 /// Helper function to make it easier to build SelectCC's if you just have an 1119 /// ISD::CondCode instead of an SDValue. 1120 SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True, 1121 SDValue False, ISD::CondCode Cond) { 1122 return getNode(ISD::SELECT_CC, DL, True.getValueType(), LHS, RHS, True, 1123 False, getCondCode(Cond)); 1124 } 1125 1126 /// Try to simplify a select/vselect into 1 of its operands or a constant. 1127 SDValue simplifySelect(SDValue Cond, SDValue TVal, SDValue FVal); 1128 1129 /// Try to simplify a shift into 1 of its operands or a constant. 1130 SDValue simplifyShift(SDValue X, SDValue Y); 1131 1132 /// Try to simplify a floating-point binary operation into 1 of its operands 1133 /// or a constant. 1134 SDValue simplifyFPBinop(unsigned Opcode, SDValue X, SDValue Y, 1135 SDNodeFlags Flags); 1136 1137 /// VAArg produces a result and token chain, and takes a pointer 1138 /// and a source value as input. 1139 SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1140 SDValue SV, unsigned Align); 1141 1142 /// Gets a node for an atomic cmpxchg op. There are two 1143 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a 1144 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded, 1145 /// a success flag (initially i1), and a chain. 1146 SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT, 1147 SDVTList VTs, SDValue Chain, SDValue Ptr, 1148 SDValue Cmp, SDValue Swp, MachineMemOperand *MMO); 1149 1150 /// Gets a node for an atomic op, produces result (if relevant) 1151 /// and chain and takes 2 operands. 1152 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain, 1153 SDValue Ptr, SDValue Val, MachineMemOperand *MMO); 1154 1155 /// Gets a node for an atomic op, produces result and chain and 1156 /// takes 1 operand. 1157 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, EVT VT, 1158 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO); 1159 1160 /// Gets a node for an atomic op, produces result and chain and takes N 1161 /// operands. 1162 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, 1163 SDVTList VTList, ArrayRef<SDValue> Ops, 1164 MachineMemOperand *MMO); 1165 1166 /// Creates a MemIntrinsicNode that may produce a 1167 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID, 1168 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not 1169 /// less than FIRST_TARGET_MEMORY_OPCODE. 1170 SDValue getMemIntrinsicNode( 1171 unsigned Opcode, const SDLoc &dl, SDVTList VTList, ArrayRef<SDValue> Ops, 1172 EVT MemVT, MachinePointerInfo PtrInfo, Align Alignment, 1173 MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad | 1174 MachineMemOperand::MOStore, 1175 uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes()); 1176 1177 inline SDValue getMemIntrinsicNode( 1178 unsigned Opcode, const SDLoc &dl, SDVTList VTList, ArrayRef<SDValue> Ops, 1179 EVT MemVT, MachinePointerInfo PtrInfo, MaybeAlign Alignment = None, 1180 MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad | 1181 MachineMemOperand::MOStore, 1182 uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes()) { 1183 // Ensure that codegen never sees alignment 0 1184 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, PtrInfo, 1185 Alignment.value_or(getEVTAlign(MemVT)), Flags, 1186 Size, AAInfo); 1187 } 1188 1189 SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList, 1190 ArrayRef<SDValue> Ops, EVT MemVT, 1191 MachineMemOperand *MMO); 1192 1193 /// Creates a LifetimeSDNode that starts (`IsStart==true`) or ends 1194 /// (`IsStart==false`) the lifetime of the portion of `FrameIndex` between 1195 /// offsets `Offset` and `Offset + Size`. 1196 SDValue getLifetimeNode(bool IsStart, const SDLoc &dl, SDValue Chain, 1197 int FrameIndex, int64_t Size, int64_t Offset = -1); 1198 1199 /// Creates a PseudoProbeSDNode with function GUID `Guid` and 1200 /// the index of the block `Index` it is probing, as well as the attributes 1201 /// `attr` of the probe. 1202 SDValue getPseudoProbeNode(const SDLoc &Dl, SDValue Chain, uint64_t Guid, 1203 uint64_t Index, uint32_t Attr); 1204 1205 /// Create a MERGE_VALUES node from the given operands. 1206 SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl); 1207 1208 /// Loads are not normal binary operators: their result type is not 1209 /// determined by their operands, and they produce a value AND a token chain. 1210 /// 1211 /// This function will set the MOLoad flag on MMOFlags, but you can set it if 1212 /// you want. The MOStore flag must not be set. 1213 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1214 MachinePointerInfo PtrInfo, 1215 MaybeAlign Alignment = MaybeAlign(), 1216 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1217 const AAMDNodes &AAInfo = AAMDNodes(), 1218 const MDNode *Ranges = nullptr); 1219 /// FIXME: Remove once transition to Align is over. 1220 inline SDValue 1221 getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1222 MachinePointerInfo PtrInfo, unsigned Alignment, 1223 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1224 const AAMDNodes &AAInfo = AAMDNodes(), 1225 const MDNode *Ranges = nullptr) { 1226 return getLoad(VT, dl, Chain, Ptr, PtrInfo, MaybeAlign(Alignment), MMOFlags, 1227 AAInfo, Ranges); 1228 } 1229 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1230 MachineMemOperand *MMO); 1231 SDValue 1232 getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain, 1233 SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT, 1234 MaybeAlign Alignment = MaybeAlign(), 1235 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1236 const AAMDNodes &AAInfo = AAMDNodes()); 1237 /// FIXME: Remove once transition to Align is over. 1238 inline SDValue 1239 getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain, 1240 SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT, 1241 unsigned Alignment, 1242 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1243 const AAMDNodes &AAInfo = AAMDNodes()) { 1244 return getExtLoad(ExtType, dl, VT, Chain, Ptr, PtrInfo, MemVT, 1245 MaybeAlign(Alignment), MMOFlags, AAInfo); 1246 } 1247 SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, 1248 SDValue Chain, SDValue Ptr, EVT MemVT, 1249 MachineMemOperand *MMO); 1250 SDValue getIndexedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base, 1251 SDValue Offset, ISD::MemIndexedMode AM); 1252 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 1253 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 1254 MachinePointerInfo PtrInfo, EVT MemVT, Align Alignment, 1255 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1256 const AAMDNodes &AAInfo = AAMDNodes(), 1257 const MDNode *Ranges = nullptr); 1258 inline SDValue getLoad( 1259 ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, const SDLoc &dl, 1260 SDValue Chain, SDValue Ptr, SDValue Offset, MachinePointerInfo PtrInfo, 1261 EVT MemVT, MaybeAlign Alignment = MaybeAlign(), 1262 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1263 const AAMDNodes &AAInfo = AAMDNodes(), const MDNode *Ranges = nullptr) { 1264 // Ensures that codegen never sees a None Alignment. 1265 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, PtrInfo, MemVT, 1266 Alignment.value_or(getEVTAlign(MemVT)), MMOFlags, AAInfo, 1267 Ranges); 1268 } 1269 /// FIXME: Remove once transition to Align is over. 1270 inline SDValue 1271 getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 1272 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 1273 MachinePointerInfo PtrInfo, EVT MemVT, unsigned Alignment, 1274 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1275 const AAMDNodes &AAInfo = AAMDNodes(), 1276 const MDNode *Ranges = nullptr) { 1277 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, PtrInfo, MemVT, 1278 MaybeAlign(Alignment), MMOFlags, AAInfo, Ranges); 1279 } 1280 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 1281 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 1282 EVT MemVT, MachineMemOperand *MMO); 1283 1284 /// Helper function to build ISD::STORE nodes. 1285 /// 1286 /// This function will set the MOStore flag on MMOFlags, but you can set it if 1287 /// you want. The MOLoad and MOInvariant flags must not be set. 1288 1289 SDValue 1290 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1291 MachinePointerInfo PtrInfo, Align Alignment, 1292 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1293 const AAMDNodes &AAInfo = AAMDNodes()); 1294 inline SDValue 1295 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1296 MachinePointerInfo PtrInfo, MaybeAlign Alignment = MaybeAlign(), 1297 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1298 const AAMDNodes &AAInfo = AAMDNodes()) { 1299 return getStore(Chain, dl, Val, Ptr, PtrInfo, 1300 Alignment.value_or(getEVTAlign(Val.getValueType())), 1301 MMOFlags, AAInfo); 1302 } 1303 /// FIXME: Remove once transition to Align is over. 1304 inline SDValue 1305 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1306 MachinePointerInfo PtrInfo, unsigned Alignment, 1307 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1308 const AAMDNodes &AAInfo = AAMDNodes()) { 1309 return getStore(Chain, dl, Val, Ptr, PtrInfo, MaybeAlign(Alignment), 1310 MMOFlags, AAInfo); 1311 } 1312 SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1313 MachineMemOperand *MMO); 1314 SDValue 1315 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1316 MachinePointerInfo PtrInfo, EVT SVT, Align Alignment, 1317 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1318 const AAMDNodes &AAInfo = AAMDNodes()); 1319 inline SDValue 1320 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1321 MachinePointerInfo PtrInfo, EVT SVT, 1322 MaybeAlign Alignment = MaybeAlign(), 1323 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1324 const AAMDNodes &AAInfo = AAMDNodes()) { 1325 return getTruncStore(Chain, dl, Val, Ptr, PtrInfo, SVT, 1326 Alignment.value_or(getEVTAlign(SVT)), MMOFlags, 1327 AAInfo); 1328 } 1329 /// FIXME: Remove once transition to Align is over. 1330 inline SDValue 1331 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1332 MachinePointerInfo PtrInfo, EVT SVT, unsigned Alignment, 1333 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1334 const AAMDNodes &AAInfo = AAMDNodes()) { 1335 return getTruncStore(Chain, dl, Val, Ptr, PtrInfo, SVT, 1336 MaybeAlign(Alignment), MMOFlags, AAInfo); 1337 } 1338 SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, 1339 SDValue Ptr, EVT SVT, MachineMemOperand *MMO); 1340 SDValue getIndexedStore(SDValue OrigStore, const SDLoc &dl, SDValue Base, 1341 SDValue Offset, ISD::MemIndexedMode AM); 1342 1343 SDValue getLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 1344 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 1345 SDValue Mask, SDValue EVL, MachinePointerInfo PtrInfo, 1346 EVT MemVT, Align Alignment, 1347 MachineMemOperand::Flags MMOFlags, const AAMDNodes &AAInfo, 1348 const MDNode *Ranges = nullptr, bool IsExpanding = false); 1349 inline SDValue 1350 getLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 1351 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 1352 SDValue Mask, SDValue EVL, MachinePointerInfo PtrInfo, EVT MemVT, 1353 MaybeAlign Alignment = MaybeAlign(), 1354 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1355 const AAMDNodes &AAInfo = AAMDNodes(), 1356 const MDNode *Ranges = nullptr, bool IsExpanding = false) { 1357 // Ensures that codegen never sees a None Alignment. 1358 return getLoadVP(AM, ExtType, VT, dl, Chain, Ptr, Offset, Mask, EVL, 1359 PtrInfo, MemVT, Alignment.value_or(getEVTAlign(MemVT)), 1360 MMOFlags, AAInfo, Ranges, IsExpanding); 1361 } 1362 SDValue getLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 1363 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 1364 SDValue Mask, SDValue EVL, EVT MemVT, 1365 MachineMemOperand *MMO, bool IsExpanding = false); 1366 SDValue getLoadVP(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1367 SDValue Mask, SDValue EVL, MachinePointerInfo PtrInfo, 1368 MaybeAlign Alignment, MachineMemOperand::Flags MMOFlags, 1369 const AAMDNodes &AAInfo, const MDNode *Ranges = nullptr, 1370 bool IsExpanding = false); 1371 SDValue getLoadVP(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1372 SDValue Mask, SDValue EVL, MachineMemOperand *MMO, 1373 bool IsExpanding = false); 1374 SDValue getExtLoadVP(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, 1375 SDValue Chain, SDValue Ptr, SDValue Mask, SDValue EVL, 1376 MachinePointerInfo PtrInfo, EVT MemVT, 1377 MaybeAlign Alignment, MachineMemOperand::Flags MMOFlags, 1378 const AAMDNodes &AAInfo, bool IsExpanding = false); 1379 SDValue getExtLoadVP(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, 1380 SDValue Chain, SDValue Ptr, SDValue Mask, SDValue EVL, 1381 EVT MemVT, MachineMemOperand *MMO, 1382 bool IsExpanding = false); 1383 SDValue getIndexedLoadVP(SDValue OrigLoad, const SDLoc &dl, SDValue Base, 1384 SDValue Offset, ISD::MemIndexedMode AM); 1385 SDValue getStoreVP(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1386 SDValue Offset, SDValue Mask, SDValue EVL, EVT MemVT, 1387 MachineMemOperand *MMO, ISD::MemIndexedMode AM, 1388 bool IsTruncating = false, bool IsCompressing = false); 1389 SDValue getTruncStoreVP(SDValue Chain, const SDLoc &dl, SDValue Val, 1390 SDValue Ptr, SDValue Mask, SDValue EVL, 1391 MachinePointerInfo PtrInfo, EVT SVT, Align Alignment, 1392 MachineMemOperand::Flags MMOFlags, 1393 const AAMDNodes &AAInfo, bool IsCompressing = false); 1394 SDValue getTruncStoreVP(SDValue Chain, const SDLoc &dl, SDValue Val, 1395 SDValue Ptr, SDValue Mask, SDValue EVL, EVT SVT, 1396 MachineMemOperand *MMO, bool IsCompressing = false); 1397 SDValue getIndexedStoreVP(SDValue OrigStore, const SDLoc &dl, SDValue Base, 1398 SDValue Offset, ISD::MemIndexedMode AM); 1399 1400 SDValue getStridedLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 1401 EVT VT, const SDLoc &DL, SDValue Chain, SDValue Ptr, 1402 SDValue Offset, SDValue Stride, SDValue Mask, 1403 SDValue EVL, MachinePointerInfo PtrInfo, EVT MemVT, 1404 Align Alignment, MachineMemOperand::Flags MMOFlags, 1405 const AAMDNodes &AAInfo, 1406 const MDNode *Ranges = nullptr, 1407 bool IsExpanding = false); 1408 inline SDValue getStridedLoadVP( 1409 ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, const SDLoc &DL, 1410 SDValue Chain, SDValue Ptr, SDValue Offset, SDValue Stride, SDValue Mask, 1411 SDValue EVL, MachinePointerInfo PtrInfo, EVT MemVT, 1412 MaybeAlign Alignment = MaybeAlign(), 1413 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1414 const AAMDNodes &AAInfo = AAMDNodes(), const MDNode *Ranges = nullptr, 1415 bool IsExpanding = false) { 1416 // Ensures that codegen never sees a None Alignment. 1417 return getStridedLoadVP(AM, ExtType, VT, DL, Chain, Ptr, Offset, Stride, 1418 Mask, EVL, PtrInfo, MemVT, 1419 Alignment.value_or(getEVTAlign(MemVT)), MMOFlags, 1420 AAInfo, Ranges, IsExpanding); 1421 } 1422 SDValue getStridedLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 1423 EVT VT, const SDLoc &DL, SDValue Chain, SDValue Ptr, 1424 SDValue Offset, SDValue Stride, SDValue Mask, 1425 SDValue EVL, EVT MemVT, MachineMemOperand *MMO, 1426 bool IsExpanding = false); 1427 SDValue getStridedLoadVP(EVT VT, const SDLoc &DL, SDValue Chain, SDValue Ptr, 1428 SDValue Stride, SDValue Mask, SDValue EVL, 1429 MachinePointerInfo PtrInfo, MaybeAlign Alignment, 1430 MachineMemOperand::Flags MMOFlags, 1431 const AAMDNodes &AAInfo, 1432 const MDNode *Ranges = nullptr, 1433 bool IsExpanding = false); 1434 SDValue getStridedLoadVP(EVT VT, const SDLoc &DL, SDValue Chain, SDValue Ptr, 1435 SDValue Stride, SDValue Mask, SDValue EVL, 1436 MachineMemOperand *MMO, bool IsExpanding = false); 1437 SDValue 1438 getExtStridedLoadVP(ISD::LoadExtType ExtType, const SDLoc &DL, EVT VT, 1439 SDValue Chain, SDValue Ptr, SDValue Stride, SDValue Mask, 1440 SDValue EVL, MachinePointerInfo PtrInfo, EVT MemVT, 1441 MaybeAlign Alignment, MachineMemOperand::Flags MMOFlags, 1442 const AAMDNodes &AAInfo, bool IsExpanding = false); 1443 SDValue getExtStridedLoadVP(ISD::LoadExtType ExtType, const SDLoc &DL, EVT VT, 1444 SDValue Chain, SDValue Ptr, SDValue Stride, 1445 SDValue Mask, SDValue EVL, EVT MemVT, 1446 MachineMemOperand *MMO, bool IsExpanding = false); 1447 SDValue getIndexedStridedLoadVP(SDValue OrigLoad, const SDLoc &DL, 1448 SDValue Base, SDValue Offset, 1449 ISD::MemIndexedMode AM); 1450 SDValue getStridedStoreVP(SDValue Chain, const SDLoc &DL, SDValue Val, 1451 SDValue Ptr, SDValue Offset, SDValue Stride, 1452 SDValue Mask, SDValue EVL, EVT MemVT, 1453 MachineMemOperand *MMO, ISD::MemIndexedMode AM, 1454 bool IsTruncating = false, 1455 bool IsCompressing = false); 1456 SDValue getTruncStridedStoreVP(SDValue Chain, const SDLoc &DL, SDValue Val, 1457 SDValue Ptr, SDValue Stride, SDValue Mask, 1458 SDValue EVL, MachinePointerInfo PtrInfo, 1459 EVT SVT, Align Alignment, 1460 MachineMemOperand::Flags MMOFlags, 1461 const AAMDNodes &AAInfo, 1462 bool IsCompressing = false); 1463 SDValue getTruncStridedStoreVP(SDValue Chain, const SDLoc &DL, SDValue Val, 1464 SDValue Ptr, SDValue Stride, SDValue Mask, 1465 SDValue EVL, EVT SVT, MachineMemOperand *MMO, 1466 bool IsCompressing = false); 1467 SDValue getIndexedStridedStoreVP(SDValue OrigStore, const SDLoc &DL, 1468 SDValue Base, SDValue Offset, 1469 ISD::MemIndexedMode AM); 1470 1471 SDValue getGatherVP(SDVTList VTs, EVT VT, const SDLoc &dl, 1472 ArrayRef<SDValue> Ops, MachineMemOperand *MMO, 1473 ISD::MemIndexType IndexType); 1474 SDValue getScatterVP(SDVTList VTs, EVT VT, const SDLoc &dl, 1475 ArrayRef<SDValue> Ops, MachineMemOperand *MMO, 1476 ISD::MemIndexType IndexType); 1477 1478 SDValue getMaskedLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Base, 1479 SDValue Offset, SDValue Mask, SDValue Src0, EVT MemVT, 1480 MachineMemOperand *MMO, ISD::MemIndexedMode AM, 1481 ISD::LoadExtType, bool IsExpanding = false); 1482 SDValue getIndexedMaskedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base, 1483 SDValue Offset, ISD::MemIndexedMode AM); 1484 SDValue getMaskedStore(SDValue Chain, const SDLoc &dl, SDValue Val, 1485 SDValue Base, SDValue Offset, SDValue Mask, EVT MemVT, 1486 MachineMemOperand *MMO, ISD::MemIndexedMode AM, 1487 bool IsTruncating = false, bool IsCompressing = false); 1488 SDValue getIndexedMaskedStore(SDValue OrigStore, const SDLoc &dl, 1489 SDValue Base, SDValue Offset, 1490 ISD::MemIndexedMode AM); 1491 SDValue getMaskedGather(SDVTList VTs, EVT MemVT, const SDLoc &dl, 1492 ArrayRef<SDValue> Ops, MachineMemOperand *MMO, 1493 ISD::MemIndexType IndexType, ISD::LoadExtType ExtTy); 1494 SDValue getMaskedScatter(SDVTList VTs, EVT MemVT, const SDLoc &dl, 1495 ArrayRef<SDValue> Ops, MachineMemOperand *MMO, 1496 ISD::MemIndexType IndexType, 1497 bool IsTruncating = false); 1498 1499 /// Construct a node to track a Value* through the backend. 1500 SDValue getSrcValue(const Value *v); 1501 1502 /// Return an MDNodeSDNode which holds an MDNode. 1503 SDValue getMDNode(const MDNode *MD); 1504 1505 /// Return a bitcast using the SDLoc of the value operand, and casting to the 1506 /// provided type. Use getNode to set a custom SDLoc. 1507 SDValue getBitcast(EVT VT, SDValue V); 1508 1509 /// Return an AddrSpaceCastSDNode. 1510 SDValue getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr, unsigned SrcAS, 1511 unsigned DestAS); 1512 1513 /// Return a freeze using the SDLoc of the value operand. 1514 SDValue getFreeze(SDValue V); 1515 1516 /// Return an AssertAlignSDNode. 1517 SDValue getAssertAlign(const SDLoc &DL, SDValue V, Align A); 1518 1519 /// Swap N1 and N2 if Opcode is a commutative binary opcode 1520 /// and the canonical form expects the opposite order. 1521 void canonicalizeCommutativeBinop(unsigned Opcode, SDValue &N1, 1522 SDValue &N2) const; 1523 1524 /// Return the specified value casted to 1525 /// the target's desired shift amount type. 1526 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op); 1527 1528 /// Expand the specified \c ISD::VAARG node as the Legalize pass would. 1529 SDValue expandVAArg(SDNode *Node); 1530 1531 /// Expand the specified \c ISD::VACOPY node as the Legalize pass would. 1532 SDValue expandVACopy(SDNode *Node); 1533 1534 /// Returs an GlobalAddress of the function from the current module with 1535 /// name matching the given ExternalSymbol. Additionally can provide the 1536 /// matched function. 1537 /// Panics the function doesn't exists. 1538 SDValue getSymbolFunctionGlobalAddress(SDValue Op, 1539 Function **TargetFunction = nullptr); 1540 1541 /// *Mutate* the specified node in-place to have the 1542 /// specified operands. If the resultant node already exists in the DAG, 1543 /// this does not modify the specified node, instead it returns the node that 1544 /// already exists. If the resultant node does not exist in the DAG, the 1545 /// input node is returned. As a degenerate case, if you specify the same 1546 /// input operands as the node already has, the input node is returned. 1547 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op); 1548 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2); 1549 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 1550 SDValue Op3); 1551 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 1552 SDValue Op3, SDValue Op4); 1553 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 1554 SDValue Op3, SDValue Op4, SDValue Op5); 1555 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops); 1556 1557 /// Creates a new TokenFactor containing \p Vals. If \p Vals contains 64k 1558 /// values or more, move values into new TokenFactors in 64k-1 blocks, until 1559 /// the final TokenFactor has less than 64k operands. 1560 SDValue getTokenFactor(const SDLoc &DL, SmallVectorImpl<SDValue> &Vals); 1561 1562 /// *Mutate* the specified machine node's memory references to the provided 1563 /// list. 1564 void setNodeMemRefs(MachineSDNode *N, 1565 ArrayRef<MachineMemOperand *> NewMemRefs); 1566 1567 // Calculate divergence of node \p N based on its operands. 1568 bool calculateDivergence(SDNode *N); 1569 1570 // Propagates the change in divergence to users 1571 void updateDivergence(SDNode * N); 1572 1573 /// These are used for target selectors to *mutate* the 1574 /// specified node to have the specified return type, Target opcode, and 1575 /// operands. Note that target opcodes are stored as 1576 /// ~TargetOpcode in the node opcode field. The resultant node is returned. 1577 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT); 1578 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, SDValue Op1); 1579 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, 1580 SDValue Op1, SDValue Op2); 1581 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, 1582 SDValue Op1, SDValue Op2, SDValue Op3); 1583 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, 1584 ArrayRef<SDValue> Ops); 1585 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, EVT VT2); 1586 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 1587 EVT VT2, ArrayRef<SDValue> Ops); 1588 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 1589 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops); 1590 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 1591 EVT VT2, SDValue Op1, SDValue Op2); 1592 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, SDVTList VTs, 1593 ArrayRef<SDValue> Ops); 1594 1595 /// This *mutates* the specified node to have the specified 1596 /// return type, opcode, and operands. 1597 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, 1598 ArrayRef<SDValue> Ops); 1599 1600 /// Mutate the specified strict FP node to its non-strict equivalent, 1601 /// unlinking the node from its chain and dropping the metadata arguments. 1602 /// The node must be a strict FP node. 1603 SDNode *mutateStrictFPToFP(SDNode *Node); 1604 1605 /// These are used for target selectors to create a new node 1606 /// with specified return type(s), MachineInstr opcode, and operands. 1607 /// 1608 /// Note that getMachineNode returns the resultant node. If there is already 1609 /// a node of the specified opcode and operands, it returns that node instead 1610 /// of the current one. 1611 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT); 1612 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1613 SDValue Op1); 1614 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1615 SDValue Op1, SDValue Op2); 1616 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1617 SDValue Op1, SDValue Op2, SDValue Op3); 1618 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1619 ArrayRef<SDValue> Ops); 1620 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1621 EVT VT2, SDValue Op1, SDValue Op2); 1622 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1623 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 1624 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1625 EVT VT2, ArrayRef<SDValue> Ops); 1626 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1627 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2); 1628 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1629 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, 1630 SDValue Op3); 1631 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1632 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops); 1633 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, 1634 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops); 1635 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, SDVTList VTs, 1636 ArrayRef<SDValue> Ops); 1637 1638 /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes. 1639 SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT, 1640 SDValue Operand); 1641 1642 /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes. 1643 SDValue getTargetInsertSubreg(int SRIdx, const SDLoc &DL, EVT VT, 1644 SDValue Operand, SDValue Subreg); 1645 1646 /// Get the specified node if it's already available, or else return NULL. 1647 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTList, 1648 ArrayRef<SDValue> Ops, const SDNodeFlags Flags); 1649 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTList, 1650 ArrayRef<SDValue> Ops); 1651 1652 /// Check if a node exists without modifying its flags. 1653 bool doesNodeExist(unsigned Opcode, SDVTList VTList, ArrayRef<SDValue> Ops); 1654 1655 /// Creates a SDDbgValue node. 1656 SDDbgValue *getDbgValue(DIVariable *Var, DIExpression *Expr, SDNode *N, 1657 unsigned R, bool IsIndirect, const DebugLoc &DL, 1658 unsigned O); 1659 1660 /// Creates a constant SDDbgValue node. 1661 SDDbgValue *getConstantDbgValue(DIVariable *Var, DIExpression *Expr, 1662 const Value *C, const DebugLoc &DL, 1663 unsigned O); 1664 1665 /// Creates a FrameIndex SDDbgValue node. 1666 SDDbgValue *getFrameIndexDbgValue(DIVariable *Var, DIExpression *Expr, 1667 unsigned FI, bool IsIndirect, 1668 const DebugLoc &DL, unsigned O); 1669 1670 /// Creates a FrameIndex SDDbgValue node. 1671 SDDbgValue *getFrameIndexDbgValue(DIVariable *Var, DIExpression *Expr, 1672 unsigned FI, 1673 ArrayRef<SDNode *> Dependencies, 1674 bool IsIndirect, const DebugLoc &DL, 1675 unsigned O); 1676 1677 /// Creates a VReg SDDbgValue node. 1678 SDDbgValue *getVRegDbgValue(DIVariable *Var, DIExpression *Expr, 1679 unsigned VReg, bool IsIndirect, 1680 const DebugLoc &DL, unsigned O); 1681 1682 /// Creates a SDDbgValue node from a list of locations. 1683 SDDbgValue *getDbgValueList(DIVariable *Var, DIExpression *Expr, 1684 ArrayRef<SDDbgOperand> Locs, 1685 ArrayRef<SDNode *> Dependencies, bool IsIndirect, 1686 const DebugLoc &DL, unsigned O, bool IsVariadic); 1687 1688 /// Creates a SDDbgLabel node. 1689 SDDbgLabel *getDbgLabel(DILabel *Label, const DebugLoc &DL, unsigned O); 1690 1691 /// Transfer debug values from one node to another, while optionally 1692 /// generating fragment expressions for split-up values. If \p InvalidateDbg 1693 /// is set, debug values are invalidated after they are transferred. 1694 void transferDbgValues(SDValue From, SDValue To, unsigned OffsetInBits = 0, 1695 unsigned SizeInBits = 0, bool InvalidateDbg = true); 1696 1697 /// Remove the specified node from the system. If any of its 1698 /// operands then becomes dead, remove them as well. Inform UpdateListener 1699 /// for each node deleted. 1700 void RemoveDeadNode(SDNode *N); 1701 1702 /// This method deletes the unreachable nodes in the 1703 /// given list, and any nodes that become unreachable as a result. 1704 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes); 1705 1706 /// Modify anything using 'From' to use 'To' instead. 1707 /// This can cause recursive merging of nodes in the DAG. Use the first 1708 /// version if 'From' is known to have a single result, use the second 1709 /// if you have two nodes with identical results (or if 'To' has a superset 1710 /// of the results of 'From'), use the third otherwise. 1711 /// 1712 /// These methods all take an optional UpdateListener, which (if not null) is 1713 /// informed about nodes that are deleted and modified due to recursive 1714 /// changes in the dag. 1715 /// 1716 /// These functions only replace all existing uses. It's possible that as 1717 /// these replacements are being performed, CSE may cause the From node 1718 /// to be given new uses. These new uses of From are left in place, and 1719 /// not automatically transferred to To. 1720 /// 1721 void ReplaceAllUsesWith(SDValue From, SDValue To); 1722 void ReplaceAllUsesWith(SDNode *From, SDNode *To); 1723 void ReplaceAllUsesWith(SDNode *From, const SDValue *To); 1724 1725 /// Replace any uses of From with To, leaving 1726 /// uses of other values produced by From.getNode() alone. 1727 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To); 1728 1729 /// Like ReplaceAllUsesOfValueWith, but for multiple values at once. 1730 /// This correctly handles the case where 1731 /// there is an overlap between the From values and the To values. 1732 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, 1733 unsigned Num); 1734 1735 /// If an existing load has uses of its chain, create a token factor node with 1736 /// that chain and the new memory node's chain and update users of the old 1737 /// chain to the token factor. This ensures that the new memory node will have 1738 /// the same relative memory dependency position as the old load. Returns the 1739 /// new merged load chain. 1740 SDValue makeEquivalentMemoryOrdering(SDValue OldChain, SDValue NewMemOpChain); 1741 1742 /// If an existing load has uses of its chain, create a token factor node with 1743 /// that chain and the new memory node's chain and update users of the old 1744 /// chain to the token factor. This ensures that the new memory node will have 1745 /// the same relative memory dependency position as the old load. Returns the 1746 /// new merged load chain. 1747 SDValue makeEquivalentMemoryOrdering(LoadSDNode *OldLoad, SDValue NewMemOp); 1748 1749 /// Topological-sort the AllNodes list and a 1750 /// assign a unique node id for each node in the DAG based on their 1751 /// topological order. Returns the number of nodes. 1752 unsigned AssignTopologicalOrder(); 1753 1754 /// Move node N in the AllNodes list to be immediately 1755 /// before the given iterator Position. This may be used to update the 1756 /// topological ordering when the list of nodes is modified. 1757 void RepositionNode(allnodes_iterator Position, SDNode *N) { 1758 AllNodes.insert(Position, AllNodes.remove(N)); 1759 } 1760 1761 /// Returns an APFloat semantics tag appropriate for the given type. If VT is 1762 /// a vector type, the element semantics are returned. 1763 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) { 1764 switch (VT.getScalarType().getSimpleVT().SimpleTy) { 1765 default: llvm_unreachable("Unknown FP format"); 1766 case MVT::f16: return APFloat::IEEEhalf(); 1767 case MVT::bf16: return APFloat::BFloat(); 1768 case MVT::f32: return APFloat::IEEEsingle(); 1769 case MVT::f64: return APFloat::IEEEdouble(); 1770 case MVT::f80: return APFloat::x87DoubleExtended(); 1771 case MVT::f128: return APFloat::IEEEquad(); 1772 case MVT::ppcf128: return APFloat::PPCDoubleDouble(); 1773 } 1774 } 1775 1776 /// Add a dbg_value SDNode. If SD is non-null that means the 1777 /// value is produced by SD. 1778 void AddDbgValue(SDDbgValue *DB, bool isParameter); 1779 1780 /// Add a dbg_label SDNode. 1781 void AddDbgLabel(SDDbgLabel *DB); 1782 1783 /// Get the debug values which reference the given SDNode. 1784 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) const { 1785 return DbgInfo->getSDDbgValues(SD); 1786 } 1787 1788 public: 1789 /// Return true if there are any SDDbgValue nodes associated 1790 /// with this SelectionDAG. 1791 bool hasDebugValues() const { return !DbgInfo->empty(); } 1792 1793 SDDbgInfo::DbgIterator DbgBegin() const { return DbgInfo->DbgBegin(); } 1794 SDDbgInfo::DbgIterator DbgEnd() const { return DbgInfo->DbgEnd(); } 1795 1796 SDDbgInfo::DbgIterator ByvalParmDbgBegin() const { 1797 return DbgInfo->ByvalParmDbgBegin(); 1798 } 1799 SDDbgInfo::DbgIterator ByvalParmDbgEnd() const { 1800 return DbgInfo->ByvalParmDbgEnd(); 1801 } 1802 1803 SDDbgInfo::DbgLabelIterator DbgLabelBegin() const { 1804 return DbgInfo->DbgLabelBegin(); 1805 } 1806 SDDbgInfo::DbgLabelIterator DbgLabelEnd() const { 1807 return DbgInfo->DbgLabelEnd(); 1808 } 1809 1810 /// To be invoked on an SDNode that is slated to be erased. This 1811 /// function mirrors \c llvm::salvageDebugInfo. 1812 void salvageDebugInfo(SDNode &N); 1813 1814 /// Signal whether instruction referencing variable locations are desired for 1815 /// this function's debug-info. 1816 void useInstrRefDebugInfo(bool Flag) { 1817 UseInstrRefDebugInfo = Flag; 1818 } 1819 1820 bool getUseInstrRefDebugInfo() const { 1821 return UseInstrRefDebugInfo; 1822 } 1823 1824 void dump() const; 1825 1826 /// In most cases this function returns the ABI alignment for a given type, 1827 /// except for illegal vector types where the alignment exceeds that of the 1828 /// stack. In such cases we attempt to break the vector down to a legal type 1829 /// and return the ABI alignment for that instead. 1830 Align getReducedAlign(EVT VT, bool UseABI); 1831 1832 /// Create a stack temporary based on the size in bytes and the alignment 1833 SDValue CreateStackTemporary(TypeSize Bytes, Align Alignment); 1834 1835 /// Create a stack temporary, suitable for holding the specified value type. 1836 /// If minAlign is specified, the slot size will have at least that alignment. 1837 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1); 1838 1839 /// Create a stack temporary suitable for holding either of the specified 1840 /// value types. 1841 SDValue CreateStackTemporary(EVT VT1, EVT VT2); 1842 1843 SDValue FoldSymbolOffset(unsigned Opcode, EVT VT, 1844 const GlobalAddressSDNode *GA, 1845 const SDNode *N2); 1846 1847 SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT, 1848 ArrayRef<SDValue> Ops); 1849 1850 /// Fold floating-point operations with 2 operands when both operands are 1851 /// constants and/or undefined. 1852 SDValue foldConstantFPMath(unsigned Opcode, const SDLoc &DL, EVT VT, 1853 SDValue N1, SDValue N2); 1854 1855 /// Constant fold a setcc to true or false. 1856 SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond, 1857 const SDLoc &dl); 1858 1859 /// See if the specified operand can be simplified with the knowledge that 1860 /// only the bits specified by DemandedBits are used. If so, return the 1861 /// simpler operand, otherwise return a null SDValue. 1862 /// 1863 /// (This exists alongside SimplifyDemandedBits because GetDemandedBits can 1864 /// simplify nodes with multiple uses more aggressively.) 1865 SDValue GetDemandedBits(SDValue V, const APInt &DemandedBits); 1866 1867 /// Return true if the sign bit of Op is known to be zero. 1868 /// We use this predicate to simplify operations downstream. 1869 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const; 1870 1871 /// Return true if 'Op & Mask' is known to be zero. We 1872 /// use this predicate to simplify operations downstream. Op and Mask are 1873 /// known to be the same type. 1874 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, 1875 unsigned Depth = 0) const; 1876 1877 /// Return true if 'Op & Mask' is known to be zero in DemandedElts. We 1878 /// use this predicate to simplify operations downstream. Op and Mask are 1879 /// known to be the same type. 1880 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, 1881 const APInt &DemandedElts, unsigned Depth = 0) const; 1882 1883 /// Return true if 'Op' is known to be zero in DemandedElts. We 1884 /// use this predicate to simplify operations downstream. 1885 bool MaskedVectorIsZero(SDValue Op, const APInt &DemandedElts, 1886 unsigned Depth = 0) const; 1887 1888 /// Return true if '(Op & Mask) == Mask'. 1889 /// Op and Mask are known to be the same type. 1890 bool MaskedValueIsAllOnes(SDValue Op, const APInt &Mask, 1891 unsigned Depth = 0) const; 1892 1893 /// Determine which bits of Op are known to be either zero or one and return 1894 /// them in Known. For vectors, the known bits are those that are shared by 1895 /// every vector element. 1896 /// Targets can implement the computeKnownBitsForTargetNode method in the 1897 /// TargetLowering class to allow target nodes to be understood. 1898 KnownBits computeKnownBits(SDValue Op, unsigned Depth = 0) const; 1899 1900 /// Determine which bits of Op are known to be either zero or one and return 1901 /// them in Known. The DemandedElts argument allows us to only collect the 1902 /// known bits that are shared by the requested vector elements. 1903 /// Targets can implement the computeKnownBitsForTargetNode method in the 1904 /// TargetLowering class to allow target nodes to be understood. 1905 KnownBits computeKnownBits(SDValue Op, const APInt &DemandedElts, 1906 unsigned Depth = 0) const; 1907 1908 /// Used to represent the possible overflow behavior of an operation. 1909 /// Never: the operation cannot overflow. 1910 /// Always: the operation will always overflow. 1911 /// Sometime: the operation may or may not overflow. 1912 enum OverflowKind { 1913 OFK_Never, 1914 OFK_Sometime, 1915 OFK_Always, 1916 }; 1917 1918 /// Determine if the result of the addition of 2 node can overflow. 1919 OverflowKind computeOverflowKind(SDValue N0, SDValue N1) const; 1920 1921 /// Test if the given value is known to have exactly one bit set. This differs 1922 /// from computeKnownBits in that it doesn't necessarily determine which bit 1923 /// is set. 1924 bool isKnownToBeAPowerOfTwo(SDValue Val) const; 1925 1926 /// Return the number of times the sign bit of the register is replicated into 1927 /// the other bits. We know that at least 1 bit is always equal to the sign 1928 /// bit (itself), but other cases can give us information. For example, 1929 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal 1930 /// to each other, so we return 3. Targets can implement the 1931 /// ComputeNumSignBitsForTarget method in the TargetLowering class to allow 1932 /// target nodes to be understood. 1933 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; 1934 1935 /// Return the number of times the sign bit of the register is replicated into 1936 /// the other bits. We know that at least 1 bit is always equal to the sign 1937 /// bit (itself), but other cases can give us information. For example, 1938 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal 1939 /// to each other, so we return 3. The DemandedElts argument allows 1940 /// us to only collect the minimum sign bits of the requested vector elements. 1941 /// Targets can implement the ComputeNumSignBitsForTarget method in the 1942 /// TargetLowering class to allow target nodes to be understood. 1943 unsigned ComputeNumSignBits(SDValue Op, const APInt &DemandedElts, 1944 unsigned Depth = 0) const; 1945 1946 /// Get the upper bound on bit size for this Value \p Op as a signed integer. 1947 /// i.e. x == sext(trunc(x to MaxSignedBits) to bitwidth(x)). 1948 /// Similar to the APInt::getSignificantBits function. 1949 /// Helper wrapper to ComputeNumSignBits. 1950 unsigned ComputeMaxSignificantBits(SDValue Op, unsigned Depth = 0) const; 1951 1952 /// Get the upper bound on bit size for this Value \p Op as a signed integer. 1953 /// i.e. x == sext(trunc(x to MaxSignedBits) to bitwidth(x)). 1954 /// Similar to the APInt::getSignificantBits function. 1955 /// Helper wrapper to ComputeNumSignBits. 1956 unsigned ComputeMaxSignificantBits(SDValue Op, const APInt &DemandedElts, 1957 unsigned Depth = 0) const; 1958 1959 /// Return true if this function can prove that \p Op is never poison 1960 /// and, if \p PoisonOnly is false, does not have undef bits. 1961 bool isGuaranteedNotToBeUndefOrPoison(SDValue Op, bool PoisonOnly = false, 1962 unsigned Depth = 0) const; 1963 1964 /// Return true if this function can prove that \p Op is never poison 1965 /// and, if \p PoisonOnly is false, does not have undef bits. The DemandedElts 1966 /// argument limits the check to the requested vector elements. 1967 bool isGuaranteedNotToBeUndefOrPoison(SDValue Op, const APInt &DemandedElts, 1968 bool PoisonOnly = false, 1969 unsigned Depth = 0) const; 1970 1971 /// Return true if this function can prove that \p Op is never poison. 1972 bool isGuaranteedNotToBePoison(SDValue Op, unsigned Depth = 0) const { 1973 return isGuaranteedNotToBeUndefOrPoison(Op, /*PoisonOnly*/ true, Depth); 1974 } 1975 1976 /// Return true if this function can prove that \p Op is never poison. The 1977 /// DemandedElts argument limits the check to the requested vector elements. 1978 bool isGuaranteedNotToBePoison(SDValue Op, const APInt &DemandedElts, 1979 unsigned Depth = 0) const { 1980 return isGuaranteedNotToBeUndefOrPoison(Op, DemandedElts, 1981 /*PoisonOnly*/ true, Depth); 1982 } 1983 1984 /// Return true if the specified operand is an ISD::ADD with a ConstantSDNode 1985 /// on the right-hand side, or if it is an ISD::OR with a ConstantSDNode that 1986 /// is guaranteed to have the same semantics as an ADD. This handles the 1987 /// equivalence: 1988 /// X|Cst == X+Cst iff X&Cst = 0. 1989 bool isBaseWithConstantOffset(SDValue Op) const; 1990 1991 /// Test whether the given SDValue is known to never be NaN. If \p SNaN is 1992 /// true, returns if \p Op is known to never be a signaling NaN (it may still 1993 /// be a qNaN). 1994 bool isKnownNeverNaN(SDValue Op, bool SNaN = false, unsigned Depth = 0) const; 1995 1996 /// \returns true if \p Op is known to never be a signaling NaN. 1997 bool isKnownNeverSNaN(SDValue Op, unsigned Depth = 0) const { 1998 return isKnownNeverNaN(Op, true, Depth); 1999 } 2000 2001 /// Test whether the given floating point SDValue is known to never be 2002 /// positive or negative zero. 2003 bool isKnownNeverZeroFloat(SDValue Op) const; 2004 2005 /// Test whether the given SDValue is known to contain non-zero value(s). 2006 bool isKnownNeverZero(SDValue Op) const; 2007 2008 /// Test whether two SDValues are known to compare equal. This 2009 /// is true if they are the same value, or if one is negative zero and the 2010 /// other positive zero. 2011 bool isEqualTo(SDValue A, SDValue B) const; 2012 2013 /// Return true if A and B have no common bits set. As an example, this can 2014 /// allow an 'add' to be transformed into an 'or'. 2015 bool haveNoCommonBitsSet(SDValue A, SDValue B) const; 2016 2017 /// Test whether \p V has a splatted value for all the demanded elements. 2018 /// 2019 /// On success \p UndefElts will indicate the elements that have UNDEF 2020 /// values instead of the splat value, this is only guaranteed to be correct 2021 /// for \p DemandedElts. 2022 /// 2023 /// NOTE: The function will return true for a demanded splat of UNDEF values. 2024 bool isSplatValue(SDValue V, const APInt &DemandedElts, APInt &UndefElts, 2025 unsigned Depth = 0) const; 2026 2027 /// Test whether \p V has a splatted value. 2028 bool isSplatValue(SDValue V, bool AllowUndefs = false) const; 2029 2030 /// If V is a splatted value, return the source vector and its splat index. 2031 SDValue getSplatSourceVector(SDValue V, int &SplatIndex); 2032 2033 /// If V is a splat vector, return its scalar source operand by extracting 2034 /// that element from the source vector. If LegalTypes is true, this method 2035 /// may only return a legally-typed splat value. If it cannot legalize the 2036 /// splatted value it will return SDValue(). 2037 SDValue getSplatValue(SDValue V, bool LegalTypes = false); 2038 2039 /// If a SHL/SRA/SRL node \p V has a constant or splat constant shift amount 2040 /// that is less than the element bit-width of the shift node, return it. 2041 const APInt *getValidShiftAmountConstant(SDValue V, 2042 const APInt &DemandedElts) const; 2043 2044 /// If a SHL/SRA/SRL node \p V has constant shift amounts that are all less 2045 /// than the element bit-width of the shift node, return the minimum value. 2046 const APInt * 2047 getValidMinimumShiftAmountConstant(SDValue V, 2048 const APInt &DemandedElts) const; 2049 2050 /// If a SHL/SRA/SRL node \p V has constant shift amounts that are all less 2051 /// than the element bit-width of the shift node, return the maximum value. 2052 const APInt * 2053 getValidMaximumShiftAmountConstant(SDValue V, 2054 const APInt &DemandedElts) const; 2055 2056 /// Match a binop + shuffle pyramid that represents a horizontal reduction 2057 /// over the elements of a vector starting from the EXTRACT_VECTOR_ELT node /p 2058 /// Extract. The reduction must use one of the opcodes listed in /p 2059 /// CandidateBinOps and on success /p BinOp will contain the matching opcode. 2060 /// Returns the vector that is being reduced on, or SDValue() if a reduction 2061 /// was not matched. If \p AllowPartials is set then in the case of a 2062 /// reduction pattern that only matches the first few stages, the extracted 2063 /// subvector of the start of the reduction is returned. 2064 SDValue matchBinOpReduction(SDNode *Extract, ISD::NodeType &BinOp, 2065 ArrayRef<ISD::NodeType> CandidateBinOps, 2066 bool AllowPartials = false); 2067 2068 /// Utility function used by legalize and lowering to 2069 /// "unroll" a vector operation by splitting out the scalars and operating 2070 /// on each element individually. If the ResNE is 0, fully unroll the vector 2071 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE. 2072 /// If the ResNE is greater than the width of the vector op, unroll the 2073 /// vector op and fill the end of the resulting vector with UNDEFS. 2074 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0); 2075 2076 /// Like UnrollVectorOp(), but for the [US](ADD|SUB|MUL)O family of opcodes. 2077 /// This is a separate function because those opcodes have two results. 2078 std::pair<SDValue, SDValue> UnrollVectorOverflowOp(SDNode *N, 2079 unsigned ResNE = 0); 2080 2081 /// Return true if loads are next to each other and can be 2082 /// merged. Check that both are nonvolatile and if LD is loading 2083 /// 'Bytes' bytes from a location that is 'Dist' units away from the 2084 /// location that the 'Base' load is loading from. 2085 bool areNonVolatileConsecutiveLoads(LoadSDNode *LD, LoadSDNode *Base, 2086 unsigned Bytes, int Dist) const; 2087 2088 /// Infer alignment of a load / store address. Return None if it cannot be 2089 /// inferred. 2090 MaybeAlign InferPtrAlign(SDValue Ptr) const; 2091 2092 /// Compute the VTs needed for the low/hi parts of a type 2093 /// which is split (or expanded) into two not necessarily identical pieces. 2094 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const; 2095 2096 /// Compute the VTs needed for the low/hi parts of a type, dependent on an 2097 /// enveloping VT that has been split into two identical pieces. Sets the 2098 /// HisIsEmpty flag when hi type has zero storage size. 2099 std::pair<EVT, EVT> GetDependentSplitDestVTs(const EVT &VT, const EVT &EnvVT, 2100 bool *HiIsEmpty) const; 2101 2102 /// Split the vector with EXTRACT_SUBVECTOR using the provides 2103 /// VTs and return the low/high part. 2104 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL, 2105 const EVT &LoVT, const EVT &HiVT); 2106 2107 /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part. 2108 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) { 2109 EVT LoVT, HiVT; 2110 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType()); 2111 return SplitVector(N, DL, LoVT, HiVT); 2112 } 2113 2114 /// Split the explicit vector length parameter of a VP operation. 2115 std::pair<SDValue, SDValue> SplitEVL(SDValue N, EVT VecVT, const SDLoc &DL); 2116 2117 /// Split the node's operand with EXTRACT_SUBVECTOR and 2118 /// return the low/high part. 2119 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo) 2120 { 2121 return SplitVector(N->getOperand(OpNo), SDLoc(N)); 2122 } 2123 2124 /// Widen the vector up to the next power of two using INSERT_SUBVECTOR. 2125 SDValue WidenVector(const SDValue &N, const SDLoc &DL); 2126 2127 /// Append the extracted elements from Start to Count out of the vector Op in 2128 /// Args. If Count is 0, all of the elements will be extracted. The extracted 2129 /// elements will have type EVT if it is provided, and otherwise their type 2130 /// will be Op's element type. 2131 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args, 2132 unsigned Start = 0, unsigned Count = 0, 2133 EVT EltVT = EVT()); 2134 2135 /// Compute the default alignment value for the given type. 2136 Align getEVTAlign(EVT MemoryVT) const; 2137 2138 /// Test whether the given value is a constant int or similar node. 2139 SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N) const; 2140 2141 /// Test whether the given value is a constant FP or similar node. 2142 SDNode *isConstantFPBuildVectorOrConstantFP(SDValue N) const ; 2143 2144 /// \returns true if \p N is any kind of constant or build_vector of 2145 /// constants, int or float. If a vector, it may not necessarily be a splat. 2146 inline bool isConstantValueOfAnyType(SDValue N) const { 2147 return isConstantIntBuildVectorOrConstantInt(N) || 2148 isConstantFPBuildVectorOrConstantFP(N); 2149 } 2150 2151 /// Set CallSiteInfo to be associated with Node. 2152 void addCallSiteInfo(const SDNode *Node, CallSiteInfoImpl &&CallInfo) { 2153 SDCallSiteDbgInfo[Node].CSInfo = std::move(CallInfo); 2154 } 2155 /// Return CallSiteInfo associated with Node, or a default if none exists. 2156 CallSiteInfo getCallSiteInfo(const SDNode *Node) { 2157 auto I = SDCallSiteDbgInfo.find(Node); 2158 return I != SDCallSiteDbgInfo.end() ? std::move(I->second).CSInfo 2159 : CallSiteInfo(); 2160 } 2161 /// Set HeapAllocSite to be associated with Node. 2162 void addHeapAllocSite(const SDNode *Node, MDNode *MD) { 2163 SDCallSiteDbgInfo[Node].HeapAllocSite = MD; 2164 } 2165 /// Return HeapAllocSite associated with Node, or nullptr if none exists. 2166 MDNode *getHeapAllocSite(const SDNode *Node) const { 2167 auto I = SDCallSiteDbgInfo.find(Node); 2168 return I != SDCallSiteDbgInfo.end() ? I->second.HeapAllocSite : nullptr; 2169 } 2170 /// Set NoMergeSiteInfo to be associated with Node if NoMerge is true. 2171 void addNoMergeSiteInfo(const SDNode *Node, bool NoMerge) { 2172 if (NoMerge) 2173 SDCallSiteDbgInfo[Node].NoMerge = NoMerge; 2174 } 2175 /// Return NoMerge info associated with Node. 2176 bool getNoMergeSiteInfo(const SDNode *Node) const { 2177 auto I = SDCallSiteDbgInfo.find(Node); 2178 return I != SDCallSiteDbgInfo.end() ? I->second.NoMerge : false; 2179 } 2180 2181 /// Return the current function's default denormal handling kind for the given 2182 /// floating point type. 2183 DenormalMode getDenormalMode(EVT VT) const { 2184 return MF->getDenormalMode(EVTToAPFloatSemantics(VT)); 2185 } 2186 2187 bool shouldOptForSize() const; 2188 2189 /// Get the (commutative) neutral element for the given opcode, if it exists. 2190 SDValue getNeutralElement(unsigned Opcode, const SDLoc &DL, EVT VT, 2191 SDNodeFlags Flags); 2192 2193 private: 2194 void InsertNode(SDNode *N); 2195 bool RemoveNodeFromCSEMaps(SDNode *N); 2196 void AddModifiedNodeToCSEMaps(SDNode *N); 2197 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); 2198 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, 2199 void *&InsertPos); 2200 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops, 2201 void *&InsertPos); 2202 SDNode *UpdateSDLocOnMergeSDNode(SDNode *N, const SDLoc &loc); 2203 2204 void DeleteNodeNotInCSEMaps(SDNode *N); 2205 void DeallocateNode(SDNode *N); 2206 2207 void allnodes_clear(); 2208 2209 /// Look up the node specified by ID in CSEMap. If it exists, return it. If 2210 /// not, return the insertion token that will make insertion faster. This 2211 /// overload is for nodes other than Constant or ConstantFP, use the other one 2212 /// for those. 2213 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos); 2214 2215 /// Look up the node specified by ID in CSEMap. If it exists, return it. If 2216 /// not, return the insertion token that will make insertion faster. Performs 2217 /// additional processing for constant nodes. 2218 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, const SDLoc &DL, 2219 void *&InsertPos); 2220 2221 /// List of non-single value types. 2222 FoldingSet<SDVTListNode> VTListMap; 2223 2224 /// Maps to auto-CSE operations. 2225 std::vector<CondCodeSDNode*> CondCodeNodes; 2226 2227 std::vector<SDNode*> ValueTypeNodes; 2228 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes; 2229 StringMap<SDNode*> ExternalSymbols; 2230 2231 std::map<std::pair<std::string, unsigned>, SDNode *> TargetExternalSymbols; 2232 DenseMap<MCSymbol *, SDNode *> MCSymbols; 2233 2234 FlagInserter *Inserter = nullptr; 2235 }; 2236 2237 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 2238 using nodes_iterator = pointer_iterator<SelectionDAG::allnodes_iterator>; 2239 2240 static nodes_iterator nodes_begin(SelectionDAG *G) { 2241 return nodes_iterator(G->allnodes_begin()); 2242 } 2243 2244 static nodes_iterator nodes_end(SelectionDAG *G) { 2245 return nodes_iterator(G->allnodes_end()); 2246 } 2247 }; 2248 2249 } // end namespace llvm 2250 2251 #endif // LLVM_CODEGEN_SELECTIONDAG_H 2252