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