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 getBasicBlock(MachineBasicBlock *MBB, SDLoc dl); 725 SDValue getExternalSymbol(const char *Sym, EVT VT); 726 SDValue getExternalSymbol(const char *Sym, const SDLoc &dl, EVT VT); 727 SDValue getTargetExternalSymbol(const char *Sym, EVT VT, 728 unsigned TargetFlags = 0); 729 SDValue getMCSymbol(MCSymbol *Sym, EVT VT); 730 731 SDValue getValueType(EVT); 732 SDValue getRegister(unsigned Reg, EVT VT); 733 SDValue getRegisterMask(const uint32_t *RegMask); 734 SDValue getEHLabel(const SDLoc &dl, SDValue Root, MCSymbol *Label); 735 SDValue getLabelNode(unsigned Opcode, const SDLoc &dl, SDValue Root, 736 MCSymbol *Label); 737 SDValue getBlockAddress(const BlockAddress *BA, EVT VT, int64_t Offset = 0, 738 bool isTarget = false, unsigned TargetFlags = 0); 739 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT, 740 int64_t Offset = 0, unsigned TargetFlags = 0) { 741 return getBlockAddress(BA, VT, Offset, true, TargetFlags); 742 } 743 744 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, 745 SDValue N) { 746 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, 747 getRegister(Reg, N.getValueType()), N); 748 } 749 750 // This version of the getCopyToReg method takes an extra operand, which 751 // indicates that there is potentially an incoming glue value (if Glue is not 752 // null) and that there should be a glue result. 753 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N, 754 SDValue Glue) { 755 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 756 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue }; 757 return getNode(ISD::CopyToReg, dl, VTs, 758 makeArrayRef(Ops, Glue.getNode() ? 4 : 3)); 759 } 760 761 // Similar to last getCopyToReg() except parameter Reg is a SDValue 762 SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, SDValue Reg, SDValue N, 763 SDValue Glue) { 764 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 765 SDValue Ops[] = { Chain, Reg, N, Glue }; 766 return getNode(ISD::CopyToReg, dl, VTs, 767 makeArrayRef(Ops, Glue.getNode() ? 4 : 3)); 768 } 769 770 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT) { 771 SDVTList VTs = getVTList(VT, MVT::Other); 772 SDValue Ops[] = { Chain, getRegister(Reg, VT) }; 773 return getNode(ISD::CopyFromReg, dl, VTs, Ops); 774 } 775 776 // This version of the getCopyFromReg method takes an extra operand, which 777 // indicates that there is potentially an incoming glue value (if Glue is not 778 // null) and that there should be a glue result. 779 SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT, 780 SDValue Glue) { 781 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue); 782 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue }; 783 return getNode(ISD::CopyFromReg, dl, VTs, 784 makeArrayRef(Ops, Glue.getNode() ? 3 : 2)); 785 } 786 787 SDValue getCondCode(ISD::CondCode Cond); 788 789 /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT, 790 /// which must be a vector type, must match the number of mask elements 791 /// NumElts. An integer mask element equal to -1 is treated as undefined. 792 SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2, 793 ArrayRef<int> Mask); 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<SDValue> Ops) { 800 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later. 801 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops); 802 } 803 804 /// Return an ISD::BUILD_VECTOR node. The number of elements in VT, 805 /// which must be a vector type, must match the number of operands in Ops. 806 /// The operands must have the same type as (or, for integers, a type wider 807 /// than) VT's element type. 808 SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDUse> Ops) { 809 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later. 810 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops); 811 } 812 813 /// Return a splat ISD::BUILD_VECTOR node, consisting of Op splatted to all 814 /// elements. VT must be a vector type. Op's type must be the same as (or, 815 /// for integers, a type wider than) VT's element type. 816 SDValue getSplatBuildVector(EVT VT, const SDLoc &DL, SDValue Op) { 817 // VerifySDNode (via InsertNode) checks BUILD_VECTOR later. 818 if (Op.getOpcode() == ISD::UNDEF) { 819 assert((VT.getVectorElementType() == Op.getValueType() || 820 (VT.isInteger() && 821 VT.getVectorElementType().bitsLE(Op.getValueType()))) && 822 "A splatted value must have a width equal or (for integers) " 823 "greater than the vector element type!"); 824 return getNode(ISD::UNDEF, SDLoc(), VT); 825 } 826 827 SmallVector<SDValue, 16> Ops(VT.getVectorNumElements(), Op); 828 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops); 829 } 830 831 // Return a splat ISD::SPLAT_VECTOR node, consisting of Op splatted to all 832 // elements. 833 SDValue getSplatVector(EVT VT, const SDLoc &DL, SDValue Op) { 834 if (Op.getOpcode() == ISD::UNDEF) { 835 assert((VT.getVectorElementType() == Op.getValueType() || 836 (VT.isInteger() && 837 VT.getVectorElementType().bitsLE(Op.getValueType()))) && 838 "A splatted value must have a width equal or (for integers) " 839 "greater than the vector element type!"); 840 return getNode(ISD::UNDEF, SDLoc(), VT); 841 } 842 return getNode(ISD::SPLAT_VECTOR, DL, VT, Op); 843 } 844 845 /// Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to 846 /// the shuffle node in input but with swapped operands. 847 /// 848 /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3> 849 SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV); 850 851 /// Convert Op, which must be of float type, to the 852 /// float type VT, by either extending or rounding (by truncation). 853 SDValue getFPExtendOrRound(SDValue Op, const SDLoc &DL, EVT VT); 854 855 /// Convert Op, which must be a STRICT operation of float type, to the 856 /// float type VT, by either extending or rounding (by truncation). 857 std::pair<SDValue, SDValue> 858 getStrictFPExtendOrRound(SDValue Op, SDValue Chain, const SDLoc &DL, EVT VT); 859 860 /// Convert Op, which must be of integer type, to the 861 /// integer type VT, by either any-extending or truncating it. 862 SDValue getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 863 864 /// Convert Op, which must be of integer type, to the 865 /// integer type VT, by either sign-extending or truncating it. 866 SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 867 868 /// Convert Op, which must be of integer type, to the 869 /// integer type VT, by either zero-extending or truncating it. 870 SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 871 872 /// Return the expression required to zero extend the Op 873 /// value assuming it was the smaller SrcTy value. 874 SDValue getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT VT); 875 876 /// Convert Op, which must be of integer type, to the integer type VT, by 877 /// either truncating it or performing either zero or sign extension as 878 /// appropriate extension for the pointer's semantics. 879 SDValue getPtrExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT); 880 881 /// Return the expression required to extend the Op as a pointer value 882 /// assuming it was the smaller SrcTy value. This may be either a zero extend 883 /// or a sign extend. 884 SDValue getPtrExtendInReg(SDValue Op, const SDLoc &DL, EVT VT); 885 886 /// Convert Op, which must be of integer type, to the integer type VT, 887 /// by using an extension appropriate for the target's 888 /// BooleanContent for type OpVT or truncating it. 889 SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT); 890 891 /// Create a bitwise NOT operation as (XOR Val, -1). 892 SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT); 893 894 /// Create a logical NOT operation as (XOR Val, BooleanOne). 895 SDValue getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT); 896 897 /// Returns sum of the base pointer and offset. 898 /// Unlike getObjectPtrOffset this does not set NoUnsignedWrap by default. 899 SDValue getMemBasePlusOffset(SDValue Base, TypeSize Offset, const SDLoc &DL, 900 const SDNodeFlags Flags = SDNodeFlags()); 901 SDValue getMemBasePlusOffset(SDValue Base, SDValue Offset, const SDLoc &DL, 902 const SDNodeFlags Flags = SDNodeFlags()); 903 904 /// Create an add instruction with appropriate flags when used for 905 /// addressing some offset of an object. i.e. if a load is split into multiple 906 /// components, create an add nuw from the base pointer to the offset. 907 SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Ptr, TypeSize Offset) { 908 SDNodeFlags Flags; 909 Flags.setNoUnsignedWrap(true); 910 return getMemBasePlusOffset(Ptr, Offset, SL, Flags); 911 } 912 913 SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Ptr, SDValue Offset) { 914 // The object itself can't wrap around the address space, so it shouldn't be 915 // possible for the adds of the offsets to the split parts to overflow. 916 SDNodeFlags Flags; 917 Flags.setNoUnsignedWrap(true); 918 return getMemBasePlusOffset(Ptr, Offset, SL, Flags); 919 } 920 921 /// Return a new CALLSEQ_START node, that starts new call frame, in which 922 /// InSize bytes are set up inside CALLSEQ_START..CALLSEQ_END sequence and 923 /// OutSize specifies part of the frame set up prior to the sequence. 924 SDValue getCALLSEQ_START(SDValue Chain, uint64_t InSize, uint64_t OutSize, 925 const SDLoc &DL) { 926 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 927 SDValue Ops[] = { Chain, 928 getIntPtrConstant(InSize, DL, true), 929 getIntPtrConstant(OutSize, DL, true) }; 930 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops); 931 } 932 933 /// Return a new CALLSEQ_END node, which always must have a 934 /// glue result (to ensure it's not CSE'd). 935 /// CALLSEQ_END does not have a useful SDLoc. 936 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, 937 SDValue InGlue, const SDLoc &DL) { 938 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue); 939 SmallVector<SDValue, 4> Ops; 940 Ops.push_back(Chain); 941 Ops.push_back(Op1); 942 Ops.push_back(Op2); 943 if (InGlue.getNode()) 944 Ops.push_back(InGlue); 945 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops); 946 } 947 948 /// Return true if the result of this operation is always undefined. 949 bool isUndef(unsigned Opcode, ArrayRef<SDValue> Ops); 950 951 /// Return an UNDEF node. UNDEF does not have a useful SDLoc. 952 SDValue getUNDEF(EVT VT) { 953 return getNode(ISD::UNDEF, SDLoc(), VT); 954 } 955 956 /// Return a node that represents the runtime scaling 'MulImm * RuntimeVL'. 957 SDValue getVScale(const SDLoc &DL, EVT VT, APInt MulImm) { 958 assert(MulImm.getMinSignedBits() <= VT.getSizeInBits() && 959 "Immediate does not fit VT"); 960 return getNode(ISD::VSCALE, DL, VT, 961 getConstant(MulImm.sextOrTrunc(VT.getSizeInBits()), DL, VT)); 962 } 963 964 /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc. 965 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) { 966 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT); 967 } 968 969 /// Gets or creates the specified node. 970 /// 971 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, 972 ArrayRef<SDUse> Ops); 973 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, 974 ArrayRef<SDValue> Ops, const SDNodeFlags Flags); 975 SDValue getNode(unsigned Opcode, const SDLoc &DL, ArrayRef<EVT> ResultTys, 976 ArrayRef<SDValue> Ops); 977 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, 978 ArrayRef<SDValue> Ops, const SDNodeFlags Flags); 979 980 // Use flags from current flag inserter. 981 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, 982 ArrayRef<SDValue> Ops); 983 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, 984 ArrayRef<SDValue> Ops); 985 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue Operand); 986 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 987 SDValue N2); 988 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 989 SDValue N2, SDValue N3); 990 991 // Specialize based on number of operands. 992 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT); 993 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue Operand, 994 const SDNodeFlags Flags); 995 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 996 SDValue N2, const SDNodeFlags Flags); 997 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 998 SDValue N2, SDValue N3, const SDNodeFlags Flags); 999 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 1000 SDValue N2, SDValue N3, SDValue N4); 1001 SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1, 1002 SDValue N2, SDValue N3, SDValue N4, SDValue N5); 1003 1004 // Specialize again based on number of operands for nodes with a VTList 1005 // rather than a single VT. 1006 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList); 1007 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N); 1008 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1, 1009 SDValue N2); 1010 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1, 1011 SDValue N2, SDValue N3); 1012 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1, 1013 SDValue N2, SDValue N3, SDValue N4); 1014 SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1, 1015 SDValue N2, SDValue N3, SDValue N4, SDValue N5); 1016 1017 /// Compute a TokenFactor to force all the incoming stack arguments to be 1018 /// loaded from the stack. This is used in tail call lowering to protect 1019 /// stack arguments from being clobbered. 1020 SDValue getStackArgumentTokenFactor(SDValue Chain); 1021 1022 LLVM_ATTRIBUTE_DEPRECATED(SDValue getMemcpy(SDValue Chain, const SDLoc &dl, 1023 SDValue Dst, SDValue Src, 1024 SDValue Size, unsigned Align, 1025 bool isVol, bool AlwaysInline, 1026 bool isTailCall, 1027 MachinePointerInfo DstPtrInfo, 1028 MachinePointerInfo SrcPtrInfo), 1029 "Use the version that takes Align instead") { 1030 return getMemcpy(Chain, dl, Dst, Src, Size, llvm::Align(Align), isVol, 1031 AlwaysInline, isTailCall, DstPtrInfo, SrcPtrInfo); 1032 } 1033 1034 SDValue getMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src, 1035 SDValue Size, Align Alignment, bool isVol, 1036 bool AlwaysInline, bool isTailCall, 1037 MachinePointerInfo DstPtrInfo, 1038 MachinePointerInfo SrcPtrInfo); 1039 1040 LLVM_ATTRIBUTE_DEPRECATED(SDValue getMemmove(SDValue Chain, const SDLoc &dl, 1041 SDValue Dst, SDValue Src, 1042 SDValue Size, unsigned Align, 1043 bool isVol, bool isTailCall, 1044 MachinePointerInfo DstPtrInfo, 1045 MachinePointerInfo SrcPtrInfo), 1046 "Use the version that takes Align instead") { 1047 return getMemmove(Chain, dl, Dst, Src, Size, llvm::Align(Align), isVol, 1048 isTailCall, DstPtrInfo, SrcPtrInfo); 1049 } 1050 SDValue getMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src, 1051 SDValue Size, Align Alignment, bool isVol, bool isTailCall, 1052 MachinePointerInfo DstPtrInfo, 1053 MachinePointerInfo SrcPtrInfo); 1054 1055 LLVM_ATTRIBUTE_DEPRECATED(SDValue getMemset(SDValue Chain, const SDLoc &dl, 1056 SDValue Dst, SDValue Src, 1057 SDValue Size, unsigned Align, 1058 bool isVol, bool isTailCall, 1059 MachinePointerInfo DstPtrInfo), 1060 "Use the version that takes Align instead") { 1061 return getMemset(Chain, dl, Dst, Src, Size, llvm::Align(Align), isVol, 1062 isTailCall, DstPtrInfo); 1063 } 1064 SDValue getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src, 1065 SDValue Size, Align Alignment, bool isVol, bool isTailCall, 1066 MachinePointerInfo DstPtrInfo); 1067 1068 SDValue getAtomicMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, 1069 unsigned DstAlign, SDValue Src, unsigned SrcAlign, 1070 SDValue Size, Type *SizeTy, unsigned ElemSz, 1071 bool isTailCall, MachinePointerInfo DstPtrInfo, 1072 MachinePointerInfo SrcPtrInfo); 1073 1074 SDValue getAtomicMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, 1075 unsigned DstAlign, SDValue Src, unsigned SrcAlign, 1076 SDValue Size, Type *SizeTy, unsigned ElemSz, 1077 bool isTailCall, MachinePointerInfo DstPtrInfo, 1078 MachinePointerInfo SrcPtrInfo); 1079 1080 SDValue getAtomicMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, 1081 unsigned DstAlign, SDValue Value, SDValue Size, 1082 Type *SizeTy, unsigned ElemSz, bool isTailCall, 1083 MachinePointerInfo DstPtrInfo); 1084 1085 /// Helper function to make it easier to build SetCC's if you just have an 1086 /// ISD::CondCode instead of an SDValue. 1087 SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS, 1088 ISD::CondCode Cond, SDValue Chain = SDValue(), 1089 bool IsSignaling = false) { 1090 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() && 1091 "Cannot compare scalars to vectors"); 1092 assert(LHS.getValueType().isVector() == VT.isVector() && 1093 "Cannot compare scalars to vectors"); 1094 assert(Cond != ISD::SETCC_INVALID && 1095 "Cannot create a setCC of an invalid node."); 1096 if (Chain) 1097 return getNode(IsSignaling ? ISD::STRICT_FSETCCS : ISD::STRICT_FSETCC, DL, 1098 {VT, MVT::Other}, {Chain, LHS, RHS, getCondCode(Cond)}); 1099 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 1100 } 1101 1102 /// Helper function to make it easier to build Select's if you just have 1103 /// operands and don't want to check for vector. 1104 SDValue getSelect(const SDLoc &DL, EVT VT, SDValue Cond, SDValue LHS, 1105 SDValue RHS) { 1106 assert(LHS.getValueType() == RHS.getValueType() && 1107 "Cannot use select on differing types"); 1108 assert(VT.isVector() == LHS.getValueType().isVector() && 1109 "Cannot mix vectors and scalars"); 1110 auto Opcode = Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT; 1111 return getNode(Opcode, DL, VT, Cond, LHS, RHS); 1112 } 1113 1114 /// Helper function to make it easier to build SelectCC's if you just have an 1115 /// ISD::CondCode instead of an SDValue. 1116 SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True, 1117 SDValue False, ISD::CondCode Cond) { 1118 return getNode(ISD::SELECT_CC, DL, True.getValueType(), LHS, RHS, True, 1119 False, getCondCode(Cond)); 1120 } 1121 1122 /// Try to simplify a select/vselect into 1 of its operands or a constant. 1123 SDValue simplifySelect(SDValue Cond, SDValue TVal, SDValue FVal); 1124 1125 /// Try to simplify a shift into 1 of its operands or a constant. 1126 SDValue simplifyShift(SDValue X, SDValue Y); 1127 1128 /// Try to simplify a floating-point binary operation into 1 of its operands 1129 /// or a constant. 1130 SDValue simplifyFPBinop(unsigned Opcode, SDValue X, SDValue Y, 1131 SDNodeFlags Flags); 1132 1133 /// VAArg produces a result and token chain, and takes a pointer 1134 /// and a source value as input. 1135 SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1136 SDValue SV, unsigned Align); 1137 1138 /// Gets a node for an atomic cmpxchg op. There are two 1139 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a 1140 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded, 1141 /// a success flag (initially i1), and a chain. 1142 SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT, 1143 SDVTList VTs, SDValue Chain, SDValue Ptr, 1144 SDValue Cmp, SDValue Swp, MachineMemOperand *MMO); 1145 1146 /// Gets a node for an atomic op, produces result (if relevant) 1147 /// and chain and takes 2 operands. 1148 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain, 1149 SDValue Ptr, SDValue Val, MachineMemOperand *MMO); 1150 1151 /// Gets a node for an atomic op, produces result and chain and 1152 /// takes 1 operand. 1153 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, EVT VT, 1154 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO); 1155 1156 /// Gets a node for an atomic op, produces result and chain and takes N 1157 /// operands. 1158 SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, 1159 SDVTList VTList, ArrayRef<SDValue> Ops, 1160 MachineMemOperand *MMO); 1161 1162 /// Creates a MemIntrinsicNode that may produce a 1163 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID, 1164 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not 1165 /// less than FIRST_TARGET_MEMORY_OPCODE. 1166 SDValue getMemIntrinsicNode( 1167 unsigned Opcode, const SDLoc &dl, SDVTList VTList, ArrayRef<SDValue> Ops, 1168 EVT MemVT, MachinePointerInfo PtrInfo, Align Alignment, 1169 MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad | 1170 MachineMemOperand::MOStore, 1171 uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes()); 1172 1173 inline SDValue getMemIntrinsicNode( 1174 unsigned Opcode, const SDLoc &dl, SDVTList VTList, ArrayRef<SDValue> Ops, 1175 EVT MemVT, MachinePointerInfo PtrInfo, MaybeAlign Alignment = None, 1176 MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad | 1177 MachineMemOperand::MOStore, 1178 uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes()) { 1179 // Ensure that codegen never sees alignment 0 1180 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, PtrInfo, 1181 Alignment.getValueOr(getEVTAlign(MemVT)), Flags, 1182 Size, AAInfo); 1183 } 1184 1185 LLVM_ATTRIBUTE_DEPRECATED( 1186 inline SDValue getMemIntrinsicNode( 1187 unsigned Opcode, const SDLoc &dl, SDVTList VTList, 1188 ArrayRef<SDValue> Ops, EVT MemVT, MachinePointerInfo PtrInfo, 1189 unsigned Alignment, 1190 MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad | 1191 MachineMemOperand::MOStore, 1192 uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes()), 1193 "") { 1194 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, PtrInfo, 1195 MaybeAlign(Alignment), Flags, Size, AAInfo); 1196 } 1197 1198 SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList, 1199 ArrayRef<SDValue> Ops, EVT MemVT, 1200 MachineMemOperand *MMO); 1201 1202 /// Creates a LifetimeSDNode that starts (`IsStart==true`) or ends 1203 /// (`IsStart==false`) the lifetime of the portion of `FrameIndex` between 1204 /// offsets `Offset` and `Offset + Size`. 1205 SDValue getLifetimeNode(bool IsStart, const SDLoc &dl, SDValue Chain, 1206 int FrameIndex, int64_t Size, int64_t Offset = -1); 1207 1208 /// Create a MERGE_VALUES node from the given operands. 1209 SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl); 1210 1211 /// Loads are not normal binary operators: their result type is not 1212 /// determined by their operands, and they produce a value AND a token chain. 1213 /// 1214 /// This function will set the MOLoad flag on MMOFlags, but you can set it if 1215 /// you want. The MOStore flag must not be set. 1216 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1217 MachinePointerInfo PtrInfo, 1218 MaybeAlign Alignment = MaybeAlign(), 1219 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1220 const AAMDNodes &AAInfo = AAMDNodes(), 1221 const MDNode *Ranges = nullptr); 1222 /// FIXME: Remove once transition to Align is over. 1223 inline SDValue 1224 getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1225 MachinePointerInfo PtrInfo, unsigned Alignment, 1226 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1227 const AAMDNodes &AAInfo = AAMDNodes(), 1228 const MDNode *Ranges = nullptr) { 1229 return getLoad(VT, dl, Chain, Ptr, PtrInfo, MaybeAlign(Alignment), MMOFlags, 1230 AAInfo, Ranges); 1231 } 1232 SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, 1233 MachineMemOperand *MMO); 1234 SDValue 1235 getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain, 1236 SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT, 1237 MaybeAlign Alignment = MaybeAlign(), 1238 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1239 const AAMDNodes &AAInfo = AAMDNodes()); 1240 /// FIXME: Remove once transition to Align is over. 1241 inline SDValue 1242 getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain, 1243 SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT, 1244 unsigned Alignment, 1245 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1246 const AAMDNodes &AAInfo = AAMDNodes()) { 1247 return getExtLoad(ExtType, dl, VT, Chain, Ptr, PtrInfo, MemVT, 1248 MaybeAlign(Alignment), MMOFlags, AAInfo); 1249 } 1250 SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, 1251 SDValue Chain, SDValue Ptr, EVT MemVT, 1252 MachineMemOperand *MMO); 1253 SDValue getIndexedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base, 1254 SDValue Offset, ISD::MemIndexedMode AM); 1255 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 1256 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 1257 MachinePointerInfo PtrInfo, EVT MemVT, Align Alignment, 1258 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1259 const AAMDNodes &AAInfo = AAMDNodes(), 1260 const MDNode *Ranges = nullptr); 1261 inline SDValue getLoad( 1262 ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, const SDLoc &dl, 1263 SDValue Chain, SDValue Ptr, SDValue Offset, MachinePointerInfo PtrInfo, 1264 EVT MemVT, MaybeAlign Alignment = MaybeAlign(), 1265 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1266 const AAMDNodes &AAInfo = AAMDNodes(), const MDNode *Ranges = nullptr) { 1267 // Ensures that codegen never sees a None Alignment. 1268 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, PtrInfo, MemVT, 1269 Alignment.getValueOr(getEVTAlign(MemVT)), MMOFlags, AAInfo, 1270 Ranges); 1271 } 1272 /// FIXME: Remove once transition to Align is over. 1273 inline SDValue 1274 getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 1275 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 1276 MachinePointerInfo PtrInfo, EVT MemVT, unsigned Alignment, 1277 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1278 const AAMDNodes &AAInfo = AAMDNodes(), 1279 const MDNode *Ranges = nullptr) { 1280 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, PtrInfo, MemVT, 1281 MaybeAlign(Alignment), MMOFlags, AAInfo, Ranges); 1282 } 1283 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, 1284 const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset, 1285 EVT MemVT, MachineMemOperand *MMO); 1286 1287 /// Helper function to build ISD::STORE nodes. 1288 /// 1289 /// This function will set the MOStore flag on MMOFlags, but you can set it if 1290 /// you want. The MOLoad and MOInvariant flags must not be set. 1291 1292 SDValue 1293 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1294 MachinePointerInfo PtrInfo, Align Alignment, 1295 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1296 const AAMDNodes &AAInfo = AAMDNodes()); 1297 inline SDValue 1298 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1299 MachinePointerInfo PtrInfo, MaybeAlign Alignment = MaybeAlign(), 1300 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1301 const AAMDNodes &AAInfo = AAMDNodes()) { 1302 return getStore(Chain, dl, Val, Ptr, PtrInfo, 1303 Alignment.getValueOr(getEVTAlign(Val.getValueType())), 1304 MMOFlags, AAInfo); 1305 } 1306 /// FIXME: Remove once transition to Align is over. 1307 inline SDValue 1308 getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1309 MachinePointerInfo PtrInfo, unsigned Alignment, 1310 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1311 const AAMDNodes &AAInfo = AAMDNodes()) { 1312 return getStore(Chain, dl, Val, Ptr, PtrInfo, MaybeAlign(Alignment), 1313 MMOFlags, AAInfo); 1314 } 1315 SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1316 MachineMemOperand *MMO); 1317 SDValue 1318 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1319 MachinePointerInfo PtrInfo, EVT SVT, Align Alignment, 1320 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1321 const AAMDNodes &AAInfo = AAMDNodes()); 1322 inline SDValue 1323 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1324 MachinePointerInfo PtrInfo, EVT SVT, 1325 MaybeAlign Alignment = MaybeAlign(), 1326 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1327 const AAMDNodes &AAInfo = AAMDNodes()) { 1328 return getTruncStore(Chain, dl, Val, Ptr, PtrInfo, SVT, 1329 Alignment.getValueOr(getEVTAlign(SVT)), MMOFlags, 1330 AAInfo); 1331 } 1332 /// FIXME: Remove once transition to Align is over. 1333 inline SDValue 1334 getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, 1335 MachinePointerInfo PtrInfo, EVT SVT, unsigned Alignment, 1336 MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone, 1337 const AAMDNodes &AAInfo = AAMDNodes()) { 1338 return getTruncStore(Chain, dl, Val, Ptr, PtrInfo, SVT, 1339 MaybeAlign(Alignment), MMOFlags, AAInfo); 1340 } 1341 SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, 1342 SDValue Ptr, EVT SVT, MachineMemOperand *MMO); 1343 SDValue getIndexedStore(SDValue OrigStore, const SDLoc &dl, SDValue Base, 1344 SDValue Offset, ISD::MemIndexedMode AM); 1345 1346 SDValue getMaskedLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Base, 1347 SDValue Offset, SDValue Mask, SDValue Src0, EVT MemVT, 1348 MachineMemOperand *MMO, ISD::MemIndexedMode AM, 1349 ISD::LoadExtType, bool IsExpanding = false); 1350 SDValue getIndexedMaskedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base, 1351 SDValue Offset, ISD::MemIndexedMode AM); 1352 SDValue getMaskedStore(SDValue Chain, const SDLoc &dl, SDValue Val, 1353 SDValue Base, SDValue Offset, SDValue Mask, EVT MemVT, 1354 MachineMemOperand *MMO, ISD::MemIndexedMode AM, 1355 bool IsTruncating = false, bool IsCompressing = false); 1356 SDValue getIndexedMaskedStore(SDValue OrigStore, const SDLoc &dl, 1357 SDValue Base, SDValue Offset, 1358 ISD::MemIndexedMode AM); 1359 SDValue getMaskedGather(SDVTList VTs, EVT VT, const SDLoc &dl, 1360 ArrayRef<SDValue> Ops, MachineMemOperand *MMO, 1361 ISD::MemIndexType IndexType); 1362 SDValue getMaskedScatter(SDVTList VTs, EVT VT, const SDLoc &dl, 1363 ArrayRef<SDValue> Ops, MachineMemOperand *MMO, 1364 ISD::MemIndexType IndexType, 1365 bool IsTruncating = false); 1366 1367 /// Construct a node to track a Value* through the backend. 1368 SDValue getSrcValue(const Value *v); 1369 1370 /// Return an MDNodeSDNode which holds an MDNode. 1371 SDValue getMDNode(const MDNode *MD); 1372 1373 /// Return a bitcast using the SDLoc of the value operand, and casting to the 1374 /// provided type. Use getNode to set a custom SDLoc. 1375 SDValue getBitcast(EVT VT, SDValue V); 1376 1377 /// Return an AddrSpaceCastSDNode. 1378 SDValue getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr, unsigned SrcAS, 1379 unsigned DestAS); 1380 1381 /// Return a freeze using the SDLoc of the value operand. 1382 SDValue getFreeze(SDValue V); 1383 1384 /// Return an AssertAlignSDNode. 1385 SDValue getAssertAlign(const SDLoc &DL, SDValue V, Align A); 1386 1387 /// Return the specified value casted to 1388 /// the target's desired shift amount type. 1389 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op); 1390 1391 /// Expand the specified \c ISD::VAARG node as the Legalize pass would. 1392 SDValue expandVAArg(SDNode *Node); 1393 1394 /// Expand the specified \c ISD::VACOPY node as the Legalize pass would. 1395 SDValue expandVACopy(SDNode *Node); 1396 1397 /// Returs an GlobalAddress of the function from the current module with 1398 /// name matching the given ExternalSymbol. Additionally can provide the 1399 /// matched function. 1400 /// Panics the function doesn't exists. 1401 SDValue getSymbolFunctionGlobalAddress(SDValue Op, 1402 Function **TargetFunction = nullptr); 1403 1404 /// *Mutate* the specified node in-place to have the 1405 /// specified operands. If the resultant node already exists in the DAG, 1406 /// this does not modify the specified node, instead it returns the node that 1407 /// already exists. If the resultant node does not exist in the DAG, the 1408 /// input node is returned. As a degenerate case, if you specify the same 1409 /// input operands as the node already has, the input node is returned. 1410 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op); 1411 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2); 1412 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 1413 SDValue Op3); 1414 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 1415 SDValue Op3, SDValue Op4); 1416 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 1417 SDValue Op3, SDValue Op4, SDValue Op5); 1418 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops); 1419 1420 /// Creates a new TokenFactor containing \p Vals. If \p Vals contains 64k 1421 /// values or more, move values into new TokenFactors in 64k-1 blocks, until 1422 /// the final TokenFactor has less than 64k operands. 1423 SDValue getTokenFactor(const SDLoc &DL, SmallVectorImpl<SDValue> &Vals); 1424 1425 /// *Mutate* the specified machine node's memory references to the provided 1426 /// list. 1427 void setNodeMemRefs(MachineSDNode *N, 1428 ArrayRef<MachineMemOperand *> NewMemRefs); 1429 1430 // Calculate divergence of node \p N based on its operands. 1431 bool calculateDivergence(SDNode *N); 1432 1433 // Propagates the change in divergence to users 1434 void updateDivergence(SDNode * N); 1435 1436 /// These are used for target selectors to *mutate* the 1437 /// specified node to have the specified return type, Target opcode, and 1438 /// operands. Note that target opcodes are stored as 1439 /// ~TargetOpcode in the node opcode field. The resultant node is returned. 1440 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT); 1441 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, SDValue Op1); 1442 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, 1443 SDValue Op1, SDValue Op2); 1444 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, 1445 SDValue Op1, SDValue Op2, SDValue Op3); 1446 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, 1447 ArrayRef<SDValue> Ops); 1448 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, EVT VT2); 1449 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 1450 EVT VT2, ArrayRef<SDValue> Ops); 1451 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 1452 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops); 1453 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 1454 EVT VT2, SDValue Op1); 1455 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 1456 EVT VT2, SDValue Op1, SDValue Op2); 1457 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, SDVTList VTs, 1458 ArrayRef<SDValue> Ops); 1459 1460 /// This *mutates* the specified node to have the specified 1461 /// return type, opcode, and operands. 1462 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, 1463 ArrayRef<SDValue> Ops); 1464 1465 /// Mutate the specified strict FP node to its non-strict equivalent, 1466 /// unlinking the node from its chain and dropping the metadata arguments. 1467 /// The node must be a strict FP node. 1468 SDNode *mutateStrictFPToFP(SDNode *Node); 1469 1470 /// These are used for target selectors to create a new node 1471 /// with specified return type(s), MachineInstr opcode, and operands. 1472 /// 1473 /// Note that getMachineNode returns the resultant node. If there is already 1474 /// a node of the specified opcode and operands, it returns that node instead 1475 /// of the current one. 1476 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT); 1477 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1478 SDValue Op1); 1479 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1480 SDValue Op1, SDValue Op2); 1481 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1482 SDValue Op1, SDValue Op2, SDValue Op3); 1483 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT, 1484 ArrayRef<SDValue> Ops); 1485 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1486 EVT VT2, SDValue Op1, SDValue Op2); 1487 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1488 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 1489 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1490 EVT VT2, ArrayRef<SDValue> Ops); 1491 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1492 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2); 1493 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1494 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, 1495 SDValue Op3); 1496 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1, 1497 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops); 1498 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, 1499 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops); 1500 MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, SDVTList VTs, 1501 ArrayRef<SDValue> Ops); 1502 1503 /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes. 1504 SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT, 1505 SDValue Operand); 1506 1507 /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes. 1508 SDValue getTargetInsertSubreg(int SRIdx, const SDLoc &DL, EVT VT, 1509 SDValue Operand, SDValue Subreg); 1510 1511 /// Get the specified node if it's already available, or else return NULL. 1512 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTList, 1513 ArrayRef<SDValue> Ops, const SDNodeFlags Flags); 1514 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTList, 1515 ArrayRef<SDValue> Ops); 1516 1517 /// Creates a SDDbgValue node. 1518 SDDbgValue *getDbgValue(DIVariable *Var, DIExpression *Expr, SDNode *N, 1519 unsigned R, bool IsIndirect, const DebugLoc &DL, 1520 unsigned O); 1521 1522 /// Creates a constant SDDbgValue node. 1523 SDDbgValue *getConstantDbgValue(DIVariable *Var, DIExpression *Expr, 1524 const Value *C, const DebugLoc &DL, 1525 unsigned O); 1526 1527 /// Creates a FrameIndex SDDbgValue node. 1528 SDDbgValue *getFrameIndexDbgValue(DIVariable *Var, DIExpression *Expr, 1529 unsigned FI, bool IsIndirect, 1530 const DebugLoc &DL, unsigned O); 1531 1532 /// Creates a VReg SDDbgValue node. 1533 SDDbgValue *getVRegDbgValue(DIVariable *Var, DIExpression *Expr, 1534 unsigned VReg, bool IsIndirect, 1535 const DebugLoc &DL, unsigned O); 1536 1537 /// Creates a SDDbgLabel node. 1538 SDDbgLabel *getDbgLabel(DILabel *Label, const DebugLoc &DL, unsigned O); 1539 1540 /// Transfer debug values from one node to another, while optionally 1541 /// generating fragment expressions for split-up values. If \p InvalidateDbg 1542 /// is set, debug values are invalidated after they are transferred. 1543 void transferDbgValues(SDValue From, SDValue To, unsigned OffsetInBits = 0, 1544 unsigned SizeInBits = 0, bool InvalidateDbg = true); 1545 1546 /// Remove the specified node from the system. If any of its 1547 /// operands then becomes dead, remove them as well. Inform UpdateListener 1548 /// for each node deleted. 1549 void RemoveDeadNode(SDNode *N); 1550 1551 /// This method deletes the unreachable nodes in the 1552 /// given list, and any nodes that become unreachable as a result. 1553 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes); 1554 1555 /// Modify anything using 'From' to use 'To' instead. 1556 /// This can cause recursive merging of nodes in the DAG. Use the first 1557 /// version if 'From' is known to have a single result, use the second 1558 /// if you have two nodes with identical results (or if 'To' has a superset 1559 /// of the results of 'From'), use the third otherwise. 1560 /// 1561 /// These methods all take an optional UpdateListener, which (if not null) is 1562 /// informed about nodes that are deleted and modified due to recursive 1563 /// changes in the dag. 1564 /// 1565 /// These functions only replace all existing uses. It's possible that as 1566 /// these replacements are being performed, CSE may cause the From node 1567 /// to be given new uses. These new uses of From are left in place, and 1568 /// not automatically transferred to To. 1569 /// 1570 void ReplaceAllUsesWith(SDValue From, SDValue To); 1571 void ReplaceAllUsesWith(SDNode *From, SDNode *To); 1572 void ReplaceAllUsesWith(SDNode *From, const SDValue *To); 1573 1574 /// Replace any uses of From with To, leaving 1575 /// uses of other values produced by From.getNode() alone. 1576 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To); 1577 1578 /// Like ReplaceAllUsesOfValueWith, but for multiple values at once. 1579 /// This correctly handles the case where 1580 /// there is an overlap between the From values and the To values. 1581 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, 1582 unsigned Num); 1583 1584 /// If an existing load has uses of its chain, create a token factor node with 1585 /// that chain and the new memory node's chain and update users of the old 1586 /// chain to the token factor. This ensures that the new memory node will have 1587 /// the same relative memory dependency position as the old load. Returns the 1588 /// new merged load chain. 1589 SDValue makeEquivalentMemoryOrdering(LoadSDNode *Old, SDValue New); 1590 1591 /// Topological-sort the AllNodes list and a 1592 /// assign a unique node id for each node in the DAG based on their 1593 /// topological order. Returns the number of nodes. 1594 unsigned AssignTopologicalOrder(); 1595 1596 /// Move node N in the AllNodes list to be immediately 1597 /// before the given iterator Position. This may be used to update the 1598 /// topological ordering when the list of nodes is modified. 1599 void RepositionNode(allnodes_iterator Position, SDNode *N) { 1600 AllNodes.insert(Position, AllNodes.remove(N)); 1601 } 1602 1603 /// Returns an APFloat semantics tag appropriate for the given type. If VT is 1604 /// a vector type, the element semantics are returned. 1605 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) { 1606 switch (VT.getScalarType().getSimpleVT().SimpleTy) { 1607 default: llvm_unreachable("Unknown FP format"); 1608 case MVT::f16: return APFloat::IEEEhalf(); 1609 case MVT::bf16: return APFloat::BFloat(); 1610 case MVT::f32: return APFloat::IEEEsingle(); 1611 case MVT::f64: return APFloat::IEEEdouble(); 1612 case MVT::f80: return APFloat::x87DoubleExtended(); 1613 case MVT::f128: return APFloat::IEEEquad(); 1614 case MVT::ppcf128: return APFloat::PPCDoubleDouble(); 1615 } 1616 } 1617 1618 /// Add a dbg_value SDNode. If SD is non-null that means the 1619 /// value is produced by SD. 1620 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter); 1621 1622 /// Add a dbg_label SDNode. 1623 void AddDbgLabel(SDDbgLabel *DB); 1624 1625 /// Get the debug values which reference the given SDNode. 1626 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) const { 1627 return DbgInfo->getSDDbgValues(SD); 1628 } 1629 1630 public: 1631 /// Return true if there are any SDDbgValue nodes associated 1632 /// with this SelectionDAG. 1633 bool hasDebugValues() const { return !DbgInfo->empty(); } 1634 1635 SDDbgInfo::DbgIterator DbgBegin() const { return DbgInfo->DbgBegin(); } 1636 SDDbgInfo::DbgIterator DbgEnd() const { return DbgInfo->DbgEnd(); } 1637 1638 SDDbgInfo::DbgIterator ByvalParmDbgBegin() const { 1639 return DbgInfo->ByvalParmDbgBegin(); 1640 } 1641 SDDbgInfo::DbgIterator ByvalParmDbgEnd() const { 1642 return DbgInfo->ByvalParmDbgEnd(); 1643 } 1644 1645 SDDbgInfo::DbgLabelIterator DbgLabelBegin() const { 1646 return DbgInfo->DbgLabelBegin(); 1647 } 1648 SDDbgInfo::DbgLabelIterator DbgLabelEnd() const { 1649 return DbgInfo->DbgLabelEnd(); 1650 } 1651 1652 /// To be invoked on an SDNode that is slated to be erased. This 1653 /// function mirrors \c llvm::salvageDebugInfo. 1654 void salvageDebugInfo(SDNode &N); 1655 1656 void dump() const; 1657 1658 /// In most cases this function returns the ABI alignment for a given type, 1659 /// except for illegal vector types where the alignment exceeds that of the 1660 /// stack. In such cases we attempt to break the vector down to a legal type 1661 /// and return the ABI alignment for that instead. 1662 Align getReducedAlign(EVT VT, bool UseABI); 1663 1664 /// Create a stack temporary based on the size in bytes and the alignment 1665 SDValue CreateStackTemporary(TypeSize Bytes, Align Alignment); 1666 1667 /// Create a stack temporary, suitable for holding the specified value type. 1668 /// If minAlign is specified, the slot size will have at least that alignment. 1669 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1); 1670 1671 /// Create a stack temporary suitable for holding either of the specified 1672 /// value types. 1673 SDValue CreateStackTemporary(EVT VT1, EVT VT2); 1674 1675 SDValue FoldSymbolOffset(unsigned Opcode, EVT VT, 1676 const GlobalAddressSDNode *GA, 1677 const SDNode *N2); 1678 1679 SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT, 1680 ArrayRef<SDValue> Ops); 1681 1682 SDValue FoldConstantVectorArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT, 1683 ArrayRef<SDValue> Ops, 1684 const SDNodeFlags Flags = SDNodeFlags()); 1685 1686 /// Fold floating-point operations with 2 operands when both operands are 1687 /// constants and/or undefined. 1688 SDValue foldConstantFPMath(unsigned Opcode, const SDLoc &DL, EVT VT, 1689 SDValue N1, SDValue N2); 1690 1691 /// Constant fold a setcc to true or false. 1692 SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond, 1693 const SDLoc &dl); 1694 1695 /// See if the specified operand can be simplified with the knowledge that 1696 /// only the bits specified by DemandedBits are used. If so, return the 1697 /// simpler operand, otherwise return a null SDValue. 1698 /// 1699 /// (This exists alongside SimplifyDemandedBits because GetDemandedBits can 1700 /// simplify nodes with multiple uses more aggressively.) 1701 SDValue GetDemandedBits(SDValue V, const APInt &DemandedBits); 1702 1703 /// See if the specified operand can be simplified with the knowledge that 1704 /// only the bits specified by DemandedBits are used in the elements specified 1705 /// by DemandedElts. If so, return the simpler operand, otherwise return a 1706 /// null SDValue. 1707 /// 1708 /// (This exists alongside SimplifyDemandedBits because GetDemandedBits can 1709 /// simplify nodes with multiple uses more aggressively.) 1710 SDValue GetDemandedBits(SDValue V, const APInt &DemandedBits, 1711 const APInt &DemandedElts); 1712 1713 /// Return true if the sign bit of Op is known to be zero. 1714 /// We use this predicate to simplify operations downstream. 1715 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const; 1716 1717 /// Return true if 'Op & Mask' is known to be zero. We 1718 /// use this predicate to simplify operations downstream. Op and Mask are 1719 /// known to be the same type. 1720 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, 1721 unsigned Depth = 0) const; 1722 1723 /// Return true if 'Op & Mask' is known to be zero in DemandedElts. We 1724 /// use this predicate to simplify operations downstream. Op and Mask are 1725 /// known to be the same type. 1726 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, 1727 const APInt &DemandedElts, unsigned Depth = 0) const; 1728 1729 /// Return true if '(Op & Mask) == Mask'. 1730 /// Op and Mask are known to be the same type. 1731 bool MaskedValueIsAllOnes(SDValue Op, const APInt &Mask, 1732 unsigned Depth = 0) const; 1733 1734 /// Determine which bits of Op are known to be either zero or one and return 1735 /// them in Known. For vectors, the known bits are those that are shared by 1736 /// every vector element. 1737 /// Targets can implement the computeKnownBitsForTargetNode method in the 1738 /// TargetLowering class to allow target nodes to be understood. 1739 KnownBits computeKnownBits(SDValue Op, unsigned Depth = 0) const; 1740 1741 /// Determine which bits of Op are known to be either zero or one and return 1742 /// them in Known. The DemandedElts argument allows us to only collect the 1743 /// known bits that are shared by the requested vector elements. 1744 /// Targets can implement the computeKnownBitsForTargetNode method in the 1745 /// TargetLowering class to allow target nodes to be understood. 1746 KnownBits computeKnownBits(SDValue Op, const APInt &DemandedElts, 1747 unsigned Depth = 0) const; 1748 1749 /// Used to represent the possible overflow behavior of an operation. 1750 /// Never: the operation cannot overflow. 1751 /// Always: the operation will always overflow. 1752 /// Sometime: the operation may or may not overflow. 1753 enum OverflowKind { 1754 OFK_Never, 1755 OFK_Sometime, 1756 OFK_Always, 1757 }; 1758 1759 /// Determine if the result of the addition of 2 node can overflow. 1760 OverflowKind computeOverflowKind(SDValue N0, SDValue N1) const; 1761 1762 /// Test if the given value is known to have exactly one bit set. This differs 1763 /// from computeKnownBits in that it doesn't necessarily determine which bit 1764 /// is set. 1765 bool isKnownToBeAPowerOfTwo(SDValue Val) const; 1766 1767 /// Return the number of times the sign bit of the register is replicated into 1768 /// the other bits. We know that at least 1 bit is always equal to the sign 1769 /// bit (itself), but other cases can give us information. For example, 1770 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal 1771 /// to each other, so we return 3. Targets can implement the 1772 /// ComputeNumSignBitsForTarget method in the TargetLowering class to allow 1773 /// target nodes to be understood. 1774 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; 1775 1776 /// Return the number of times the sign bit of the register is replicated into 1777 /// the other bits. We know that at least 1 bit is always equal to the sign 1778 /// bit (itself), but other cases can give us information. For example, 1779 /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal 1780 /// to each other, so we return 3. The DemandedElts argument allows 1781 /// us to only collect the minimum sign bits of the requested vector elements. 1782 /// Targets can implement the ComputeNumSignBitsForTarget method in the 1783 /// TargetLowering class to allow target nodes to be understood. 1784 unsigned ComputeNumSignBits(SDValue Op, const APInt &DemandedElts, 1785 unsigned Depth = 0) const; 1786 1787 /// Return true if the specified operand is an ISD::ADD with a ConstantSDNode 1788 /// on the right-hand side, or if it is an ISD::OR with a ConstantSDNode that 1789 /// is guaranteed to have the same semantics as an ADD. This handles the 1790 /// equivalence: 1791 /// X|Cst == X+Cst iff X&Cst = 0. 1792 bool isBaseWithConstantOffset(SDValue Op) const; 1793 1794 /// Test whether the given SDValue is known to never be NaN. If \p SNaN is 1795 /// true, returns if \p Op is known to never be a signaling NaN (it may still 1796 /// be a qNaN). 1797 bool isKnownNeverNaN(SDValue Op, bool SNaN = false, unsigned Depth = 0) const; 1798 1799 /// \returns true if \p Op is known to never be a signaling NaN. 1800 bool isKnownNeverSNaN(SDValue Op, unsigned Depth = 0) const { 1801 return isKnownNeverNaN(Op, true, Depth); 1802 } 1803 1804 /// Test whether the given floating point SDValue is known to never be 1805 /// positive or negative zero. 1806 bool isKnownNeverZeroFloat(SDValue Op) const; 1807 1808 /// Test whether the given SDValue is known to contain non-zero value(s). 1809 bool isKnownNeverZero(SDValue Op) const; 1810 1811 /// Test whether two SDValues are known to compare equal. This 1812 /// is true if they are the same value, or if one is negative zero and the 1813 /// other positive zero. 1814 bool isEqualTo(SDValue A, SDValue B) const; 1815 1816 /// Return true if A and B have no common bits set. As an example, this can 1817 /// allow an 'add' to be transformed into an 'or'. 1818 bool haveNoCommonBitsSet(SDValue A, SDValue B) const; 1819 1820 /// Test whether \p V has a splatted value for all the demanded elements. 1821 /// 1822 /// On success \p UndefElts will indicate the elements that have UNDEF 1823 /// values instead of the splat value, this is only guaranteed to be correct 1824 /// for \p DemandedElts. 1825 /// 1826 /// NOTE: The function will return true for a demanded splat of UNDEF values. 1827 bool isSplatValue(SDValue V, const APInt &DemandedElts, APInt &UndefElts); 1828 1829 /// Test whether \p V has a splatted value. 1830 bool isSplatValue(SDValue V, bool AllowUndefs = false); 1831 1832 /// If V is a splatted value, return the source vector and its splat index. 1833 SDValue getSplatSourceVector(SDValue V, int &SplatIndex); 1834 1835 /// If V is a splat vector, return its scalar source operand by extracting 1836 /// that element from the source vector. 1837 SDValue getSplatValue(SDValue V); 1838 1839 /// If a SHL/SRA/SRL node \p V has a constant or splat constant shift amount 1840 /// that is less than the element bit-width of the shift node, return it. 1841 const APInt *getValidShiftAmountConstant(SDValue V, 1842 const APInt &DemandedElts) const; 1843 1844 /// If a SHL/SRA/SRL node \p V has constant shift amounts that are all less 1845 /// than the element bit-width of the shift node, return the minimum value. 1846 const APInt * 1847 getValidMinimumShiftAmountConstant(SDValue V, 1848 const APInt &DemandedElts) const; 1849 1850 /// If a SHL/SRA/SRL node \p V has constant shift amounts that are all less 1851 /// than the element bit-width of the shift node, return the maximum value. 1852 const APInt * 1853 getValidMaximumShiftAmountConstant(SDValue V, 1854 const APInt &DemandedElts) const; 1855 1856 /// Match a binop + shuffle pyramid that represents a horizontal reduction 1857 /// over the elements of a vector starting from the EXTRACT_VECTOR_ELT node /p 1858 /// Extract. The reduction must use one of the opcodes listed in /p 1859 /// CandidateBinOps and on success /p BinOp will contain the matching opcode. 1860 /// Returns the vector that is being reduced on, or SDValue() if a reduction 1861 /// was not matched. If \p AllowPartials is set then in the case of a 1862 /// reduction pattern that only matches the first few stages, the extracted 1863 /// subvector of the start of the reduction is returned. 1864 SDValue matchBinOpReduction(SDNode *Extract, ISD::NodeType &BinOp, 1865 ArrayRef<ISD::NodeType> CandidateBinOps, 1866 bool AllowPartials = false); 1867 1868 /// Utility function used by legalize and lowering to 1869 /// "unroll" a vector operation by splitting out the scalars and operating 1870 /// on each element individually. If the ResNE is 0, fully unroll the vector 1871 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE. 1872 /// If the ResNE is greater than the width of the vector op, unroll the 1873 /// vector op and fill the end of the resulting vector with UNDEFS. 1874 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0); 1875 1876 /// Like UnrollVectorOp(), but for the [US](ADD|SUB|MUL)O family of opcodes. 1877 /// This is a separate function because those opcodes have two results. 1878 std::pair<SDValue, SDValue> UnrollVectorOverflowOp(SDNode *N, 1879 unsigned ResNE = 0); 1880 1881 /// Return true if loads are next to each other and can be 1882 /// merged. Check that both are nonvolatile and if LD is loading 1883 /// 'Bytes' bytes from a location that is 'Dist' units away from the 1884 /// location that the 'Base' load is loading from. 1885 bool areNonVolatileConsecutiveLoads(LoadSDNode *LD, LoadSDNode *Base, 1886 unsigned Bytes, int Dist) const; 1887 1888 /// Infer alignment of a load / store address. Return None if it cannot be 1889 /// inferred. 1890 MaybeAlign InferPtrAlign(SDValue Ptr) const; 1891 1892 LLVM_ATTRIBUTE_DEPRECATED(inline unsigned InferPtrAlignment(SDValue Ptr) 1893 const, 1894 "Use InferPtrAlign instead") { 1895 if (auto A = InferPtrAlign(Ptr)) 1896 return A->value(); 1897 return 0; 1898 } 1899 1900 /// Compute the VTs needed for the low/hi parts of a type 1901 /// which is split (or expanded) into two not necessarily identical pieces. 1902 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const; 1903 1904 /// Compute the VTs needed for the low/hi parts of a type, dependent on an 1905 /// enveloping VT that has been split into two identical pieces. Sets the 1906 /// HisIsEmpty flag when hi type has zero storage size. 1907 std::pair<EVT, EVT> GetDependentSplitDestVTs(const EVT &VT, const EVT &EnvVT, 1908 bool *HiIsEmpty) const; 1909 1910 /// Split the vector with EXTRACT_SUBVECTOR using the provides 1911 /// VTs and return the low/high part. 1912 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL, 1913 const EVT &LoVT, const EVT &HiVT); 1914 1915 /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part. 1916 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) { 1917 EVT LoVT, HiVT; 1918 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType()); 1919 return SplitVector(N, DL, LoVT, HiVT); 1920 } 1921 1922 /// Split the node's operand with EXTRACT_SUBVECTOR and 1923 /// return the low/high part. 1924 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo) 1925 { 1926 return SplitVector(N->getOperand(OpNo), SDLoc(N)); 1927 } 1928 1929 /// Widen the vector up to the next power of two using INSERT_SUBVECTOR. 1930 SDValue WidenVector(const SDValue &N, const SDLoc &DL); 1931 1932 /// Append the extracted elements from Start to Count out of the vector Op in 1933 /// Args. If Count is 0, all of the elements will be extracted. The extracted 1934 /// elements will have type EVT if it is provided, and otherwise their type 1935 /// will be Op's element type. 1936 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args, 1937 unsigned Start = 0, unsigned Count = 0, 1938 EVT EltVT = EVT()); 1939 1940 /// Compute the default alignment value for the given type. 1941 Align getEVTAlign(EVT MemoryVT) const; 1942 /// Compute the default alignment value for the given type. 1943 /// FIXME: Remove once transition to Align is over. 1944 inline unsigned getEVTAlignment(EVT MemoryVT) const { 1945 return getEVTAlign(MemoryVT).value(); 1946 } 1947 1948 /// Test whether the given value is a constant int or similar node. 1949 SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N); 1950 1951 /// Test whether the given value is a constant FP or similar node. 1952 SDNode *isConstantFPBuildVectorOrConstantFP(SDValue N); 1953 1954 /// \returns true if \p N is any kind of constant or build_vector of 1955 /// constants, int or float. If a vector, it may not necessarily be a splat. 1956 inline bool isConstantValueOfAnyType(SDValue N) { 1957 return isConstantIntBuildVectorOrConstantInt(N) || 1958 isConstantFPBuildVectorOrConstantFP(N); 1959 } 1960 1961 void addCallSiteInfo(const SDNode *CallNode, CallSiteInfoImpl &&CallInfo) { 1962 SDCallSiteDbgInfo[CallNode].CSInfo = std::move(CallInfo); 1963 } 1964 1965 CallSiteInfo getSDCallSiteInfo(const SDNode *CallNode) { 1966 auto I = SDCallSiteDbgInfo.find(CallNode); 1967 if (I != SDCallSiteDbgInfo.end()) 1968 return std::move(I->second).CSInfo; 1969 return CallSiteInfo(); 1970 } 1971 1972 void addHeapAllocSite(const SDNode *Node, MDNode *MD) { 1973 SDCallSiteDbgInfo[Node].HeapAllocSite = MD; 1974 } 1975 1976 /// Return the HeapAllocSite type associated with the SDNode, if it exists. 1977 MDNode *getHeapAllocSite(const SDNode *Node) { 1978 auto It = SDCallSiteDbgInfo.find(Node); 1979 if (It == SDCallSiteDbgInfo.end()) 1980 return nullptr; 1981 return It->second.HeapAllocSite; 1982 } 1983 1984 void addNoMergeSiteInfo(const SDNode *Node, bool NoMerge) { 1985 if (NoMerge) 1986 SDCallSiteDbgInfo[Node].NoMerge = NoMerge; 1987 } 1988 1989 bool getNoMergeSiteInfo(const SDNode *Node) { 1990 auto I = SDCallSiteDbgInfo.find(Node); 1991 if (I == SDCallSiteDbgInfo.end()) 1992 return false; 1993 return I->second.NoMerge; 1994 } 1995 1996 /// Return the current function's default denormal handling kind for the given 1997 /// floating point type. 1998 DenormalMode getDenormalMode(EVT VT) const { 1999 return MF->getDenormalMode(EVTToAPFloatSemantics(VT)); 2000 } 2001 2002 bool shouldOptForSize() const; 2003 2004 /// Get the (commutative) neutral element for the given opcode, if it exists. 2005 SDValue getNeutralElement(unsigned Opcode, const SDLoc &DL, EVT VT, 2006 SDNodeFlags Flags); 2007 2008 private: 2009 void InsertNode(SDNode *N); 2010 bool RemoveNodeFromCSEMaps(SDNode *N); 2011 void AddModifiedNodeToCSEMaps(SDNode *N); 2012 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); 2013 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, 2014 void *&InsertPos); 2015 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops, 2016 void *&InsertPos); 2017 SDNode *UpdateSDLocOnMergeSDNode(SDNode *N, const SDLoc &loc); 2018 2019 void DeleteNodeNotInCSEMaps(SDNode *N); 2020 void DeallocateNode(SDNode *N); 2021 2022 void allnodes_clear(); 2023 2024 /// Look up the node specified by ID in CSEMap. If it exists, return it. If 2025 /// not, return the insertion token that will make insertion faster. This 2026 /// overload is for nodes other than Constant or ConstantFP, use the other one 2027 /// for those. 2028 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos); 2029 2030 /// Look up the node specified by ID in CSEMap. If it exists, return it. If 2031 /// not, return the insertion token that will make insertion faster. Performs 2032 /// additional processing for constant nodes. 2033 SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, const SDLoc &DL, 2034 void *&InsertPos); 2035 2036 /// List of non-single value types. 2037 FoldingSet<SDVTListNode> VTListMap; 2038 2039 /// Maps to auto-CSE operations. 2040 std::vector<CondCodeSDNode*> CondCodeNodes; 2041 2042 std::vector<SDNode*> ValueTypeNodes; 2043 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes; 2044 StringMap<SDNode*> ExternalSymbols; 2045 2046 std::map<std::pair<std::string, unsigned>, SDNode *> TargetExternalSymbols; 2047 DenseMap<MCSymbol *, SDNode *> MCSymbols; 2048 2049 FlagInserter *Inserter = nullptr; 2050 }; 2051 2052 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 2053 using nodes_iterator = pointer_iterator<SelectionDAG::allnodes_iterator>; 2054 2055 static nodes_iterator nodes_begin(SelectionDAG *G) { 2056 return nodes_iterator(G->allnodes_begin()); 2057 } 2058 2059 static nodes_iterator nodes_end(SelectionDAG *G) { 2060 return nodes_iterator(G->allnodes_end()); 2061 } 2062 }; 2063 2064 } // end namespace llvm 2065 2066 #endif // LLVM_CODEGEN_SELECTIONDAG_H 2067