SelectionDAG.h revision fd4418fc9b4725c44210c169c4d6500be468ca70
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, const Value* PtrVal, 374 unsigned Alignment=0); 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, const Value* PtrVal, 380 unsigned Alignment = 0); 381 382 /// getLoad - Loads are not normal binary operators: their result type is not 383 /// determined by their operands, and they produce a value AND a token chain. 384 /// 385 SDOperand getLoad(MVT VT, SDOperand Chain, SDOperand Ptr, 386 const Value *SV, int SVOffset, bool isVolatile=false, 387 unsigned Alignment=0); 388 SDOperand getExtLoad(ISD::LoadExtType ExtType, MVT VT, 389 SDOperand Chain, SDOperand Ptr, const Value *SV, 390 int SVOffset, MVT EVT, bool isVolatile=false, 391 unsigned Alignment=0); 392 SDOperand getIndexedLoad(SDOperand OrigLoad, SDOperand Base, 393 SDOperand Offset, ISD::MemIndexedMode AM); 394 SDOperand getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 395 MVT VT, SDOperand Chain, 396 SDOperand Ptr, SDOperand Offset, 397 const Value *SV, int SVOffset, MVT EVT, 398 bool isVolatile=false, unsigned Alignment=0); 399 400 /// getStore - Helper function to build ISD::STORE nodes. 401 /// 402 SDOperand getStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 403 const Value *SV, int SVOffset, bool isVolatile=false, 404 unsigned Alignment=0); 405 SDOperand getTruncStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 406 const Value *SV, int SVOffset, MVT TVT, 407 bool isVolatile=false, unsigned Alignment=0); 408 SDOperand getIndexedStore(SDOperand OrigStoe, SDOperand Base, 409 SDOperand Offset, ISD::MemIndexedMode AM); 410 411 // getSrcValue - Construct a node to track a Value* through the backend. 412 SDOperand getSrcValue(const Value *v); 413 414 // getMemOperand - Construct a node to track a memory reference 415 // through the backend. 416 SDOperand getMemOperand(const MachineMemOperand &MO); 417 418 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 419 /// specified operands. If the resultant node already exists in the DAG, 420 /// this does not modify the specified node, instead it returns the node that 421 /// already exists. If the resultant node does not exist in the DAG, the 422 /// input node is returned. As a degenerate case, if you specify the same 423 /// input operands as the node already has, the input node is returned. 424 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op); 425 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2); 426 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 427 SDOperand Op3); 428 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 429 SDOperand Op3, SDOperand Op4); 430 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 431 SDOperand Op3, SDOperand Op4, SDOperand Op5); 432 SDOperand UpdateNodeOperands(SDOperand N, SDOperandPtr Ops, unsigned NumOps); 433 434 /// SelectNodeTo - These are used for target selectors to *mutate* the 435 /// specified node to have the specified return type, Target opcode, and 436 /// operands. Note that target opcodes are stored as 437 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. The 0th value 438 /// of the resultant node is returned. 439 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT); 440 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, SDOperand Op1); 441 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 442 SDOperand Op1, SDOperand Op2); 443 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 444 SDOperand Op1, SDOperand Op2, SDOperand Op3); 445 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, 446 SDOperandPtr Ops, unsigned NumOps); 447 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 448 MVT VT2, SDOperand Op1, SDOperand Op2); 449 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT1, 450 MVT VT2, SDOperand Op1, SDOperand Op2, 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 VT); 460 SDNode *getTargetNode(unsigned Opcode, MVT VT, SDOperand Op1); 461 SDNode *getTargetNode(unsigned Opcode, MVT VT, SDOperand Op1, SDOperand Op2); 462 SDNode *getTargetNode(unsigned Opcode, MVT VT, 463 SDOperand Op1, SDOperand Op2, SDOperand Op3); 464 SDNode *getTargetNode(unsigned Opcode, MVT VT, 465 SDOperandPtr Ops, unsigned NumOps); 466 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2); 467 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, SDOperand Op1); 468 SDNode *getTargetNode(unsigned Opcode, MVT VT1, 469 MVT VT2, SDOperand Op1, SDOperand Op2); 470 SDNode *getTargetNode(unsigned Opcode, MVT VT1, 471 MVT VT2, SDOperand Op1, SDOperand Op2, SDOperand Op3); 472 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, 473 SDOperandPtr Ops, unsigned NumOps); 474 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, 475 SDOperand Op1, SDOperand Op2); 476 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, 477 SDOperand Op1, SDOperand Op2, SDOperand Op3); 478 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, 479 SDOperandPtr Ops, unsigned NumOps); 480 SDNode *getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3, MVT VT4, 481 SDOperandPtr Ops, unsigned NumOps); 482 SDNode *getTargetNode(unsigned Opcode, std::vector<MVT> &ResultTys, 483 SDOperandPtr Ops, unsigned NumOps); 484 485 /// getNodeIfExists - Get the specified node if it's already available, or 486 /// else return NULL. 487 SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, 488 SDOperandPtr Ops, unsigned NumOps); 489 490 /// DAGUpdateListener - Clients of various APIs that cause global effects on 491 /// the DAG can optionally implement this interface. This allows the clients 492 /// to handle the various sorts of updates that happen. 493 class DAGUpdateListener { 494 public: 495 virtual ~DAGUpdateListener(); 496 497 /// NodeDeleted - The node N that was deleted and, if E is not null, an 498 /// equivalent node E that replaced it. 499 virtual void NodeDeleted(SDNode *N, SDNode *E) = 0; 500 501 /// NodeUpdated - The node N that was updated. 502 virtual void NodeUpdated(SDNode *N) = 0; 503 }; 504 505 /// RemoveDeadNode - Remove the specified node from the system. If any of its 506 /// operands then becomes dead, remove them as well. Inform UpdateListener 507 /// for each node deleted. 508 void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0); 509 510 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 511 /// This can cause recursive merging of nodes in the DAG. Use the first 512 /// version if 'From' is known to have a single result, use the second 513 /// if you have two nodes with identical results, use the third otherwise. 514 /// 515 /// These methods all take an optional UpdateListener, which (if not null) is 516 /// informed about nodes that are deleted and modified due to recursive 517 /// changes in the dag. 518 /// 519 void ReplaceAllUsesWith(SDOperand From, SDOperand Op, 520 DAGUpdateListener *UpdateListener = 0); 521 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 522 DAGUpdateListener *UpdateListener = 0); 523 void ReplaceAllUsesWith(SDNode *From, SDOperandPtr To, 524 DAGUpdateListener *UpdateListener = 0); 525 526 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 527 /// uses of other values produced by From.Val alone. 528 void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 529 DAGUpdateListener *UpdateListener = 0); 530 531 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on 532 /// their allnodes order. It returns the maximum id. 533 unsigned AssignNodeIds(); 534 535 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 536 /// based on their topological order. It returns the maximum id and a vector 537 /// of the SDNodes* in assigned order by reference. 538 unsigned AssignTopologicalOrder(std::vector<SDNode*> &TopOrder); 539 540 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 541 /// operation. 542 static bool isCommutativeBinOp(unsigned Opcode) { 543 // FIXME: This should get its info from the td file, so that we can include 544 // target info. 545 switch (Opcode) { 546 case ISD::ADD: 547 case ISD::MUL: 548 case ISD::MULHU: 549 case ISD::MULHS: 550 case ISD::SMUL_LOHI: 551 case ISD::UMUL_LOHI: 552 case ISD::FADD: 553 case ISD::FMUL: 554 case ISD::AND: 555 case ISD::OR: 556 case ISD::XOR: 557 case ISD::ADDC: 558 case ISD::ADDE: return true; 559 default: return false; 560 } 561 } 562 563 void dump() const; 564 565 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 566 /// specified value type. 567 SDOperand CreateStackTemporary(MVT VT); 568 569 /// FoldSetCC - Constant fold a setcc to true or false. 570 SDOperand FoldSetCC(MVT VT, SDOperand N1, 571 SDOperand N2, ISD::CondCode Cond); 572 573 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 574 /// use this predicate to simplify operations downstream. 575 bool SignBitIsZero(SDOperand Op, unsigned Depth = 0) const; 576 577 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 578 /// use this predicate to simplify operations downstream. Op and Mask are 579 /// known to be the same type. 580 bool MaskedValueIsZero(SDOperand Op, const APInt &Mask, unsigned Depth = 0) 581 const; 582 583 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 584 /// known to be either zero or one and return them in the KnownZero/KnownOne 585 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 586 /// processing. Targets can implement the computeMaskedBitsForTargetNode 587 /// method in the TargetLowering class to allow target nodes to be understood. 588 void ComputeMaskedBits(SDOperand Op, const APInt &Mask, APInt &KnownZero, 589 APInt &KnownOne, unsigned Depth = 0) const; 590 591 /// ComputeNumSignBits - Return the number of times the sign bit of the 592 /// register is replicated into the other bits. We know that at least 1 bit 593 /// is always equal to the sign bit (itself), but other cases can give us 594 /// information. For example, immediately after an "SRA X, 2", we know that 595 /// the top 3 bits are all equal to each other, so we return 3. Targets can 596 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 597 /// class to allow target nodes to be understood. 598 unsigned ComputeNumSignBits(SDOperand Op, unsigned Depth = 0) const; 599 600 /// isVerifiedDebugInfoDesc - Returns true if the specified SDOperand has 601 /// been verified as a debug information descriptor. 602 bool isVerifiedDebugInfoDesc(SDOperand Op) const; 603 604 /// getShuffleScalarElt - Returns the scalar element that will make up the ith 605 /// element of the result of the vector shuffle. 606 SDOperand getShuffleScalarElt(const SDNode *N, unsigned Idx); 607 608private: 609 void RemoveNodeFromCSEMaps(SDNode *N); 610 SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); 611 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos); 612 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2, 613 void *&InsertPos); 614 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperandPtr Ops, unsigned NumOps, 615 void *&InsertPos); 616 617 void DeleteNodeNotInCSEMaps(SDNode *N); 618 619 // List of non-single value types. 620 std::list<std::vector<MVT> > VTList; 621 622 // Maps to auto-CSE operations. 623 std::vector<CondCodeSDNode*> CondCodeNodes; 624 625 std::vector<SDNode*> ValueTypeNodes; 626 std::map<MVT, SDNode*, MVT::compareRawBits> ExtendedValueTypeNodes; 627 StringMap<SDNode*> ExternalSymbols; 628 StringMap<SDNode*> TargetExternalSymbols; 629 StringMap<StringSDNode*> StringNodes; 630}; 631 632template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 633 typedef SelectionDAG::allnodes_iterator nodes_iterator; 634 static nodes_iterator nodes_begin(SelectionDAG *G) { 635 return G->allnodes_begin(); 636 } 637 static nodes_iterator nodes_end(SelectionDAG *G) { 638 return G->allnodes_end(); 639 } 640}; 641 642} // end namespace llvm 643 644#endif 645