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