1 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG Rep. ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file declares the SelectionDAG class, which is used to represent an LLVM
11 // function in a low-level representation suitable for instruction selection.
12 // This DAG is constructed as the first step of instruction selection in order
13 // to allow implementation of machine specific optimizations and code
16 // The representation used by the SelectionDAG is a target-independent
17 // representation, which is loosly modeled after the GCC RTL representation, but
18 // is significantly simpler.
20 //===----------------------------------------------------------------------===//
22 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
23 #define LLVM_CODEGEN_SELECTIONDAG_H
25 #include "llvm/CodeGen/ValueTypes.h"
26 #include "llvm/Support/DataTypes.h"
38 class MachineBasicBlock;
39 class MachineFunction;
41 class SelectionDAGNode;
42 class SelectionDAGBlock;
43 class SelectionDAGBuilder;
44 class SelectionDAGTargetBuilder;
46 /// ISD namespace - This namespace contains an enum which represents all of the
47 /// SelectionDAG node types and value types.
51 // ChainNode nodes are used to sequence operations within a basic block
52 // which cannot be reordered (such as loads, stores, calls, etc).
53 // BlockChainNodes are used to connect the DAG's for different basic blocks
55 ChainNode, BlockChainNode,
57 // ProtoNodes are nodes that are only half way constructed.
61 Constant, FrameIndex, BasicBlock,
63 // Simple binary arithmetic operators
64 Plus, Minus, Times, SDiv, UDiv, SRem, URem,
70 SetEQ, SetNE, SetLT, SetLE, SetGT, SetGE,
72 // Control flow instructions
73 Br, BrCond, Switch, Ret, RetVoid,
76 Load, Store, PHI, Call,
78 // Unknown operators, of a specified arity
84 friend class SelectionDAGBuilder;
86 const TargetMachine &TM;
87 MVT::ValueType PointerType; // The ValueType the target uses for pointers
89 // ValueMap - The SelectionDAGNode for each LLVM value in the function.
90 std::map<const Value*, SelectionDAGNode*> ValueMap;
92 // BlockMap - The MachineBasicBlock created for each LLVM BasicBlock
93 std::map<const BasicBlock*, MachineBasicBlock*> BlockMap;
95 // Root - The root of the entire DAG
96 SelectionDAGNode *Root;
98 // AllNodes - All of the nodes in the DAG
99 std::vector<SelectionDAGNode*> AllNodes;
101 /// SelectionDAG constructor - Build a SelectionDAG for the specified
102 /// function. Implemented in DAGBuilder.cpp
104 SelectionDAG(MachineFunction &F, const TargetMachine &TM,
105 SelectionDAGTargetBuilder &SDTB);
108 /// getValueType - Return the ValueType for the specified LLVM type. This
109 /// method works on all scalar LLVM types.
111 MVT::ValueType getValueType(const Type *Ty) const;
113 /// getRoot - Return the root of the current SelectionDAG.
115 SelectionDAGNode *getRoot() const { return Root; }
117 /// getMachineFunction - Return the MachineFunction object that this
118 /// SelectionDAG corresponds to.
120 MachineFunction &getMachineFunction() const { return F; }
122 //===--------------------------------------------------------------------===//
123 // Addition and updating methods
126 /// addNode - Add the specified node to the SelectionDAG so that it will be
127 /// deleted when the DAG is...
129 SelectionDAGNode *addNode(SelectionDAGNode *N) {
130 AllNodes.push_back(N);
134 /// addNodeForValue - Add the specified node to the SelectionDAG so that it
135 /// will be deleted when the DAG is... and update the value map to indicate
136 /// that the specified DAG node computes the value. Note that it is an error
137 /// to specify multiple DAG nodes that compute the same value.
139 SelectionDAGNode *addNodeForValue(SelectionDAGNode *N, const Value *V) {
140 assert(ValueMap.count(V) == 0 && "Value already has a DAG node!");
141 return addNode(ValueMap[V] = N);
146 void addInstructionToDAG(const Instruction &I, const BasicBlock &BB);
150 /// SelectionDAGReducedValue - During the reducer pass we need the ability to
151 /// add an arbitrary (but usually 1 or 0) number of arbitrarily sized values to
152 /// the selection DAG. Because of this, we represent these values as a singly
153 /// linked list of values attached to the DAGNode. We end up putting the
154 /// arbitrary state for the value in subclasses of this node.
156 /// Note that this class does not have a virtual dtor, this is because we know
157 /// that the subclasses will not hold state that needs to be destroyed.
159 class SelectionDAGReducedValue {
161 SelectionDAGReducedValue *Next;
163 SelectionDAGReducedValue(unsigned C) : Code(C), Next(0) {}
165 /// getValueCode - Return the code for this reducer value...
167 unsigned getValueCode() const { return Code; }
169 /// getNext - Return the next value in the list
171 const SelectionDAGReducedValue *getNext() const { return Next; }
172 void setNext(SelectionDAGReducedValue *N) { Next = N; }
174 SelectionDAGReducedValue *getNext() { return Next; }
179 /// SelectionDAGNode - Represents one node in the selection DAG.
181 class SelectionDAGNode {
182 std::vector<SelectionDAGNode*> Uses;
183 ISD::NodeType NodeType;
184 MVT::ValueType ValueType;
185 MachineBasicBlock *BB;
186 SelectionDAGReducedValue *ValList;
188 /// Costs - Each pair of elements of 'Costs' contains the cost of producing
189 /// the value with the target specific slot number and the production number
190 /// to use to produce it. A zero value for the production number indicates
191 /// that the cost has not yet been computed.
194 SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT,
195 MachineBasicBlock *bb = 0)
196 : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {}
198 SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
200 : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
201 assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
202 Uses.reserve(1); Uses.push_back(N);
204 SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
205 SelectionDAGNode *N1, SelectionDAGNode *N2)
206 : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
207 assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
208 Uses.reserve(2); Uses.push_back(N1); Uses.push_back(N2);
210 SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
211 SelectionDAGNode *N1, SelectionDAGNode *N2,
212 SelectionDAGNode *N3)
213 : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
214 assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
215 Uses.reserve(3); Uses.push_back(N1); Uses.push_back(N2); Uses.push_back(N3);
218 ~SelectionDAGNode() { delete [] Costs; delete ValList; }
220 void setNode(ISD::NodeType NT, MachineBasicBlock *bb) {
221 assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
222 NodeType = NT; BB = bb;
224 void setNode(ISD::NodeType NT, MachineBasicBlock *bb, SelectionDAGNode *N) {
225 assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
226 NodeType = NT; BB = bb; Uses.reserve(1); Uses.push_back(N);
228 void setNode(ISD::NodeType NT, MachineBasicBlock *bb,
229 SelectionDAGNode *N1, SelectionDAGNode *N2) {
230 assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
231 NodeType = NT; BB = bb;
232 Uses.reserve(1); Uses.push_back(N1); Uses.push_back(N2);
235 //===--------------------------------------------------------------------===//
238 ISD::NodeType getNodeType() const { return NodeType; }
239 MVT::ValueType getValueType() const { return ValueType; }
240 MachineBasicBlock *getBB() const { return BB; }
242 SelectionDAGNode *getUse(unsigned Num) {
243 assert(Num < Uses.size() && "Invalid child # of SelectionDAGNode!");
248 Type *getValue(unsigned Code) const {
249 SelectionDAGReducedValue *Vals = ValList;
251 assert(Vals && "Code does not exist in this list!");
252 if (Vals->getValueCode() == Code)
254 Vals = Vals->getNext();
259 Type *hasValue(unsigned Code) const {
260 SelectionDAGReducedValue *Vals = ValList;
262 if (Vals->getValueCode() == Code)
264 Vals = Vals->getNext();
269 void addValue(SelectionDAGReducedValue *New) {
270 assert(New->getNext() == 0);
271 New->setNext(ValList);
275 //===--------------------------------------------------------------------===//
276 // Utility methods used by the pattern matching instruction selector
279 /// getPatternFor - Return the pattern selected to compute the specified slot,
280 /// or zero if there is no pattern yet.
282 unsigned getPatternFor(unsigned Slot) const {
283 return Costs ? Costs[Slot*2] : 0;
286 /// getCostFor - Return the cost to compute the value corresponding to Slot.
288 unsigned getCostFor(unsigned Slot) const {
289 return Costs ? Costs[Slot*2+1] : 0;
292 /// setPatternCostFor - Sets the pattern and the cost for the specified slot
293 /// to the specified values. This allocates the Costs vector if necessary, so
294 /// you must specify the maximum number of slots that may be used.
296 void setPatternCostFor(unsigned Slot, unsigned Pattern, unsigned Cost,
299 Costs = new unsigned[NumSlots*2];
300 for (unsigned i = 0; i != NumSlots*2; ++i) Costs[i] = 0;
302 Costs[Slot*2] = Pattern;
303 Costs[Slot*2+1] = Cost;
308 void printit(unsigned Offset, unsigned &LastID,
309 std::map<const SelectionDAGNode*, unsigned> &NodeIDs) const;
313 /// SelectionDAGTargetBuilder - This class must be implemented by the target, to
314 /// indicate how to perform the extremely target-specific tasks of building DAG
315 /// nodes to represent the calling convention used by the target.
317 struct SelectionDAGTargetBuilder {
318 /// expandArguments - This method is called once by the SelectionDAG
319 /// construction mechanisms to add DAG nodes for each formal argument to the
320 /// current function. If any of the incoming arguments lives on the stack,
321 /// this method should also create the stack slots for the arguments as
323 virtual void expandArguments(SelectionDAG &SD) = 0;
325 /// expandCall - This method is called once per function call by the
326 /// SelectionDAG construction algorithm. It must add DAG nodes to the
327 /// SelectionDAG specified to perform that call.
328 virtual void expandCall(SelectionDAG &SD, CallInst &CI) = 0;
332 enum { // Builtin Slot numbers
349 template<typename ValType, unsigned NodeCode>
350 struct ReducedValue : public SelectionDAGReducedValue {
351 ReducedValue(const ValType &V) : SelectionDAGReducedValue(NodeCode), Val(V) {}
355 typedef ReducedValue<int, ISD::FrameIndex_i32_Slot > ReducedValue_FrameIndex_i32;
356 typedef ReducedValue<int, ISD::FrameIndex_i64_Slot > ReducedValue_FrameIndex_i64;
357 typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i32_Slot > ReducedValue_BasicBlock_i32;
358 typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i64_Slot > ReducedValue_BasicBlock_i64;
360 typedef ReducedValue<bool , ISD::Constant_i1_Slot > ReducedValue_Constant_i1;
361 typedef ReducedValue<unsigned char , ISD::Constant_i8_Slot > ReducedValue_Constant_i8;
362 typedef ReducedValue<unsigned short, ISD::Constant_i16_Slot> ReducedValue_Constant_i16;
363 typedef ReducedValue<unsigned , ISD::Constant_i32_Slot> ReducedValue_Constant_i32;
364 typedef ReducedValue<uint64_t , ISD::Constant_i64_Slot> ReducedValue_Constant_i64;
365 typedef ReducedValue<float , ISD::Constant_f32_Slot> ReducedValue_Constant_f32;
366 typedef ReducedValue<double , ISD::Constant_f64_Slot> ReducedValue_Constant_f64;
368 } // End llvm namespace