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