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