SelectionDAG.h revision 08ce9769718354e6767d3815e4c255e7c9fc0a46
1//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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" 20#include "llvm/CodeGen/SelectionDAGNodes.h" 21 22#include <list> 23#include <vector> 24#include <map> 25#include <set> 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 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 MachineModuleInfo *MMI; 51 52 /// Root - The root of the entire DAG. EntryNode - The starting token. 53 SDOperand Root, EntryNode; 54 55 /// AllNodes - A linked list of nodes in the current DAG. 56 ilist<SDNode> AllNodes; 57 58 /// CSEMap - This structure is used to memoize nodes, automatically performing 59 /// CSE with existing nodes with a duplicate is requested. 60 FoldingSet<SDNode> CSEMap; 61 62public: 63 SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineModuleInfo *mmi) 64 : TLI(tli), MF(mf), MMI(mmi) { 65 EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); 66 } 67 ~SelectionDAG(); 68 69 MachineFunction &getMachineFunction() const { return MF; } 70 const TargetMachine &getTarget() const; 71 TargetLowering &getTargetLoweringInfo() const { return TLI; } 72 MachineModuleInfo *getMachineModuleInfo() const { return MMI; } 73 74 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 75 /// 76 void viewGraph(); 77 78#ifndef NDEBUG 79 std::map<const SDNode *, std::string> NodeGraphAttrs; 80#endif 81 82 /// clearGraphAttrs - Clear all previously defined node graph attributes. 83 /// Intended to be used from a debugging tool (eg. gdb). 84 void clearGraphAttrs(); 85 86 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".) 87 /// 88 void setGraphAttrs(const SDNode *N, const char *Attrs); 89 90 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".) 91 /// Used from getNodeAttributes. 92 const std::string getGraphAttrs(const SDNode *N) const; 93 94 /// setGraphColor - Convenience for setting node color attribute. 95 /// 96 void setGraphColor(const SDNode *N, const char *Color); 97 98 typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 99 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 100 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 101 typedef ilist<SDNode>::iterator allnodes_iterator; 102 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 103 allnodes_iterator allnodes_end() { return AllNodes.end(); } 104 105 /// getRoot - Return the root tag of the SelectionDAG. 106 /// 107 const SDOperand &getRoot() const { return Root; } 108 109 /// getEntryNode - Return the token chain corresponding to the entry of the 110 /// function. 111 const SDOperand &getEntryNode() const { return EntryNode; } 112 113 /// setRoot - Set the current root tag of the SelectionDAG. 114 /// 115 const SDOperand &setRoot(SDOperand N) { return Root = N; } 116 117 /// Combine - This iterates over the nodes in the SelectionDAG, folding 118 /// certain types of nodes together, or eliminating superfluous nodes. When 119 /// the AfterLegalize argument is set to 'true', Combine takes care not to 120 /// generate any nodes that will be illegal on the target. 121 void Combine(bool AfterLegalize, AliasAnalysis &AA); 122 123 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 124 /// compatible with the target instruction selector, as indicated by the 125 /// TargetLowering object. 126 /// 127 /// Note that this is an involved process that may invalidate pointers into 128 /// the graph. 129 void Legalize(); 130 131 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 132 /// SelectionDAG. 133 void RemoveDeadNodes(); 134 135 /// RemoveDeadNode - Remove the specified node from the system. If any of its 136 /// operands then becomes dead, remove them as well. The vector Deleted is 137 /// populated with nodes that are deleted. 138 void RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted); 139 140 /// DeleteNode - Remove the specified node from the system. This node must 141 /// have no referrers. 142 void DeleteNode(SDNode *N); 143 144 /// getVTList - Return an SDVTList that represents the list of values 145 /// specified. 146 SDVTList getVTList(MVT::ValueType VT); 147 SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2); 148 SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2,MVT::ValueType VT3); 149 SDVTList getVTList(const MVT::ValueType *VTs, unsigned NumVTs); 150 151 /// getNodeValueTypes - These are obsolete, use getVTList instead. 152 const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT) { 153 return getVTList(VT).VTs; 154 } 155 const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1, 156 MVT::ValueType VT2) { 157 return getVTList(VT1, VT2).VTs; 158 } 159 const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1,MVT::ValueType VT2, 160 MVT::ValueType VT3) { 161 return getVTList(VT1, VT2, VT3).VTs; 162 } 163 const MVT::ValueType *getNodeValueTypes(std::vector<MVT::ValueType> &VTList) { 164 return getVTList(&VTList[0], VTList.size()).VTs; 165 } 166 167 168 //===--------------------------------------------------------------------===// 169 // Node creation methods. 170 // 171 SDOperand getString(const std::string &Val); 172 SDOperand getConstant(uint64_t Val, MVT::ValueType VT, bool isTarget = false); 173 SDOperand getTargetConstant(uint64_t Val, MVT::ValueType VT) { 174 return getConstant(Val, VT, true); 175 } 176 SDOperand getConstantFP(double Val, MVT::ValueType VT, bool isTarget = false); 177 SDOperand getConstantFP(const APFloat& Val, MVT::ValueType VT, 178 bool isTarget = false); 179 SDOperand getTargetConstantFP(double Val, MVT::ValueType VT) { 180 return getConstantFP(Val, VT, true); 181 } 182 SDOperand getTargetConstantFP(const APFloat& Val, MVT::ValueType VT) { 183 return getConstantFP(Val, VT, true); 184 } 185 SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 186 int offset = 0, bool isTargetGA = false); 187 SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 188 int offset = 0) { 189 return getGlobalAddress(GV, VT, offset, true); 190 } 191 SDOperand getFrameIndex(int FI, MVT::ValueType VT, bool isTarget = false); 192 SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT) { 193 return getFrameIndex(FI, VT, true); 194 } 195 SDOperand getJumpTable(int JTI, MVT::ValueType VT, bool isTarget = false); 196 SDOperand getTargetJumpTable(int JTI, MVT::ValueType VT) { 197 return getJumpTable(JTI, VT, true); 198 } 199 SDOperand getConstantPool(Constant *C, MVT::ValueType VT, 200 unsigned Align = 0, int Offs = 0, bool isT=false); 201 SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT, 202 unsigned Align = 0, int Offset = 0) { 203 return getConstantPool(C, VT, Align, Offset, true); 204 } 205 SDOperand getConstantPool(MachineConstantPoolValue *C, MVT::ValueType VT, 206 unsigned Align = 0, int Offs = 0, bool isT=false); 207 SDOperand getTargetConstantPool(MachineConstantPoolValue *C, 208 MVT::ValueType VT, unsigned Align = 0, 209 int Offset = 0) { 210 return getConstantPool(C, VT, Align, Offset, true); 211 } 212 SDOperand getBasicBlock(MachineBasicBlock *MBB); 213 SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT); 214 SDOperand getTargetExternalSymbol(const char *Sym, MVT::ValueType VT); 215 SDOperand getValueType(MVT::ValueType); 216 SDOperand getRegister(unsigned Reg, MVT::ValueType VT); 217 218 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) { 219 return getNode(ISD::CopyToReg, MVT::Other, Chain, 220 getRegister(Reg, N.getValueType()), N); 221 } 222 223 // This version of the getCopyToReg method takes an extra operand, which 224 // indicates that there is potentially an incoming flag value (if Flag is not 225 // null) and that there should be a flag result. 226 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N, 227 SDOperand Flag) { 228 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 229 SDOperand Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; 230 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 231 } 232 233 // Similar to last getCopyToReg() except parameter Reg is a SDOperand 234 SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N, 235 SDOperand Flag) { 236 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 237 SDOperand Ops[] = { Chain, Reg, N, Flag }; 238 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 239 } 240 241 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) { 242 const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other); 243 SDOperand Ops[] = { Chain, getRegister(Reg, VT) }; 244 return getNode(ISD::CopyFromReg, VTs, 2, Ops, 2); 245 } 246 247 // This version of the getCopyFromReg method takes an extra operand, which 248 // indicates that there is potentially an incoming flag value (if Flag is not 249 // null) and that there should be a flag result. 250 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT, 251 SDOperand Flag) { 252 const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other, MVT::Flag); 253 SDOperand Ops[] = { Chain, getRegister(Reg, VT), Flag }; 254 return getNode(ISD::CopyFromReg, VTs, 3, Ops, Flag.Val ? 3 : 2); 255 } 256 257 SDOperand getCondCode(ISD::CondCode Cond); 258 259 /// getZeroExtendInReg - Return the expression required to zero extend the Op 260 /// value assuming it was the smaller SrcTy value. 261 SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy); 262 263 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 264 /// a flag result (to ensure it's not CSE'd). 265 SDOperand getCALLSEQ_START(SDOperand Chain, SDOperand Op) { 266 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 267 SDOperand Ops[] = { Chain, Op }; 268 return getNode(ISD::CALLSEQ_START, VTs, 2, Ops, 2); 269 } 270 271 /// getNode - Gets or creates the specified node. 272 /// 273 SDOperand getNode(unsigned Opcode, MVT::ValueType VT); 274 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N); 275 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 276 SDOperand N1, SDOperand N2); 277 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 278 SDOperand N1, SDOperand N2, SDOperand N3); 279 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 280 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 281 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 282 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 283 SDOperand N5); 284 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 285 const SDOperand *Ops, unsigned NumOps); 286 SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 287 const SDOperand *Ops, unsigned NumOps); 288 SDOperand getNode(unsigned Opcode, const MVT::ValueType *VTs, unsigned NumVTs, 289 const SDOperand *Ops, unsigned NumOps); 290 SDOperand getNode(unsigned Opcode, SDVTList VTs); 291 SDOperand getNode(unsigned Opcode, SDVTList VTs, SDOperand N); 292 SDOperand getNode(unsigned Opcode, SDVTList VTs, 293 SDOperand N1, SDOperand N2); 294 SDOperand getNode(unsigned Opcode, SDVTList VTs, 295 SDOperand N1, SDOperand N2, SDOperand N3); 296 SDOperand getNode(unsigned Opcode, SDVTList VTs, 297 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 298 SDOperand getNode(unsigned Opcode, SDVTList VTs, 299 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 300 SDOperand N5); 301 SDOperand getNode(unsigned Opcode, SDVTList VTs, 302 const SDOperand *Ops, unsigned NumOps); 303 304 /// getSetCC - Helper function to make it easier to build SetCC's if you just 305 /// have an ISD::CondCode instead of an SDOperand. 306 /// 307 SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS, 308 ISD::CondCode Cond) { 309 return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond)); 310 } 311 312 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 313 /// just have an ISD::CondCode instead of an SDOperand. 314 /// 315 SDOperand getSelectCC(SDOperand LHS, SDOperand RHS, 316 SDOperand True, SDOperand False, ISD::CondCode Cond) { 317 return getNode(ISD::SELECT_CC, True.getValueType(), LHS, RHS, True, False, 318 getCondCode(Cond)); 319 } 320 321 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 322 /// and a source value as input. 323 SDOperand getVAArg(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 324 SDOperand SV); 325 326 /// getLoad - Loads are not normal binary operators: their result type is not 327 /// determined by their operands, and they produce a value AND a token chain. 328 /// 329 SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 330 const Value *SV, int SVOffset, bool isVolatile=false, 331 unsigned Alignment=0); 332 SDOperand getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, 333 SDOperand Chain, SDOperand Ptr, const Value *SV, 334 int SVOffset, MVT::ValueType EVT, bool isVolatile=false, 335 unsigned Alignment=0); 336 SDOperand getIndexedLoad(SDOperand OrigLoad, SDOperand Base, 337 SDOperand Offset, ISD::MemIndexedMode AM); 338 339 /// getStore - Helper function to build ISD::STORE nodes. 340 /// 341 SDOperand getStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 342 const Value *SV, int SVOffset, bool isVolatile=false, 343 unsigned Alignment=0); 344 SDOperand getTruncStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 345 const Value *SV, int SVOffset, MVT::ValueType TVT, 346 bool isVolatile=false, unsigned Alignment=0); 347 SDOperand getIndexedStore(SDOperand OrigStoe, SDOperand Base, 348 SDOperand Offset, ISD::MemIndexedMode AM); 349 350 // getSrcValue - construct a node to track a Value* through the backend 351 SDOperand getSrcValue(const Value* I, int offset = 0); 352 353 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 354 /// specified operands. If the resultant node already exists in the DAG, 355 /// this does not modify the specified node, instead it returns the node that 356 /// already exists. If the resultant node does not exist in the DAG, the 357 /// input node is returned. As a degenerate case, if you specify the same 358 /// input operands as the node already has, the input node is returned. 359 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op); 360 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2); 361 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 362 SDOperand Op3); 363 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 364 SDOperand Op3, SDOperand Op4); 365 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 366 SDOperand Op3, SDOperand Op4, SDOperand Op5); 367 SDOperand UpdateNodeOperands(SDOperand N, SDOperand *Ops, unsigned NumOps); 368 369 /// SelectNodeTo - These are used for target selectors to *mutate* the 370 /// specified node to have the specified return type, Target opcode, and 371 /// operands. Note that target opcodes are stored as 372 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. The 0th value 373 /// of the resultant node is returned. 374 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT); 375 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 376 SDOperand Op1); 377 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 378 SDOperand Op1, SDOperand Op2); 379 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 380 SDOperand Op1, SDOperand Op2, SDOperand Op3); 381 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 382 const SDOperand *Ops, unsigned NumOps); 383 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 384 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 385 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 386 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 387 SDOperand Op3); 388 389 390 /// getTargetNode - These are used for target selectors to create a new node 391 /// with specified return type(s), target opcode, and operands. 392 /// 393 /// Note that getTargetNode returns the resultant node. If there is already a 394 /// node of the specified opcode and operands, it returns that node instead of 395 /// the current one. 396 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT); 397 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 398 SDOperand Op1); 399 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 400 SDOperand Op1, SDOperand Op2); 401 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 402 SDOperand Op1, SDOperand Op2, SDOperand Op3); 403 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 404 const SDOperand *Ops, unsigned NumOps); 405 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 406 MVT::ValueType VT2, SDOperand Op1); 407 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 408 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 409 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 410 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 411 SDOperand Op3); 412 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 413 MVT::ValueType VT2, 414 const SDOperand *Ops, unsigned NumOps); 415 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 416 MVT::ValueType VT2, MVT::ValueType VT3, 417 SDOperand Op1, SDOperand Op2); 418 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 419 MVT::ValueType VT2, MVT::ValueType VT3, 420 SDOperand Op1, SDOperand Op2, SDOperand Op3); 421 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 422 MVT::ValueType VT2, MVT::ValueType VT3, 423 const SDOperand *Ops, unsigned NumOps); 424 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 425 MVT::ValueType VT2, MVT::ValueType VT3, 426 MVT::ValueType VT4, 427 const SDOperand *Ops, unsigned NumOps); 428 SDNode *getTargetNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 429 const SDOperand *Ops, unsigned NumOps); 430 431 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 432 /// This can cause recursive merging of nodes in the DAG. Use the first 433 /// version if 'From' is known to have a single result, use the second 434 /// if you have two nodes with identical results, use the third otherwise. 435 /// 436 /// These methods all take an optional vector, which (if not null) is 437 /// populated with any nodes that are deleted from the SelectionDAG, due to 438 /// new equivalences that are discovered. 439 /// 440 void ReplaceAllUsesWith(SDOperand From, SDOperand Op, 441 std::vector<SDNode*> *Deleted = 0); 442 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 443 std::vector<SDNode*> *Deleted = 0); 444 void ReplaceAllUsesWith(SDNode *From, const SDOperand *To, 445 std::vector<SDNode*> *Deleted = 0); 446 447 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 448 /// uses of other values produced by From.Val alone. The Deleted vector is 449 /// handled the same was as for ReplaceAllUsesWith, but it is required for 450 /// this method. 451 void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 452 std::vector<SDNode*> &Deleted); 453 454 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on 455 /// their allnodes order. It returns the maximum id. 456 unsigned AssignNodeIds(); 457 458 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 459 /// based on their topological order. It returns the maximum id and a vector 460 /// of the SDNodes* in assigned order by reference. 461 unsigned AssignTopologicalOrder(std::vector<SDNode*> &TopOrder); 462 463 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 464 /// operation. 465 static bool isCommutativeBinOp(unsigned Opcode) { 466 switch (Opcode) { 467 case ISD::ADD: 468 case ISD::MUL: 469 case ISD::MULHU: 470 case ISD::MULHS: 471 case ISD::SMUL_LOHI: 472 case ISD::UMUL_LOHI: 473 case ISD::FADD: 474 case ISD::FMUL: 475 case ISD::AND: 476 case ISD::OR: 477 case ISD::XOR: 478 case ISD::ADDC: 479 case ISD::ADDE: return true; 480 default: return false; 481 } 482 } 483 484 void dump() const; 485 486 /// FoldSetCC - Constant fold a setcc to true or false. 487 SDOperand FoldSetCC(MVT::ValueType VT, SDOperand N1, 488 SDOperand N2, ISD::CondCode Cond); 489 490 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 491 /// use this predicate to simplify operations downstream. Op and Mask are 492 /// known to be the same type. 493 bool MaskedValueIsZero(SDOperand Op, uint64_t Mask, unsigned Depth = 0) 494 const; 495 496 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 497 /// known to be either zero or one and return them in the KnownZero/KnownOne 498 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 499 /// processing. Targets can implement the computeMaskedBitsForTargetNode 500 /// method in the TargetLowering class to allow target nodes to be understood. 501 void ComputeMaskedBits(SDOperand Op, uint64_t Mask, uint64_t &KnownZero, 502 uint64_t &KnownOne, unsigned Depth = 0) const; 503 504 /// ComputeNumSignBits - Return the number of times the sign bit of the 505 /// register is replicated into the other bits. We know that at least 1 bit 506 /// is always equal to the sign bit (itself), but other cases can give us 507 /// information. For example, immediately after an "SRA X, 2", we know that 508 /// the top 3 bits are all equal to each other, so we return 3. Targets can 509 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 510 /// class to allow target nodes to be understood. 511 unsigned ComputeNumSignBits(SDOperand Op, unsigned Depth = 0) const; 512 513private: 514 void RemoveNodeFromCSEMaps(SDNode *N); 515 SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); 516 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos); 517 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2, 518 void *&InsertPos); 519 SDNode *FindModifiedNodeSlot(SDNode *N, const SDOperand *Ops, unsigned NumOps, 520 void *&InsertPos); 521 522 void DeleteNodeNotInCSEMaps(SDNode *N); 523 524 // List of non-single value types. 525 std::list<std::vector<MVT::ValueType> > VTList; 526 527 // Maps to auto-CSE operations. 528 std::vector<CondCodeSDNode*> CondCodeNodes; 529 530 std::vector<SDNode*> ValueTypeNodes; 531 std::map<std::string, SDNode*> ExternalSymbols; 532 std::map<std::string, SDNode*> TargetExternalSymbols; 533 std::map<std::string, StringSDNode*> StringNodes; 534}; 535 536template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 537 typedef SelectionDAG::allnodes_iterator nodes_iterator; 538 static nodes_iterator nodes_begin(SelectionDAG *G) { 539 return G->allnodes_begin(); 540 } 541 static nodes_iterator nodes_end(SelectionDAG *G) { 542 return G->allnodes_end(); 543 } 544}; 545 546} // end namespace llvm 547 548#endif 549