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