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/DenseSet.h" 19 #include "llvm/ADT/StringMap.h" 20 #include "llvm/ADT/ilist.h" 21 #include "llvm/CodeGen/DAGCombine.h" 22 #include "llvm/CodeGen/SelectionDAGNodes.h" 23 #include "llvm/Support/RecyclingAllocator.h" 24 #include "llvm/Target/TargetMachine.h" 25 #include <cassert> 26 #include <map> 27 #include <string> 28 #include <vector> 29 30 namespace llvm { 31 32 class AliasAnalysis; 33 class MachineConstantPoolValue; 34 class MachineFunction; 35 class MDNode; 36 class SDDbgValue; 37 class TargetLowering; 38 class TargetSelectionDAGInfo; 39 40 class SDVTListNode : public FoldingSetNode { 41 friend struct FoldingSetTrait<SDVTListNode>; 42 /// FastID - A reference to an Interned FoldingSetNodeID for this node. 43 /// The Allocator in SelectionDAG holds the data. 44 /// SDVTList contains all types which are frequently accessed in SelectionDAG. 45 /// The size of this list is not expected big so it won't introduce memory penalty. 46 FoldingSetNodeIDRef FastID; 47 const EVT *VTs; 48 unsigned int NumVTs; 49 /// The hash value for SDVTList is fixed so cache it to avoid hash calculation 50 unsigned HashValue; 51 public: 52 SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) : 53 FastID(ID), VTs(VT), NumVTs(Num) { 54 HashValue = ID.ComputeHash(); 55 } 56 SDVTList getSDVTList() { 57 SDVTList result = {VTs, NumVTs}; 58 return result; 59 } 60 }; 61 62 // Specialize FoldingSetTrait for SDVTListNode 63 // To avoid computing temp FoldingSetNodeID and hash value. 64 template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> { 65 static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) { 66 ID = X.FastID; 67 } 68 static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID, 69 unsigned IDHash, FoldingSetNodeID &TempID) { 70 if (X.HashValue != IDHash) 71 return false; 72 return ID == X.FastID; 73 } 74 static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) { 75 return X.HashValue; 76 } 77 }; 78 79 template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> { 80 private: 81 mutable ilist_half_node<SDNode> Sentinel; 82 public: 83 SDNode *createSentinel() const { 84 return static_cast<SDNode*>(&Sentinel); 85 } 86 static void destroySentinel(SDNode *) {} 87 88 SDNode *provideInitialHead() const { return createSentinel(); } 89 SDNode *ensureHead(SDNode*) const { return createSentinel(); } 90 static void noteHead(SDNode*, SDNode*) {} 91 92 static void deleteNode(SDNode *) { 93 llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!"); 94 } 95 private: 96 static void createNode(const SDNode &); 97 }; 98 99 /// SDDbgInfo - Keeps track of dbg_value information through SDISel. We do 100 /// not build SDNodes for these so as not to perturb the generated code; 101 /// instead the info is kept off to the side in this structure. Each SDNode may 102 /// have one or more associated dbg_value entries. This information is kept in 103 /// DbgValMap. 104 /// Byval parameters are handled separately because they don't use alloca's, 105 /// which busts the normal mechanism. There is good reason for handling all 106 /// parameters separately: they may not have code generated for them, they 107 /// should always go at the beginning of the function regardless of other code 108 /// motion, and debug info for them is potentially useful even if the parameter 109 /// is unused. Right now only byval parameters are handled separately. 110 class SDDbgInfo { 111 SmallVector<SDDbgValue*, 32> DbgValues; 112 SmallVector<SDDbgValue*, 32> ByvalParmDbgValues; 113 typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType; 114 DbgValMapType DbgValMap; 115 116 void operator=(const SDDbgInfo&) LLVM_DELETED_FUNCTION; 117 SDDbgInfo(const SDDbgInfo&) LLVM_DELETED_FUNCTION; 118 public: 119 SDDbgInfo() {} 120 121 void add(SDDbgValue *V, const SDNode *Node, bool isParameter) { 122 if (isParameter) { 123 ByvalParmDbgValues.push_back(V); 124 } else DbgValues.push_back(V); 125 if (Node) 126 DbgValMap[Node].push_back(V); 127 } 128 129 void clear() { 130 DbgValMap.clear(); 131 DbgValues.clear(); 132 ByvalParmDbgValues.clear(); 133 } 134 135 bool empty() const { 136 return DbgValues.empty() && ByvalParmDbgValues.empty(); 137 } 138 139 ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) { 140 DbgValMapType::iterator I = DbgValMap.find(Node); 141 if (I != DbgValMap.end()) 142 return I->second; 143 return ArrayRef<SDDbgValue*>(); 144 } 145 146 typedef SmallVectorImpl<SDDbgValue*>::iterator DbgIterator; 147 DbgIterator DbgBegin() { return DbgValues.begin(); } 148 DbgIterator DbgEnd() { return DbgValues.end(); } 149 DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); } 150 DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); } 151 }; 152 153 class SelectionDAG; 154 void checkForCycles(const SelectionDAG *DAG, bool force = false); 155 156 /// SelectionDAG class - This is used to represent a portion of an LLVM function 157 /// in a low-level Data Dependence DAG representation suitable for instruction 158 /// selection. This DAG is constructed as the first step of instruction 159 /// selection in order to allow implementation of machine specific optimizations 160 /// and code simplifications. 161 /// 162 /// The representation used by the SelectionDAG is a target-independent 163 /// representation, which has some similarities to the GCC RTL representation, 164 /// but is significantly more simple, powerful, and is a graph form instead of a 165 /// linear form. 166 /// 167 class SelectionDAG { 168 const TargetMachine &TM; 169 const TargetSelectionDAGInfo &TSI; 170 const TargetLowering *TLI; 171 MachineFunction *MF; 172 LLVMContext *Context; 173 CodeGenOpt::Level OptLevel; 174 175 /// EntryNode - The starting token. 176 SDNode EntryNode; 177 178 /// Root - The root of the entire DAG. 179 SDValue Root; 180 181 /// AllNodes - A linked list of nodes in the current DAG. 182 ilist<SDNode> AllNodes; 183 184 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use 185 /// pool allocation with recycling. 186 typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode), 187 AlignOf<MostAlignedSDNode>::Alignment> 188 NodeAllocatorType; 189 190 /// NodeAllocator - Pool allocation for nodes. 191 NodeAllocatorType NodeAllocator; 192 193 /// CSEMap - This structure is used to memoize nodes, automatically performing 194 /// CSE with existing nodes when a duplicate is requested. 195 FoldingSet<SDNode> CSEMap; 196 197 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands. 198 BumpPtrAllocator OperandAllocator; 199 200 /// Allocator - Pool allocation for misc. objects that are created once per 201 /// SelectionDAG. 202 BumpPtrAllocator Allocator; 203 204 /// DbgInfo - Tracks dbg_value information through SDISel. 205 SDDbgInfo *DbgInfo; 206 207 public: 208 /// DAGUpdateListener - Clients of various APIs that cause global effects on 209 /// the DAG can optionally implement this interface. This allows the clients 210 /// to handle the various sorts of updates that happen. 211 /// 212 /// A DAGUpdateListener automatically registers itself with DAG when it is 213 /// constructed, and removes itself when destroyed in RAII fashion. 214 struct DAGUpdateListener { 215 DAGUpdateListener *const Next; 216 SelectionDAG &DAG; 217 218 explicit DAGUpdateListener(SelectionDAG &D) 219 : Next(D.UpdateListeners), DAG(D) { 220 DAG.UpdateListeners = this; 221 } 222 223 virtual ~DAGUpdateListener() { 224 assert(DAG.UpdateListeners == this && 225 "DAGUpdateListeners must be destroyed in LIFO order"); 226 DAG.UpdateListeners = Next; 227 } 228 229 /// NodeDeleted - The node N that was deleted and, if E is not null, an 230 /// equivalent node E that replaced it. 231 virtual void NodeDeleted(SDNode *N, SDNode *E); 232 233 /// NodeUpdated - The node N that was updated. 234 virtual void NodeUpdated(SDNode *N); 235 }; 236 237 /// NewNodesMustHaveLegalTypes - When true, additional steps are taken to 238 /// ensure that getConstant() and similar functions return DAG nodes that 239 /// have legal types. This is important after type legalization since 240 /// any illegally typed nodes generated after this point will not experience 241 /// type legalization. 242 bool NewNodesMustHaveLegalTypes; 243 244 private: 245 /// DAGUpdateListener is a friend so it can manipulate the listener stack. 246 friend struct DAGUpdateListener; 247 248 /// UpdateListeners - Linked list of registered DAGUpdateListener instances. 249 /// This stack is maintained by DAGUpdateListener RAII. 250 DAGUpdateListener *UpdateListeners; 251 252 /// setGraphColorHelper - Implementation of setSubgraphColor. 253 /// Return whether we had to truncate the search. 254 /// 255 bool setSubgraphColorHelper(SDNode *N, const char *Color, 256 DenseSet<SDNode *> &visited, 257 int level, bool &printed); 258 259 void operator=(const SelectionDAG&) LLVM_DELETED_FUNCTION; 260 SelectionDAG(const SelectionDAG&) LLVM_DELETED_FUNCTION; 261 262 public: 263 explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level); 264 ~SelectionDAG(); 265 266 /// init - Prepare this SelectionDAG to process code in the given 267 /// MachineFunction. 268 /// 269 void init(MachineFunction &mf, const TargetLowering *TLI); 270 271 /// clear - Clear state and free memory necessary to make this 272 /// SelectionDAG ready to process a new block. 273 /// 274 void clear(); 275 276 MachineFunction &getMachineFunction() const { return *MF; } 277 const TargetMachine &getTarget() const { return TM; } 278 const TargetLowering &getTargetLoweringInfo() const { return *TLI; } 279 const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; } 280 LLVMContext *getContext() const {return Context; } 281 282 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 283 /// 284 void viewGraph(const std::string &Title); 285 void viewGraph(); 286 287 #ifndef NDEBUG 288 std::map<const SDNode *, std::string> NodeGraphAttrs; 289 #endif 290 291 /// clearGraphAttrs - Clear all previously defined node graph attributes. 292 /// Intended to be used from a debugging tool (eg. gdb). 293 void clearGraphAttrs(); 294 295 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".) 296 /// 297 void setGraphAttrs(const SDNode *N, const char *Attrs); 298 299 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".) 300 /// Used from getNodeAttributes. 301 const std::string getGraphAttrs(const SDNode *N) const; 302 303 /// setGraphColor - Convenience for setting node color attribute. 304 /// 305 void setGraphColor(const SDNode *N, const char *Color); 306 307 /// setGraphColor - Convenience for setting subgraph color attribute. 308 /// 309 void setSubgraphColor(SDNode *N, const char *Color); 310 311 typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 312 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 313 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 314 typedef ilist<SDNode>::iterator allnodes_iterator; 315 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 316 allnodes_iterator allnodes_end() { return AllNodes.end(); } 317 ilist<SDNode>::size_type allnodes_size() const { 318 return AllNodes.size(); 319 } 320 321 /// getRoot - Return the root tag of the SelectionDAG. 322 /// 323 const SDValue &getRoot() const { return Root; } 324 325 /// getEntryNode - Return the token chain corresponding to the entry of the 326 /// function. 327 SDValue getEntryNode() const { 328 return SDValue(const_cast<SDNode *>(&EntryNode), 0); 329 } 330 331 /// setRoot - Set the current root tag of the SelectionDAG. 332 /// 333 const SDValue &setRoot(SDValue N) { 334 assert((!N.getNode() || N.getValueType() == MVT::Other) && 335 "DAG root value is not a chain!"); 336 if (N.getNode()) 337 checkForCycles(N.getNode(), this); 338 Root = N; 339 if (N.getNode()) 340 checkForCycles(this); 341 return Root; 342 } 343 344 /// Combine - This iterates over the nodes in the SelectionDAG, folding 345 /// certain types of nodes together, or eliminating superfluous nodes. The 346 /// Level argument controls whether Combine is allowed to produce nodes and 347 /// types that are illegal on the target. 348 void Combine(CombineLevel Level, AliasAnalysis &AA, 349 CodeGenOpt::Level OptLevel); 350 351 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 352 /// only uses types natively supported by the target. Returns "true" if it 353 /// made any changes. 354 /// 355 /// Note that this is an involved process that may invalidate pointers into 356 /// the graph. 357 bool LegalizeTypes(); 358 359 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 360 /// compatible with the target instruction selector, as indicated by the 361 /// TargetLowering object. 362 /// 363 /// Note that this is an involved process that may invalidate pointers into 364 /// the graph. 365 void Legalize(); 366 367 /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG 368 /// that only uses vector math operations supported by the target. This is 369 /// necessary as a separate step from Legalize because unrolling a vector 370 /// operation can introduce illegal types, which requires running 371 /// LegalizeTypes again. 372 /// 373 /// This returns true if it made any changes; in that case, LegalizeTypes 374 /// is called again before Legalize. 375 /// 376 /// Note that this is an involved process that may invalidate pointers into 377 /// the graph. 378 bool LegalizeVectors(); 379 380 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 381 /// SelectionDAG. 382 void RemoveDeadNodes(); 383 384 /// DeleteNode - Remove the specified node from the system. This node must 385 /// have no referrers. 386 void DeleteNode(SDNode *N); 387 388 /// getVTList - Return an SDVTList that represents the list of values 389 /// specified. 390 SDVTList getVTList(EVT VT); 391 SDVTList getVTList(EVT VT1, EVT VT2); 392 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3); 393 SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4); 394 SDVTList getVTList(ArrayRef<EVT> VTs); 395 396 //===--------------------------------------------------------------------===// 397 // Node creation methods. 398 // 399 SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false, 400 bool isOpaque = false); 401 SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false, 402 bool isOpaque = false); 403 SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false, 404 bool isOpaque = false); 405 SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false); 406 SDValue getTargetConstant(uint64_t Val, EVT VT, bool isOpaque = false) { 407 return getConstant(Val, VT, true, isOpaque); 408 } 409 SDValue getTargetConstant(const APInt &Val, EVT VT, bool isOpaque = false) { 410 return getConstant(Val, VT, true, isOpaque); 411 } 412 SDValue getTargetConstant(const ConstantInt &Val, EVT VT, 413 bool isOpaque = false) { 414 return getConstant(Val, VT, true, isOpaque); 415 } 416 // The forms below that take a double should only be used for simple 417 // constants that can be exactly represented in VT. No checks are made. 418 SDValue getConstantFP(double Val, EVT VT, bool isTarget = false); 419 SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false); 420 SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false); 421 SDValue getTargetConstantFP(double Val, EVT VT) { 422 return getConstantFP(Val, VT, true); 423 } 424 SDValue getTargetConstantFP(const APFloat& Val, EVT VT) { 425 return getConstantFP(Val, VT, true); 426 } 427 SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) { 428 return getConstantFP(Val, VT, true); 429 } 430 SDValue getGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT, 431 int64_t offset = 0, bool isTargetGA = false, 432 unsigned char TargetFlags = 0); 433 SDValue getTargetGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT, 434 int64_t offset = 0, 435 unsigned char TargetFlags = 0) { 436 return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags); 437 } 438 SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false); 439 SDValue getTargetFrameIndex(int FI, EVT VT) { 440 return getFrameIndex(FI, VT, true); 441 } 442 SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false, 443 unsigned char TargetFlags = 0); 444 SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) { 445 return getJumpTable(JTI, VT, true, TargetFlags); 446 } 447 SDValue getConstantPool(const Constant *C, EVT VT, 448 unsigned Align = 0, int Offs = 0, bool isT=false, 449 unsigned char TargetFlags = 0); 450 SDValue getTargetConstantPool(const Constant *C, EVT VT, 451 unsigned Align = 0, int Offset = 0, 452 unsigned char TargetFlags = 0) { 453 return getConstantPool(C, VT, Align, Offset, true, TargetFlags); 454 } 455 SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT, 456 unsigned Align = 0, int Offs = 0, bool isT=false, 457 unsigned char TargetFlags = 0); 458 SDValue getTargetConstantPool(MachineConstantPoolValue *C, 459 EVT VT, unsigned Align = 0, 460 int Offset = 0, unsigned char TargetFlags=0) { 461 return getConstantPool(C, VT, Align, Offset, true, TargetFlags); 462 } 463 SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0, 464 unsigned char TargetFlags = 0); 465 // When generating a branch to a BB, we don't in general know enough 466 // to provide debug info for the BB at that time, so keep this one around. 467 SDValue getBasicBlock(MachineBasicBlock *MBB); 468 SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl); 469 SDValue getExternalSymbol(const char *Sym, EVT VT); 470 SDValue getExternalSymbol(const char *Sym, SDLoc dl, EVT VT); 471 SDValue getTargetExternalSymbol(const char *Sym, EVT VT, 472 unsigned char TargetFlags = 0); 473 SDValue getValueType(EVT); 474 SDValue getRegister(unsigned Reg, EVT VT); 475 SDValue getRegisterMask(const uint32_t *RegMask); 476 SDValue getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label); 477 SDValue getBlockAddress(const BlockAddress *BA, EVT VT, 478 int64_t Offset = 0, bool isTarget = false, 479 unsigned char TargetFlags = 0); 480 SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT, 481 int64_t Offset = 0, 482 unsigned char TargetFlags = 0) { 483 return getBlockAddress(BA, VT, Offset, true, TargetFlags); 484 } 485 486 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N) { 487 return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, 488 getRegister(Reg, N.getValueType()), N); 489 } 490 491 // This version of the getCopyToReg method takes an extra operand, which 492 // indicates that there is potentially an incoming glue value (if Glue is not 493 // null) and that there should be a glue result. 494 SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N, 495 SDValue Glue) { 496 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 497 SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue }; 498 return getNode(ISD::CopyToReg, dl, VTs, 499 ArrayRef<SDValue>(Ops, Glue.getNode() ? 4 : 3)); 500 } 501 502 // Similar to last getCopyToReg() except parameter Reg is a SDValue 503 SDValue getCopyToReg(SDValue Chain, SDLoc dl, SDValue Reg, SDValue N, 504 SDValue Glue) { 505 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 506 SDValue Ops[] = { Chain, Reg, N, Glue }; 507 return getNode(ISD::CopyToReg, dl, VTs, 508 ArrayRef<SDValue>(Ops, Glue.getNode() ? 4 : 3)); 509 } 510 511 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT) { 512 SDVTList VTs = getVTList(VT, MVT::Other); 513 SDValue Ops[] = { Chain, getRegister(Reg, VT) }; 514 return getNode(ISD::CopyFromReg, dl, VTs, Ops); 515 } 516 517 // This version of the getCopyFromReg method takes an extra operand, which 518 // indicates that there is potentially an incoming glue value (if Glue is not 519 // null) and that there should be a glue result. 520 SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT, 521 SDValue Glue) { 522 SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue); 523 SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue }; 524 return getNode(ISD::CopyFromReg, dl, VTs, 525 ArrayRef<SDValue>(Ops, Glue.getNode() ? 3 : 2)); 526 } 527 528 SDValue getCondCode(ISD::CondCode Cond); 529 530 /// Returns the ConvertRndSat Note: Avoid using this node because it may 531 /// disappear in the future and most targets don't support it. 532 SDValue getConvertRndSat(EVT VT, SDLoc dl, SDValue Val, SDValue DTy, 533 SDValue STy, 534 SDValue Rnd, SDValue Sat, ISD::CvtCode Code); 535 536 /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node. The number of 537 /// elements in VT, which must be a vector type, must match the number of 538 /// mask elements NumElts. A integer mask element equal to -1 is treated as 539 /// undefined. 540 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2, 541 const int *MaskElts); 542 SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2, 543 ArrayRef<int> MaskElts) { 544 assert(VT.getVectorNumElements() == MaskElts.size() && 545 "Must have the same number of vector elements as mask elements!"); 546 return getVectorShuffle(VT, dl, N1, N2, MaskElts.data()); 547 } 548 549 /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the 550 /// integer type VT, by either any-extending or truncating it. 551 SDValue getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT); 552 553 /// getSExtOrTrunc - Convert Op, which must be of integer type, to the 554 /// integer type VT, by either sign-extending or truncating it. 555 SDValue getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT); 556 557 /// getZExtOrTrunc - Convert Op, which must be of integer type, to the 558 /// integer type VT, by either zero-extending or truncating it. 559 SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT); 560 561 /// getZeroExtendInReg - Return the expression required to zero extend the Op 562 /// value assuming it was the smaller SrcTy value. 563 SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy); 564 565 /// getAnyExtendVectorInReg - Return an operation which will any-extend the 566 /// low lanes of the operand into the specified vector type. For example, 567 /// this can convert a v16i8 into a v4i32 by any-extending the low four 568 /// lanes of the operand from i8 to i32. 569 SDValue getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT); 570 571 /// getSignExtendVectorInReg - Return an operation which will sign extend the 572 /// low lanes of the operand into the specified vector type. For example, 573 /// this can convert a v16i8 into a v4i32 by sign extending the low four 574 /// lanes of the operand from i8 to i32. 575 SDValue getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT); 576 577 /// getZeroExtendVectorInReg - Return an operation which will zero extend the 578 /// low lanes of the operand into the specified vector type. For example, 579 /// this can convert a v16i8 into a v4i32 by zero extending the low four 580 /// lanes of the operand from i8 to i32. 581 SDValue getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT); 582 583 /// getBoolExtOrTrunc - Convert Op, which must be of integer type, to the 584 /// integer type VT, by using an extension appropriate for the target's 585 /// BooleanContent for type OpVT or truncating it. 586 SDValue getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT, EVT OpVT); 587 588 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). 589 SDValue getNOT(SDLoc DL, SDValue Val, EVT VT); 590 591 /// \brief Create a logical NOT operation as (XOR Val, BooleanOne). 592 SDValue getLogicalNOT(SDLoc DL, SDValue Val, EVT VT); 593 594 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 595 /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a 596 /// useful SDLoc. 597 SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) { 598 SDVTList VTs = getVTList(MVT::Other, MVT::Glue); 599 SDValue Ops[] = { Chain, Op }; 600 return getNode(ISD::CALLSEQ_START, DL, VTs, Ops); 601 } 602 603 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a 604 /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have 605 /// a useful SDLoc. 606 SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, 607 SDValue InGlue, SDLoc DL) { 608 SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue); 609 SmallVector<SDValue, 4> Ops; 610 Ops.push_back(Chain); 611 Ops.push_back(Op1); 612 Ops.push_back(Op2); 613 if (InGlue.getNode()) 614 Ops.push_back(InGlue); 615 return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops); 616 } 617 618 /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful SDLoc. 619 SDValue getUNDEF(EVT VT) { 620 return getNode(ISD::UNDEF, SDLoc(), VT); 621 } 622 623 /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does 624 /// not have a useful SDLoc. 625 SDValue getGLOBAL_OFFSET_TABLE(EVT VT) { 626 return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT); 627 } 628 629 /// getNode - Gets or creates the specified node. 630 /// 631 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT); 632 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N); 633 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, 634 bool nuw = false, bool nsw = false, bool exact = false); 635 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, 636 SDValue N3); 637 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, 638 SDValue N3, SDValue N4); 639 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, 640 SDValue N3, SDValue N4, SDValue N5); 641 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, ArrayRef<SDUse> Ops); 642 SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, 643 ArrayRef<SDValue> Ops); 644 SDValue getNode(unsigned Opcode, SDLoc DL, 645 ArrayRef<EVT> ResultTys, 646 ArrayRef<SDValue> Ops); 647 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, 648 ArrayRef<SDValue> Ops); 649 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs); 650 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N); 651 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, 652 SDValue N1, SDValue N2); 653 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, 654 SDValue N1, SDValue N2, SDValue N3); 655 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, 656 SDValue N1, SDValue N2, SDValue N3, SDValue N4); 657 SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, 658 SDValue N1, SDValue N2, SDValue N3, SDValue N4, 659 SDValue N5); 660 661 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all 662 /// the incoming stack arguments to be loaded from the stack. This is 663 /// used in tail call lowering to protect stack arguments from being 664 /// clobbered. 665 SDValue getStackArgumentTokenFactor(SDValue Chain); 666 667 SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src, 668 SDValue Size, unsigned Align, bool isVol, bool AlwaysInline, 669 MachinePointerInfo DstPtrInfo, 670 MachinePointerInfo SrcPtrInfo); 671 672 SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src, 673 SDValue Size, unsigned Align, bool isVol, 674 MachinePointerInfo DstPtrInfo, 675 MachinePointerInfo SrcPtrInfo); 676 677 SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src, 678 SDValue Size, unsigned Align, bool isVol, 679 MachinePointerInfo DstPtrInfo); 680 681 /// getSetCC - Helper function to make it easier to build SetCC's if you just 682 /// have an ISD::CondCode instead of an SDValue. 683 /// 684 SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS, 685 ISD::CondCode Cond) { 686 assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() && 687 "Cannot compare scalars to vectors"); 688 assert(LHS.getValueType().isVector() == VT.isVector() && 689 "Cannot compare scalars to vectors"); 690 assert(Cond != ISD::SETCC_INVALID && 691 "Cannot create a setCC of an invalid node."); 692 return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); 693 } 694 695 // getSelect - Helper function to make it easier to build Select's if you just 696 // have operands and don't want to check for vector. 697 SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond, 698 SDValue LHS, SDValue RHS) { 699 assert(LHS.getValueType() == RHS.getValueType() && 700 "Cannot use select on differing types"); 701 assert(VT.isVector() == LHS.getValueType().isVector() && 702 "Cannot mix vectors and scalars"); 703 return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT, 704 Cond, LHS, RHS); 705 } 706 707 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 708 /// just have an ISD::CondCode instead of an SDValue. 709 /// 710 SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS, 711 SDValue True, SDValue False, ISD::CondCode Cond) { 712 return getNode(ISD::SELECT_CC, DL, True.getValueType(), 713 LHS, RHS, True, False, getCondCode(Cond)); 714 } 715 716 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 717 /// and a source value as input. 718 SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr, 719 SDValue SV, unsigned Align); 720 721 /// getAtomicCmpSwap - Gets a node for an atomic cmpxchg op. There are two 722 /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces a the value loaded and a 723 /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded, 724 /// a success flag (initially i1), and a chain. 725 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, 726 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp, 727 MachinePointerInfo PtrInfo, unsigned Alignment, 728 AtomicOrdering SuccessOrdering, 729 AtomicOrdering FailureOrdering, 730 SynchronizationScope SynchScope); 731 SDValue getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, 732 SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp, 733 MachineMemOperand *MMO, 734 AtomicOrdering SuccessOrdering, 735 AtomicOrdering FailureOrdering, 736 SynchronizationScope SynchScope); 737 738 /// getAtomic - Gets a node for an atomic op, produces result (if relevant) 739 /// and chain and takes 2 operands. 740 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain, 741 SDValue Ptr, SDValue Val, const Value *PtrVal, 742 unsigned Alignment, AtomicOrdering Ordering, 743 SynchronizationScope SynchScope); 744 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain, 745 SDValue Ptr, SDValue Val, MachineMemOperand *MMO, 746 AtomicOrdering Ordering, 747 SynchronizationScope SynchScope); 748 749 /// getAtomic - Gets a node for an atomic op, produces result and chain and 750 /// takes 1 operand. 751 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT, 752 SDValue Chain, SDValue Ptr, MachineMemOperand *MMO, 753 AtomicOrdering Ordering, 754 SynchronizationScope SynchScope); 755 756 /// getAtomic - Gets a node for an atomic op, produces result and chain and 757 /// takes N operands. 758 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList, 759 ArrayRef<SDValue> Ops, MachineMemOperand *MMO, 760 AtomicOrdering SuccessOrdering, 761 AtomicOrdering FailureOrdering, 762 SynchronizationScope SynchScope); 763 SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList, 764 ArrayRef<SDValue> Ops, MachineMemOperand *MMO, 765 AtomicOrdering Ordering, SynchronizationScope SynchScope); 766 767 /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a 768 /// result and takes a list of operands. Opcode may be INTRINSIC_VOID, 769 /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not 770 /// less than FIRST_TARGET_MEMORY_OPCODE. 771 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList, 772 ArrayRef<SDValue> Ops, 773 EVT MemVT, MachinePointerInfo PtrInfo, 774 unsigned Align = 0, bool Vol = false, 775 bool ReadMem = true, bool WriteMem = true); 776 777 SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList, 778 ArrayRef<SDValue> Ops, 779 EVT MemVT, MachineMemOperand *MMO); 780 781 /// getMergeValues - Create a MERGE_VALUES node from the given operands. 782 SDValue getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl); 783 784 /// getLoad - Loads are not normal binary operators: their result type is not 785 /// determined by their operands, and they produce a value AND a token chain. 786 /// 787 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr, 788 MachinePointerInfo PtrInfo, bool isVolatile, 789 bool isNonTemporal, bool isInvariant, unsigned Alignment, 790 const MDNode *TBAAInfo = nullptr, 791 const MDNode *Ranges = nullptr); 792 SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr, 793 MachineMemOperand *MMO); 794 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT, 795 SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, 796 EVT MemVT, bool isVolatile, 797 bool isNonTemporal, unsigned Alignment, 798 const MDNode *TBAAInfo = nullptr); 799 SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT, 800 SDValue Chain, SDValue Ptr, EVT MemVT, 801 MachineMemOperand *MMO); 802 SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base, 803 SDValue Offset, ISD::MemIndexedMode AM); 804 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 805 EVT VT, SDLoc dl, 806 SDValue Chain, SDValue Ptr, SDValue Offset, 807 MachinePointerInfo PtrInfo, EVT MemVT, 808 bool isVolatile, bool isNonTemporal, bool isInvariant, 809 unsigned Alignment, const MDNode *TBAAInfo = nullptr, 810 const MDNode *Ranges = nullptr); 811 SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 812 EVT VT, SDLoc dl, 813 SDValue Chain, SDValue Ptr, SDValue Offset, 814 EVT MemVT, MachineMemOperand *MMO); 815 816 /// getStore - Helper function to build ISD::STORE nodes. 817 /// 818 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr, 819 MachinePointerInfo PtrInfo, bool isVolatile, 820 bool isNonTemporal, unsigned Alignment, 821 const MDNode *TBAAInfo = nullptr); 822 SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr, 823 MachineMemOperand *MMO); 824 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr, 825 MachinePointerInfo PtrInfo, EVT TVT, 826 bool isNonTemporal, bool isVolatile, 827 unsigned Alignment, 828 const MDNode *TBAAInfo = nullptr); 829 SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr, 830 EVT TVT, MachineMemOperand *MMO); 831 SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base, 832 SDValue Offset, ISD::MemIndexedMode AM); 833 834 /// getSrcValue - Construct a node to track a Value* through the backend. 835 SDValue getSrcValue(const Value *v); 836 837 /// getMDNode - Return an MDNodeSDNode which holds an MDNode. 838 SDValue getMDNode(const MDNode *MD); 839 840 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode. 841 SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr, 842 unsigned SrcAS, unsigned DestAS); 843 844 /// getShiftAmountOperand - Return the specified value casted to 845 /// the target's desired shift amount type. 846 SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op); 847 848 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 849 /// specified operands. If the resultant node already exists in the DAG, 850 /// this does not modify the specified node, instead it returns the node that 851 /// already exists. If the resultant node does not exist in the DAG, the 852 /// input node is returned. As a degenerate case, if you specify the same 853 /// input operands as the node already has, the input node is returned. 854 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op); 855 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2); 856 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 857 SDValue Op3); 858 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 859 SDValue Op3, SDValue Op4); 860 SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 861 SDValue Op3, SDValue Op4, SDValue Op5); 862 SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops); 863 864 /// SelectNodeTo - These are used for target selectors to *mutate* the 865 /// specified node to have the specified return type, Target opcode, and 866 /// operands. Note that target opcodes are stored as 867 /// ~TargetOpcode in the node opcode field. The resultant node is returned. 868 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT); 869 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1); 870 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 871 SDValue Op1, SDValue Op2); 872 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 873 SDValue Op1, SDValue Op2, SDValue Op3); 874 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, 875 ArrayRef<SDValue> Ops); 876 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2); 877 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 878 EVT VT2, ArrayRef<SDValue> Ops); 879 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 880 EVT VT2, EVT VT3, ArrayRef<SDValue> Ops); 881 SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, 882 EVT VT2, EVT VT3, EVT VT4, ArrayRef<SDValue> Ops); 883 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 884 EVT VT2, SDValue Op1); 885 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 886 EVT VT2, SDValue Op1, SDValue Op2); 887 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 888 EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); 889 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, 890 EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); 891 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs, 892 ArrayRef<SDValue> Ops); 893 894 /// MorphNodeTo - This *mutates* the specified node to have the specified 895 /// return type, opcode, and operands. 896 SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, 897 ArrayRef<SDValue> Ops); 898 899 /// getMachineNode - These are used for target selectors to create a new node 900 /// with specified return type(s), MachineInstr opcode, and operands. 901 /// 902 /// Note that getMachineNode returns the resultant node. If there is already 903 /// a node of the specified opcode and operands, it returns that node instead 904 /// of the current one. 905 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT); 906 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, 907 SDValue Op1); 908 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, 909 SDValue Op1, SDValue Op2); 910 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, 911 SDValue Op1, SDValue Op2, SDValue Op3); 912 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, 913 ArrayRef<SDValue> Ops); 914 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2); 915 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, 916 SDValue Op1); 917 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, 918 SDValue Op1, SDValue Op2); 919 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, 920 SDValue Op1, SDValue Op2, SDValue Op3); 921 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, 922 ArrayRef<SDValue> Ops); 923 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, 924 EVT VT3, SDValue Op1, SDValue Op2); 925 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, 926 EVT VT3, SDValue Op1, SDValue Op2, 927 SDValue Op3); 928 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, 929 EVT VT3, ArrayRef<SDValue> Ops); 930 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, 931 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops); 932 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, 933 ArrayRef<EVT> ResultTys, 934 ArrayRef<SDValue> Ops); 935 MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs, 936 ArrayRef<SDValue> Ops); 937 938 /// getTargetExtractSubreg - A convenience function for creating 939 /// TargetInstrInfo::EXTRACT_SUBREG nodes. 940 SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT, 941 SDValue Operand); 942 943 /// getTargetInsertSubreg - A convenience function for creating 944 /// TargetInstrInfo::INSERT_SUBREG nodes. 945 SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT, 946 SDValue Operand, SDValue Subreg); 947 948 /// getNodeIfExists - Get the specified node if it's already available, or 949 /// else return NULL. 950 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops, 951 bool nuw = false, bool nsw = false, 952 bool exact = false); 953 954 /// getDbgValue - Creates a SDDbgValue node. 955 /// 956 SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, 957 bool IsIndirect, uint64_t Off, 958 DebugLoc DL, unsigned O); 959 /// Constant. 960 SDDbgValue *getConstantDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off, 961 DebugLoc DL, unsigned O); 962 /// Frame index. 963 SDDbgValue *getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off, 964 DebugLoc DL, unsigned O); 965 966 /// RemoveDeadNode - Remove the specified node from the system. If any of its 967 /// operands then becomes dead, remove them as well. Inform UpdateListener 968 /// for each node deleted. 969 void RemoveDeadNode(SDNode *N); 970 971 /// RemoveDeadNodes - This method deletes the unreachable nodes in the 972 /// given list, and any nodes that become unreachable as a result. 973 void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes); 974 975 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 976 /// This can cause recursive merging of nodes in the DAG. Use the first 977 /// version if 'From' is known to have a single result, use the second 978 /// if you have two nodes with identical results (or if 'To' has a superset 979 /// of the results of 'From'), use the third otherwise. 980 /// 981 /// These methods all take an optional UpdateListener, which (if not null) is 982 /// informed about nodes that are deleted and modified due to recursive 983 /// changes in the dag. 984 /// 985 /// These functions only replace all existing uses. It's possible that as 986 /// these replacements are being performed, CSE may cause the From node 987 /// to be given new uses. These new uses of From are left in place, and 988 /// not automatically transferred to To. 989 /// 990 void ReplaceAllUsesWith(SDValue From, SDValue Op); 991 void ReplaceAllUsesWith(SDNode *From, SDNode *To); 992 void ReplaceAllUsesWith(SDNode *From, const SDValue *To); 993 994 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 995 /// uses of other values produced by From.Val alone. 996 void ReplaceAllUsesOfValueWith(SDValue From, SDValue To); 997 998 /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but 999 /// for multiple values at once. This correctly handles the case where 1000 /// there is an overlap between the From values and the To values. 1001 void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, 1002 unsigned Num); 1003 1004 /// AssignTopologicalOrder - Topological-sort the AllNodes list and a 1005 /// assign a unique node id for each node in the DAG based on their 1006 /// topological order. Returns the number of nodes. 1007 unsigned AssignTopologicalOrder(); 1008 1009 /// RepositionNode - Move node N in the AllNodes list to be immediately 1010 /// before the given iterator Position. This may be used to update the 1011 /// topological ordering when the list of nodes is modified. 1012 void RepositionNode(allnodes_iterator Position, SDNode *N) { 1013 AllNodes.insert(Position, AllNodes.remove(N)); 1014 } 1015 1016 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 1017 /// operation. 1018 static bool isCommutativeBinOp(unsigned Opcode) { 1019 // FIXME: This should get its info from the td file, so that we can include 1020 // target info. 1021 switch (Opcode) { 1022 case ISD::ADD: 1023 case ISD::MUL: 1024 case ISD::MULHU: 1025 case ISD::MULHS: 1026 case ISD::SMUL_LOHI: 1027 case ISD::UMUL_LOHI: 1028 case ISD::FADD: 1029 case ISD::FMUL: 1030 case ISD::AND: 1031 case ISD::OR: 1032 case ISD::XOR: 1033 case ISD::SADDO: 1034 case ISD::UADDO: 1035 case ISD::ADDC: 1036 case ISD::ADDE: return true; 1037 default: return false; 1038 } 1039 } 1040 1041 /// Returns an APFloat semantics tag appropriate for the given type. If VT is 1042 /// a vector type, the element semantics are returned. 1043 static const fltSemantics &EVTToAPFloatSemantics(EVT VT) { 1044 switch (VT.getScalarType().getSimpleVT().SimpleTy) { 1045 default: llvm_unreachable("Unknown FP format"); 1046 case MVT::f16: return APFloat::IEEEhalf; 1047 case MVT::f32: return APFloat::IEEEsingle; 1048 case MVT::f64: return APFloat::IEEEdouble; 1049 case MVT::f80: return APFloat::x87DoubleExtended; 1050 case MVT::f128: return APFloat::IEEEquad; 1051 case MVT::ppcf128: return APFloat::PPCDoubleDouble; 1052 } 1053 } 1054 1055 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the 1056 /// value is produced by SD. 1057 void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter); 1058 1059 /// GetDbgValues - Get the debug values which reference the given SDNode. 1060 ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) { 1061 return DbgInfo->getSDDbgValues(SD); 1062 } 1063 1064 /// TransferDbgValues - Transfer SDDbgValues. 1065 void TransferDbgValues(SDValue From, SDValue To); 1066 1067 /// hasDebugValues - Return true if there are any SDDbgValue nodes associated 1068 /// with this SelectionDAG. 1069 bool hasDebugValues() const { return !DbgInfo->empty(); } 1070 1071 SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); } 1072 SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); } 1073 SDDbgInfo::DbgIterator ByvalParmDbgBegin() { 1074 return DbgInfo->ByvalParmDbgBegin(); 1075 } 1076 SDDbgInfo::DbgIterator ByvalParmDbgEnd() { 1077 return DbgInfo->ByvalParmDbgEnd(); 1078 } 1079 1080 void dump() const; 1081 1082 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 1083 /// specified value type. If minAlign is specified, the slot size will have 1084 /// at least that alignment. 1085 SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1); 1086 1087 /// CreateStackTemporary - Create a stack temporary suitable for holding 1088 /// either of the specified value types. 1089 SDValue CreateStackTemporary(EVT VT1, EVT VT2); 1090 1091 /// FoldConstantArithmetic - 1092 SDValue FoldConstantArithmetic(unsigned Opcode, EVT VT, 1093 SDNode *Cst1, SDNode *Cst2); 1094 1095 /// FoldSetCC - Constant fold a setcc to true or false. 1096 SDValue FoldSetCC(EVT VT, SDValue N1, 1097 SDValue N2, ISD::CondCode Cond, SDLoc dl); 1098 1099 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 1100 /// use this predicate to simplify operations downstream. 1101 bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const; 1102 1103 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 1104 /// use this predicate to simplify operations downstream. Op and Mask are 1105 /// known to be the same type. 1106 bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0) 1107 const; 1108 1109 /// Determine which bits of Op are known to be either zero or one and return 1110 /// them in the KnownZero/KnownOne bitsets. Targets can implement the 1111 /// computeKnownBitsForTargetNode method in the TargetLowering class to allow 1112 /// target nodes to be understood. 1113 void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne, 1114 unsigned Depth = 0) const; 1115 1116 /// ComputeNumSignBits - Return the number of times the sign bit of the 1117 /// register is replicated into the other bits. We know that at least 1 bit 1118 /// is always equal to the sign bit (itself), but other cases can give us 1119 /// information. For example, immediately after an "SRA X, 2", we know that 1120 /// the top 3 bits are all equal to each other, so we return 3. Targets can 1121 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 1122 /// class to allow target nodes to be understood. 1123 unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; 1124 1125 /// isBaseWithConstantOffset - Return true if the specified operand is an 1126 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an 1127 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same 1128 /// semantics as an ADD. This handles the equivalence: 1129 /// X|Cst == X+Cst iff X&Cst = 0. 1130 bool isBaseWithConstantOffset(SDValue Op) const; 1131 1132 /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN. 1133 bool isKnownNeverNaN(SDValue Op) const; 1134 1135 /// isKnownNeverZero - Test whether the given SDValue is known to never be 1136 /// positive or negative Zero. 1137 bool isKnownNeverZero(SDValue Op) const; 1138 1139 /// isEqualTo - Test whether two SDValues are known to compare equal. This 1140 /// is true if they are the same value, or if one is negative zero and the 1141 /// other positive zero. 1142 bool isEqualTo(SDValue A, SDValue B) const; 1143 1144 /// UnrollVectorOp - Utility function used by legalize and lowering to 1145 /// "unroll" a vector operation by splitting out the scalars and operating 1146 /// on each element individually. If the ResNE is 0, fully unroll the vector 1147 /// op. If ResNE is less than the width of the vector op, unroll up to ResNE. 1148 /// If the ResNE is greater than the width of the vector op, unroll the 1149 /// vector op and fill the end of the resulting vector with UNDEFS. 1150 SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0); 1151 1152 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a 1153 /// location that is 'Dist' units away from the location that the 'Base' load 1154 /// is loading from. 1155 bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base, 1156 unsigned Bytes, int Dist) const; 1157 1158 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if 1159 /// it cannot be inferred. 1160 unsigned InferPtrAlignment(SDValue Ptr) const; 1161 1162 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type 1163 /// which is split (or expanded) into two not necessarily identical pieces. 1164 std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const; 1165 1166 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR using the provides 1167 /// VTs and return the low/high part. 1168 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL, 1169 const EVT &LoVT, const EVT &HiVT); 1170 1171 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the 1172 /// low/high part. 1173 std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) { 1174 EVT LoVT, HiVT; 1175 std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType()); 1176 return SplitVector(N, DL, LoVT, HiVT); 1177 } 1178 1179 /// SplitVectorOperand - Split the node's operand with EXTRACT_SUBVECTOR and 1180 /// return the low/high part. 1181 std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo) 1182 { 1183 return SplitVector(N->getOperand(OpNo), SDLoc(N)); 1184 } 1185 1186 /// ExtractVectorElements - Append the extracted elements from Start to Count 1187 /// out of the vector Op in Args. If Count is 0, all of the elements will be 1188 /// extracted. 1189 void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args, 1190 unsigned Start = 0, unsigned Count = 0); 1191 1192 unsigned getEVTAlignment(EVT MemoryVT) const; 1193 1194 private: 1195 bool RemoveNodeFromCSEMaps(SDNode *N); 1196 void AddModifiedNodeToCSEMaps(SDNode *N); 1197 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos); 1198 SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2, 1199 void *&InsertPos); 1200 SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops, 1201 void *&InsertPos); 1202 SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc); 1203 1204 void DeleteNodeNotInCSEMaps(SDNode *N); 1205 void DeallocateNode(SDNode *N); 1206 1207 void allnodes_clear(); 1208 1209 BinarySDNode *GetBinarySDNode(unsigned Opcode, SDLoc DL, SDVTList VTs, 1210 SDValue N1, SDValue N2, bool nuw, bool nsw, 1211 bool exact); 1212 1213 /// VTList - List of non-single value types. 1214 FoldingSet<SDVTListNode> VTListMap; 1215 1216 /// CondCodeNodes - Maps to auto-CSE operations. 1217 std::vector<CondCodeSDNode*> CondCodeNodes; 1218 1219 std::vector<SDNode*> ValueTypeNodes; 1220 std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes; 1221 StringMap<SDNode*> ExternalSymbols; 1222 1223 std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols; 1224 }; 1225 1226 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 1227 typedef SelectionDAG::allnodes_iterator nodes_iterator; 1228 static nodes_iterator nodes_begin(SelectionDAG *G) { 1229 return G->allnodes_begin(); 1230 } 1231 static nodes_iterator nodes_end(SelectionDAG *G) { 1232 return G->allnodes_end(); 1233 } 1234 }; 1235 1236 } // end namespace llvm 1237 1238 #endif 1239