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