include/llvm/CodeGen/SelectionDAG.h

   1 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG Rep. ----*- C++ -*-===//
   2 //
   3 // This file declares the SelectionDAG class, which is used to represent an LLVM
   4 // function in a low-level representation suitable for instruction selection.
   5 // This DAG is constructed as the first step of instruction selection in order
   6 // to allow implementation of machine specific optimizations and code
   7 // simplifications.
   8 //
   9 // The representation used by the SelectionDAG is a target-independent
  10 // representation, which is loosly modeled after the GCC RTL representation, but
  11 // is significantly simpler.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
  16 #define LLVM_CODEGEN_SELECTIONDAG_H
  17
  18 #include "llvm/CodeGen/ValueTypes.h"
  19 #include "Support/DataTypes.h"
  20 #include <map>
  21 #include <vector>
  22 #include <cassert>
  23 class Value;
  24 class Type;
  25 class Instruction;
  26 class CallInst;
  27 class BasicBlock;
  28 class MachineBasicBlock;
  29 class MachineFunction;
  30 class TargetMachine;
  31 class SelectionDAGNode;
  32 class SelectionDAGBlock;
  33 class SelectionDAGBuilder;
  34 class SelectionDAGTargetBuilder;
  35
  36 /// ISD namespace - This namespace contains an enum which represents all of the
  37 /// SelectionDAG node types and value types.
  38 ///
  39 namespace ISD {
  40   enum NodeType {
  41     // ChainNode nodes are used to sequence operations within a basic block
  42     // which cannot be reordered (such as loads, stores, calls, etc).
  43     // BlockChainNodes are used to connect the DAG's for different basic blocks
  44     // into one big DAG.
  45     ChainNode, BlockChainNode,
  46
  47     // ProtoNodes are nodes that are only half way constructed.
  48     ProtoNode,
  49
  50     // Leaf nodes
  51     Constant, FrameIndex, BasicBlock,
  52
  53     // Simple binary arithmetic operators
  54     Plus, Minus, Times, SDiv, UDiv, SRem, URem,
  55
  56     // Bitwise operators
  57     And, Or, Xor,
  58
  59     // Comparisons
  60     SetEQ, SetNE, SetLT, SetLE, SetGT, SetGE,
  61
  62     // Control flow instructions
  63     Br, BrCond, Switch, Ret, RetVoid,
  64
  65     // Other operators
  66     Load, Store, PHI, Call,
  67
  68     // Unknown operators, of a specified arity
  69     Unspec1, Unspec2
  70   };
  71 }
  72
  73 class SelectionDAG {
  74   friend class SelectionDAGBuilder;
  75   MachineFunction &F;
  76   const TargetMachine &TM;
  77   MVT::ValueType PointerType;    // The ValueType the target uses for pointers
  78
  79   // ValueMap - The SelectionDAGNode for each LLVM value in the function.
  80   std::map<const Value*, SelectionDAGNode*> ValueMap;
  81
  82   // BlockMap - The MachineBasicBlock created for each LLVM BasicBlock
  83   std::map<const BasicBlock*, MachineBasicBlock*> BlockMap;
  84
  85   // Root - The root of the entire DAG
  86   SelectionDAGNode *Root;
  87
  88   // AllNodes - All of the nodes in the DAG
  89   std::vector<SelectionDAGNode*> AllNodes;
  90 public:
  91   /// SelectionDAG constructor - Build a SelectionDAG for the specified
  92   /// function.  Implemented in DAGBuilder.cpp
  93   ///
  94   SelectionDAG(MachineFunction &F, const TargetMachine &TM,
  95                SelectionDAGTargetBuilder &SDTB);
  96   ~SelectionDAG();
  97
  98   /// getValueType - Return the ValueType for the specified LLVM type.  This
  99   /// method works on all scalar LLVM types.
 100   ///
 101   MVT::ValueType getValueType(const Type *Ty) const;
 102
 103   /// getRoot - Return the root of the current SelectionDAG.
 104   ///
 105   SelectionDAGNode *getRoot() const { return Root; }
 106
 107   /// getMachineFunction - Return the MachineFunction object that this
 108   /// SelectionDAG corresponds to.
 109   ///
 110   MachineFunction &getMachineFunction() const { return F; }
 111
 112   //===--------------------------------------------------------------------===//
 113   // Addition and updating methods
 114   //
 115
 116   /// addNode - Add the specified node to the SelectionDAG so that it will be
 117   /// deleted when the DAG is...
 118   ///
 119   SelectionDAGNode *addNode(SelectionDAGNode *N) {
 120     AllNodes.push_back(N);
 121     return N;
 122   }
 123
 124   /// addNodeForValue - Add the specified node to the SelectionDAG so that it
 125   /// will be deleted when the DAG is... and update the value map to indicate
 126   /// that the specified DAG node computes the value.  Note that it is an error
 127   /// to specify multiple DAG nodes that compute the same value.
 128   ///
 129   SelectionDAGNode *addNodeForValue(SelectionDAGNode *N, const Value *V) {
 130     assert(ValueMap.count(V) == 0 && "Value already has a DAG node!");
 131     return addNode(ValueMap[V] = N);
 132   }
 133
 134   void dump() const;
 135 private:
 136   void addInstructionToDAG(const Instruction &I, const BasicBlock &BB);
 137 };
 138
 139
 140 /// SelectionDAGReducedValue - During the reducer pass we need the ability to
 141 /// add an arbitrary (but usually 1 or 0) number of arbitrarily sized values to
 142 /// the selection DAG.  Because of this, we represent these values as a singly
 143 /// linked list of values attached to the DAGNode.  We end up putting the
 144 /// arbitrary state for the value in subclasses of this node.
 145 ///
 146 /// Note that this class does not have a virtual dtor, this is because we know
 147 /// that the subclasses will not hold state that needs to be destroyed.
 148 ///
 149 class SelectionDAGReducedValue {
 150   unsigned Code;
 151   SelectionDAGReducedValue *Next;
 152 public:
 153   SelectionDAGReducedValue(unsigned C) : Code(C), Next(0) {}
 154
 155   /// getValueCode - Return the code for this reducer value...
 156   ///
 157   unsigned getValueCode() const { return Code; }
 158
 159   /// getNext - Return the next value in the list
 160   ///
 161   const SelectionDAGReducedValue *getNext() const { return Next; }
 162   void setNext(SelectionDAGReducedValue *N) { Next = N; }
 163
 164   SelectionDAGReducedValue *getNext() { return Next; }
 165 };
 166
 167
 168
 169 /// SelectionDAGNode - Represents one node in the selection DAG.
 170 ///
 171 class SelectionDAGNode {
 172   std::vector<SelectionDAGNode*> Uses;
 173   ISD::NodeType  NodeType;
 174   MVT::ValueType ValueType;
 175   MachineBasicBlock *BB;
 176   SelectionDAGReducedValue *ValList;
 177
 178   /// Costs - Each pair of elements of 'Costs' contains the cost of producing
 179   /// the value with the target specific slot number and the production number
 180   /// to use to produce it.  A zero value for the production number indicates
 181   /// that the cost has not yet been computed.
 182   unsigned *Costs;
 183 public:
 184   SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT,
 185                    MachineBasicBlock *bb = 0)
 186     : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {}
 187
 188   SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
 189                    SelectionDAGNode *N)
 190     : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
 191     assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
 192     Uses.reserve(1); Uses.push_back(N);
 193   }
 194   SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
 195                    SelectionDAGNode *N1, SelectionDAGNode *N2)
 196     : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
 197     assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
 198     Uses.reserve(2); Uses.push_back(N1); Uses.push_back(N2);
 199   }
 200   SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
 201                    SelectionDAGNode *N1, SelectionDAGNode *N2,
 202                    SelectionDAGNode *N3)
 203     : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
 204     assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
 205     Uses.reserve(3); Uses.push_back(N1); Uses.push_back(N2); Uses.push_back(N3);
 206   }
 207
 208   ~SelectionDAGNode() { delete [] Costs; delete ValList; }
 209
 210   void setNode(ISD::NodeType NT, MachineBasicBlock *bb) {
 211     assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
 212     NodeType = NT; BB = bb;
 213   }
 214   void setNode(ISD::NodeType NT, MachineBasicBlock *bb, SelectionDAGNode *N) {
 215     assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
 216     NodeType = NT; BB = bb; Uses.reserve(1); Uses.push_back(N);
 217   }
 218   void setNode(ISD::NodeType NT, MachineBasicBlock *bb,
 219                SelectionDAGNode *N1, SelectionDAGNode *N2) {
 220     assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
 221     NodeType = NT; BB = bb;
 222     Uses.reserve(1); Uses.push_back(N1); Uses.push_back(N2);
 223   }
 224
 225   //===--------------------------------------------------------------------===//
 226   //  Accessors
 227   //
 228   ISD::NodeType  getNodeType()  const { return NodeType; }
 229   MVT::ValueType getValueType() const { return ValueType; }
 230   MachineBasicBlock *getBB() const { return BB; }
 231
 232   SelectionDAGNode *getUse(unsigned Num) {
 233     assert(Num < Uses.size() && "Invalid child # of SelectionDAGNode!");
 234     return Uses[Num];
 235   }
 236
 237   template<class Type>
 238   Type *getValue(unsigned Code) const {
 239     SelectionDAGReducedValue *Vals = ValList;
 240     while (1) {
 241       assert(Vals && "Code does not exist in this list!");
 242       if (Vals->getValueCode() == Code)
 243         return (Type*)Vals;
 244       Vals = Vals->getNext();
 245     }
 246   }
 247
 248   template<class Type>
 249   Type *hasValue(unsigned Code) const {
 250     SelectionDAGReducedValue *Vals = ValList;
 251     while (Vals) {
 252       if (Vals->getValueCode() == Code)
 253         return (Type*)Vals;
 254       Vals = Vals->getNext();
 255     }
 256     return false;
 257   }
 258
 259   void addValue(SelectionDAGReducedValue *New) {
 260     assert(New->getNext() == 0);
 261     New->setNext(ValList);
 262     ValList = New;
 263   }
 264
 265   //===--------------------------------------------------------------------===//
 266   // Utility methods used by the pattern matching instruction selector
 267   //
 268
 269   /// getPatternFor - Return the pattern selected to compute the specified slot,
 270   /// or zero if there is no pattern yet.
 271   ///
 272   unsigned getPatternFor(unsigned Slot) const {
 273     return Costs ? Costs[Slot*2] : 0;
 274   }
 275
 276   /// getCostFor - Return the cost to compute the value corresponding to Slot.
 277   ///
 278   unsigned getCostFor(unsigned Slot) const {
 279     return Costs ? Costs[Slot*2+1] : 0;
 280   }
 281
 282   /// setPatternCostFor - Sets the pattern and the cost for the specified slot
 283   /// to the specified values.  This allocates the Costs vector if necessary, so
 284   /// you must specify the maximum number of slots that may be used.
 285   ///
 286   void setPatternCostFor(unsigned Slot, unsigned Pattern, unsigned Cost,
 287                          unsigned NumSlots) {
 288     if (Costs == 0) {
 289       Costs = new unsigned[NumSlots*2];
 290       for (unsigned i = 0; i != NumSlots*2; ++i) Costs[i] = 0;
 291     }
 292     Costs[Slot*2] = Pattern;
 293     Costs[Slot*2+1] = Cost;
 294   }
 295
 296   void dump() const;
 297 private:
 298   void printit(unsigned Offset, unsigned &LastID,
 299                std::map<const SelectionDAGNode*, unsigned> &NodeIDs) const;
 300 };
 301
 302
 303 /// SelectionDAGTargetBuilder - This class must be implemented by the target, to
 304 /// indicate how to perform the extremely target-specific tasks of building DAG
 305 /// nodes to represent the calling convention used by the target.
 306 ///
 307 struct SelectionDAGTargetBuilder {
 308   /// expandArguments - This method is called once by the SelectionDAG
 309   /// construction mechanisms to add DAG nodes for each formal argument to the
 310   /// current function.  If any of the incoming arguments lives on the stack,
 311   /// this method should also create the stack slots for the arguments as
 312   /// necessary.
 313   virtual void expandArguments(SelectionDAG &SD) = 0;
 314
 315   /// expandCall - This method is called once per function call by the
 316   /// SelectionDAG construction algorithm.  It must add DAG nodes to the
 317   /// SelectionDAG specified to perform that call.
 318   virtual void expandCall(SelectionDAG &SD, CallInst &CI) = 0;
 319 };
 320
 321 namespace ISD {
 322   enum {   // Builtin Slot numbers
 323     Constant_i1_Slot,
 324     Constant_i8_Slot,
 325     Constant_i16_Slot,
 326     Constant_i32_Slot,
 327     Constant_i64_Slot,
 328     Constant_f32_Slot,
 329     Constant_f64_Slot,
 330
 331     FrameIndex_i32_Slot,
 332     FrameIndex_i64_Slot,
 333     BasicBlock_i32_Slot,
 334     BasicBlock_i64_Slot,
 335     NumBuiltinSlots
 336   };
 337 }
 338
 339 template<typename ValType, unsigned NodeCode>
 340 struct ReducedValue : public SelectionDAGReducedValue {
 341   ReducedValue(const ValType &V) : SelectionDAGReducedValue(NodeCode), Val(V) {}
 342   ValType Val;
 343 };
 344
 345 typedef ReducedValue<int, ISD::FrameIndex_i32_Slot > ReducedValue_FrameIndex_i32;
 346 typedef ReducedValue<int, ISD::FrameIndex_i64_Slot > ReducedValue_FrameIndex_i64;
 347 typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i32_Slot > ReducedValue_BasicBlock_i32;
 348 typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i64_Slot > ReducedValue_BasicBlock_i64;
 349
 350 typedef ReducedValue<bool          , ISD::Constant_i1_Slot > ReducedValue_Constant_i1;
 351 typedef ReducedValue<unsigned char , ISD::Constant_i8_Slot > ReducedValue_Constant_i8;
 352 typedef ReducedValue<unsigned short, ISD::Constant_i16_Slot> ReducedValue_Constant_i16;
 353 typedef ReducedValue<unsigned      , ISD::Constant_i32_Slot> ReducedValue_Constant_i32;
 354 typedef ReducedValue<uint64_t      , ISD::Constant_i64_Slot> ReducedValue_Constant_i64;
 355 typedef ReducedValue<float         , ISD::Constant_f32_Slot> ReducedValue_Constant_f32;
 356 typedef ReducedValue<double        , ISD::Constant_f64_Slot> ReducedValue_Constant_f64;
 357
 358 #endif