include/llvm/CodeGen/SelectionDAG.h

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