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