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