SelectionDAG.h revision 0f8d9c04d9feef86cee35cf5fecfb348a6b3de50
12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===// 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The LLVM Compiler Infrastructure 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This file was developed by the LLVM research group and is distributed under 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// the University of Illinois Open Source License. See LICENSE.TXT for details. 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 8116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch//===----------------------------------------------------------------------===// 95f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 10c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// This file declares the SelectionDAG class, and transitively defines the 115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// SDNode class and subclasses. 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef LLVM_CODEGEN_SELECTIONDAG_H 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define LLVM_CODEGEN_SELECTIONDAG_H 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/FoldingSet.h" 1990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "llvm/ADT/ilist" 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/CodeGen/SelectionDAGNodes.h" 21116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 22116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <list> 23116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <vector> 24116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <map> 25116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <set> 265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <string> 275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace llvm { 295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) class AliasAnalysis; 305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) class TargetLowering; 315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) class TargetMachine; 325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) class MachineModuleInfo; 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) class MachineFunction; 34424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) class MachineConstantPoolValue; 355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)/// SelectionDAG class - This is used to represent a portion of an LLVM function 375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)/// in a low-level Data Dependence DAG representation suitable for instruction 385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)/// selection. This DAG is constructed as the first step of instruction 395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)/// selection in order to allow implementation of machine specific optimizations 40424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)/// and code simplifications. 415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)/// 420529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch/// The representation used by the SelectionDAG is a target-independent 43424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)/// representation, which has some similarities to the GCC RTL representation, 44424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)/// but is significantly more simple, powerful, and is a graph form instead of a 455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)/// linear form. 465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)/// 475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)class SelectionDAG { 4890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) TargetLowering &TLI; 49cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) MachineFunction &MF; 50cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) MachineModuleInfo *MMI; 51cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 52cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// Root - The root of the entire DAG. EntryNode - The starting token. 53cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SDOperand Root, EntryNode; 545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 55116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch /// AllNodes - A linked list of nodes in the current DAG. 56116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ilist<SDNode> AllNodes; 57116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// CSEMap - This structure is used to memoize nodes, automatically performing 595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// CSE with existing nodes with a duplicate is requested. 605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) FoldingSet<SDNode> CSEMap; 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)public: 63116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineModuleInfo *mmi) 64116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch : TLI(tli), MF(mf), MMI(mmi) { 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ~SelectionDAG(); 685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) MachineFunction &getMachineFunction() const { return MF; } 705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const TargetMachine &getTarget() const; 715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TargetLowering &getTargetLoweringInfo() const { return TLI; } 72116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch MachineModuleInfo *getMachineModuleInfo() const { return MMI; } 735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 7590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// 7690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void viewGraph(); 7790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#ifndef NDEBUG 7990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::map<const SDNode *, std::string> NodeGraphAttrs; 805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#endif 81f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 8290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// clearGraphAttrs - Clear all previously defined node graph attributes. 83cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// Intended to be used from a debugging tool (eg. gdb). 84cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void clearGraphAttrs(); 85cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 86cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".) 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// 88cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void setGraphAttrs(const SDNode *N, const char *Attrs); 89cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".) 91424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) /// Used from getNodeAttributes. 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string getGraphAttrs(const SDNode *N) const; 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// setGraphColor - Convenience for setting node color attribute. 955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// 965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) void setGraphColor(const SDNode *N, const char *Color); 975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 1005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef ilist<SDNode>::iterator allnodes_iterator; 1025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 1035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) allnodes_iterator allnodes_end() { return AllNodes.end(); } 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 10590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// getRoot - Return the root tag of the SelectionDAG. 10690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// 1075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const SDOperand &getRoot() const { return Root; } 1085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// getEntryNode - Return the token chain corresponding to the entry of the 11090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// function. 11190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) const SDOperand &getEntryNode() const { return EntryNode; } 1125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 113116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch /// setRoot - Set the current root tag of the SelectionDAG. 114116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch /// 115116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const SDOperand &setRoot(SDOperand N) { return Root = N; } 116116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 117116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch /// Combine - This iterates over the nodes in the SelectionDAG, folding 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// certain types of nodes together, or eliminating superfluous nodes. When 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// the AfterLegalize argument is set to 'true', Combine takes care not to 1205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// generate any nodes that will be illegal on the target. 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void Combine(bool AfterLegalize, AliasAnalysis &AA); 1225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 1245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) /// only uses types natively supported by the target. 1255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// 1265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// Note that this is an involved process that may invalidate pointers into 1275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) /// the graph. 1285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) void LegalizeTypes(); 1295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 1315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// compatible with the target instruction selector, as indicated by the 13290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// TargetLowering object. 1335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// 1345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// Note that this is an involved process that may invalidate pointers into 13590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// the graph. 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void Legalize(); 1375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// RemoveDeadNodes - This method deletes all unreachable nodes in the 1395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// SelectionDAG. 1405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) void RemoveDeadNodes(); 1415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 14290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// RemoveDeadNode - Remove the specified node from the system. If any of its 14390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// operands then becomes dead, remove them as well. The vector Deleted is 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// populated with nodes that are deleted. 1455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) void RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted); 146116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 14790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) /// DeleteNode - Remove the specified node from the system. This node must 1487d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) /// have no referrers. 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void DeleteNode(SDNode *N); 1505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 151116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch /// getVTList - Return an SDVTList that represents the list of values 152116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch /// specified. 153116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch SDVTList getVTList(MVT::ValueType VT); 154116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2); 155116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2,MVT::ValueType VT3); 156116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch SDVTList getVTList(const MVT::ValueType *VTs, unsigned NumVTs); 157116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 158116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch /// getNodeValueTypes - These are obsolete, use getVTList instead. 159116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT) { 160116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return getVTList(VT).VTs; 161116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 162116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1, 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) MVT::ValueType VT2) { 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return getVTList(VT1, VT2).VTs; 1655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 166116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1,MVT::ValueType VT2, 167116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch MVT::ValueType VT3) { 168116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return getVTList(VT1, VT2, VT3).VTs; 169116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const MVT::ValueType *getNodeValueTypes(std::vector<MVT::ValueType> &VTList) { 17190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return getVTList(&VTList[0], VTList.size()).VTs; 1722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) //===--------------------------------------------------------------------===// 1762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Node creation methods. 1775f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SDOperand getString(const std::string &Val); 1795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SDOperand getConstant(uint64_t Val, MVT::ValueType VT, bool isTarget = false); 1802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SDOperand getTargetConstant(uint64_t Val, MVT::ValueType VT) { 1812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return getConstant(Val, VT, true); 1822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SDOperand getConstantFP(double Val, MVT::ValueType VT, bool isTarget = false); 184 SDOperand getConstantFP(const APFloat& Val, MVT::ValueType VT, 185 bool isTarget = false); 186 SDOperand getTargetConstantFP(double Val, MVT::ValueType VT) { 187 return getConstantFP(Val, VT, true); 188 } 189 SDOperand getTargetConstantFP(const APFloat& Val, MVT::ValueType VT) { 190 return getConstantFP(Val, VT, true); 191 } 192 SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 193 int offset = 0, bool isTargetGA = false); 194 SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 195 int offset = 0) { 196 return getGlobalAddress(GV, VT, offset, true); 197 } 198 SDOperand getFrameIndex(int FI, MVT::ValueType VT, bool isTarget = false); 199 SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT) { 200 return getFrameIndex(FI, VT, true); 201 } 202 SDOperand getJumpTable(int JTI, MVT::ValueType VT, bool isTarget = false); 203 SDOperand getTargetJumpTable(int JTI, MVT::ValueType VT) { 204 return getJumpTable(JTI, VT, true); 205 } 206 SDOperand getConstantPool(Constant *C, MVT::ValueType VT, 207 unsigned Align = 0, int Offs = 0, bool isT=false); 208 SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT, 209 unsigned Align = 0, int Offset = 0) { 210 return getConstantPool(C, VT, Align, Offset, true); 211 } 212 SDOperand getConstantPool(MachineConstantPoolValue *C, MVT::ValueType VT, 213 unsigned Align = 0, int Offs = 0, bool isT=false); 214 SDOperand getTargetConstantPool(MachineConstantPoolValue *C, 215 MVT::ValueType VT, unsigned Align = 0, 216 int Offset = 0) { 217 return getConstantPool(C, VT, Align, Offset, true); 218 } 219 SDOperand getBasicBlock(MachineBasicBlock *MBB); 220 SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT); 221 SDOperand getTargetExternalSymbol(const char *Sym, MVT::ValueType VT); 222 SDOperand getValueType(MVT::ValueType); 223 SDOperand getRegister(unsigned Reg, MVT::ValueType VT); 224 225 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) { 226 return getNode(ISD::CopyToReg, MVT::Other, Chain, 227 getRegister(Reg, N.getValueType()), N); 228 } 229 230 // This version of the getCopyToReg method takes an extra operand, which 231 // indicates that there is potentially an incoming flag value (if Flag is not 232 // null) and that there should be a flag result. 233 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N, 234 SDOperand Flag) { 235 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 236 SDOperand Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; 237 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 238 } 239 240 // Similar to last getCopyToReg() except parameter Reg is a SDOperand 241 SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N, 242 SDOperand Flag) { 243 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 244 SDOperand Ops[] = { Chain, Reg, N, Flag }; 245 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 246 } 247 248 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) { 249 const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other); 250 SDOperand Ops[] = { Chain, getRegister(Reg, VT) }; 251 return getNode(ISD::CopyFromReg, VTs, 2, Ops, 2); 252 } 253 254 // This version of the getCopyFromReg method takes an extra operand, which 255 // indicates that there is potentially an incoming flag value (if Flag is not 256 // null) and that there should be a flag result. 257 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT, 258 SDOperand Flag) { 259 const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other, MVT::Flag); 260 SDOperand Ops[] = { Chain, getRegister(Reg, VT), Flag }; 261 return getNode(ISD::CopyFromReg, VTs, 3, Ops, Flag.Val ? 3 : 2); 262 } 263 264 SDOperand getCondCode(ISD::CondCode Cond); 265 266 /// getZeroExtendInReg - Return the expression required to zero extend the Op 267 /// value assuming it was the smaller SrcTy value. 268 SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy); 269 270 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 271 /// a flag result (to ensure it's not CSE'd). 272 SDOperand getCALLSEQ_START(SDOperand Chain, SDOperand Op) { 273 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 274 SDOperand Ops[] = { Chain, Op }; 275 return getNode(ISD::CALLSEQ_START, VTs, 2, Ops, 2); 276 } 277 278 /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a 279 /// flag result (to ensure it's not CSE'd). 280 SDOperand getCALLSEQ_END(SDOperand Chain, SDOperand Op1, SDOperand Op2, 281 SDOperand InFlag) { 282 SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag); 283 SmallVector<SDOperand, 4> Ops; 284 Ops.push_back(Chain); 285 Ops.push_back(Op1); 286 Ops.push_back(Op2); 287 Ops.push_back(InFlag); 288 return getNode(ISD::CALLSEQ_END, NodeTys, &Ops[0], 289 Ops.size() - (InFlag.Val == 0 ? 1 : 0)); 290 } 291 292 /// getNode - Gets or creates the specified node. 293 /// 294 SDOperand getNode(unsigned Opcode, MVT::ValueType VT); 295 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N); 296 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 297 SDOperand N1, SDOperand N2); 298 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 299 SDOperand N1, SDOperand N2, SDOperand N3); 300 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 301 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 302 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 303 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 304 SDOperand N5); 305 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 306 const SDOperand *Ops, unsigned NumOps); 307 SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 308 const SDOperand *Ops, unsigned NumOps); 309 SDOperand getNode(unsigned Opcode, const MVT::ValueType *VTs, unsigned NumVTs, 310 const SDOperand *Ops, unsigned NumOps); 311 SDOperand getNode(unsigned Opcode, SDVTList VTs); 312 SDOperand getNode(unsigned Opcode, SDVTList VTs, SDOperand N); 313 SDOperand getNode(unsigned Opcode, SDVTList VTs, 314 SDOperand N1, SDOperand N2); 315 SDOperand getNode(unsigned Opcode, SDVTList VTs, 316 SDOperand N1, SDOperand N2, SDOperand N3); 317 SDOperand getNode(unsigned Opcode, SDVTList VTs, 318 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 319 SDOperand getNode(unsigned Opcode, SDVTList VTs, 320 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 321 SDOperand N5); 322 SDOperand getNode(unsigned Opcode, SDVTList VTs, 323 const SDOperand *Ops, unsigned NumOps); 324 325 SDOperand getMemcpy(SDOperand Chain, SDOperand Dest, SDOperand Src, 326 SDOperand Size, SDOperand Align, 327 SDOperand AlwaysInline); 328 329 SDOperand getMemmove(SDOperand Chain, SDOperand Dest, SDOperand Src, 330 SDOperand Size, SDOperand Align, 331 SDOperand AlwaysInline); 332 333 SDOperand getMemset(SDOperand Chain, SDOperand Dest, SDOperand Src, 334 SDOperand Size, SDOperand Align, 335 SDOperand AlwaysInline); 336 337 /// getSetCC - Helper function to make it easier to build SetCC's if you just 338 /// have an ISD::CondCode instead of an SDOperand. 339 /// 340 SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS, 341 ISD::CondCode Cond) { 342 return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond)); 343 } 344 345 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 346 /// just have an ISD::CondCode instead of an SDOperand. 347 /// 348 SDOperand getSelectCC(SDOperand LHS, SDOperand RHS, 349 SDOperand True, SDOperand False, ISD::CondCode Cond) { 350 return getNode(ISD::SELECT_CC, True.getValueType(), LHS, RHS, True, False, 351 getCondCode(Cond)); 352 } 353 354 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 355 /// and a source value as input. 356 SDOperand getVAArg(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 357 SDOperand SV); 358 359 /// getLoad - Loads are not normal binary operators: their result type is not 360 /// determined by their operands, and they produce a value AND a token chain. 361 /// 362 SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 363 const Value *SV, int SVOffset, bool isVolatile=false, 364 unsigned Alignment=0); 365 SDOperand getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, 366 SDOperand Chain, SDOperand Ptr, const Value *SV, 367 int SVOffset, MVT::ValueType EVT, bool isVolatile=false, 368 unsigned Alignment=0); 369 SDOperand getIndexedLoad(SDOperand OrigLoad, SDOperand Base, 370 SDOperand Offset, ISD::MemIndexedMode AM); 371 372 /// getStore - Helper function to build ISD::STORE nodes. 373 /// 374 SDOperand getStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 375 const Value *SV, int SVOffset, bool isVolatile=false, 376 unsigned Alignment=0); 377 SDOperand getTruncStore(SDOperand Chain, SDOperand Val, SDOperand Ptr, 378 const Value *SV, int SVOffset, MVT::ValueType TVT, 379 bool isVolatile=false, unsigned Alignment=0); 380 SDOperand getIndexedStore(SDOperand OrigStoe, SDOperand Base, 381 SDOperand Offset, ISD::MemIndexedMode AM); 382 383 // getSrcValue - construct a node to track a Value* through the backend 384 SDOperand getSrcValue(const Value* I, int offset = 0); 385 386 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 387 /// specified operands. If the resultant node already exists in the DAG, 388 /// this does not modify the specified node, instead it returns the node that 389 /// already exists. If the resultant node does not exist in the DAG, the 390 /// input node is returned. As a degenerate case, if you specify the same 391 /// input operands as the node already has, the input node is returned. 392 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op); 393 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2); 394 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 395 SDOperand Op3); 396 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 397 SDOperand Op3, SDOperand Op4); 398 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 399 SDOperand Op3, SDOperand Op4, SDOperand Op5); 400 SDOperand UpdateNodeOperands(SDOperand N, SDOperand *Ops, unsigned NumOps); 401 402 /// SelectNodeTo - These are used for target selectors to *mutate* the 403 /// specified node to have the specified return type, Target opcode, and 404 /// operands. Note that target opcodes are stored as 405 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. The 0th value 406 /// of the resultant node is returned. 407 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT); 408 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 409 SDOperand Op1); 410 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 411 SDOperand Op1, SDOperand Op2); 412 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 413 SDOperand Op1, SDOperand Op2, SDOperand Op3); 414 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 415 const SDOperand *Ops, unsigned NumOps); 416 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 417 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 418 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 419 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 420 SDOperand Op3); 421 422 423 /// getTargetNode - These are used for target selectors to create a new node 424 /// with specified return type(s), target opcode, and operands. 425 /// 426 /// Note that getTargetNode returns the resultant node. If there is already a 427 /// node of the specified opcode and operands, it returns that node instead of 428 /// the current one. 429 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT); 430 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 431 SDOperand Op1); 432 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 433 SDOperand Op1, SDOperand Op2); 434 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 435 SDOperand Op1, SDOperand Op2, SDOperand Op3); 436 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 437 const SDOperand *Ops, unsigned NumOps); 438 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 439 MVT::ValueType VT2); 440 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 441 MVT::ValueType VT2, SDOperand Op1); 442 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 443 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 444 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 445 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 446 SDOperand Op3); 447 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 448 MVT::ValueType VT2, 449 const SDOperand *Ops, unsigned NumOps); 450 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 451 MVT::ValueType VT2, MVT::ValueType VT3, 452 SDOperand Op1, SDOperand Op2); 453 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 454 MVT::ValueType VT2, MVT::ValueType VT3, 455 SDOperand Op1, SDOperand Op2, SDOperand Op3); 456 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 457 MVT::ValueType VT2, MVT::ValueType VT3, 458 const SDOperand *Ops, unsigned NumOps); 459 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 460 MVT::ValueType VT2, MVT::ValueType VT3, 461 MVT::ValueType VT4, 462 const SDOperand *Ops, unsigned NumOps); 463 SDNode *getTargetNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 464 const SDOperand *Ops, unsigned NumOps); 465 466 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 467 /// This can cause recursive merging of nodes in the DAG. Use the first 468 /// version if 'From' is known to have a single result, use the second 469 /// if you have two nodes with identical results, use the third otherwise. 470 /// 471 /// These methods all take an optional vector, which (if not null) is 472 /// populated with any nodes that are deleted from the SelectionDAG, due to 473 /// new equivalences that are discovered. 474 /// 475 void ReplaceAllUsesWith(SDOperand From, SDOperand Op, 476 std::vector<SDNode*> *Deleted = 0); 477 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 478 std::vector<SDNode*> *Deleted = 0); 479 void ReplaceAllUsesWith(SDNode *From, const SDOperand *To, 480 std::vector<SDNode*> *Deleted = 0); 481 482 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 483 /// uses of other values produced by From.Val alone. The Deleted vector is 484 /// handled the same was as for ReplaceAllUsesWith, but it is required for 485 /// this method. 486 void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 487 std::vector<SDNode*> *Deleted = 0); 488 489 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on 490 /// their allnodes order. It returns the maximum id. 491 unsigned AssignNodeIds(); 492 493 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 494 /// based on their topological order. It returns the maximum id and a vector 495 /// of the SDNodes* in assigned order by reference. 496 unsigned AssignTopologicalOrder(std::vector<SDNode*> &TopOrder); 497 498 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 499 /// operation. 500 static bool isCommutativeBinOp(unsigned Opcode) { 501 switch (Opcode) { 502 case ISD::ADD: 503 case ISD::MUL: 504 case ISD::MULHU: 505 case ISD::MULHS: 506 case ISD::SMUL_LOHI: 507 case ISD::UMUL_LOHI: 508 case ISD::FADD: 509 case ISD::FMUL: 510 case ISD::AND: 511 case ISD::OR: 512 case ISD::XOR: 513 case ISD::ADDC: 514 case ISD::ADDE: return true; 515 default: return false; 516 } 517 } 518 519 void dump() const; 520 521 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 522 /// specified value type. 523 SDOperand CreateStackTemporary(MVT::ValueType VT); 524 525 /// FoldSetCC - Constant fold a setcc to true or false. 526 SDOperand FoldSetCC(MVT::ValueType VT, SDOperand N1, 527 SDOperand N2, ISD::CondCode Cond); 528 529 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We 530 /// use this predicate to simplify operations downstream. Op and Mask are 531 /// known to be the same type. 532 bool MaskedValueIsZero(SDOperand Op, uint64_t Mask, unsigned Depth = 0) 533 const; 534 535 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 536 /// known to be either zero or one and return them in the KnownZero/KnownOne 537 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 538 /// processing. Targets can implement the computeMaskedBitsForTargetNode 539 /// method in the TargetLowering class to allow target nodes to be understood. 540 void ComputeMaskedBits(SDOperand Op, uint64_t Mask, uint64_t &KnownZero, 541 uint64_t &KnownOne, unsigned Depth = 0) const; 542 543 /// ComputeNumSignBits - Return the number of times the sign bit of the 544 /// register is replicated into the other bits. We know that at least 1 bit 545 /// is always equal to the sign bit (itself), but other cases can give us 546 /// information. For example, immediately after an "SRA X, 2", we know that 547 /// the top 3 bits are all equal to each other, so we return 3. Targets can 548 /// implement the ComputeNumSignBitsForTarget method in the TargetLowering 549 /// class to allow target nodes to be understood. 550 unsigned ComputeNumSignBits(SDOperand Op, unsigned Depth = 0) const; 551 552private: 553 void RemoveNodeFromCSEMaps(SDNode *N); 554 SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); 555 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos); 556 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2, 557 void *&InsertPos); 558 SDNode *FindModifiedNodeSlot(SDNode *N, const SDOperand *Ops, unsigned NumOps, 559 void *&InsertPos); 560 561 void DeleteNodeNotInCSEMaps(SDNode *N); 562 563 // List of non-single value types. 564 std::list<std::vector<MVT::ValueType> > VTList; 565 566 // Maps to auto-CSE operations. 567 std::vector<CondCodeSDNode*> CondCodeNodes; 568 569 std::vector<SDNode*> ValueTypeNodes; 570 std::map<MVT::ValueType, SDNode*> ExtendedValueTypeNodes; 571 std::map<std::string, SDNode*> ExternalSymbols; 572 std::map<std::string, SDNode*> TargetExternalSymbols; 573 std::map<std::string, StringSDNode*> StringNodes; 574}; 575 576template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 577 typedef SelectionDAG::allnodes_iterator nodes_iterator; 578 static nodes_iterator nodes_begin(SelectionDAG *G) { 579 return G->allnodes_begin(); 580 } 581 static nodes_iterator nodes_end(SelectionDAG *G) { 582 return G->allnodes_end(); 583 } 584}; 585 586} // end namespace llvm 587 588#endif 589