1 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG Rep. ----*- C++ -*-===//
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
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.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
16 #define LLVM_CODEGEN_SELECTIONDAG_H
18 #include "llvm/CodeGen/ValueTypes.h"
19 #include "Support/DataTypes.h"
28 class MachineBasicBlock;
29 class MachineFunction;
31 class SelectionDAGNode;
32 class SelectionDAGBlock;
33 class SelectionDAGBuilder;
34 class SelectionDAGTargetBuilder;
36 /// ISD namespace - This namespace contains an enum which represents all of the
37 /// SelectionDAG node types and value types.
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
45 ChainNode, BlockChainNode,
47 // ProtoNodes are nodes that are only half way constructed.
51 Constant, FrameIndex, BasicBlock,
53 // Simple binary arithmetic operators
54 Plus, Minus, Times, SDiv, UDiv, SRem, URem,
60 SetEQ, SetNE, SetLT, SetLE, SetGT, SetGE,
62 // Control flow instructions
63 Br, BrCond, Switch, Ret, RetVoid,
66 Load, Store, PHI, Call,
68 // Unknown operators, of a specified arity
74 friend class SelectionDAGBuilder;
76 const TargetMachine &TM;
77 MVT::ValueType PointerType; // The ValueType the target uses for pointers
79 // ValueMap - The SelectionDAGNode for each LLVM value in the function.
80 std::map<const Value*, SelectionDAGNode*> ValueMap;
82 // BlockMap - The MachineBasicBlock created for each LLVM BasicBlock
83 std::map<const BasicBlock*, MachineBasicBlock*> BlockMap;
85 // Root - The root of the entire DAG
86 SelectionDAGNode *Root;
88 // AllNodes - All of the nodes in the DAG
89 std::vector<SelectionDAGNode*> AllNodes;
91 /// SelectionDAG constructor - Build a SelectionDAG for the specified
92 /// function. Implemented in DAGBuilder.cpp
94 SelectionDAG(MachineFunction &F, const TargetMachine &TM,
95 SelectionDAGTargetBuilder &SDTB);
98 /// getValueType - Return the ValueType for the specified LLVM type. This
99 /// method works on all scalar LLVM types.
101 MVT::ValueType getValueType(const Type *Ty) const;
103 /// getRoot - Return the root of the current SelectionDAG.
105 SelectionDAGNode *getRoot() const { return Root; }
107 /// getMachineFunction - Return the MachineFunction object that this
108 /// SelectionDAG corresponds to.
110 MachineFunction &getMachineFunction() const { return F; }
112 //===--------------------------------------------------------------------===//
113 // Addition and updating methods
116 /// addNode - Add the specified node to the SelectionDAG so that it will be
117 /// deleted when the DAG is...
119 SelectionDAGNode *addNode(SelectionDAGNode *N) {
120 AllNodes.push_back(N);
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.
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);
136 void addInstructionToDAG(const Instruction &I, const BasicBlock &BB);
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.
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.
149 class SelectionDAGReducedValue {
151 SelectionDAGReducedValue *Next;
153 SelectionDAGReducedValue(unsigned C) : Code(C), Next(0) {}
155 /// getValueCode - Return the code for this reducer value...
157 unsigned getValueCode() const { return Code; }
159 /// getNext - Return the next value in the list
161 const SelectionDAGReducedValue *getNext() const { return Next; }
162 void setNext(SelectionDAGReducedValue *N) { Next = N; }
164 SelectionDAGReducedValue *getNext() { return Next; }
169 /// SelectionDAGNode - Represents one node in the selection DAG.
171 class SelectionDAGNode {
172 std::vector<SelectionDAGNode*> Uses;
173 ISD::NodeType NodeType;
174 MVT::ValueType ValueType;
175 MachineBasicBlock *BB;
176 SelectionDAGReducedValue *ValList;
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.
184 SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT,
185 MachineBasicBlock *bb = 0)
186 : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {}
188 SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
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);
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);
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);
208 ~SelectionDAGNode() { delete [] Costs; delete ValList; }
210 void setNode(ISD::NodeType NT, MachineBasicBlock *bb) {
211 assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
212 NodeType = NT; BB = bb;
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);
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);
225 //===--------------------------------------------------------------------===//
228 ISD::NodeType getNodeType() const { return NodeType; }
229 MVT::ValueType getValueType() const { return ValueType; }
230 MachineBasicBlock *getBB() const { return BB; }
232 SelectionDAGNode *getUse(unsigned Num) {
233 assert(Num < Uses.size() && "Invalid child # of SelectionDAGNode!");
238 Type *getValue(unsigned Code) const {
239 SelectionDAGReducedValue *Vals = ValList;
241 assert(Vals && "Code does not exist in this list!");
242 if (Vals->getValueCode() == Code)
244 Vals = Vals->getNext();
249 Type *hasValue(unsigned Code) const {
250 SelectionDAGReducedValue *Vals = ValList;
252 if (Vals->getValueCode() == Code)
254 Vals = Vals->getNext();
259 void addValue(SelectionDAGReducedValue *New) {
260 assert(New->getNext() == 0);
261 New->setNext(ValList);
265 //===--------------------------------------------------------------------===//
266 // Utility methods used by the pattern matching instruction selector
269 /// getPatternFor - Return the pattern selected to compute the specified slot,
270 /// or zero if there is no pattern yet.
272 unsigned getPatternFor(unsigned Slot) const {
273 return Costs ? Costs[Slot*2] : 0;
276 /// getCostFor - Return the cost to compute the value corresponding to Slot.
278 unsigned getCostFor(unsigned Slot) const {
279 return Costs ? Costs[Slot*2+1] : 0;
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.
286 void setPatternCostFor(unsigned Slot, unsigned Pattern, unsigned Cost,
289 Costs = new unsigned[NumSlots*2];
290 for (unsigned i = 0; i != NumSlots*2; ++i) Costs[i] = 0;
292 Costs[Slot*2] = Pattern;
293 Costs[Slot*2+1] = Cost;
298 void printit(unsigned Offset, unsigned &LastID,
299 std::map<const SelectionDAGNode*, unsigned> &NodeIDs) const;
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.
307 struct 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
313 virtual void expandArguments(SelectionDAG &SD) = 0;
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;
322 enum { // Builtin Slot numbers
339 template<typename ValType, unsigned NodeCode>
340 struct ReducedValue : public SelectionDAGReducedValue {
341 ReducedValue(const ValType &V) : SelectionDAGReducedValue(NodeCode), Val(V) {}
345 typedef ReducedValue<int, ISD::FrameIndex_i32_Slot > ReducedValue_FrameIndex_i32;
346 typedef ReducedValue<int, ISD::FrameIndex_i64_Slot > ReducedValue_FrameIndex_i64;
347 typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i32_Slot > ReducedValue_BasicBlock_i32;
348 typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i64_Slot > ReducedValue_BasicBlock_i64;
350 typedef ReducedValue<bool , ISD::Constant_i1_Slot > ReducedValue_Constant_i1;
351 typedef ReducedValue<unsigned char , ISD::Constant_i8_Slot > ReducedValue_Constant_i8;
352 typedef ReducedValue<unsigned short, ISD::Constant_i16_Slot> ReducedValue_Constant_i16;
353 typedef ReducedValue<unsigned , ISD::Constant_i32_Slot> ReducedValue_Constant_i32;
354 typedef ReducedValue<uint64_t , ISD::Constant_i64_Slot> ReducedValue_Constant_i64;
355 typedef ReducedValue<float , ISD::Constant_f32_Slot> ReducedValue_Constant_f32;
356 typedef ReducedValue<double , ISD::Constant_f64_Slot> ReducedValue_Constant_f64;