LLVM API Documentation
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