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