#define SUPPRESS_COMPILER_INLINES
#include "std.h"
#include "generate.h"
#include "compiler.h"
static parse_node_t *optimize (parse_node_t *);
static parse_node_t **last_local_refs = 0;
static int optimizer_num_locals;
/* Document optimizations here so we can make sure they don't interfere.
*
* Transfer of dying variables:
* . If the last F_LOCAL was not in a loop, replace with transfer_local.
* . Similarly, if an assign is done, change the last use to a transfer if safe
* CAVEATS: we ignore while_dec, loop_cond, and loop_incr. Justification is
* that transfer_local doesn't clobber ints since it just sets type to T_NUMBER
* This optimization also can't deal with code motion. Since it assumes the
* order optimized is the same as the order emitted.
* It also can't detect that a variable dies along multiple branches, so:
* if (y) { use(x); } else { use(x); } x = 1;
* doesn't get optimized.
*/
static void
optimize_expr_list (parse_node_t * expr) {
if (!expr) return;
do {
expr->v.expr = optimize(expr->v.expr);
} while ((expr = expr->r.expr));
}
static void
optimize_lvalue_list (parse_node_t * expr) {
while ((expr = expr->r.expr)) {
expr->v.expr = optimize(expr->l.expr);
}
}
#define OPT(x) x = optimize(x)
#define OPTIMIZER_IN_LOOP 1
#define OPTIMIZER_IN_COND 2 /* switch or if or ?: */
static int optimizer_state = 0;
static parse_node_t *
optimize (parse_node_t * expr) {
if (!expr) return 0;
switch (expr->kind) {
case NODE_TERNARY_OP:
OPT(expr->l.expr);
OPT(expr->r.expr->l.expr);
OPT(expr->r.expr->r.expr);
break;
case NODE_BINARY_OP:
OPT(expr->l.expr);
if (expr->v.number == F_ASSIGN) {
if (IS_NODE(expr->r.expr, NODE_OPCODE_1, F_LOCAL_LVALUE)) {
if (!optimizer_state) {
int x = expr->r.expr->l.number;
if (last_local_refs[x]) {
last_local_refs[x]->v.number = F_TRANSFER_LOCAL;
last_local_refs[x] = 0;
}
}
}
}
OPT(expr->r.expr);
break;
case NODE_UNARY_OP:
OPT(expr->r.expr);
break;
case NODE_OPCODE:
break;
case NODE_TERNARY_OP_1:
OPT(expr->l.expr);
OPT(expr->r.expr->l.expr);
OPT(expr->r.expr->r.expr);
break;
case NODE_BINARY_OP_1:
OPT(expr->l.expr);
OPT(expr->r.expr);
break;
case NODE_UNARY_OP_1:
OPT(expr->r.expr);
if (expr->v.number == F_VOID_ASSIGN_LOCAL) {
if (last_local_refs[expr->l.number] && !optimizer_state) {
last_local_refs[expr->l.number]->v.number = F_TRANSFER_LOCAL;
last_local_refs[expr->l.number] = 0;
}
}
break;
case NODE_OPCODE_1:
if (expr->v.number == F_LOCAL || expr->v.number == F_LOCAL_LVALUE) {
if (expr->v.number == F_LOCAL) {
if(!optimizer_state) {
last_local_refs[expr->l.number] = expr;
break;
}
}
last_local_refs[expr->l.number] = 0;
}
break;
case NODE_OPCODE_2:
break;
case NODE_RETURN:
OPT(expr->r.expr);
break;
case NODE_STRING:
case NODE_REAL:
case NODE_NUMBER:
break;
case NODE_LAND_LOR:
case NODE_BRANCH_LINK:
{
int in_cond = (optimizer_state & OPTIMIZER_IN_COND);
OPT(expr->l.expr);
optimizer_state |= OPTIMIZER_IN_COND;
OPT(expr->r.expr);
optimizer_state &= ~OPTIMIZER_IN_COND;
optimizer_state |= in_cond;
break;
}
case NODE_CALL_2:
case NODE_CALL_1:
case NODE_CALL:
optimize_expr_list(expr->r.expr);
break;
case NODE_TWO_VALUES:
OPT(expr->l.expr);
OPT(expr->r.expr);
break;
case NODE_CONTROL_JUMP:
case NODE_PARAMETER:
case NODE_PARAMETER_LVALUE:
break;
case NODE_IF:
{
int in_cond;
OPT(expr->v.expr);
in_cond = (optimizer_state & OPTIMIZER_IN_COND);
optimizer_state |= OPTIMIZER_IN_COND;
OPT(expr->l.expr);
OPT(expr->r.expr);
optimizer_state &= ~OPTIMIZER_IN_COND;
optimizer_state |= in_cond;
break;
}
case NODE_LOOP:
{
int in_loop = (optimizer_state & OPTIMIZER_IN_LOOP);
optimizer_state |= OPTIMIZER_IN_LOOP;
OPT(expr->v.expr);
OPT(expr->l.expr);
OPT(expr->r.expr);
optimizer_state &= ~OPTIMIZER_IN_LOOP;
optimizer_state |= in_loop;
break;
}
case NODE_FOREACH:
OPT(expr->l.expr);
OPT(expr->r.expr);
OPT(expr->v.expr);
break;
case NODE_CASE_NUMBER:
case NODE_CASE_STRING:
case NODE_DEFAULT:
break;
case NODE_SWITCH_STRINGS:
case NODE_SWITCH_NUMBERS:
case NODE_SWITCH_DIRECT:
case NODE_SWITCH_RANGES:
{
int in_cond;
OPT(expr->l.expr);
in_cond = (optimizer_state & OPTIMIZER_IN_COND);
optimizer_state |= OPTIMIZER_IN_COND;
OPT(expr->r.expr);
optimizer_state &= ~OPTIMIZER_IN_COND;
optimizer_state |= in_cond;
break;
}
case NODE_CATCH:
OPT(expr->r.expr);
break;
case NODE_LVALUE_EFUN:
OPT(expr->l.expr);
optimize_lvalue_list(expr->r.expr);
break;
case NODE_FUNCTION_CONSTRUCTOR:
/* Don't optimize inside of these; we'll get confused by local vars
* since it's a separate frame, etc
*
* OPT(expr->r.expr);
*
* BUT make sure to optimize the things which AREN'T part of that
* frame, namely, the arguments, otherwise we will screw up:
*
* use(local); return (: foo, local :); // local evaluated at
* use(local); return (: ... $(local) ... :); // construction time
*/
if (expr->r.expr)
optimize_expr_list(expr->r.expr); /* arguments */
break;
case NODE_ANON_FUNC:
break;
case NODE_EFUN:
optimize_expr_list(expr->r.expr);
break;
default:
break;
}
return expr;
}
#ifdef DEBUG
char *lpc_tree_name[] = {
"return", "two values", "opcode", "opcode_1", "opcode_2",
"unary op", "unary op_1", "binary op", "binary op_1",
"ternary op", "ternary op_1", "control jump", "loop", "call",
"call_1", "call_2", "&& ||", "foreach", "lvalue_efun", "switch_range",
"switch_string", "switch_direct", "switch_number", "case_number",
"case_string", "default", "if", "branch link", "parameter",
"parameter_lvalue", "efun", "anon func", "real", "number",
"string", "function", "catch"
};
static void lpc_tree (parse_node_t * dest, int num) {
parse_node_t *pn;
dest->kind = NODE_CALL;
dest->v.number = F_AGGREGATE;
dest->type = TYPE_ANY | TYPE_MOD_ARRAY;
dest->l.number = num;
if (!num)
dest->r.expr = 0;
else {
dest->r.expr = new_node_no_line();
dest->r.expr->kind = num--;
pn = dest->r.expr;
while (num--) {
pn->r.expr = new_node_no_line();
pn->type = 0;
pn = pn->r.expr;
}
pn->type = 0;
pn->r.expr = 0;
dest->r.expr->l.expr = pn;
}
}
static void lpc_tree_number (parse_node_t * dest, int num) {
CREATE_NUMBER(dest->v.expr, num);
}
static void lpc_tree_real (parse_node_t * dest, float real) {
CREATE_REAL(dest->v.expr, real);
}
static void lpc_tree_expr (parse_node_t * dest, parse_node_t * expr) {
dest->v.expr = new_node_no_line();
lpc_tree_form(expr, dest->v.expr);
}
static void lpc_tree_string (parse_node_t * dest, const char * str) {
CREATE_STRING(dest->v.expr, str);
}
static void lpc_tree_list (parse_node_t * dest, parse_node_t * expr) {
parse_node_t *pn;
int num = 0;
pn = expr;
while (pn) {
pn = pn->r.expr;
num++;
}
dest->v.expr = new_node_no_line();
lpc_tree(dest->v.expr, num);
dest = dest->v.expr;
while (expr) {
dest = dest->r.expr;
lpc_tree_expr(dest, expr->v.expr);
expr = expr->r.expr;
}
}
#define lpc_tree_opc(x, y) lpc_tree_string(x, query_instr_name(y & ~NOVALUE_USED_FLAG))
#define ARG_1 dest->r.expr
#define ARG_2 dest->r.expr->r.expr
#define ARG_3 dest->r.expr->r.expr->r.expr
#define ARG_4 dest->r.expr->r.expr->r.expr->r.expr
#define ARG_5 dest->r.expr->r.expr->r.expr->r.expr->r.expr
void
lpc_tree_form (parse_node_t * expr, parse_node_t * dest) {
if (!expr) {
dest->kind = NODE_NUMBER;
dest->type = TYPE_ANY;
dest->v.number = 0;
return;
}
switch (expr->kind) {
case NODE_TERNARY_OP:
lpc_tree(dest, 4);
lpc_tree_opc(ARG_2, expr->r.expr->v.number);
lpc_tree_expr(ARG_3, expr->l.expr);
lpc_tree_expr(ARG_4, expr->r.expr);
break;
case NODE_TERNARY_OP_1:
lpc_tree(dest, 5);
lpc_tree_opc(ARG_2, expr->r.expr->v.number);
lpc_tree_number(ARG_3, expr->type);
lpc_tree_expr(ARG_4, expr->l.expr);
lpc_tree_expr(ARG_5, expr->r.expr);
break;
case NODE_BINARY_OP:
case NODE_LAND_LOR:
case NODE_BRANCH_LINK:
lpc_tree(dest, 4);
lpc_tree_opc(ARG_2, expr->v.number);
lpc_tree_expr(ARG_3, expr->l.expr);
lpc_tree_expr(ARG_4, expr->r.expr);
break;
case NODE_TWO_VALUES:
lpc_tree(dest, 3);
lpc_tree_expr(ARG_2, expr->l.expr);
lpc_tree_expr(ARG_3, expr->r.expr);
break;
case NODE_BINARY_OP_1:
lpc_tree(dest, 5);
lpc_tree_opc(ARG_2, expr->v.number);
lpc_tree_number(ARG_3, expr->type);
lpc_tree_expr(ARG_4, expr->l.expr);
lpc_tree_expr(ARG_5, expr->r.expr);
break;
case NODE_UNARY_OP:
lpc_tree(dest, 3);
lpc_tree_opc(ARG_2, expr->v.number);
lpc_tree_expr(ARG_3, expr->r.expr);
break;
case NODE_UNARY_OP_1:
lpc_tree(dest, 4);
lpc_tree_opc(ARG_2, expr->v.number);
lpc_tree_number(ARG_3, expr->l.number);
lpc_tree_expr(ARG_4, expr->r.expr);
break;
case NODE_OPCODE:
lpc_tree(dest, 2);
lpc_tree_opc(ARG_2, expr->v.number);
break;
case NODE_CONTROL_JUMP:
case NODE_PARAMETER:
case NODE_PARAMETER_LVALUE:
lpc_tree(dest, 2);
lpc_tree_number(ARG_2, expr->v.number);
break;
case NODE_OPCODE_1:
lpc_tree(dest, 3);
lpc_tree_opc(ARG_2, expr->v.number);
lpc_tree_number(ARG_3, expr->l.number);
break;
case NODE_OPCODE_2:
lpc_tree(dest, 4);
lpc_tree_opc(ARG_2, expr->v.number);
lpc_tree_number(ARG_3, expr->l.number);
lpc_tree_number(ARG_4, expr->r.number);
break;
case NODE_RETURN:
lpc_tree(dest, 2);
lpc_tree_expr(ARG_2, expr->r.expr);
break;
case NODE_STRING:
case NODE_NUMBER:
lpc_tree(dest, 2);
lpc_tree_number(ARG_2, expr->v.number);
break;
case NODE_REAL:
lpc_tree(dest, 2);
lpc_tree_real(ARG_2, expr->v.real);
break;
case NODE_CALL_2:
case NODE_CALL_1:
case NODE_CALL:
lpc_tree(dest, 4);
lpc_tree_opc(ARG_2, expr->v.number);
lpc_tree_list(ARG_3, expr->r.expr);
lpc_tree_number(ARG_4, expr->l.number);
break;
case NODE_IF:
case NODE_FOREACH:
lpc_tree(dest, 4);
lpc_tree_expr(ARG_2, expr->l.expr);
lpc_tree_expr(ARG_3, expr->r.expr);
lpc_tree_expr(ARG_4, expr->v.expr);
break;
case NODE_LOOP:
lpc_tree(dest, 5);
lpc_tree_number(ARG_2, expr->type);
lpc_tree_expr(ARG_3, expr->v.expr);
lpc_tree_expr(ARG_4, expr->r.expr);
lpc_tree_expr(ARG_5, expr->l.expr);
break;
case NODE_CASE_NUMBER:
case NODE_CASE_STRING:
case NODE_DEFAULT:
lpc_tree(dest, 1);
break;
case NODE_SWITCH_STRINGS:
case NODE_SWITCH_NUMBERS:
case NODE_SWITCH_DIRECT:
case NODE_SWITCH_RANGES:
lpc_tree(dest, 3);
lpc_tree_expr(ARG_2, expr->l.expr);
lpc_tree_expr(ARG_3, expr->r.expr);
break;
case NODE_CATCH:
lpc_tree(dest, 2);
lpc_tree_expr(ARG_2, expr->r.expr);
break;
case NODE_LVALUE_EFUN:
lpc_tree(dest, 3);
lpc_tree_expr(ARG_2, expr->l.expr);
lpc_tree_list(ARG_3, expr->r.expr);
break;
case NODE_FUNCTION_CONSTRUCTOR:
case NODE_EFUN:
lpc_tree(dest, 3);
lpc_tree_opc(ARG_2, expr->v.number);
lpc_tree_list(ARG_3, expr->r.expr);
break;
default:
lpc_tree(dest,1);
lpc_tree_string(ARG_1, "!GARBAGE!");
return;
}
lpc_tree_string(ARG_1, lpc_tree_name[expr->kind]);
}
#endif
short
generate (parse_node_t * node) {
short where = CURRENT_PROGRAM_SIZE;
if (num_parse_error) return 0;
{
i_generate_node(node);
}
free_tree();
return where;
}
static void optimizer_start_function (int n) {
if (n) {
last_local_refs = CALLOCATE(n, parse_node_t *, TAG_COMPILER, "c_start_function");
optimizer_num_locals = n;
while (n--) {
last_local_refs[n] = 0;
}
} else last_local_refs = 0;
}
static void optimizer_end_function (void) {
int i;
if (last_local_refs) {
for (i = 0; i < optimizer_num_locals; i++)
if (last_local_refs[i]) {
last_local_refs[i]->v.number = F_TRANSFER_LOCAL;
}
FREE(last_local_refs);
last_local_refs = 0;
}
}
short generate_function (function_t * f, parse_node_t * node, int num) {
short ret;
if (pragmas & PRAGMA_OPTIMIZE) {
optimizer_start_function(num);
optimizer_state = 0;
node = optimize(node);
optimizer_end_function();
}
ret = generate(node);
return ret;
}
int
node_always_true (parse_node_t * node) {
if (!node) return 1;
if (node->kind == NODE_NUMBER)
return node->v.number;
return 0;
}
int
generate_conditional_branch (parse_node_t * node) {
int branch;
if (!node)
return F_BBRANCH;
/* only have to handle while (x != 0) since while (x == 0) will be
* handled by the x == 0 -> !x and !x optimizations.
*/
if (IS_NODE(node, NODE_BINARY_OP, F_NE)) {
if (IS_NODE(node->r.expr, NODE_NUMBER, 0))
node = node->l.expr;
else if (IS_NODE(node->l.expr, NODE_NUMBER, 0))
node = node->r.expr;
}
if (IS_NODE(node, NODE_UNARY_OP, F_NOT)) {
node = node->r.expr;
branch = F_BBRANCH_WHEN_ZERO;
} else {
branch = F_BBRANCH_WHEN_NON_ZERO;
if (node->kind == NODE_NUMBER) {
if (node->v.number == 0)
branch = 0;
else
branch = F_BBRANCH;
node = 0;
}
if (node) {
if (IS_NODE(node, NODE_BINARY_OP, F_LT)) {
generate(node->l.expr);
generate(node->r.expr);
return F_BBRANCH_LT;
}
if (IS_NODE(node, NODE_OPCODE_1, F_WHILE_DEC)) {
generate(node);
return F_WHILE_DEC;
}
}
}
generate(node);
return branch;
}
#ifdef DEBUG
void
dump_expr_list (parse_node_t * expr) {
if (!expr) return;
do {
dump_tree(expr->v.expr);
} while ((expr = expr->r.expr));
}
static void
dump_lvalue_list (parse_node_t * expr) {
printf("(lvalue_list ");
while ((expr = expr->r.expr))
dump_tree(expr->l.expr);
}
void
dump_tree (parse_node_t * expr) {
if (!expr) return;
switch (expr->kind) {
case NODE_TERNARY_OP:
printf("(%s ", instrs[expr->r.expr->v.number].name);
dump_tree(expr->l.expr);
expr = expr->r.expr;
dump_tree(expr->l.expr);
dump_tree(expr->r.expr);
printf(")");
break;
case NODE_BINARY_OP:
printf("(%s ", instrs[expr->v.number].name);
dump_tree(expr->l.expr);
dump_tree(expr->r.expr);
printf(")");
break;
case NODE_UNARY_OP:
printf("(%s ", instrs[expr->v.number].name);
dump_tree(expr->r.expr);
printf(")");
break;
case NODE_OPCODE:
printf("(%s)", instrs[expr->v.number].name);
break;
case NODE_TERNARY_OP_1:
{
int p = expr->type;
printf("(%s ", instrs[expr->r.expr->v.number].name);
dump_tree(expr->l.expr);
expr = expr->r.expr;
dump_tree(expr->l.expr);
dump_tree(expr->r.expr);
printf(" %i)", p);
break;
}
case NODE_BINARY_OP_1:
printf("(%s ", instrs[expr->v.number].name);
dump_tree(expr->l.expr);
dump_tree(expr->r.expr);
printf(" %i)", expr->type);
break;
case NODE_UNARY_OP_1:
printf("(%s ", instrs[expr->v.number].name);
dump_tree(expr->r.expr);
printf(" %i)", expr->l.number);
break;
case NODE_OPCODE_1:
printf("(%s %i)", instrs[expr->v.number].name, expr->l.number);
break;
case NODE_OPCODE_2:
printf("(%s %i %i)", instrs[expr->v.number].name, expr->l.number, expr->r.number);
break;
case NODE_RETURN:
if (expr->r.expr) {
printf("(return ");
dump_tree(expr->r.expr);
printf(")");
} else {
printf("(return_zero)");
}
break;
case NODE_STRING:
printf("(string %i)", expr->v.number);
break;
case NODE_REAL:
printf("(real %f)", expr->v.real);
break;
case NODE_NUMBER:
printf("(number %i)", expr->v.number);
break;
case NODE_LAND_LOR:
if (expr->v.number == F_LAND)
printf("(&& ");
else
printf("(|| ");
dump_tree(expr->l.expr);
dump_tree(expr->r.expr);
printf(")");
break;
case NODE_BRANCH_LINK:
printf("(branch_link ");
dump_tree(expr->l.expr);
dump_tree(expr->r.expr);
printf(")");
break;
case NODE_CALL_2:
printf("(%s %i %i %i ", instrs[expr->v.number].name, expr->l.number >> 16,
expr->l.number & 0xffff, (expr->r.expr ? expr->r.expr->kind : 0));
dump_expr_list(expr->r.expr);
printf(")");
break;
case NODE_CALL_1:
printf("(%s %i %i ", instrs[expr->v.number].name, expr->l.number,
(expr->r.expr ? expr->r.expr->kind : 0));
dump_expr_list(expr->r.expr);
printf(")");
break;
case NODE_CALL:
printf("(%s %i ", instrs[expr->v.number].name, expr->l.number);
dump_expr_list(expr->r.expr);
printf(")");
break;
case NODE_TWO_VALUES:
dump_tree(expr->l.expr);
printf("\n");
dump_tree(expr->r.expr);
break;
case NODE_CONTROL_JUMP:
if (expr->v.number == CJ_BREAK_SWITCH) {
printf("(break_switch)");
} else if (expr->v.number == CJ_BREAK) {
printf("(break)");
} else if (expr->v.number == CJ_CONTINUE) {
printf("(continue)");
} else {
printf("(UNKNOWN CONTROL JUMP)");
}
break;
case NODE_PARAMETER:
printf("(parameter %i)", expr->v.number);
break;
case NODE_PARAMETER_LVALUE:
printf("(parameter_lvalue %i)", expr->v.number);
break;
case NODE_IF:
printf("(if ");
dump_tree(expr->v.expr);
printf("\n");
dump_tree(expr->l.expr);
if (expr->r.expr) {
printf("\n");
dump_tree(expr->r.expr);
}
printf(")\n");
break;
case NODE_LOOP:
printf("(loop %i\n", expr->type);
dump_tree(expr->v.expr);
printf("\n");
dump_tree(expr->l.expr);
printf("\n");
dump_tree(expr->r.expr);
printf(")\n");
break;
case NODE_FOREACH:
printf("(foreach ");
dump_tree(expr->l.expr);
dump_tree(expr->r.expr);
dump_tree(expr->v.expr);
printf(")\n");
break;
case NODE_CASE_NUMBER:
case NODE_CASE_STRING:
printf("(case)");
break;
case NODE_DEFAULT:
printf("(default)");
break;
case NODE_SWITCH_STRINGS:
case NODE_SWITCH_NUMBERS:
case NODE_SWITCH_DIRECT:
case NODE_SWITCH_RANGES:
printf("(switch ");
dump_tree(expr->l.expr);
dump_tree(expr->r.expr);
printf(")");
break;
case NODE_CATCH:
printf("(catch ");
dump_tree(expr->r.expr);
printf(")");
break;
case NODE_LVALUE_EFUN:
printf("(lvalue_efun ");
dump_tree(expr->l.expr);
dump_lvalue_list(expr->r.expr);
printf(")");
break;
case NODE_FUNCTION_CONSTRUCTOR:
printf("(function %i ", expr->v.number & 0xff);
if (expr->r.expr) {
printf("(array ");
dump_expr_list(expr->r.expr);
printf(")");
} else {
printf("(number 0)");
}
switch (expr->v.number & 0xff) {
case FP_SIMUL:
printf("(fp-simul %i)", expr->v.number >> 8);
break;
case FP_LOCAL:
printf("(fp-local %i)", expr->v.number >> 8);
break;
case FP_EFUN:
printf("(fp-efun %s)", instrs[expr->v.number >> 8].name);
break;
case FP_FUNCTIONAL:
case FP_FUNCTIONAL | FP_NOT_BINDABLE:
printf("(fp-functional %i ", expr->v.number >> 8);
dump_tree(expr->l.expr);
printf(")");
break;
}
printf(" %i)", expr->v.number >> 8);
break;
case NODE_ANON_FUNC:
printf("(anon-func %i %i ", expr->v.number, expr->l.number);
dump_tree(expr->r.expr);
printf(")");
break;
case NODE_EFUN:
printf("(%s ", instrs[expr->v.number & ~NOVALUE_USED_FLAG].name);
dump_expr_list(expr->r.expr);
printf(")");
break;
default:
printf("(unknown)");
break;
}
fflush(stdout);
}
#endif
