SelectionDAG.h revision cacf462915344c2af25eef1af1f3ee2c7280ff56
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG Rep. ----*- C++ -*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file declares the SelectionDAG class, which is used to represent an LLVM 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// function in a low-level representation suitable for instruction selection. 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This DAG is constructed as the first step of instruction selection in order 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// to allow implementation of machine specific optimizations and code 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// simplifications. 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The representation used by the SelectionDAG is a target-independent 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// representation, which is loosly modeled after the GCC RTL representation, but 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// is significantly simpler. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef LLVM_CODEGEN_SELECTIONDAG_H 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LLVM_CODEGEN_SELECTIONDAG_H 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/CodeGen/ValueTypes.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "Support/DataTypes.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <map> 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Value; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Type; 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Instruction; 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class BasicBlock; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MachineBasicBlock; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MachineFunction; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class TargetMachine; 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SelectionDAGNode; 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SelectionDAGBlock; 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SelectionDAGBuilder; 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SelectionDAGTargetBuilder; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// ISD namespace - This namespace contains an enum which represents all of the 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// SelectionDAG node types and value types. 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace ISD { 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enum NodeType { 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ChainNode nodes are used to sequence operations within a basic block 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // which cannot be reordered (such as loads, stores, calls, etc). 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // BlockChainNodes are used to connect the DAG's for different basic blocks 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // into one big DAG. 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ChainNode, BlockChainNode, 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ProtoNodes are nodes that are only half way constructed. 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProtoNode, 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Leaf nodes. 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Constant, FrameIndex, 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Simple binary arithmetic operators 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Plus, Minus, Times, SDiv, UDiv, SRem, URem, 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Bitwise operators 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) And, Or, Xor, 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Control flow instructions 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Br, Switch, Ret, RetVoid, 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Other operators 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Load, Store, PHI, Call, 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SelectionDAG { 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class SelectionDAGBuilder; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction &F; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetMachine &TM; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MVT::ValueType PointerType; // The ValueType the target uses for pointers 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ValueMap - The SelectionDAGNode for each LLVM value in the function. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::map<const Value*, SelectionDAGNode*> ValueMap; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // BlockMap - The MachineBasicBlock created for each LLVM BasicBlock 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::map<const BasicBlock*, MachineBasicBlock*> BlockMap; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Root - The root of the entire DAG 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SelectionDAGNode *Root; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // AllNodes - All of the nodes in the DAG 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<SelectionDAGNode*> AllNodes; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SelectionDAG constructor - Build a SelectionDAG for the specified 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// function. Implemented in DAGBuilder.cpp 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SelectionDAG(MachineFunction &F, const TargetMachine &TM, 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SelectionDAGTargetBuilder &SDTB); 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~SelectionDAG(); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getValueType - Return the ValueType for the specified LLVM type. This 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// method works on all scalar LLVM types. 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MVT::ValueType getValueType(const Type *Ty) const; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getRoot - Return the root of the current SelectionDAG. 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SelectionDAGNode *getRoot() const { return Root; } 98 99 /// getMachineFunction - Return the MachineFunction object that this 100 /// SelectionDAG corresponds to. 101 /// 102 MachineFunction &getMachineFunction() const { return F; } 103 104 //===--------------------------------------------------------------------===// 105 // Addition and updating methods 106 // 107 108 /// addNode - Add the specified node to the SelectionDAG so that it will be 109 /// deleted when the DAG is... 110 /// 111 SelectionDAGNode *addNode(SelectionDAGNode *N) { 112 AllNodes.push_back(N); 113 return N; 114 } 115 116 /// addNodeForValue - Add the specified node to the SelectionDAG so that it 117 /// will be deleted when the DAG is... and update the value map to indicate 118 /// that the specified DAG node computes the value. Note that it is an error 119 /// to specify multiple DAG nodes that compute the same value. 120 /// 121 SelectionDAGNode *addNodeForValue(SelectionDAGNode *N, const Value *V) { 122 assert(ValueMap.count(V) == 0 && "Value already has a DAG node!"); 123 return addNode(ValueMap[V] = N); 124 } 125 126 void dump() const; 127private: 128 void addInstructionToDAG(const Instruction &I, const BasicBlock &BB); 129}; 130 131 132/// SelectionDAGReducedValue - During the reducer pass we need the ability to 133/// add an arbitrary (but usually 1 or 0) number of arbitrarily sized values to 134/// the selection DAG. Because of this, we represent these values as a singly 135/// linked list of values attached to the DAGNode. We end up putting the 136/// arbitrary state for the value in subclasses of this node. 137/// 138/// Note that this class does not have a virtual dtor, this is because we know 139/// that the subclasses will not hold state that needs to be destroyed. 140/// 141class SelectionDAGReducedValue { 142 unsigned Code; 143 SelectionDAGReducedValue *Next; 144public: 145 SelectionDAGReducedValue(unsigned C) : Code(C), Next(0) {} 146 147 /// getValueCode - Return the code for this reducer value... 148 /// 149 unsigned getValueCode() const { return Code; } 150 151 /// getNext - Return the next value in the list 152 /// 153 const SelectionDAGReducedValue *getNext() const { return Next; } 154 void setNext(SelectionDAGReducedValue *N) { Next = N; } 155 156 SelectionDAGReducedValue *getNext() { return Next; } 157}; 158 159 160 161/// SelectionDAGNode - Represents one node in the selection DAG. 162/// 163class SelectionDAGNode { 164 std::vector<SelectionDAGNode*> Uses; 165 ISD::NodeType NodeType; 166 MVT::ValueType ValueType; 167 MachineBasicBlock *BB; 168 SelectionDAGReducedValue *ValList; 169 170 /// Costs - Each pair of elements of 'Costs' contains the cost of producing 171 /// the value with the target specific slot number and the production number 172 /// to use to produce it. A zero value for the production number indicates 173 /// that the cost has not yet been computed. 174 unsigned *Costs; 175public: 176 SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, 177 MachineBasicBlock *bb = 0) 178 : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {} 179 180 SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb, 181 SelectionDAGNode *N) 182 : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) { 183 assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!"); 184 Uses.reserve(1); Uses.push_back(N); 185 } 186 SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb, 187 SelectionDAGNode *N1, SelectionDAGNode *N2) 188 : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) { 189 assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!"); 190 Uses.reserve(2); Uses.push_back(N1); Uses.push_back(N2); 191 } 192 193 ~SelectionDAGNode() { delete [] Costs; delete ValList; } 194 195 void setNode(ISD::NodeType NT, MachineBasicBlock *bb) { 196 assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode); 197 NodeType = NT; BB = bb; 198 } 199 void setNode(ISD::NodeType NT, MachineBasicBlock *bb, SelectionDAGNode *N) { 200 assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode); 201 NodeType = NT; BB = bb; Uses.reserve(1); Uses.push_back(N); 202 } 203 void setNode(ISD::NodeType NT, MachineBasicBlock *bb, 204 SelectionDAGNode *N1, SelectionDAGNode *N2) { 205 assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode); 206 NodeType = NT; BB = bb; 207 Uses.reserve(1); Uses.push_back(N1); Uses.push_back(N2); 208 } 209 210 //===--------------------------------------------------------------------===// 211 // Accessors 212 // 213 ISD::NodeType getNodeType() const { return NodeType; } 214 MVT::ValueType getValueType() const { return ValueType; } 215 MachineBasicBlock *getBB() const { return BB; } 216 217 SelectionDAGNode *getUse(unsigned Num) { 218 assert(Num < Uses.size() && "Invalid child # of SelectionDAGNode!"); 219 return Uses[Num]; 220 } 221 222 template<class Type> 223 Type *getValue(unsigned Code) const { 224 SelectionDAGReducedValue *Vals = ValList; 225 while (1) { 226 assert(Vals && "Code does not exist in this list!"); 227 if (Vals->getValueCode() == Code) 228 return (Type*)Vals; 229 Vals = Vals->getNext(); 230 } 231 } 232 233 template<class Type> 234 Type *hasValue(unsigned Code) const { 235 SelectionDAGReducedValue *Vals = ValList; 236 while (Vals) { 237 if (Vals->getValueCode() == Code) 238 return (Type*)Vals; 239 Vals = Vals->getNext(); 240 } 241 return false; 242 } 243 244 void addValue(SelectionDAGReducedValue *New) { 245 assert(New->getNext() == 0); 246 New->setNext(ValList); 247 ValList = New; 248 } 249 250 //===--------------------------------------------------------------------===// 251 // Utility methods used by the pattern matching instruction selector 252 // 253 254 /// getPatternFor - Return the pattern selected to compute the specified slot, 255 /// or zero if there is no pattern yet. 256 /// 257 unsigned getPatternFor(unsigned Slot) const { 258 return Costs ? Costs[Slot*2] : 0; 259 } 260 261 /// getCostFor - Return the cost to compute the value corresponding to Slot. 262 /// 263 unsigned getCostFor(unsigned Slot) const { 264 return Costs ? Costs[Slot*2+1] : 0; 265 } 266 267 /// setPatternCostFor - Sets the pattern and the cost for the specified slot 268 /// to the specified values. This allocates the Costs vector if necessary, so 269 /// you must specify the maximum number of slots that may be used. 270 /// 271 void setPatternCostFor(unsigned Slot, unsigned Pattern, unsigned Cost, 272 unsigned NumSlots) { 273 if (Costs == 0) { 274 Costs = new unsigned[NumSlots*2]; 275 for (unsigned i = 0; i != NumSlots*2; ++i) Costs[i] = 0; 276 } 277 Costs[Slot*2] = Pattern; 278 Costs[Slot*2+1] = Cost; 279 } 280 281 void dump() const; 282private: 283 void printit(unsigned Offset, unsigned &LastID, 284 std::map<const SelectionDAGNode*, unsigned> &NodeIDs) const; 285}; 286 287 288/// SelectionDAGTargetBuilder - This class must be implemented by the target, to 289/// indicate how to perform the extremely target-specific tasks of building DAG 290/// nodes to represent the calling convention used by the target. 291/// 292struct SelectionDAGTargetBuilder { 293 /// expandArguments - This method is called once by the SelectionDAG 294 /// construction mechanisms to add DAG nodes for each formal argument to the 295 /// current function. If any of the incoming arguments lives on the stack, 296 /// this method should also create the stack slots for the arguments as 297 /// necessary. 298 virtual void expandArguments(SelectionDAG &SD, MachineFunction &MF) = 0; 299}; 300 301namespace ISD { 302 enum { // Builtin Slot numbers 303 Constant_i1_Slot, 304 Constant_i8_Slot, 305 Constant_i16_Slot, 306 Constant_i32_Slot, 307 Constant_i64_Slot, 308 Constant_f32_Slot, 309 Constant_f64_Slot, 310 311 FrameIndex_i32_Slot, 312 FrameIndex_i64_Slot, 313 NumBuiltinSlots 314 }; 315} 316 317template<typename ValType, unsigned NodeCode> 318struct ReducedValue : public SelectionDAGReducedValue { 319 ReducedValue(const ValType &V) : SelectionDAGReducedValue(NodeCode), Val(V) {} 320 ValType Val; 321}; 322 323typedef ReducedValue<int, ISD::FrameIndex_i32_Slot > ReducedValue_FrameIndex_i32; 324typedef ReducedValue<int, ISD::FrameIndex_i64_Slot > ReducedValue_FrameIndex_i64; 325 326typedef ReducedValue<bool , ISD::Constant_i1_Slot > ReducedValue_Constant_i1; 327typedef ReducedValue<unsigned char , ISD::Constant_i8_Slot > ReducedValue_Constant_i8; 328typedef ReducedValue<unsigned short, ISD::Constant_i16_Slot> ReducedValue_Constant_i16; 329typedef ReducedValue<unsigned , ISD::Constant_i32_Slot> ReducedValue_Constant_i32; 330typedef ReducedValue<uint64_t , ISD::Constant_i64_Slot> ReducedValue_Constant_i64; 331typedef ReducedValue<float , ISD::Constant_f32_Slot> ReducedValue_Constant_f32; 332typedef ReducedValue<double , ISD::Constant_f64_Slot> ReducedValue_Constant_f64; 333 334#endif 335