include/llvm/CodeGen/SelectionDAG.h

   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/CodeGen/SelectionDAGNodes.h"
  19 #include <map>
  20 #include <string> // FIXME remove eventually, turning map into const char* map.
  21
  22 namespace llvm {
  23   class TargetLowering;
  24   class TargetMachine;
  25   class MachineFunction;
  26
  27 /// SelectionDAG class - This is used to represent a portion of an LLVM function
  28 /// in a low-level Data Dependence DAG representation suitable for instruction
  29 /// selection.  This DAG is constructed as the first step of instruction
  30 /// selection in order to allow implementation of machine specific optimizations
  31 /// and code simplifications.
  32 ///
  33 /// The representation used by the SelectionDAG is a target-independent
  34 /// representation, which has some similarities to the GCC RTL representation,
  35 /// but is significantly more simple, powerful, and is a graph form instead of a
  36 /// linear form.
  37 ///
  38 class SelectionDAG {
  39   const TargetMachine &TM;
  40   MachineFunction &MF;
  41
  42   // Root - The root of the entire DAG.  EntryNode - The starting token.
  43   SDOperand Root, EntryNode;
  44
  45   // AllNodes - All of the nodes in the DAG
  46   std::vector<SDNode*> AllNodes;
  47
  48   // Maps to auto-CSE operations.
  49   std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >,
  50            SDNode *> UnaryOps;
  51   std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >,
  52            SDNode *> BinaryOps;
  53
  54   std::map<std::pair<std::pair<SDOperand, SDOperand>, ISD::CondCode>,
  55            SetCCSDNode*> SetCCs;
  56
  57   std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >,
  58            SDNode *> Loads;
  59
  60   std::map<const GlobalValue*, SDNode*> GlobalValues;
  61   std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants;
  62   std::map<std::pair<double, MVT::ValueType>, SDNode*> ConstantFPs;
  63   std::map<int, SDNode*> FrameIndices;
  64   std::map<unsigned, SDNode*> ConstantPoolIndices;
  65   std::map<MachineBasicBlock *, SDNode*> BBNodes;
  66   std::map<std::string, SDNode*> ExternalSymbols;
  67 public:
  68   SelectionDAG(const TargetMachine &tm, MachineFunction &mf) : TM(tm), MF(mf) {
  69     EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
  70   }
  71   ~SelectionDAG();
  72
  73   MachineFunction &getMachineFunction() const { return MF; }
  74   const TargetMachine &getTarget() { return TM; }
  75
  76   /// viewGraph - Pop up a ghostview window with the DAG rendered using 'dot'.
  77   ///
  78   void viewGraph();
  79
  80
  81   typedef std::vector<SDNode*>::const_iterator allnodes_iterator;
  82   allnodes_iterator allnodes_begin() const { return AllNodes.begin(); }
  83   allnodes_iterator allnodes_end() const { return AllNodes.end(); }
  84
  85   /// getRoot - Return the root tag of the SelectionDAG.
  86   ///
  87   const SDOperand &getRoot() const { return Root; }
  88
  89   /// getEntryNode - Return the token chain corresponding to the entry of the
  90   /// function.
  91   const SDOperand &getEntryNode() const { return EntryNode; }
  92
  93   /// setRoot - Set the current root tag of the SelectionDAG.
  94   ///
  95   const SDOperand &setRoot(SDOperand N) { return Root = N; }
  96
  97   /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
  98   /// compatible with the target instruction selector, as indicated by the
  99   /// TargetLowering object.
 100   ///
 101   /// Note that this is an involved process that may invalidate pointers into
 102   /// the graph.
 103   void Legalize(TargetLowering &TLI);
 104
 105   /// RemoveDeadNodes - This method deletes all unreachable nodes in the
 106   /// SelectionDAG, including nodes (like loads) that have uses of their token
 107   /// chain but no other uses and no side effect.  If a node is passed in as an
 108   /// argument, it is used as the seed for node deletion.
 109   void RemoveDeadNodes(SDNode *N = 0);
 110
 111   SDOperand getConstant(uint64_t Val, MVT::ValueType VT);
 112   SDOperand getConstantFP(double Val, MVT::ValueType VT);
 113   SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT);
 114   SDOperand getFrameIndex(int FI, MVT::ValueType VT);
 115   SDOperand getConstantPool(unsigned CPIdx, MVT::ValueType VT);
 116   SDOperand getBasicBlock(MachineBasicBlock *MBB);
 117   SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT);
 118
 119   SDOperand getCopyToReg(SDOperand Chain, SDOperand N, unsigned Reg) {
 120     // Note: these are auto-CSE'd because the caller doesn't make requests that
 121     // could cause duplicates to occur.
 122     SDNode *NN = new CopyRegSDNode(Chain, N, Reg);
 123     AllNodes.push_back(NN);
 124     return SDOperand(NN, 0);
 125   }
 126
 127   SDOperand getCopyFromReg(unsigned Reg, MVT::ValueType VT) {
 128     // Note: These nodes are auto-CSE'd by the caller of this method.
 129     SDNode *NN = new CopyRegSDNode(Reg, VT);
 130     AllNodes.push_back(NN);
 131     return SDOperand(NN, 0);
 132   }
 133
 134   /// getCall - Note that this destroys the vector of RetVals passed in.
 135   ///
 136   SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain,
 137                   SDOperand Callee) {
 138     SDNode *NN = new SDNode(ISD::CALL, Chain, Callee);
 139     NN->setValueTypes(RetVals);
 140     AllNodes.push_back(NN);
 141     return NN;
 142   }
 143
 144   SDOperand getSetCC(ISD::CondCode, SDOperand LHS, SDOperand RHS);
 145
 146   /// getNode - Gets or creates the specified node.
 147   ///
 148   SDOperand getNode(unsigned Opcode, MVT::ValueType VT);
 149   SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N);
 150   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
 151                     SDOperand N1, SDOperand N2);
 152   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
 153                     SDOperand N1, SDOperand N2, SDOperand N3);
 154   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
 155                     std::vector<SDOperand> &Children);
 156
 157   /// getLoad - Loads are not normal binary operators: their result type is not
 158   /// determined by their operands, and they produce a value AND a token chain.
 159   ///
 160   SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr);
 161
 162   void replaceAllUsesWith(SDOperand Old, SDOperand New) {
 163     assert(Old != New && "RAUW self!");
 164     assert(0 && "Unimplemented!");
 165   }
 166
 167   void dump() const;
 168
 169 private:
 170   void DeleteNodeIfDead(SDNode *N, void *NodeSet);
 171 };
 172
 173 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
 174   typedef SelectionDAG::allnodes_iterator nodes_iterator;
 175   static nodes_iterator nodes_begin(SelectionDAG *G) {
 176     return G->allnodes_begin();
 177   }
 178   static nodes_iterator nodes_end(SelectionDAG *G) {
 179     return G->allnodes_end();
 180   }
 181 };
 182
 183 }
 184
 185 #endif