3 Xinclude <llvm/CodeGen/InstrForest.h>
5 typedef InstrTreeNode* NODEPTR_TYPE;
6 Xdefine OP_LABEL(p) ((p)->opLabel)
7 Xdefine LEFT_CHILD(p) ((p)->LeftChild)
8 Xdefine RIGHT_CHILD(p) ((p)->RightChild)
9 Xdefine STATE_LABEL(p) ((p)->state)
12 // Get definitions for various instruction values that we will need...
13 #define HANDLE_TERM_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N
14 #define HANDLE_UNARY_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N
15 #define HANDLE_BINARY_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N
16 #define HANDLE_MEMORY_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N
17 #define HANDLE_OTHER_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N
19 #include "llvm/Instruction.def"
25 %term Ret=RetOPCODE /* return void from a function */
26 %term RetValue=101 /* return a value from a function */
27 %term BrUncond=BrOPCODE
29 %term Switch=SwitchOPCODE
40 /* Use the next 4 to distinguish bitwise operators (reg) from
41 * logical operators (bool). Burg will diverge otherwise.
48 %term SetCC=114 /* use this to match all SetCC instructions */
55 %term Malloc=MallocOPCODE
57 %term Alloca=AllocaOPCODE
58 %term AllocaN=122 /* alloca with arg N */
60 %term LoadIdx=123 /* load with index vector */
61 %term Store=StoreOPCODE
62 %term GetElemPtr=GetElementPtrOPCODE
63 %term GetElemPtrIdx=125 /* getElemPtr with index vector */
65 %term Phi=PHINodeOPCODE
67 %term Cast=CastOPCODE /* cast that will be ignored. others are made explicit */
85 /* 30...46 are unused */
87 * The foll. values should match the constants in InstrForest.h
93 /* 50+i is a variant of i, as defined above */
97 /*-----------------------------------------------------------------------*
98 * The productions of the grammar.
99 * Note that all chain rules are numbered 101 and above.
100 * Also, a special case of production X is numbered 100+X, 200+X, etc.
101 * The cost of a 1-cycle operation is represented as 10, to allow
102 * finer comparisons of costs (effectively, fractions of 1/10).
103 *-----------------------------------------------------------------------*/
106 * The top-level statements
109 stmt: RetValue(reg) = 2 (30);
110 stmt: Store(reg,reg) = 3 (10);
111 stmt: Store(reg,ptrreg) = 4 (10);
112 stmt: BrUncond = 5 (20);
113 stmt: BrCond(bool) = 6 (20);
114 stmt: BrCond(setCCconst) = 206 (10); /* may save one instruction */
115 stmt: BrCond(boolreg) = 8 (20); /* may avoid an extra instr */
116 stmt: BrCond(boolconst) = 208 (20); /* may avoid an extra instr */
117 stmt: Switch(reg) = 9 (30); /* cost = load + branch */
120 stmt: bool = 113 (0);
123 * List node used for nodes with more than 2 children
125 reg: VRegList(reg,reg) = 10 (0);
128 * Special case non-terminals to help combine unary instructions.
129 * Eg1: zdouble <- todouble(xfloat) * todouble(yfloat)
130 * Eg2: c <- a AND (NOT b).
131 * Note that the costs are counted for the special non-terminals
132 * here, not for the bool or reg productions later.
134 not: Not(bool) = 21 (10);
135 tobool: ToBoolTy(bool) = 22 (10);
136 tobool: ToBoolTy(reg) = 322 (10);
137 toubyte: ToUByteTy(reg) = 23 (10);
138 tosbyte: ToSByteTy(reg) = 24 (10);
139 toushort: ToUShortTy(reg) = 25 (10);
140 toshort: ToShortTy(reg) = 26 (10);
141 touint: ToUIntTy(reg) = 27 (10);
142 toint: ToIntTy(reg) = 28 (10);
143 toulong: ToULongTy(reg) = 29 (10);
144 tolong: ToLongTy(reg) = 30 (10);
145 tofloat: ToFloatTy(reg) = 31 (10);
146 todouble: ToDoubleTy(reg) = 32 (10);
147 todoubleConst: ToDoubleTy(Constant) = 232 (10);
150 * All the ways to produce a boolean value:
151 * -- boolean operators: Not, And, Or, ..., ToBoolTy, SetCC
152 * -- an existing boolean register not in the same tree
153 * -- a boolean constant
155 * We add special cases for when one operand is a constant.
156 * We do not need the cases when all operands (one or both) are const
157 * because constant folding should take care of that beforehand.
159 bool: And(bool,bool) = 38 (10);
160 bool: And(bool,not) = 138 (0); /* cost is counted for not */
161 bool: And(bool,boolconst) = 238 (10);
162 bool: Or (bool,bool) = 39 (10);
163 bool: Or (bool,not) = 139 (0); /* cost is counted for not */
164 bool: Or (bool,boolconst) = 239 (10);
165 bool: Xor(bool,bool) = 40 (10);
166 bool: Xor(bool,not) = 140 (0); /* cost is counted for not */
167 bool: Xor(bool,boolconst) = 240 (10);
170 bool: tobool = 222 (0);
171 bool: setCCconst = 241 (0);
172 bool: setCC = 242 (0);
173 bool: boolreg = 243 (10);
174 bool: boolconst = 244 (10);
176 setCCconst: SetCC(reg,Constant) = 41 (5);
177 setCC: SetCC(reg,reg) = 42 (10);
178 boolreg: VReg = 43 (0);
179 boolconst: Constant = 44 (0);
182 * The unary cast operators.
184 reg: toubyte = 123 (0);
185 reg: tosbyte = 124 (0);
186 reg: toushort = 125 (0);
187 reg: toshort = 126 (0);
188 reg: touint = 127 (0);
189 reg: toint = 128 (0);
190 reg: toulong = 129 (0);
191 reg: tolong = 130 (0);
192 reg: tofloat = 131 (0);
193 reg: todouble = 132 (0);
194 reg: todoubleConst = 133 (0);
196 reg: ToArrayTy(reg) = 19 (10);
197 reg: ToPointerTy(reg) = 20 (10);
200 * The binary arithmetic operators.
202 reg: Add(reg,reg) = 33 (10);
203 reg: Sub(reg,reg) = 34 (10);
204 reg: Mul(reg,reg) = 35 (30);
205 reg: Mul(todouble,todouble) = 135 (20); /* avoids 1-2 type converts */
206 reg: Div(reg,reg) = 36 (60);
207 reg: Rem(reg,reg) = 37 (60);
210 * The binary bitwise logical operators.
212 reg: BAnd(reg,reg) = 338 (10);
213 reg: BAnd(reg,bnot) = 438 (10);
214 reg: BOr( reg,reg) = 339 (10);
215 reg: BOr( reg,bnot) = 439 (10);
216 reg: BXor(reg,reg) = 340 (10);
217 reg: BXor(reg,bnot) = 440 (10);
219 reg: bnot = 321 ( 0);
220 bnot: BNot(reg) = 421 (10);
223 * The binary operators with one constant argument.
225 reg: Add(reg,Constant) = 233 (10);
226 reg: Sub(reg,Constant) = 234 (10);
227 reg: Mul(reg,Constant) = 235 (30);
228 reg: Mul(todouble,todoubleConst) = 335 (20); /* avoids 1-2 type converts */
229 reg: Div(reg,Constant) = 236 (60);
230 reg: Rem(reg,Constant) = 237 (60);
232 reg: BAnd(reg,Constant) = 538 (0);
233 reg: BOr( reg,Constant) = 539 (0);
234 reg: BXor(reg,Constant) = 540 (0);
237 * Memory access instructions
239 reg: Load(reg) = 51 (30);
240 reg: Load(ptrreg) = 52 (20); /* 1 counted for ptrreg */
241 reg: LoadIdx(reg,reg) = 53 (30);
242 reg: LoadIdx(ptrreg,reg) = 54 (20); /* 1 counted for ptrreg */
243 reg: ptrreg = 155 (0);
244 ptrreg: GetElemPtr(reg) = 55 (10);
245 ptrreg: GetElemPtrIdx(reg,reg) = 56 (10);
246 reg: Alloca = 57 (10);
247 reg: AllocaN(reg) = 58 (10);
250 * Other operators producing register values
252 reg: Call = 61 (20); /* just ignore the operands! */
253 reg: Shl(reg,reg) = 62 (20); /* 1 for issue restrictions */
254 reg: Shr(reg,reg) = 63 (20); /* 1 for issue restrictions */
255 reg: Phi(reg,reg) = 64 (0);
258 * Finally, leaf nodes of expression trees (other than boolreg)
261 reg: Constant = 72 (3); /* prefer direct use */
266 /*-----------------------------------------------------------------------*
267 * The rest of this file provides code to print the cover produced
268 * by BURG and information about computed tree cost and matches.
269 * This code was taken from sample.gr provided with BURG.
270 *-----------------------------------------------------------------------*/
272 void printcover(NODEPTR_TYPE p, int goalnt, int indent) {
273 int eruleno = burm_rule(STATE_LABEL(p), goalnt);
274 short *nts = burm_nts[eruleno];
275 NODEPTR_TYPE kids[10];
279 printf("no cover\n");
282 for (i = 0; i < indent; i++)
284 printf("%s\n", burm_string[eruleno]);
285 burm_kids(p, eruleno, kids);
286 for (i = 0; nts[i]; i++)
287 printcover(kids[i], nts[i], indent+1);
290 void printtree(NODEPTR_TYPE p) {
291 int op = burm_op_label(p);
293 printf("%s", burm_opname[op]);
294 switch (burm_arity[op]) {
299 printtree(burm_child(p, 0));
304 printtree(burm_child(p, 0));
306 printtree(burm_child(p, 1));
312 int treecost(NODEPTR_TYPE p, int goalnt, int costindex) {
313 int eruleno = burm_rule(STATE_LABEL(p), goalnt);
314 int cost = burm_cost[eruleno][costindex], i;
315 short *nts = burm_nts[eruleno];
316 NODEPTR_TYPE kids[10];
318 burm_kids(p, eruleno, kids);
319 for (i = 0; nts[i]; i++)
320 cost += treecost(kids[i], nts[i], costindex);
324 void printMatches(NODEPTR_TYPE p) {
328 printf("Node 0x%lx= ", (unsigned long)p);
330 printf(" matched rules:\n");
331 for (nt = 1; burm_ntname[nt] != (char*)NULL; nt++)
332 if ((eruleno = burm_rule(STATE_LABEL(p), nt)) != 0)
333 printf("\t%s\n", burm_string[eruleno]);