LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

SelectionDAG.h

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG Rep. ----*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 // 
00010 // This file declares the SelectionDAG class, which is used to represent an LLVM
00011 // function in a low-level representation suitable for instruction selection.
00012 // This DAG is constructed as the first step of instruction selection in order
00013 // to allow implementation of machine specific optimizations and code
00014 // simplifications.
00015 //
00016 // The representation used by the SelectionDAG is a target-independent
00017 // representation, which is loosly modeled after the GCC RTL representation, but
00018 // is significantly simpler.
00019 //   
00020 //===----------------------------------------------------------------------===//
00021 
00022 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
00023 #define LLVM_CODEGEN_SELECTIONDAG_H
00024 
00025 #include "llvm/CodeGen/ValueTypes.h"
00026 #include "llvm/Support/DataTypes.h"
00027 #include <map>
00028 #include <vector>
00029 #include <cassert>
00030 
00031 namespace llvm {
00032 
00033 class Value;
00034 class Type;
00035 class Instruction;
00036 class CallInst;
00037 class BasicBlock;
00038 class MachineBasicBlock;
00039 class MachineFunction;
00040 class TargetMachine;
00041 class SelectionDAGNode;
00042 class SelectionDAGBlock;
00043 class SelectionDAGBuilder;
00044 class SelectionDAGTargetBuilder;
00045 
00046 /// ISD namespace - This namespace contains an enum which represents all of the
00047 /// SelectionDAG node types and value types.
00048 ///
00049 namespace ISD {
00050   enum NodeType {
00051     // ChainNode nodes are used to sequence operations within a basic block
00052     // which cannot be reordered (such as loads, stores, calls, etc).
00053     // BlockChainNodes are used to connect the DAG's for different basic blocks
00054     // into one big DAG.
00055     ChainNode, BlockChainNode,
00056 
00057     // ProtoNodes are nodes that are only half way constructed.
00058     ProtoNode,
00059 
00060     // Leaf nodes
00061     Constant, FrameIndex, BasicBlock,
00062 
00063     // Simple binary arithmetic operators
00064     Plus, Minus, Times, SDiv, UDiv, SRem, URem,
00065 
00066     // Bitwise operators
00067     And, Or, Xor,
00068 
00069     // Comparisons
00070     SetEQ, SetNE, SetLT, SetLE, SetGT, SetGE,
00071 
00072     // Control flow instructions
00073     Br, BrCond, Switch, Ret, RetVoid,
00074 
00075     // Other operators
00076     Load, Store, PHI, Call,
00077 
00078     // Unknown operators, of a specified arity
00079     Unspec1, Unspec2
00080   };
00081 }
00082 
00083 class SelectionDAG {
00084   friend class SelectionDAGBuilder;
00085   MachineFunction &F;
00086   const TargetMachine &TM;
00087   MVT::ValueType PointerType;    // The ValueType the target uses for pointers
00088 
00089   // ValueMap - The SelectionDAGNode for each LLVM value in the function.
00090   std::map<const Value*, SelectionDAGNode*> ValueMap;
00091 
00092   // BlockMap - The MachineBasicBlock created for each LLVM BasicBlock
00093   std::map<const BasicBlock*, MachineBasicBlock*> BlockMap;
00094 
00095   // Root - The root of the entire DAG
00096   SelectionDAGNode *Root;
00097 
00098   // AllNodes - All of the nodes in the DAG
00099   std::vector<SelectionDAGNode*> AllNodes;
00100 public:
00101   /// SelectionDAG constructor - Build a SelectionDAG for the specified
00102   /// function.  Implemented in DAGBuilder.cpp
00103   ///
00104   SelectionDAG(MachineFunction &F, const TargetMachine &TM,
00105                SelectionDAGTargetBuilder &SDTB);
00106   ~SelectionDAG();
00107 
00108   /// getValueType - Return the ValueType for the specified LLVM type.  This
00109   /// method works on all scalar LLVM types.
00110   ///
00111   MVT::ValueType getValueType(const Type *Ty) const;
00112 
00113   /// getRoot - Return the root of the current SelectionDAG.
00114   ///
00115   SelectionDAGNode *getRoot() const { return Root; }
00116 
00117   /// getMachineFunction - Return the MachineFunction object that this
00118   /// SelectionDAG corresponds to.
00119   ///
00120   MachineFunction &getMachineFunction() const { return F; }
00121 
00122   //===--------------------------------------------------------------------===//
00123   // Addition and updating methods
00124   //
00125 
00126   /// addNode - Add the specified node to the SelectionDAG so that it will be
00127   /// deleted when the DAG is...
00128   ///
00129   SelectionDAGNode *addNode(SelectionDAGNode *N) {
00130     AllNodes.push_back(N);
00131     return N;
00132   }
00133 
00134   /// addNodeForValue - Add the specified node to the SelectionDAG so that it
00135   /// will be deleted when the DAG is... and update the value map to indicate
00136   /// that the specified DAG node computes the value.  Note that it is an error
00137   /// to specify multiple DAG nodes that compute the same value.
00138   ///
00139   SelectionDAGNode *addNodeForValue(SelectionDAGNode *N, const Value *V) {
00140     assert(ValueMap.count(V) == 0 && "Value already has a DAG node!");
00141     return addNode(ValueMap[V] = N);
00142   }
00143 
00144   void dump() const;
00145 private:
00146   void addInstructionToDAG(const Instruction &I, const BasicBlock &BB);
00147 };
00148 
00149 
00150 /// SelectionDAGReducedValue - During the reducer pass we need the ability to
00151 /// add an arbitrary (but usually 1 or 0) number of arbitrarily sized values to
00152 /// the selection DAG.  Because of this, we represent these values as a singly
00153 /// linked list of values attached to the DAGNode.  We end up putting the
00154 /// arbitrary state for the value in subclasses of this node.
00155 ///
00156 /// Note that this class does not have a virtual dtor, this is because we know
00157 /// that the subclasses will not hold state that needs to be destroyed.
00158 ///
00159 class SelectionDAGReducedValue {
00160   unsigned Code;
00161   SelectionDAGReducedValue *Next;
00162 public:
00163   SelectionDAGReducedValue(unsigned C) : Code(C), Next(0) {}
00164 
00165   /// getValueCode - Return the code for this reducer value...
00166   ///
00167   unsigned getValueCode() const { return Code; }
00168   
00169   /// getNext - Return the next value in the list
00170   ///
00171   const SelectionDAGReducedValue *getNext() const { return Next; }
00172   void setNext(SelectionDAGReducedValue *N) { Next = N; }
00173 
00174   SelectionDAGReducedValue *getNext() { return Next; }
00175 };
00176 
00177 
00178 
00179 /// SelectionDAGNode - Represents one node in the selection DAG.
00180 ///
00181 class SelectionDAGNode {
00182   std::vector<SelectionDAGNode*> Uses;
00183   ISD::NodeType  NodeType;
00184   MVT::ValueType ValueType;
00185   MachineBasicBlock *BB;
00186   SelectionDAGReducedValue *ValList;
00187 
00188   /// Costs - Each pair of elements of 'Costs' contains the cost of producing
00189   /// the value with the target specific slot number and the production number
00190   /// to use to produce it.  A zero value for the production number indicates
00191   /// that the cost has not yet been computed.
00192   unsigned *Costs;
00193 public:
00194   SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT,
00195                    MachineBasicBlock *bb = 0) 
00196     : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {}
00197 
00198   SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
00199                    SelectionDAGNode *N)
00200     : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
00201     assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
00202     Uses.reserve(1); Uses.push_back(N);
00203   }
00204   SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
00205                    SelectionDAGNode *N1, SelectionDAGNode *N2)
00206     : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
00207     assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
00208     Uses.reserve(2); Uses.push_back(N1); Uses.push_back(N2);
00209   }
00210   SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
00211                    SelectionDAGNode *N1, SelectionDAGNode *N2,
00212                    SelectionDAGNode *N3)
00213     : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
00214     assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
00215     Uses.reserve(3); Uses.push_back(N1); Uses.push_back(N2); Uses.push_back(N3);
00216   }
00217 
00218   ~SelectionDAGNode() { delete [] Costs; delete ValList; }
00219 
00220   void setNode(ISD::NodeType NT, MachineBasicBlock *bb) {
00221     assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
00222     NodeType = NT; BB = bb;
00223   }
00224   void setNode(ISD::NodeType NT, MachineBasicBlock *bb, SelectionDAGNode *N) {
00225     assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
00226     NodeType = NT; BB = bb; Uses.reserve(1); Uses.push_back(N);
00227   }
00228   void setNode(ISD::NodeType NT, MachineBasicBlock *bb, 
00229                SelectionDAGNode *N1, SelectionDAGNode *N2) {
00230     assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
00231     NodeType = NT; BB = bb;
00232     Uses.reserve(1); Uses.push_back(N1); Uses.push_back(N2);
00233   }
00234 
00235   //===--------------------------------------------------------------------===//
00236   //  Accessors
00237   //
00238   ISD::NodeType  getNodeType()  const { return NodeType; }
00239   MVT::ValueType getValueType() const { return ValueType; }
00240   MachineBasicBlock *getBB() const { return BB; }
00241 
00242   SelectionDAGNode *getUse(unsigned Num) {
00243     assert(Num < Uses.size() && "Invalid child # of SelectionDAGNode!");
00244     return Uses[Num];
00245   }
00246 
00247   template<class Type>
00248   Type *getValue(unsigned Code) const {
00249     SelectionDAGReducedValue *Vals = ValList;
00250     while (1) {
00251       assert(Vals && "Code does not exist in this list!");
00252       if (Vals->getValueCode() == Code)
00253         return (Type*)Vals;
00254       Vals = Vals->getNext();
00255     }
00256   }
00257 
00258   template<class Type>
00259   Type *hasValue(unsigned Code) const {
00260     SelectionDAGReducedValue *Vals = ValList;
00261     while (Vals) {
00262       if (Vals->getValueCode() == Code)
00263         return (Type*)Vals;
00264       Vals = Vals->getNext();
00265     }
00266     return false;
00267   }
00268 
00269   void addValue(SelectionDAGReducedValue *New) {
00270     assert(New->getNext() == 0);
00271     New->setNext(ValList);
00272     ValList = New;
00273   }
00274 
00275   //===--------------------------------------------------------------------===//
00276   // Utility methods used by the pattern matching instruction selector
00277   //
00278 
00279   /// getPatternFor - Return the pattern selected to compute the specified slot,
00280   /// or zero if there is no pattern yet.
00281   ///
00282   unsigned getPatternFor(unsigned Slot) const {
00283     return Costs ? Costs[Slot*2] : 0;
00284   }
00285 
00286   /// getCostFor - Return the cost to compute the value corresponding to Slot.
00287   ///
00288   unsigned getCostFor(unsigned Slot) const {
00289     return Costs ? Costs[Slot*2+1] : 0;
00290   }
00291 
00292   /// setPatternCostFor - Sets the pattern and the cost for the specified slot
00293   /// to the specified values.  This allocates the Costs vector if necessary, so
00294   /// you must specify the maximum number of slots that may be used.
00295   ///
00296   void setPatternCostFor(unsigned Slot, unsigned Pattern, unsigned Cost,
00297                          unsigned NumSlots) {
00298     if (Costs == 0) {
00299       Costs = new unsigned[NumSlots*2];
00300       for (unsigned i = 0; i != NumSlots*2; ++i) Costs[i] = 0;
00301     }
00302     Costs[Slot*2] = Pattern;
00303     Costs[Slot*2+1] = Cost;
00304   }
00305 
00306   void dump() const;
00307 private:
00308   void printit(unsigned Offset, unsigned &LastID,
00309                std::map<const SelectionDAGNode*, unsigned> &NodeIDs) const;
00310 };
00311 
00312 
00313 /// SelectionDAGTargetBuilder - This class must be implemented by the target, to
00314 /// indicate how to perform the extremely target-specific tasks of building DAG
00315 /// nodes to represent the calling convention used by the target.
00316 ///
00317 struct SelectionDAGTargetBuilder {
00318   /// expandArguments - This method is called once by the SelectionDAG
00319   /// construction mechanisms to add DAG nodes for each formal argument to the
00320   /// current function.  If any of the incoming arguments lives on the stack,
00321   /// this method should also create the stack slots for the arguments as
00322   /// necessary.
00323   virtual void expandArguments(SelectionDAG &SD) = 0;
00324 
00325   /// expandCall - This method is called once per function call by the
00326   /// SelectionDAG construction algorithm.  It must add DAG nodes to the
00327   /// SelectionDAG specified to perform that call.
00328   virtual void expandCall(SelectionDAG &SD, CallInst &CI) = 0;
00329 };
00330 
00331 namespace ISD {
00332   enum {   // Builtin Slot numbers
00333     Constant_i1_Slot,
00334     Constant_i8_Slot,
00335     Constant_i16_Slot,
00336     Constant_i32_Slot,
00337     Constant_i64_Slot,
00338     Constant_f32_Slot,
00339     Constant_f64_Slot,
00340 
00341     FrameIndex_i32_Slot,
00342     FrameIndex_i64_Slot,
00343     BasicBlock_i32_Slot,
00344     BasicBlock_i64_Slot,
00345     NumBuiltinSlots
00346   };
00347 }
00348 
00349 template<typename ValType, unsigned NodeCode>
00350 struct ReducedValue : public SelectionDAGReducedValue {
00351   ReducedValue(const ValType &V) : SelectionDAGReducedValue(NodeCode), Val(V) {}
00352   ValType Val;
00353 };
00354 
00355 typedef ReducedValue<int, ISD::FrameIndex_i32_Slot > ReducedValue_FrameIndex_i32;
00356 typedef ReducedValue<int, ISD::FrameIndex_i64_Slot > ReducedValue_FrameIndex_i64;
00357 typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i32_Slot > ReducedValue_BasicBlock_i32;
00358 typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i64_Slot > ReducedValue_BasicBlock_i64;
00359 
00360 typedef ReducedValue<bool          , ISD::Constant_i1_Slot > ReducedValue_Constant_i1;
00361 typedef ReducedValue<unsigned char , ISD::Constant_i8_Slot > ReducedValue_Constant_i8;
00362 typedef ReducedValue<unsigned short, ISD::Constant_i16_Slot> ReducedValue_Constant_i16;
00363 typedef ReducedValue<unsigned      , ISD::Constant_i32_Slot> ReducedValue_Constant_i32;
00364 typedef ReducedValue<uint64_t      , ISD::Constant_i64_Slot> ReducedValue_Constant_i64;
00365 typedef ReducedValue<float         , ISD::Constant_f32_Slot> ReducedValue_Constant_f32;
00366 typedef ReducedValue<double        , ISD::Constant_f64_Slot> ReducedValue_Constant_f64;
00367 
00368 } // End llvm namespace
00369 
00370 #endif