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