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