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