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