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