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