SelectionDAG.h revision 43d1fd449f1a0ac9d9dafa0b9569bb6b2e976198
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/FoldingSet.h" 19#include "llvm/ADT/ilist.h" 20#include "llvm/CodeGen/SelectionDAGNodes.h" 21 22#include <list> 23#include <vector> 24#include <map> 25#include <set> 26#include <string> 27 28namespace llvm { 29 class AliasAnalysis; 30 class TargetLowering; 31 class TargetMachine; 32 class MachineModuleInfo; 33 class MachineFunction; 34 class MachineConstantPoolValue; 35 36/// SelectionDAG class - This is used to represent a portion of an LLVM function 37/// in a low-level Data Dependence DAG representation suitable for instruction 38/// selection. This DAG is constructed as the first step of instruction 39/// selection in order to allow implementation of machine specific optimizations 40/// and code simplifications. 41/// 42/// The representation used by the SelectionDAG is a target-independent 43/// representation, which has some similarities to the GCC RTL representation, 44/// but is significantly more simple, powerful, and is a graph form instead of a 45/// linear form. 46/// 47class SelectionDAG { 48 TargetLowering &TLI; 49 MachineFunction &MF; 50 MachineModuleInfo *MMI; 51 52 /// Root - The root of the entire DAG. EntryNode - The starting token. 53 SDOperand Root, EntryNode; 54 55 /// AllNodes - A linked list of nodes in the current DAG. 56 ilist<SDNode> AllNodes; 57 58 /// CSEMap - This structure is used to memoize nodes, automatically performing 59 /// CSE with existing nodes with a duplicate is requested. 60 FoldingSet<SDNode> CSEMap; 61 62public: 63 SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineModuleInfo *mmi) 64 : TLI(tli), MF(mf), MMI(mmi) { 65 EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); 66 } 67 ~SelectionDAG(); 68 69 MachineFunction &getMachineFunction() const { return MF; } 70 const TargetMachine &getTarget() const; 71 TargetLowering &getTargetLoweringInfo() const { return TLI; } 72 MachineModuleInfo *getMachineModuleInfo() const { return MMI; } 73 74 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 75 /// 76 void viewGraph(); 77 78#ifndef NDEBUG 79 std::map<const SDNode *, std::string> NodeGraphAttrs; 80#endif 81 82 /// clearGraphAttrs - Clear all previously defined node graph attributes. 83 /// Intended to be used from a debugging tool (eg. gdb). 84 void clearGraphAttrs(); 85 86 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".) 87 /// 88 void setGraphAttrs(const SDNode *N, const char *Attrs); 89 90 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".) 91 /// Used from getNodeAttributes. 92 const std::string getGraphAttrs(const SDNode *N) const; 93 94 /// setGraphColor - Convenience for setting node color attribute. 95 /// 96 void setGraphColor(const SDNode *N, const char *Color); 97 98 typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 99 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 100 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 101 typedef ilist<SDNode>::iterator allnodes_iterator; 102 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 103 allnodes_iterator allnodes_end() { return AllNodes.end(); } 104 105 /// getRoot - Return the root tag of the SelectionDAG. 106 /// 107 const SDOperand &getRoot() const { return Root; } 108 109 /// getEntryNode - Return the token chain corresponding to the entry of the 110 /// function. 111 const SDOperand &getEntryNode() const { return EntryNode; } 112 113 /// setRoot - Set the current root tag of the SelectionDAG. 114 /// 115 const SDOperand &setRoot(SDOperand N) { return Root = N; } 116 117 /// Combine - This iterates over the nodes in the SelectionDAG, folding 118 /// certain types of nodes together, or eliminating superfluous nodes. When 119 /// the AfterLegalize argument is set to 'true', Combine takes care not to 120 /// generate any nodes that will be illegal on the target. 121 void Combine(bool AfterLegalize, AliasAnalysis &AA); 122 123 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 124 /// only uses types natively supported by the target. 125 /// 126 /// Note that this is an involved process that may invalidate pointers into 127 /// the graph. 128 void LegalizeTypes(); 129 130 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 131 /// compatible with the target instruction selector, as indicated by the 132 /// TargetLowering object. 133 /// 134 /// Note that this is an involved process that may invalidate pointers into 135 /// the graph. 136 void Legalize(); 137 138 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 139 /// SelectionDAG. 140 void RemoveDeadNodes(); 141 142 /// DeleteNode - Remove the specified node from the system. This node must 143 /// have no referrers. 144 void DeleteNode(SDNode *N); 145 146 /// getVTList - Return an SDVTList that represents the list of values 147 /// specified. 148 SDVTList getVTList(MVT::ValueType VT); 149 SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2); 150 SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2,MVT::ValueType VT3); 151 SDVTList getVTList(const MVT::ValueType *VTs, unsigned NumVTs); 152 153 /// getNodeValueTypes - These are obsolete, use getVTList instead. 154 const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT) { 155 return getVTList(VT).VTs; 156 } 157 const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1, 158 MVT::ValueType VT2) { 159 return getVTList(VT1, VT2).VTs; 160 } 161 const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1,MVT::ValueType VT2, 162 MVT::ValueType VT3) { 163 return getVTList(VT1, VT2, VT3).VTs; 164 } 165 const MVT::ValueType *getNodeValueTypes(std::vector<MVT::ValueType> &vtList) { 166 return getVTList(&vtList[0], (unsigned)vtList.size()).VTs; 167 } 168 169 170 //===--------------------------------------------------------------------===// 171 // Node creation methods. 172 // 173 SDOperand getString(const std::string &Val); 174 SDOperand getConstant(uint64_t Val, MVT::ValueType VT, bool isTarget = false); 175 SDOperand getConstant(const APInt &Val, MVT::ValueType VT, bool isTarget = false); 176 SDOperand getIntPtrConstant(uint64_t Val, bool isTarget = false); 177 SDOperand getTargetConstant(uint64_t Val, MVT::ValueType VT) { 178 return getConstant(Val, VT, true); 179 } 180 SDOperand getTargetConstant(const APInt &Val, MVT::ValueType VT) { 181 return getConstant(Val, VT, true); 182 } 183 SDOperand getConstantFP(double Val, MVT::ValueType VT, bool isTarget = false); 184 SDOperand getConstantFP(const APFloat& Val, MVT::ValueType VT, 185 bool isTarget = false); 186 SDOperand getTargetConstantFP(double Val, MVT::ValueType VT) { 187 return getConstantFP(Val, VT, true); 188 } 189 SDOperand getTargetConstantFP(const APFloat& Val, MVT::ValueType VT) { 190 return getConstantFP(Val, VT, true); 191 } 192 SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 193 int offset = 0, bool isTargetGA = false); 194 SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 195 int offset = 0) { 196 return getGlobalAddress(GV, VT, offset, true); 197 } 198 SDOperand getFrameIndex(int FI, MVT::ValueType VT, bool isTarget = false); 199 SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT) { 200 return getFrameIndex(FI, VT, true); 201 } 202 SDOperand getJumpTable(int JTI, MVT::ValueType VT, bool isTarget = false); 203 SDOperand getTargetJumpTable(int JTI, MVT::ValueType VT) { 204 return getJumpTable(JTI, VT, true); 205 } 206 SDOperand getConstantPool(Constant *C, MVT::ValueType VT, 207 unsigned Align = 0, int Offs = 0, bool isT=false); 208 SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT, 209 unsigned Align = 0, int Offset = 0) { 210 return getConstantPool(C, VT, Align, Offset, true); 211 } 212 SDOperand getConstantPool(MachineConstantPoolValue *C, MVT::ValueType VT, 213 unsigned Align = 0, int Offs = 0, bool isT=false); 214 SDOperand getTargetConstantPool(MachineConstantPoolValue *C, 215 MVT::ValueType VT, unsigned Align = 0, 216 int Offset = 0) { 217 return getConstantPool(C, VT, Align, Offset, true); 218 } 219 SDOperand getBasicBlock(MachineBasicBlock *MBB); 220 SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT); 221 SDOperand getTargetExternalSymbol(const char *Sym, MVT::ValueType VT); 222 SDOperand getArgFlags(ISD::ArgFlagsTy Flags); 223 SDOperand getValueType(MVT::ValueType); 224 SDOperand getRegister(unsigned Reg, MVT::ValueType VT); 225 226 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) { 227 return getNode(ISD::CopyToReg, MVT::Other, Chain, 228 getRegister(Reg, N.getValueType()), N); 229 } 230 231 // This version of the getCopyToReg method takes an extra operand, which 232 // indicates that there is potentially an incoming flag value (if Flag is not 233 // null) and that there should be a flag result. 234 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N, 235 SDOperand Flag) { 236 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 237 SDOperand Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; 238 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 239 } 240 241 // Similar to last getCopyToReg() except parameter Reg is a SDOperand 242 SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N, 243 SDOperand Flag) { 244 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 245 SDOperand Ops[] = { Chain, Reg, N, Flag }; 246 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 247 } 248 249 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) { 250 const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other); 251 SDOperand Ops[] = { Chain, getRegister(Reg, VT) }; 252 return getNode(ISD::CopyFromReg, VTs, 2, Ops, 2); 253 } 254 255 // This version of the getCopyFromReg method takes an extra operand, which 256 // indicates that there is potentially an incoming flag value (if Flag is not 257 // null) and that there should be a flag result. 258 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT, 259 SDOperand Flag) { 260 const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other, MVT::Flag); 261 SDOperand Ops[] = { Chain, getRegister(Reg, VT), Flag }; 262 return getNode(ISD::CopyFromReg, VTs, 3, Ops, Flag.Val ? 3 : 2); 263 } 264 265 SDOperand getCondCode(ISD::CondCode Cond); 266 267 /// getZeroExtendInReg - Return the expression required to zero extend the Op 268 /// value assuming it was the smaller SrcTy value. 269 SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy); 270 271 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 272 /// a flag result (to ensure it's not CSE'd). 273 SDOperand getCALLSEQ_START(SDOperand Chain, SDOperand Op) { 274 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 275 SDOperand Ops[] = { Chain, Op }; 276 return getNode(ISD::CALLSEQ_START, VTs, 2, Ops, 2); 277 } 278 279 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a 280 /// flag result (to ensure it's not CSE'd). 281 SDOperand getCALLSEQ_END(SDOperand Chain, SDOperand Op1, SDOperand Op2, 282 SDOperand InFlag) { 283 SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag); 284 SmallVector<SDOperand, 4> Ops; 285 Ops.push_back(Chain); 286 Ops.push_back(Op1); 287 Ops.push_back(Op2); 288 Ops.push_back(InFlag); 289 return getNode(ISD::CALLSEQ_END, NodeTys, &Ops[0], 290 (unsigned)Ops.size() - (InFlag.Val == 0 ? 1 : 0)); 291 } 292 293 /// getNode - Gets or creates the specified node. 294 /// 295 SDOperand getNode(unsigned Opcode, MVT::ValueType VT); 296 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N); 297 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 298 SDOperand N1, SDOperand N2); 299 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 300 SDOperand N1, SDOperand N2, SDOperand N3); 301 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 302 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 303 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 304 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 305 SDOperand N5); 306 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 307 SDOperandPtr Ops, unsigned NumOps); 308 SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 309 SDOperandPtr Ops, unsigned NumOps); 310 SDOperand getNode(unsigned Opcode, const MVT::ValueType *VTs, unsigned NumVTs, 311 SDOperandPtr Ops, unsigned NumOps); 312 SDOperand getNode(unsigned Opcode, SDVTList VTs); 313 SDOperand getNode(unsigned Opcode, SDVTList VTs, SDOperand N); 314 SDOperand getNode(unsigned Opcode, SDVTList VTs, 315 SDOperand N1, SDOperand N2); 316 SDOperand getNode(unsigned Opcode, SDVTList VTs, 317 SDOperand N1, SDOperand N2, SDOperand N3); 318 SDOperand getNode(unsigned Opcode, SDVTList VTs, 319 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 320 SDOperand getNode(unsigned Opcode, SDVTList VTs, 321 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 322 SDOperand N5); 323 SDOperand getNode(unsigned Opcode, SDVTList VTs, 324 SDOperandPtr Ops, unsigned NumOps); 325 326 SDOperand getMemcpy(SDOperand Chain, SDOperand Dst, SDOperand Src, 327 SDOperand Size, unsigned Align, 328 bool AlwaysInline, 329 const Value *DstSV, uint64_t DstSVOff, 330 const Value *SrcSV, uint64_t SrcSVOff); 331 332 SDOperand getMemmove(SDOperand Chain, SDOperand Dst, SDOperand Src, 333 SDOperand Size, unsigned Align, 334 const Value *DstSV, uint64_t DstOSVff, 335 const Value *SrcSV, uint64_t SrcSVOff); 336 337 SDOperand getMemset(SDOperand Chain, SDOperand Dst, SDOperand Src, 338 SDOperand Size, unsigned Align, 339 const Value *DstSV, uint64_t DstSVOff); 340 341 /// getSetCC - Helper function to make it easier to build SetCC's if you just 342 /// have an ISD::CondCode instead of an SDOperand. 343 /// 344 SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS, 345 ISD::CondCode Cond) { 346 return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond)); 347 } 348 349 /// getVSetCC - Helper function to make it easier to build VSetCC's nodes 350 /// if you just have an ISD::CondCode instead of an SDOperand. 351 /// 352 SDOperand getVSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS, 353 ISD::CondCode Cond) { 354 return getNode(ISD::VSETCC, VT, LHS, RHS, getCondCode(Cond)); 355 } 356 357 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 358 /// just have an ISD::CondCode instead of an SDOperand. 359 /// 360 SDOperand getSelectCC(SDOperand LHS, SDOperand RHS, 361 SDOperand True, SDOperand False, ISD::CondCode Cond) { 362 return getNode(ISD::SELECT_CC, True.getValueType(), LHS, RHS, True, False, 363 getCondCode(Cond)); 364 } 365 366 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 367 /// and a source value as input. 368 SDOperand getVAArg(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 369 SDOperand SV); 370 371 /// getAtomic - Gets a node for an atomic op, produces result and chain, takes 372 // 3 operands 373 SDOperand getAtomic(unsigned Opcode, SDOperand Chain, SDOperand Ptr, 374 SDOperand Cmp, SDOperand Swp, MVT::ValueType VT); 375 376 /// getAtomic - Gets a node for an atomic op, produces result and chain, takes 377 // 2 operands 378 SDOperand getAtomic(unsigned Opcode, SDOperand Chain, SDOperand Ptr, 379 SDOperand Val, MVT::ValueType VT); 380 381 /// getLoad - Loads are not normal binary operators: their result type is not 382 /// determined by their operands, and they produce a value AND a token chain. 383 /// 384 SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 385 const Value *SV, int SVOffset, bool isVolatile=false, 386 unsigned Alignment=0); 387 SDOperand getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, 388 SDOperand Chain, SDOperand Ptr, const Value *SV, 389 int SVOffset, MVT::ValueType EVT, bool isVolatile=false, 390 unsigned Alignment=0); 391 SDOperand getIndexedLoad(SDOperand OrigLoad, SDOperand Base, 392 SDOperand Offset, ISD::MemIndexedMode AM); 393 SDOperand getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 394 MVT::ValueType VT, SDOperand Chain, 395 SDOperand Ptr, SDOperand Offset, 396 const Value *SV, int SVOffset, MVT::ValueType EVT, 397 bool isVolatile=false, unsigned Alignment=0); 398 399 /// getStore - Helper function to build ISD::STORE nodes. 400 /// 401 SDOperand getStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 402 const Value *SV, int SVOffset, bool isVolatile=false, 403 unsigned Alignment=0); 404 SDOperand getTruncStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 405 const Value *SV, int SVOffset, MVT::ValueType TVT, 406 bool isVolatile=false, unsigned Alignment=0); 407 SDOperand getIndexedStore(SDOperand OrigStoe, SDOperand Base, 408 SDOperand Offset, ISD::MemIndexedMode AM); 409 410 // getSrcValue - Construct a node to track a Value* through the backend. 411 SDOperand getSrcValue(const Value *v); 412 413 // getMemOperand - Construct a node to track a memory reference 414 // through the backend. 415 SDOperand getMemOperand(const MachineMemOperand &MO); 416 417 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 418 /// specified operands. If the resultant node already exists in the DAG, 419 /// this does not modify the specified node, instead it returns the node that 420 /// already exists. If the resultant node does not exist in the DAG, the 421 /// input node is returned. As a degenerate case, if you specify the same 422 /// input operands as the node already has, the input node is returned. 423 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op); 424 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2); 425 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 426 SDOperand Op3); 427 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 428 SDOperand Op3, SDOperand Op4); 429 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 430 SDOperand Op3, SDOperand Op4, SDOperand Op5); 431 SDOperand UpdateNodeOperands(SDOperand N, SDOperandPtr Ops, unsigned NumOps); 432 433 /// SelectNodeTo - These are used for target selectors to *mutate* the 434 /// specified node to have the specified return type, Target opcode, and 435 /// operands. Note that target opcodes are stored as 436 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. The 0th value 437 /// of the resultant node is returned. 438 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT); 439 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 440 SDOperand Op1); 441 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 442 SDOperand Op1, SDOperand Op2); 443 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 444 SDOperand Op1, SDOperand Op2, SDOperand Op3); 445 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 446 SDOperandPtr Ops, unsigned NumOps); 447 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 448 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 449 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 450 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 451 SDOperand Op3); 452 453 454 /// getTargetNode - These are used for target selectors to create a new node 455 /// with specified return type(s), target opcode, and operands. 456 /// 457 /// Note that getTargetNode returns the resultant node. If there is already a 458 /// node of the specified opcode and operands, it returns that node instead of 459 /// the current one. 460 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT); 461 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 462 SDOperand Op1); 463 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 464 SDOperand Op1, SDOperand Op2); 465 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 466 SDOperand Op1, SDOperand Op2, SDOperand Op3); 467 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 468 SDOperandPtr Ops, unsigned NumOps); 469 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 470 MVT::ValueType VT2); 471 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 472 MVT::ValueType VT2, SDOperand Op1); 473 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 474 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 475 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 476 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 477 SDOperand Op3); 478 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 479 MVT::ValueType VT2, 480 SDOperandPtr Ops, unsigned NumOps); 481 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 482 MVT::ValueType VT2, MVT::ValueType VT3, 483 SDOperand Op1, SDOperand Op2); 484 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 485 MVT::ValueType VT2, MVT::ValueType VT3, 486 SDOperand Op1, SDOperand Op2, SDOperand Op3); 487 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 488 MVT::ValueType VT2, MVT::ValueType VT3, 489 SDOperandPtr Ops, unsigned NumOps); 490 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 491 MVT::ValueType VT2, MVT::ValueType VT3, 492 MVT::ValueType VT4, 493 SDOperandPtr Ops, unsigned NumOps); 494 SDNode *getTargetNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 495 SDOperandPtr Ops, unsigned NumOps); 496 497 /// getNodeIfExists - Get the specified node if it's already available, or 498 /// else return NULL. 499 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, 500 SDOperandPtr Ops, unsigned NumOps); 501 502 /// DAGUpdateListener - Clients of various APIs that cause global effects on 503 /// the DAG can optionally implement this interface. This allows the clients 504 /// to handle the various sorts of updates that happen. 505 class DAGUpdateListener { 506 public: 507 virtual ~DAGUpdateListener(); 508 virtual void NodeDeleted(SDNode *N) = 0; 509 virtual void NodeUpdated(SDNode *N) = 0; 510 }; 511 512 /// RemoveDeadNode - Remove the specified node from the system. If any of its 513 /// operands then becomes dead, remove them as well. Inform UpdateListener 514 /// for each node deleted. 515 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0); 516 517 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 518 /// This can cause recursive merging of nodes in the DAG. Use the first 519 /// version if 'From' is known to have a single result, use the second 520 /// if you have two nodes with identical results, use the third otherwise. 521 /// 522 /// These methods all take an optional UpdateListener, which (if not null) is 523 /// informed about nodes that are deleted and modified due to recursive 524 /// changes in the dag. 525 /// 526 void ReplaceAllUsesWith(SDOperand From, SDOperand Op, 527 DAGUpdateListener *UpdateListener = 0); 528 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 529 DAGUpdateListener *UpdateListener = 0); 530 void ReplaceAllUsesWith(SDNode *From, SDOperandPtr To, 531 DAGUpdateListener *UpdateListener = 0); 532 533 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 534 /// uses of other values produced by From.Val alone. 535 void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 536 DAGUpdateListener *UpdateListener = 0); 537 538 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on 539 /// their allnodes order. It returns the maximum id. 540 unsigned AssignNodeIds(); 541 542 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 543 /// based on their topological order. It returns the maximum id and a vector 544 /// of the SDNodes* in assigned order by reference. 545 unsigned AssignTopologicalOrder(std::vector<SDNode*> &TopOrder); 546 547 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 548 /// operation. 549 static bool isCommutativeBinOp(unsigned Opcode) { 550 // FIXME: This should get its info from the td file, so that we can include 551 // target info. 552 switch (Opcode) { 553 case ISD::ADD: 554 case ISD::MUL: 555 case ISD::MULHU: 556 case ISD::MULHS: 557 case ISD::SMUL_LOHI: 558 case ISD::UMUL_LOHI: 559 case ISD::FADD: 560 case ISD::FMUL: 561 case ISD::AND: 562 case ISD::OR: 563 case ISD::XOR: 564 case ISD::ADDC: 565 case ISD::ADDE: return true; 566 default: return false; 567 } 568 } 569 570 void dump() const; 571 572 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 573 /// specified value type. 574 SDOperand CreateStackTemporary(MVT::ValueType VT); 575 576 /// FoldSetCC - Constant fold a setcc to true or false. 577 SDOperand FoldSetCC(MVT::ValueType VT, SDOperand N1, 578 SDOperand N2, ISD::CondCode Cond); 579 580 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 581 /// use this predicate to simplify operations downstream. 582 bool SignBitIsZero(SDOperand Op, unsigned Depth = 0) const; 583 584 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 585 /// use this predicate to simplify operations downstream. Op and Mask are 586 /// known to be the same type. 587 bool MaskedValueIsZero(SDOperand Op, const APInt &Mask, unsigned Depth = 0) 588 const; 589 590 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 591 /// known to be either zero or one and return them in the KnownZero/KnownOne 592 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 593 /// processing. Targets can implement the computeMaskedBitsForTargetNode 594 /// method in the TargetLowering class to allow target nodes to be understood. 595 void ComputeMaskedBits(SDOperand Op, const APInt &Mask, APInt &KnownZero, 596 APInt &KnownOne, unsigned Depth = 0) const; 597 598 /// ComputeNumSignBits - Return the number of times the sign bit of the 599 /// register is replicated into the other bits. We know that at least 1 bit 600 /// is always equal to the sign bit (itself), but other cases can give us 601 /// information. For example, immediately after an "SRA X, 2", we know that 602 /// the top 3 bits are all equal to each other, so we return 3. Targets can 603 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 604 /// class to allow target nodes to be understood. 605 unsigned ComputeNumSignBits(SDOperand Op, unsigned Depth = 0) const; 606 607 /// isVerifiedDebugInfoDesc - Returns true if the specified SDOperand has 608 /// been verified as a debug information descriptor. 609 bool isVerifiedDebugInfoDesc(SDOperand Op) const; 610 611 /// getShuffleScalarElt - Returns the scalar element that will make up the ith 612 /// element of the result of the vector shuffle. 613 SDOperand getShuffleScalarElt(const SDNode *N, unsigned Idx); 614 615private: 616 void RemoveNodeFromCSEMaps(SDNode *N); 617 SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); 618 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos); 619 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2, 620 void *&InsertPos); 621 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperandPtr Ops, unsigned NumOps, 622 void *&InsertPos); 623 624 void DeleteNodeNotInCSEMaps(SDNode *N); 625 626 // List of non-single value types. 627 std::list<std::vector<MVT::ValueType> > VTList; 628 629 // Maps to auto-CSE operations. 630 std::vector<CondCodeSDNode*> CondCodeNodes; 631 632 std::vector<SDNode*> ValueTypeNodes; 633 std::map<MVT::ValueType, SDNode*> ExtendedValueTypeNodes; 634 std::map<std::string, SDNode*> ExternalSymbols; 635 std::map<std::string, SDNode*> TargetExternalSymbols; 636 std::map<std::string, StringSDNode*> StringNodes; 637}; 638 639template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 640 typedef SelectionDAG::allnodes_iterator nodes_iterator; 641 static nodes_iterator nodes_begin(SelectionDAG *G) { 642 return G->allnodes_begin(); 643 } 644 static nodes_iterator nodes_end(SelectionDAG *G) { 645 return G->allnodes_end(); 646 } 647}; 648 649} // end namespace llvm 650 651#endif 652