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