| %{ // -*- C++ -*- |
| /* ===----------------------------------------------------------------------=== |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file was developed by the LLVM research group and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===*/ |
| |
| Xinclude <cstdio> |
| Xinclude <llvm/CodeGen/InstrForest.h> |
| |
| typedef llvm::InstrTreeNode* NODEPTR_TYPE; |
| Xdefine OP_LABEL(p) ((p)->opLabel) |
| Xdefine LEFT_CHILD(p) ((p)->LeftChild) |
| Xdefine RIGHT_CHILD(p) ((p)->RightChild) |
| Xdefine STATE_LABEL(p) ((p)->state) |
| Xdefine PANIC printf |
| |
| // Get definitions for various instruction values that we will need... |
| #define HANDLE_TERM_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N |
| #define HANDLE_UNARY_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N |
| #define HANDLE_BINARY_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N |
| #define HANDLE_MEMORY_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N |
| #define HANDLE_OTHER_INST(N, OPC, CLASS) Ydefine OPC##OPCODE N |
| |
| #include "llvm/Instruction.def" |
| |
| %} |
| |
| %start stmt |
| |
| %term Ret=RetOPCODE /* return void from a function */ |
| %term RetValue=101 /* return a value from a function */ |
| %term BrUncond=BrOPCODE |
| %term BrCond=102 |
| %term Switch=SwitchOPCODE |
| /* 4 is unused */ |
| %term Add=AddOPCODE |
| %term Sub=SubOPCODE |
| %term Mul=MulOPCODE |
| %term Div=DivOPCODE |
| %term Rem=RemOPCODE |
| %term And=AndOPCODE |
| %term Or=OrOPCODE |
| %term Xor=XorOPCODE |
| /* Use the next 4 to distinguish bitwise operators from |
| * logical operators. This is no longer used for Sparc, |
| * but may be useful for other target machines. |
| * The last one is the bitwise Not(val) == XOR val, 11..1. |
| * Note that it is also a binary operator, not unary. |
| */ |
| %term BAnd=111 |
| %term BOr=112 |
| %term BXor=113 |
| %term BNot=213 |
| /* The next one is the boolean Not(val) == bool XOR val, true |
| * Note that it is also a binary operator, not unary. |
| */ |
| %term Not=313 |
| |
| %term SetCC=114 /* use this to match all SetCC instructions */ |
| /* %term SetEQ=13 */ |
| /* %term SetNE=14 */ |
| /* %term SetLE=15 */ |
| /* %term SetGE=16 */ |
| /* %term SetLT=17 */ |
| /* %term SetGT=18 */ |
| %term Malloc=MallocOPCODE |
| %term Free=FreeOPCODE |
| %term Alloca=AllocaOPCODE |
| %term AllocaN=122 /* alloca with arg N */ |
| %term Load=LoadOPCODE |
| %term Store=StoreOPCODE |
| %term GetElemPtr=GetElementPtrOPCODE |
| %term GetElemPtrIdx=125 /* getElemPtr with index vector */ |
| |
| %term Phi=PHIOPCODE |
| |
| %term Cast=CastOPCODE /* cast that will be ignored. others are made explicit */ |
| %term ToBoolTy=127 |
| %term ToUByteTy=128 |
| %term ToSByteTy=129 |
| %term ToUShortTy=130 |
| %term ToShortTy=131 |
| %term ToUIntTy=132 |
| %term ToIntTy=133 |
| %term ToULongTy=134 |
| %term ToLongTy=135 |
| %term ToFloatTy=136 |
| %term ToDoubleTy=137 |
| %term ToArrayTy=138 |
| %term ToPointerTy=139 |
| |
| %term Call=CallOPCODE |
| %term Shl=ShlOPCODE |
| %term Shr=ShrOPCODE |
| %term VANext=VANextOPCODE |
| %term VAArg=VAArgOPCODE |
| /* 33...46 are unused */ |
| /* |
| * The foll. values should match the constants in InstrForest.h |
| */ |
| %term VRegList=97 |
| %term VReg=98 |
| %term Constant=99 |
| %term Label=100 |
| /* 50+i is a variant of i, as defined above */ |
| |
| |
| %% |
| /*-----------------------------------------------------------------------* |
| * The productions of the grammar. |
| * Note that all chain rules are numbered 101 and above. |
| * Also, a special case of production X is numbered 100+X, 200+X, etc. |
| * The cost of a 1-cycle operation is represented as 10, to allow |
| * finer comparisons of costs (effectively, fractions of 1/10). |
| *-----------------------------------------------------------------------*/ |
| |
| /* |
| * The top-level statements |
| */ |
| stmt: Ret = 1 (30); |
| stmt: RetValue(reg) = 2 (30); |
| stmt: Store(reg,reg) = 3 (10); |
| stmt: Store(reg,ptrreg) = 4 (10); |
| stmt: BrUncond = 5 (20); |
| stmt: BrCond(setCC) = 6 (20); /* branch on cond. code */ |
| stmt: BrCond(setCCconst) = 206 (10); /* may save one instruction */ |
| stmt: BrCond(reg) = 8 (20); /* may avoid an extra instr */ |
| stmt: BrCond(Constant) = 208 (20); /* may avoid an extra instr */ |
| stmt: Switch(reg) = 9 (30); /* cost = load + branch */ |
| |
| stmt: reg = 111 (0); |
| |
| /* |
| * List node used for nodes with more than 2 children |
| */ |
| reg: VRegList(reg,reg) = 10 (0); |
| |
| /* |
| * Special case non-terminals to help combine unary instructions. |
| * Eg1: zdouble <- todouble(xfloat) * todouble(yfloat) |
| * Eg2: c <- a AND (NOT b). |
| * Note that the costs are counted for the special non-terminals here, |
| * and should not be counted again for the reg productions later. |
| */ |
| not: Not(reg,reg) = 21 (10); |
| tobool: ToBoolTy(reg) = 22 (10); |
| not: Not(tobool, reg) = 322 (10); // fold cast-to-bool into not |
| toubyte: ToUByteTy(reg) = 23 (10); |
| tosbyte: ToSByteTy(reg) = 24 (10); |
| toushort: ToUShortTy(reg) = 25 (10); |
| toshort: ToShortTy(reg) = 26 (10); |
| touint: ToUIntTy(reg) = 27 (10); |
| toint: ToIntTy(reg) = 28 (10); |
| toulong: ToULongTy(reg) = 29 (10); |
| tolong: ToLongTy(reg) = 30 (10); |
| tofloat: ToFloatTy(reg) = 31 (10); |
| todouble: ToDoubleTy(reg) = 32 (10); |
| todoubleConst: ToDoubleTy(Constant) = 232 (10); |
| |
| /* |
| * All the ways to produce a boolean value (Not and ToBoolTy are above): |
| * -- boolean operators: Not, And, Or, ..., ToBoolTy, SetCC |
| * -- an existing boolean register not in the same tree |
| * -- a boolean constant |
| * |
| * For And, Or, Xor, we add special cases for when: |
| * (a) one operand is a constant. |
| * (b) one operand is a NOT, to use the ANDN, ORN, and XORN instrns. |
| * We do not need the cases when both operands are constant |
| * because constant folding should take care of that beforehand. |
| */ |
| reg: And(reg,reg) = 38 (10); |
| reg: And(reg,not) = 138 (0); /* cost is counted for not */ |
| reg: And(reg,Constant) = 238 (10); |
| reg: Or (reg,reg) = 39 (10); |
| reg: Or (reg,not) = 139 (0); /* cost is counted for not */ |
| reg: Or (reg,Constant) = 239 (10); |
| reg: Xor(reg,reg) = 40 (10); |
| reg: Xor(reg,not) = 140 (0); /* cost is counted for not */ |
| reg: Xor(reg,Constant) = 240 (10); |
| |
| /* Special case non-terms for BrCond(setCC) and BrCond(setCCconst) */ |
| setCCconst: SetCC(reg,Constant) = 41 (5); |
| setCC: SetCC(reg,reg) = 42 (10); |
| |
| reg: not = 221 (0); |
| reg: tobool = 222 (0); |
| reg: setCCconst = 241 (0); |
| reg: setCC = 242 (0); |
| |
| /* |
| * Special case non-terminals for the unary cast operators. |
| * Some of these can be folded into other operations (e.g., todouble). |
| * The rest are just for uniformity. |
| */ |
| reg: toubyte = 123 (0); |
| reg: tosbyte = 124 (0); |
| reg: toushort = 125 (0); |
| reg: toshort = 126 (0); |
| reg: touint = 127 (0); |
| reg: toint = 128 (0); |
| reg: toulong = 129 (0); |
| reg: tolong = 130 (0); |
| reg: tofloat = 131 (0); |
| reg: todouble = 132 (0); |
| reg: todoubleConst = 133 (0); |
| |
| reg: ToArrayTy(reg) = 19 (10); |
| reg: ToPointerTy(reg) = 20 (10); |
| |
| /* |
| * The binary arithmetic operators. |
| */ |
| reg: Add(reg,reg) = 33 (10); |
| reg: Sub(reg,reg) = 34 (10); |
| reg: Mul(reg,reg) = 35 (30); |
| reg: Mul(todouble,todouble) = 135 (20); /* avoids 1-2 type converts */ |
| reg: Div(reg,reg) = 36 (60); |
| reg: Rem(reg,reg) = 37 (60); |
| |
| /* |
| * The binary bitwise logical operators. |
| */ |
| reg: BAnd(reg,reg) = 338 (10); |
| reg: BAnd(reg,bnot) = 438 ( 0); /* cost is counted for not */ |
| reg: BOr( reg,reg) = 339 (10); |
| reg: BOr( reg,bnot) = 439 ( 0); /* cost is counted for not */ |
| reg: BXor(reg,reg) = 340 (10); |
| reg: BXor(reg,bnot) = 440 ( 0); /* cost is counted for not */ |
| |
| reg: bnot = 321 ( 0); |
| bnot: BNot(reg,reg) = 421 (10); |
| |
| /* |
| * Special cases for the binary operators with one constant argument. |
| * Not and BNot are effectively just one argument, so not needed here. |
| */ |
| reg: Add(reg,Constant) = 233 (10); |
| reg: Sub(reg,Constant) = 234 (10); |
| reg: Mul(reg,Constant) = 235 (30); |
| reg: Mul(todouble,todoubleConst) = 335 (20); /* avoids 1-2 type converts */ |
| reg: Div(reg,Constant) = 236 (60); |
| reg: Rem(reg,Constant) = 237 (60); |
| |
| reg: BAnd(reg,Constant) = 538 (0); |
| reg: BOr( reg,Constant) = 539 (0); |
| reg: BXor(reg,Constant) = 540 (0); |
| |
| /* |
| * Memory access instructions |
| */ |
| reg: Load(reg) = 51 (30); |
| reg: Load(ptrreg) = 52 (20); /* 1 counted for ptrreg */ |
| reg: ptrreg = 155 (0); |
| ptrreg: GetElemPtr(reg) = 55 (10); |
| ptrreg: GetElemPtrIdx(reg,reg) = 56 (10); |
| reg: Alloca = 57 (10); |
| reg: AllocaN(reg) = 58 (10); |
| |
| /* |
| * Other operators producing register values |
| */ |
| reg: Call = 61 (20); /* just ignore the operands! */ |
| reg: Shl(reg,reg) = 62 (20); /* 1 for issue restrictions */ |
| reg: Shr(reg,reg) = 63 (20); /* 1 for issue restrictions */ |
| reg: Phi(reg,reg) = 64 (0); |
| reg: VANext(reg) = 65 (40); /* incr stack slot pointer */ |
| reg: VAArg(reg) = 66 (40); /* get a vararg */ |
| |
| /* |
| * Finally, leaf nodes of expression trees. |
| */ |
| reg: VReg = 71 (0); |
| reg: Constant = 72 (3); /* prefer direct use */ |
| |
| |
| |
| %% |
| /*-----------------------------------------------------------------------* |
| * The rest of this file provides code to print the cover produced |
| * by BURG and information about computed tree cost and matches. |
| * This code was taken from sample.gr provided with BURG. |
| *-----------------------------------------------------------------------*/ |
| |
| void printcover(NODEPTR_TYPE p, int goalnt, int indent) { |
| int eruleno = burm_rule(STATE_LABEL(p), goalnt); |
| short *nts = burm_nts[eruleno]; |
| NODEPTR_TYPE kids[10]; |
| int i; |
| |
| if (eruleno == 0) { |
| printf("no cover\n"); |
| return; |
| } |
| for (i = 0; i < indent; i++) |
| printf("."); |
| printf("%s\n", burm_string[eruleno]); |
| burm_kids(p, eruleno, kids); |
| for (i = 0; nts[i]; i++) |
| printcover(kids[i], nts[i], indent+1); |
| } |
| |
| void printtree(NODEPTR_TYPE p) { |
| int op = burm_op_label(p); |
| |
| printf("%s", burm_opname[op]); |
| switch (burm_arity[op]) { |
| case 0: |
| break; |
| case 1: |
| printf("("); |
| printtree(burm_child(p, 0)); |
| printf(")"); |
| break; |
| case 2: |
| printf("("); |
| printtree(burm_child(p, 0)); |
| printf(", "); |
| printtree(burm_child(p, 1)); |
| printf(")"); |
| break; |
| } |
| } |
| |
| int treecost(NODEPTR_TYPE p, int goalnt, int costindex) { |
| int eruleno = burm_rule(STATE_LABEL(p), goalnt); |
| int cost = burm_cost[eruleno][costindex], i; |
| short *nts = burm_nts[eruleno]; |
| NODEPTR_TYPE kids[10]; |
| |
| burm_kids(p, eruleno, kids); |
| for (i = 0; nts[i]; i++) |
| cost += treecost(kids[i], nts[i], costindex); |
| return cost; |
| } |
| |
| void printMatches(NODEPTR_TYPE p) { |
| int nt; |
| int eruleno; |
| |
| printf("Node 0x%lx= ", (unsigned long)p); |
| printtree(p); |
| printf(" matched rules:\n"); |
| for (nt = 1; burm_ntname[nt] != (char*)NULL; nt++) |
| if ((eruleno = burm_rule(STATE_LABEL(p), nt)) != 0) |
| printf("\t%s\n", burm_string[eruleno]); |
| } |