SelectionDAG.h revision 7f460203b0c5350e9b2c592f438e40f7a7de6e45
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 getConstant(uint64_t Val, MVT VT, bool isTarget = false); 177 SDOperand getConstant(const APInt &Val, MVT VT, bool isTarget = false); 178 SDOperand getIntPtrConstant(uint64_t Val, bool isTarget = false); 179 SDOperand getTargetConstant(uint64_t Val, MVT VT) { 180 return getConstant(Val, VT, true); 181 } 182 SDOperand getTargetConstant(const APInt &Val, MVT VT) { 183 return getConstant(Val, VT, true); 184 } 185 SDOperand getConstantFP(double Val, MVT VT, bool isTarget = false); 186 SDOperand getConstantFP(const APFloat& Val, MVT VT, bool isTarget = false); 187 SDOperand getTargetConstantFP(double Val, MVT VT) { 188 return getConstantFP(Val, VT, true); 189 } 190 SDOperand getTargetConstantFP(const APFloat& Val, MVT VT) { 191 return getConstantFP(Val, VT, true); 192 } 193 SDOperand getGlobalAddress(const GlobalValue *GV, MVT VT, 194 int offset = 0, bool isTargetGA = false); 195 SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT VT, 196 int offset = 0) { 197 return getGlobalAddress(GV, VT, offset, true); 198 } 199 SDOperand getFrameIndex(int FI, MVT VT, bool isTarget = false); 200 SDOperand getTargetFrameIndex(int FI, MVT VT) { 201 return getFrameIndex(FI, VT, true); 202 } 203 SDOperand getJumpTable(int JTI, MVT VT, bool isTarget = false); 204 SDOperand getTargetJumpTable(int JTI, MVT VT) { 205 return getJumpTable(JTI, VT, true); 206 } 207 SDOperand getConstantPool(Constant *C, MVT VT, 208 unsigned Align = 0, int Offs = 0, bool isT=false); 209 SDOperand getTargetConstantPool(Constant *C, MVT VT, 210 unsigned Align = 0, int Offset = 0) { 211 return getConstantPool(C, VT, Align, Offset, true); 212 } 213 SDOperand getConstantPool(MachineConstantPoolValue *C, MVT VT, 214 unsigned Align = 0, int Offs = 0, bool isT=false); 215 SDOperand getTargetConstantPool(MachineConstantPoolValue *C, 216 MVT VT, unsigned Align = 0, 217 int Offset = 0) { 218 return getConstantPool(C, VT, Align, Offset, true); 219 } 220 SDOperand getBasicBlock(MachineBasicBlock *MBB); 221 SDOperand getExternalSymbol(const char *Sym, MVT VT); 222 SDOperand getTargetExternalSymbol(const char *Sym, MVT VT); 223 SDOperand getArgFlags(ISD::ArgFlagsTy Flags); 224 SDOperand getValueType(MVT); 225 SDOperand getRegister(unsigned Reg, MVT VT); 226 SDOperand getDbgStopPoint(SDOperand Root, unsigned Line, unsigned Col, 227 const CompileUnitDesc *CU); 228 229 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) { 230 return getNode(ISD::CopyToReg, MVT::Other, Chain, 231 getRegister(Reg, N.getValueType()), N); 232 } 233 234 // This version of the getCopyToReg method takes an extra operand, which 235 // indicates that there is potentially an incoming flag value (if Flag is not 236 // null) and that there should be a flag result. 237 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N, 238 SDOperand Flag) { 239 const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 240 SDOperand Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; 241 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 242 } 243 244 // Similar to last getCopyToReg() except parameter Reg is a SDOperand 245 SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N, 246 SDOperand Flag) { 247 const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 248 SDOperand Ops[] = { Chain, Reg, N, Flag }; 249 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 250 } 251 252 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT VT) { 253 const MVT *VTs = getNodeValueTypes(VT, MVT::Other); 254 SDOperand Ops[] = { Chain, getRegister(Reg, VT) }; 255 return getNode(ISD::CopyFromReg, VTs, 2, Ops, 2); 256 } 257 258 // This version of the getCopyFromReg method takes an extra operand, which 259 // indicates that there is potentially an incoming flag value (if Flag is not 260 // null) and that there should be a flag result. 261 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT VT, 262 SDOperand Flag) { 263 const MVT *VTs = getNodeValueTypes(VT, MVT::Other, MVT::Flag); 264 SDOperand Ops[] = { Chain, getRegister(Reg, VT), Flag }; 265 return getNode(ISD::CopyFromReg, VTs, 3, Ops, Flag.Val ? 3 : 2); 266 } 267 268 SDOperand getCondCode(ISD::CondCode Cond); 269 270 /// getZeroExtendInReg - Return the expression required to zero extend the Op 271 /// value assuming it was the smaller SrcTy value. 272 SDOperand getZeroExtendInReg(SDOperand Op, MVT SrcTy); 273 274 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 275 /// a flag result (to ensure it's not CSE'd). 276 SDOperand getCALLSEQ_START(SDOperand Chain, SDOperand Op) { 277 const MVT *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 278 SDOperand Ops[] = { Chain, Op }; 279 return getNode(ISD::CALLSEQ_START, VTs, 2, Ops, 2); 280 } 281 282 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a 283 /// flag result (to ensure it's not CSE'd). 284 SDOperand getCALLSEQ_END(SDOperand Chain, SDOperand Op1, SDOperand Op2, 285 SDOperand InFlag) { 286 SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag); 287 SmallVector<SDOperand, 4> Ops; 288 Ops.push_back(Chain); 289 Ops.push_back(Op1); 290 Ops.push_back(Op2); 291 Ops.push_back(InFlag); 292 return getNode(ISD::CALLSEQ_END, NodeTys, &Ops[0], 293 (unsigned)Ops.size() - (InFlag.Val == 0 ? 1 : 0)); 294 } 295 296 /// getNode - Gets or creates the specified node. 297 /// 298 SDOperand getNode(unsigned Opcode, MVT VT); 299 SDOperand getNode(unsigned Opcode, MVT VT, SDOperand N); 300 SDOperand getNode(unsigned Opcode, MVT VT, SDOperand N1, SDOperand N2); 301 SDOperand getNode(unsigned Opcode, MVT VT, 302 SDOperand N1, SDOperand N2, SDOperand N3); 303 SDOperand getNode(unsigned Opcode, MVT VT, 304 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 305 SDOperand getNode(unsigned Opcode, MVT VT, 306 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 307 SDOperand N5); 308 SDOperand getNode(unsigned Opcode, MVT VT, SDOperandPtr Ops, unsigned NumOps); 309 SDOperand getNode(unsigned Opcode, std::vector<MVT> &ResultTys, 310 SDOperandPtr Ops, unsigned NumOps); 311 SDOperand getNode(unsigned Opcode, const MVT *VTs, unsigned NumVTs, 312 SDOperandPtr Ops, unsigned NumOps); 313 SDOperand getNode(unsigned Opcode, SDVTList VTs); 314 SDOperand getNode(unsigned Opcode, SDVTList VTs, SDOperand N); 315 SDOperand getNode(unsigned Opcode, SDVTList VTs, 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 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 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 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, const Value* PtrVal, 375 unsigned Alignment=0); 376 377 /// getAtomic - Gets a node for an atomic op, produces result and chain, takes 378 /// 2 operands 379 SDOperand getAtomic(unsigned Opcode, SDOperand Chain, SDOperand Ptr, 380 SDOperand Val, const Value* PtrVal, 381 unsigned Alignment = 0); 382 383 /// getMergeValues - Create a MERGE_VALUES node from the given types and ops. 384 /// Allowed to return something different (and simpler) if Simplify is true. 385 SDOperand getMergeValues(SDVTList VTs, SDOperandPtr Ops, unsigned NumOps, 386 bool Simplify = true) { 387 if (Simplify && NumOps == 1) 388 return Ops[0]; 389 return getNode(ISD::MERGE_VALUES, VTs, Ops, NumOps); 390 } 391 392 /// getLoad - Loads are not normal binary operators: their result type is not 393 /// determined by their operands, and they produce a value AND a token chain. 394 /// 395 SDOperand getLoad(MVT VT, SDOperand Chain, SDOperand Ptr, 396 const Value *SV, int SVOffset, bool isVolatile=false, 397 unsigned Alignment=0); 398 SDOperand getExtLoad(ISD::LoadExtType ExtType, MVT VT, 399 SDOperand Chain, SDOperand Ptr, const Value *SV, 400 int SVOffset, MVT EVT, bool isVolatile=false, 401 unsigned Alignment=0); 402 SDOperand getIndexedLoad(SDOperand OrigLoad, SDOperand Base, 403 SDOperand Offset, ISD::MemIndexedMode AM); 404 SDOperand getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 405 MVT VT, SDOperand Chain, 406 SDOperand Ptr, SDOperand Offset, 407 const Value *SV, int SVOffset, MVT EVT, 408 bool isVolatile=false, unsigned Alignment=0); 409 410 /// getStore - Helper function to build ISD::STORE nodes. 411 /// 412 SDOperand getStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 413 const Value *SV, int SVOffset, bool isVolatile=false, 414 unsigned Alignment=0); 415 SDOperand getTruncStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 416 const Value *SV, int SVOffset, MVT TVT, 417 bool isVolatile=false, unsigned Alignment=0); 418 SDOperand getIndexedStore(SDOperand OrigStoe, SDOperand Base, 419 SDOperand Offset, ISD::MemIndexedMode AM); 420 421 // getSrcValue - Construct a node to track a Value* through the backend. 422 SDOperand getSrcValue(const Value *v); 423 424 // getMemOperand - Construct a node to track a memory reference 425 // through the backend. 426 SDOperand getMemOperand(const MachineMemOperand &MO); 427 428 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 429 /// specified operands. If the resultant node already exists in the DAG, 430 /// this does not modify the specified node, instead it returns the node that 431 /// already exists. If the resultant node does not exist in the DAG, the 432 /// input node is returned. As a degenerate case, if you specify the same 433 /// input operands as the node already has, the input node is returned. 434 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op); 435 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2); 436 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 437 SDOperand Op3); 438 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 439 SDOperand Op3, SDOperand Op4); 440 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 441 SDOperand Op3, SDOperand Op4, SDOperand Op5); 442 SDOperand UpdateNodeOperands(SDOperand N, SDOperandPtr Ops, unsigned NumOps); 443 444 /// SelectNodeTo - These are used for target selectors to *mutate* the 445 /// specified node to have the specified return type, Target opcode, and 446 /// operands. Note that target opcodes are stored as 447 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. The 0th value 448 /// of the resultant node is returned. 449 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT); 450 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, SDOperand Op1); 451 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 452 SDOperand Op1, SDOperand Op2); 453 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 454 SDOperand Op1, SDOperand Op2, SDOperand Op3); 455 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 456 SDOperandPtr Ops, unsigned NumOps); 457 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 458 MVT VT2, SDOperand Op1, SDOperand Op2); 459 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 460 MVT VT2, SDOperand Op1, SDOperand Op2, SDOperand Op3); 461 462 463 /// getTargetNode - These are used for target selectors to create a new node 464 /// with specified return type(s), target opcode, and operands. 465 /// 466 /// Note that getTargetNode returns the resultant node. If there is already a 467 /// node of the specified opcode and operands, it returns that node instead of 468 /// the current one. 469 SDNode *getTargetNode(unsigned Opcode, MVT VT); 470 SDNode *getTargetNode(unsigned Opcode, MVT VT, SDOperand Op1); 471 SDNode *getTargetNode(unsigned Opcode, MVT VT, SDOperand Op1, SDOperand Op2); 472 SDNode *getTargetNode(unsigned Opcode, MVT VT, 473 SDOperand Op1, SDOperand Op2, SDOperand Op3); 474 SDNode *getTargetNode(unsigned Opcode, MVT VT, 475 SDOperandPtr Ops, unsigned NumOps); 476 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2); 477 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, SDOperand Op1); 478 SDNode *getTargetNode(unsigned Opcode, MVT VT1, 479 MVT VT2, SDOperand Op1, SDOperand Op2); 480 SDNode *getTargetNode(unsigned Opcode, MVT VT1, 481 MVT VT2, SDOperand Op1, SDOperand Op2, SDOperand Op3); 482 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, 483 SDOperandPtr Ops, unsigned NumOps); 484 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, 485 SDOperand Op1, SDOperand Op2); 486 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, 487 SDOperand Op1, SDOperand Op2, SDOperand Op3); 488 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, 489 SDOperandPtr Ops, unsigned NumOps); 490 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, MVT VT4, 491 SDOperandPtr Ops, unsigned NumOps); 492 SDNode *getTargetNode(unsigned Opcode, std::vector<MVT> &ResultTys, 493 SDOperandPtr Ops, unsigned NumOps); 494 495 /// getNodeIfExists - Get the specified node if it's already available, or 496 /// else return NULL. 497 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, 498 SDOperandPtr Ops, unsigned NumOps); 499 500 /// DAGUpdateListener - Clients of various APIs that cause global effects on 501 /// the DAG can optionally implement this interface. This allows the clients 502 /// to handle the various sorts of updates that happen. 503 class DAGUpdateListener { 504 public: 505 virtual ~DAGUpdateListener(); 506 507 /// NodeDeleted - The node N that was deleted and, if E is not null, an 508 /// equivalent node E that replaced it. 509 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0; 510 511 /// NodeUpdated - The node N that was updated. 512 virtual void NodeUpdated(SDNode *N) = 0; 513 }; 514 515 /// RemoveDeadNode - Remove the specified node from the system. If any of its 516 /// operands then becomes dead, remove them as well. Inform UpdateListener 517 /// for each node deleted. 518 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0); 519 520 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 521 /// This can cause recursive merging of nodes in the DAG. Use the first 522 /// version if 'From' is known to have a single result, use the second 523 /// if you have two nodes with identical results, use the third otherwise. 524 /// 525 /// These methods all take an optional UpdateListener, which (if not null) is 526 /// informed about nodes that are deleted and modified due to recursive 527 /// changes in the dag. 528 /// 529 void ReplaceAllUsesWith(SDOperand From, SDOperand Op, 530 DAGUpdateListener *UpdateListener = 0); 531 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 532 DAGUpdateListener *UpdateListener = 0); 533 void ReplaceAllUsesWith(SDNode *From, SDOperandPtr To, 534 DAGUpdateListener *UpdateListener = 0); 535 536 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 537 /// uses of other values produced by From.Val alone. 538 void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 539 DAGUpdateListener *UpdateListener = 0); 540 541 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on 542 /// their allnodes order. It returns the maximum id. 543 unsigned AssignNodeIds(); 544 545 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 546 /// based on their topological order. It returns the maximum id and a vector 547 /// of the SDNodes* in assigned order by reference. 548 unsigned AssignTopologicalOrder(std::vector<SDNode*> &TopOrder); 549 550 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 551 /// operation. 552 static bool isCommutativeBinOp(unsigned Opcode) { 553 // FIXME: This should get its info from the td file, so that we can include 554 // target info. 555 switch (Opcode) { 556 case ISD::ADD: 557 case ISD::MUL: 558 case ISD::MULHU: 559 case ISD::MULHS: 560 case ISD::SMUL_LOHI: 561 case ISD::UMUL_LOHI: 562 case ISD::FADD: 563 case ISD::FMUL: 564 case ISD::AND: 565 case ISD::OR: 566 case ISD::XOR: 567 case ISD::ADDC: 568 case ISD::ADDE: return true; 569 default: return false; 570 } 571 } 572 573 void dump() const; 574 575 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 576 /// specified value type. 577 SDOperand CreateStackTemporary(MVT VT); 578 579 /// FoldSetCC - Constant fold a setcc to true or false. 580 SDOperand FoldSetCC(MVT VT, SDOperand N1, 581 SDOperand N2, ISD::CondCode Cond); 582 583 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 584 /// use this predicate to simplify operations downstream. 585 bool SignBitIsZero(SDOperand Op, unsigned Depth = 0) const; 586 587 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 588 /// use this predicate to simplify operations downstream. Op and Mask are 589 /// known to be the same type. 590 bool MaskedValueIsZero(SDOperand Op, const APInt &Mask, unsigned Depth = 0) 591 const; 592 593 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 594 /// known to be either zero or one and return them in the KnownZero/KnownOne 595 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 596 /// processing. Targets can implement the computeMaskedBitsForTargetNode 597 /// method in the TargetLowering class to allow target nodes to be understood. 598 void ComputeMaskedBits(SDOperand Op, const APInt &Mask, APInt &KnownZero, 599 APInt &KnownOne, unsigned Depth = 0) const; 600 601 /// ComputeNumSignBits - Return the number of times the sign bit of the 602 /// register is replicated into the other bits. We know that at least 1 bit 603 /// is always equal to the sign bit (itself), but other cases can give us 604 /// information. For example, immediately after an "SRA X, 2", we know that 605 /// the top 3 bits are all equal to each other, so we return 3. Targets can 606 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 607 /// class to allow target nodes to be understood. 608 unsigned ComputeNumSignBits(SDOperand Op, unsigned Depth = 0) const; 609 610 /// isVerifiedDebugInfoDesc - Returns true if the specified SDOperand has 611 /// been verified as a debug information descriptor. 612 bool isVerifiedDebugInfoDesc(SDOperand Op) const; 613 614 /// getShuffleScalarElt - Returns the scalar element that will make up the ith 615 /// element of the result of the vector shuffle. 616 SDOperand getShuffleScalarElt(const SDNode *N, unsigned Idx); 617 618private: 619 void RemoveNodeFromCSEMaps(SDNode *N); 620 SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); 621 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos); 622 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2, 623 void *&InsertPos); 624 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperandPtr Ops, unsigned NumOps, 625 void *&InsertPos); 626 627 void DeleteNodeNotInCSEMaps(SDNode *N); 628 629 // List of non-single value types. 630 std::list<std::vector<MVT> > VTList; 631 632 // Maps to auto-CSE operations. 633 std::vector<CondCodeSDNode*> CondCodeNodes; 634 635 std::vector<SDNode*> ValueTypeNodes; 636 std::map<MVT, SDNode*, MVT::compareRawBits> ExtendedValueTypeNodes; 637 StringMap<SDNode*> ExternalSymbols; 638 StringMap<SDNode*> TargetExternalSymbols; 639}; 640 641template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 642 typedef SelectionDAG::allnodes_iterator nodes_iterator; 643 static nodes_iterator nodes_begin(SelectionDAG *G) { 644 return G->allnodes_begin(); 645 } 646 static nodes_iterator nodes_end(SelectionDAG *G) { 647 return G->allnodes_end(); 648 } 649}; 650 651} // end namespace llvm 652 653#endif 654