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