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