%{ // -*- C++ -*- Xinclude Xinclude typedef 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 Not=NotOPCODE %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 (reg) from * logical operators (bool). Burg will diverge otherwise. */ %term BAnd=111 %term BOr=112 %term BXor=113 %term BNot=105 %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 LoadIdx=123 /* load with index vector */ %term Store=StoreOPCODE %term GetElemPtr=GetElementPtrOPCODE %term GetElemPtrIdx=125 /* getElemPtr with index vector */ %term Phi=PHINodeOPCODE %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 /* 30...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(bool) = 6 (20); stmt: BrCond(setCCconst) = 206 (10); /* may save one instruction */ stmt: BrCond(boolreg) = 8 (20); /* may avoid an extra instr */ stmt: BrCond(boolconst) = 208 (20); /* may avoid an extra instr */ stmt: Switch(reg) = 9 (30); /* cost = load + branch */ stmt: reg = 111 (0); stmt: bool = 113 (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, not for the bool or reg productions later. */ not: Not(bool) = 21 (10); tobool: ToBoolTy(bool) = 22 (10); tobool: ToBoolTy(reg) = 322 (10); 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: * -- boolean operators: Not, And, Or, ..., ToBoolTy, SetCC * -- an existing boolean register not in the same tree * -- a boolean constant * * We add special cases for when one operand is a constant. * We do not need the cases when all operands (one or both) are const * because constant folding should take care of that beforehand. */ bool: And(bool,bool) = 38 (10); bool: And(bool,not) = 138 (0); /* cost is counted for not */ bool: And(bool,boolconst) = 238 (10); bool: Or (bool,bool) = 39 (10); bool: Or (bool,not) = 139 (0); /* cost is counted for not */ bool: Or (bool,boolconst) = 239 (10); bool: Xor(bool,bool) = 40 (10); bool: Xor(bool,not) = 140 (0); /* cost is counted for not */ bool: Xor(bool,boolconst) = 240 (10); bool: not = 221 (0); bool: tobool = 222 (0); bool: setCCconst = 241 (0); bool: setCC = 242 (0); bool: boolreg = 243 (10); bool: boolconst = 244 (10); setCCconst: SetCC(reg,Constant) = 41 (5); setCC: SetCC(reg,reg) = 42 (10); boolreg: VReg = 43 (0); boolconst: Constant = 44 (0); /* * The unary cast operators. */ 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 (10); reg: BOr( reg,reg) = 339 (10); reg: BOr( reg,bnot) = 439 (10); reg: BXor(reg,reg) = 340 (10); reg: BXor(reg,bnot) = 440 (10); reg: bnot = 321 ( 0); bnot: BNot(reg) = 421 (10); /* * The binary operators with one constant argument. */ 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: LoadIdx(reg,reg) = 53 (30); reg: LoadIdx(ptrreg,reg) = 54 (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); /* * Finally, leaf nodes of expression trees (other than boolreg) */ 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]); }