1 //===-- llvm/CodeGen/InstForest.h ------------------------------*- C++ -*--===//
4 // Convert SSA graph to instruction trees for instruction selection.
7 // The basic idea is that we would like to group instructions into a single
8 // tree if one or more of them might be potentially combined into a single
9 // complex instruction in the target machine.
10 // Since this grouping is completely machine-independent, it is as
11 // aggressive as possible. In particular, we group two instructions
13 // (1) Instruction O computes an operand of instruction I, and
14 // (2) O and I are part of the same basic block, and
15 // (3) O has only a single use, viz., I.
17 //===----------------------------------------------------------------------===//
19 #ifndef LLVM_CODEGEN_INSTRFOREST_H
20 #define LLVM_CODEGEN_INSTRFOREST_H
22 #include "llvm/Instruction.h"
23 #include "Support/hash_map"
30 //--------------------------------------------------------------------------
31 // OpLabel values for special-case nodes created for instruction selection.
32 // All op-labels not defined here are identical to the instruction
33 // opcode returned by Instruction::getOpcode()
34 //--------------------------------------------------------------------------
36 const int InvalidOp = -1;
37 const int VRegListOp = 97;
38 const int VRegNodeOp = 98;
39 const int ConstantNodeOp= 99;
40 const int LabelNodeOp = 100;
42 const int RetValueOp = 100 + Instruction::Ret; // 101
43 const int BrCondOp = 100 + Instruction::Br; // 102
45 const int BAndOp = 100 + Instruction::And; // 111
46 const int BOrOp = 100 + Instruction::Or; // 112
47 const int BXorOp = 100 + Instruction::Xor; // 113
48 const int BNotOp = 200 + Instruction::Xor; // 213
49 const int NotOp = 300 + Instruction::Xor; // 313
51 const int SetCCOp = 100 + Instruction::SetEQ; // 114
53 const int AllocaN = 100 + Instruction::Alloca; // 122
54 const int LoadIdx = 100 + Instruction::Load; // 123
55 const int GetElemPtrIdx= 100 + Instruction::GetElementPtr; // 125
57 const int ToBoolTy = 100 + Instruction::Cast; // 127
58 const int ToUByteTy = ToBoolTy + 1;
59 const int ToSByteTy = ToBoolTy + 2;
60 const int ToUShortTy = ToBoolTy + 3;
61 const int ToShortTy = ToBoolTy + 4;
62 const int ToUIntTy = ToBoolTy + 5;
63 const int ToIntTy = ToBoolTy + 6;
64 const int ToULongTy = ToBoolTy + 7;
65 const int ToLongTy = ToBoolTy + 8;
66 const int ToFloatTy = ToBoolTy + 9;
67 const int ToDoubleTy = ToBoolTy + 10;
68 const int ToArrayTy = ToBoolTy + 11;
69 const int ToPointerTy = ToBoolTy + 12;
71 //-------------------------------------------------------------------------
72 // Data types needed by BURG and implemented by us
73 //-------------------------------------------------------------------------
76 typedef int StateLabel;
78 //-------------------------------------------------------------------------
79 // Declarations of data and functions created by BURG
80 //-------------------------------------------------------------------------
82 extern short* burm_nts[];
84 extern StateLabel burm_label (InstrTreeNode* p);
86 extern StateLabel burm_state (OpLabel op, StateLabel leftState,
87 StateLabel rightState);
89 extern StateLabel burm_rule (StateLabel state, int goalNT);
91 extern InstrTreeNode** burm_kids (InstrTreeNode* p, int eruleno,
92 InstrTreeNode* kids[]);
94 extern void printcover (InstrTreeNode*, int, int);
95 extern void printtree (InstrTreeNode*);
96 extern int treecost (InstrTreeNode*, int, int);
97 extern void printMatches (InstrTreeNode*);
100 //------------------------------------------------------------------------
101 // class InstrTreeNode
103 // A single tree node in the instruction tree used for
104 // instruction selection via BURG.
105 //------------------------------------------------------------------------
107 class InstrTreeNode {
108 InstrTreeNode(const InstrTreeNode &); // DO NOT IMPLEMENT
109 void operator=(const InstrTreeNode &); // DO NOT IMPLEMENT
111 enum InstrTreeNodeType { NTInstructionNode,
117 // BASIC TREE NODE START
118 InstrTreeNode* LeftChild;
119 InstrTreeNode* RightChild;
120 InstrTreeNode* Parent;
123 // BASIC TREE NODE END
126 InstrTreeNodeType treeNodeType;
130 InstrTreeNode(InstrTreeNodeType nodeType, Value* _val)
131 : treeNodeType(nodeType), val(_val) {
132 LeftChild = RightChild = Parent = 0;
135 virtual ~InstrTreeNode() {
140 InstrTreeNodeType getNodeType () const { return treeNodeType; }
142 Value* getValue () const { return val; }
144 inline OpLabel getOpLabel () const { return opLabel; }
146 inline InstrTreeNode* leftChild() const {
150 // If right child is a list node, recursively get its *left* child
151 inline InstrTreeNode* rightChild() const {
152 return (!RightChild ? 0 :
153 (RightChild->getOpLabel() == VRegListOp
154 ? RightChild->LeftChild : RightChild));
157 inline InstrTreeNode *parent() const {
161 void dump(int dumpChildren, int indent) const;
164 virtual void dumpNode(int indent) const = 0;
166 friend class InstrForest;
170 class InstructionNode : public InstrTreeNode {
172 bool codeIsFoldedIntoParent;
175 InstructionNode(Instruction *_instr);
177 Instruction *getInstruction() const {
178 assert(treeNodeType == NTInstructionNode);
179 return cast<Instruction>(val);
182 void markFoldedIntoParent() { codeIsFoldedIntoParent = true; }
183 bool isFoldedIntoParent() { return codeIsFoldedIntoParent; }
185 // Methods to support type inquiry through isa, cast, and dyn_cast:
186 static inline bool classof(const InstructionNode *N) { return true; }
187 static inline bool classof(const InstrTreeNode *N) {
188 return N->getNodeType() == InstrTreeNode::NTInstructionNode;
192 virtual void dumpNode(int indent) const;
196 class VRegListNode : public InstrTreeNode {
198 VRegListNode() : InstrTreeNode(NTVRegListNode, 0) {
199 opLabel = VRegListOp;
202 // Methods to support type inquiry through isa, cast, and dyn_cast:
203 static inline bool classof(const VRegListNode *N) { return true; }
204 static inline bool classof(const InstrTreeNode *N) {
205 return N->getNodeType() == InstrTreeNode::NTVRegListNode;
209 virtual void dumpNode(int indent) const;
213 class VRegNode : public InstrTreeNode {
215 VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) {
216 opLabel = VRegNodeOp;
219 // Methods to support type inquiry through isa, cast, and dyn_cast:
220 static inline bool classof(const VRegNode *N) { return true; }
221 static inline bool classof(const InstrTreeNode *N) {
222 return N->getNodeType() == InstrTreeNode::NTVRegNode;
226 virtual void dumpNode(int indent) const;
230 class ConstantNode : public InstrTreeNode {
232 ConstantNode(Constant *constVal)
233 : InstrTreeNode(NTConstNode, (Value*)constVal) {
234 opLabel = ConstantNodeOp;
236 Constant *getConstVal() const { return (Constant*) val;}
238 // Methods to support type inquiry through isa, cast, and dyn_cast:
239 static inline bool classof(const ConstantNode *N) { return true; }
240 static inline bool classof(const InstrTreeNode *N) {
241 return N->getNodeType() == InstrTreeNode::NTConstNode;
245 virtual void dumpNode(int indent) const;
249 class LabelNode : public InstrTreeNode {
251 LabelNode(BasicBlock* BB) : InstrTreeNode(NTLabelNode, (Value*)BB) {
252 opLabel = LabelNodeOp;
255 BasicBlock *getBasicBlock() const { return (BasicBlock*)val;}
257 // Methods to support type inquiry through isa, cast, and dyn_cast:
258 static inline bool classof(const LabelNode *N) { return true; }
259 static inline bool classof(const InstrTreeNode *N) {
260 return N->getNodeType() == InstrTreeNode::NTLabelNode;
264 virtual void dumpNode(int indent) const;
268 //------------------------------------------------------------------------
271 // A forest of instruction trees, usually for a single method.
274 // buildTreesForMethod() Builds the forest of trees for a method
275 // getTreeNodeForInstr() Returns the tree node for an Instruction
276 // getRootSet() Returns a set of root nodes for all the trees
278 //------------------------------------------------------------------------
280 class InstrForest : private hash_map<const Instruction *, InstructionNode*> {
282 // Use a vector for the root set to get a deterministic iterator
283 // for stable code generation. Even though we need to erase nodes
284 // during forest construction, a vector should still be efficient
285 // because the elements to erase are nearly always near the end.
286 typedef std::vector<InstructionNode*> RootSet;
287 typedef RootSet:: iterator root_iterator;
288 typedef RootSet::const_iterator const_root_iterator;
294 /*ctor*/ InstrForest (Function *F);
295 /*dtor*/ ~InstrForest ();
297 inline InstructionNode *getTreeNodeForInstr(Instruction* instr) {
298 return (*this)[instr];
301 const_root_iterator roots_begin() const { return treeRoots.begin(); }
302 root_iterator roots_begin() { return treeRoots.begin(); }
303 const_root_iterator roots_end () const { return treeRoots.end(); }
304 root_iterator roots_end () { return treeRoots.end(); }
310 // Private methods for buidling the instruction forest
312 void eraseRoot (InstructionNode* node);
313 void setLeftChild (InstrTreeNode* parent, InstrTreeNode* child);
314 void setRightChild(InstrTreeNode* parent, InstrTreeNode* child);
315 void setParent (InstrTreeNode* child, InstrTreeNode* parent);
316 void noteTreeNodeForInstr(Instruction* instr, InstructionNode* treeNode);
318 InstructionNode* buildTreeForInstruction(Instruction* instr);