%{               // -*- C++ -*-
Xinclude <cstdio>
Xinclude <llvm/CodeGen/InstrForest.h>

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 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=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
%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]);
}