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