Assignment 1: Basically Better Blocks

Again working with the compiler from Assignment 0, in this step you will add the purely forward basic block optimizations.

Algorithms For Generator Functions

The following algorithms are presented as rough guide- lines for the optimized versions of the generator functions given in the opcode table. These are deliberately incom- plete and imperfect . . . you must decide where and how to do what is missing or ambiguous.

binop

tuple *
binop(o, t0, t1)
opcode o;
tuple *t0, *t1;

/* simplify later matching by normalizing operand order */
if (o is commutative) {
     normalize order of t0 and t1;
}

/* local special-case optimizations */
if (local optimization applies) {
     perform local optimization;
     return(ptr. to result tuple);
}

/* constant folding */
if (both args are constants) {
     fold the expression into a single constant value;
     return( cop(the resulting value) );
}

/* common subexpression elimination */
if (equivalent tuple is available) {
     return(ptr. to available tuple);
}

/* some things just can't be optimized away...  yet */
make a new tuple for o(t0, t1);
mark tuple as non-constant-valued;
assign the tuple a new value number;
return(ptr. to this tuple);

cop

tuple *
cop(c)
int c;

/* constant pooling (common subexpression elimination) */
if (equivalent tuple is available) {
     return(ptr. to available tuple);
}

/* some things just can't be optimized away...  yet */
make a new tuple for const(c);
mark tuple as non-constant-valued;
assign the tuple a new value number;
return(ptr. to this tuple);

ldop

tuple *
ldop(v)
var *v;

/* value propagation */
if (current value of var[0] is an available tuple) {
     return(ptr. to available tuple);
}

/* some things just can't be optimized away...  yet */
update symbol table entry for v[0];
make a new tuple for ld(v);
mark tuple as non-constant-valued;
assign the tuple a new value number;
return(ptr. to this tuple);

ldxop

tuple *
ldxop(v, t)
var *v;
tuple *t;

/* value propagation */
if (current value of var[t] is an available tuple) {
     return(ptr. to available tuple);
}

/* some things just can't be optimized away...  yet */
update symbol table entry for v[t];
make a new tuple for ldx(v, t);
mark tuple as non-constant-valued;
assign the tuple a new value number;
return(ptr. to this tuple);

stop

tuple *
stop(v, t)
var *v;
tuple *t;

/* symbol table stuff... */
delete all v[t0] entries where t0 is not constant;
update symbol table entry for v[0];

/* some things just can't be optimized away...  yet */
update symbol table entry for v:
if (there exist entries for v[t] where t is not constant) {
     delete entry for v[t];
}
make a new tuple for st(v, t);
mark tuple as non-constant-valued;
assign the tuple a new value number;
return(tuple ptr. t);

stxop

tuple *
stxop(v, t1, t2)
var *v;
tuple *t1, *t2;

/* symbol table stuff... */
if (t1 is a constant) {
     delete all v[t] entries where t is not constant;
} else {
     delete all v[t] entries;
}
update symbol table entry for v[t1];

/* some things just can't be optimized away...  yet */
make a new tuple for stx(v, t1, t2);
mark tuple as non-constant-valued;
assign the tuple a new value number;
return(tuple ptr. t2);

labop

tuple *
labop(l)
int l;

/* some things just can't be optimized away...  yet */
make a new tuple for label(l);
update label table entry for l;
return(ptr. to this tuple);

selop

tuple *
selop(t, l1, l2)
tuple *t;
int l1, l2;

/* local special-case optimizations */
if (sel tests a constant-valued tuple) {
     make t = ;
     replicate the appropriate label;
}

/* some things just can't be optimized away... yet */
make a new tuple for sel(t, l1, l2);
return(ptr. to this tuple);

killop

tuple *
killop(v)
var *v;

/* not really an operation for forward flow.... */
update symbol table entry for v to say v is dead;
make a new tuple for kill(v);
return(ptr. to this tuple);

Tuple Structure

The basic tuple structure is:

#define tuple struct _tuple
tuple {
    tuple *next, *prev; /* sequential order links */
    opcode oarg;        /* tuple opcode */
    tuple *targ[2];     /* tuple arguments */
    konst carg;         /* constant argument */
    label larg[2];      /* label arguments */
    var *varg;          /* variable name argument */
};

where the use of fields is obvious from the tuple descrip- tions given earlier.

All the tuple code generated will be linked into a cir- cular linked list whose permanent header node is code. Upon end of input, the tuples linked into the code list are auto- matically printed.

The Symbol Table

In the above, there are several references to the han- dling of symbol table entries. Symbol table entries are described by var * values which directly access them. A partial definition of the var structure is:

#define var struct _var
var {
    char *text;         /* pointer to string */
    int type;           /* token type of variable (e.g., KIF) */
    int dim;            /* size of dimension (1 means scalar) */
    ...
};

It will be necessary for you to add fields to this structure so that your tracking of value numbers (i.e., tuple point- ers) for particular subscripts can be accommodated. Notice that dim will be 1 for a scalar -- i.e., int a[1]; and int a; make identical var entries.

Scoping is handled automatically and, in anticipation of the global optimizer, var entries are never deleted. You may assume that the var * values passed to your routines are always valid.

Due Dates, Submission Procedure, & Such

TBA.