From 66fe2227dfbfd2086fb0266cdeea1ca904d76198 Mon Sep 17 00:00:00 2001 From: Eric Biederman Date: Fri, 4 Jul 2003 15:14:04 +0000 Subject: - Moved 2 of the test cases into tests for failure - Reworked the transformation into ssa form and now I catch all unitialized variable uses. - Several more test cases - Bumped the version to 0.34 - Verified that -O2 the scc_transform now works. git-svn-id: svn://svn.coreboot.org/coreboot/trunk@934 2b7e53f0-3cfb-0310-b3e9-8179ed1497e1 --- util/romcc/Makefile | 16 +- util/romcc/romcc.c | 308 ++++++++++++++++++++++++++++++--------- util/romcc/tests/fail_test2.c | 18 +++ util/romcc/tests/fail_test3.c | 10 ++ util/romcc/tests/simple_test55.c | 24 +++ util/romcc/tests/simple_test56.c | 43 ++++++ 6 files changed, 345 insertions(+), 74 deletions(-) create mode 100644 util/romcc/tests/fail_test2.c create mode 100644 util/romcc/tests/fail_test3.c create mode 100644 util/romcc/tests/simple_test55.c create mode 100644 util/romcc/tests/simple_test56.c (limited to 'util/romcc') diff --git a/util/romcc/Makefile b/util/romcc/Makefile index 58778218ed..6161ad3e1e 100644 --- a/util/romcc/Makefile +++ b/util/romcc/Makefile @@ -1,5 +1,5 @@ -VERSION:=0.33 -RELEASE_DATE:=1 July 2003 +VERSION:=0.34 +RELEASE_DATE:=4 July 2003 PACKAGE:=romcc @@ -61,9 +61,7 @@ TESTS=\ simple_test39.c \ simple_test40.c \ simple_test41.c \ - simple_test42.c \ simple_test43.c \ - simple_test44.c \ simple_test45.c \ simple_test46.c \ simple_test47.c \ @@ -74,6 +72,8 @@ TESTS=\ simple_test52.c \ simple_test53.c \ simple_test54.c \ + simple_test55.c \ + simple_test56.c \ raminit_test.c \ raminit_test2.c \ raminit_test3.c \ @@ -81,7 +81,9 @@ TESTS=\ raminit_test5.c FAIL_TESTS = \ - fail_test1.c + fail_test1.c \ + fail_test2.c \ + fail_test3.c TEST_SRCS:=$(patsubst %, tests/%, $(TESTS)) TEST_ASM:=$(patsubst %.c, tests/%.S, $(TESTS)) @@ -93,10 +95,10 @@ FAIL_OUT:=$(patsubst %.c, tests/%.out, $(FAIL_TESTS)) $(TEST_ASM): %.S: %.c romcc - export ALLOC_CHECK_=2; ./romcc -O -mcpu=k8 -o $@ $< > $*.debug + export ALLOC_CHECK_=2; ./romcc -O2 -mcpu=k8 -o $@ $< > $*.debug $(FAIL_OUT): %.out: %.c romcc - export ALLOC_CHECK_=2; if ./romcc -O -o $*.S $< > $*.debug 2> $@ ; then exit 1 ; else exit 0 ; fi + export ALLOC_CHECK_=2; if ./romcc -O2 -o $*.S $< > $*.debug 2> $@ ; then exit 1 ; else exit 0 ; fi $(TEST_OBJ): %.o: %.S as $< -o $@ diff --git a/util/romcc/romcc.c b/util/romcc/romcc.c index 48632a8fc6..42e06d3498 100644 --- a/util/romcc/romcc.c +++ b/util/romcc/romcc.c @@ -23,7 +23,6 @@ #warning "FIXME boundary cases with small types in larger registers" #warning "FIXME give clear error messages about unused variables" #warning "FIXME properly handle multi dimensional arrays" -#warning "FIXME fix scc_transform" /* Control flow graph of a loop without goto. * @@ -1015,6 +1014,9 @@ static void __internal_warning(struct compile_state *state, struct triple *ptr, va_list args; va_start(args, fmt); loc(stderr, state, ptr); + if (ptr) { + fprintf(stderr, "%p %s ", ptr, tops(ptr->op)); + } fprintf(stderr, "Internal compiler warning: "); vfprintf(stderr, fmt, args); fprintf(stderr, "\n"); @@ -1184,40 +1186,6 @@ static void unuse_triple(struct triple *used, struct triple *unuser) } } -static void push_triple(struct triple *used, struct triple *user) -{ - struct triple_set *new; - if (!used) - return; - if (!user) - return; - /* Append new to the head of the list, - * it's the only sensible behavoir for a stack. - */ - new = xcmalloc(sizeof(*new), "triple_set"); - new->member = user; - new->next = used->use; - used->use = new; -} - -static void pop_triple(struct triple *used, struct triple *unuser) -{ - struct triple_set *use, **ptr; - ptr = &used->use; - while(*ptr) { - use = *ptr; - if (use->member == unuser) { - *ptr = use->next; - xfree(use); - /* Only free one occurance from the stack */ - return; - } - else { - ptr = &use->next; - } - } -} - static void put_occurance(struct occurance *occurance) { occurance->count -= 1; @@ -1827,6 +1795,15 @@ static void release_triple(struct compile_state *state, struct triple *ptr) { struct triple_set *set, *next; struct triple **expr; + struct block *block; + /* Make certain the we are not the first or last element of a block */ + block = block_of_triple(state, ptr); + if (block && (block->last == ptr)) { + block->last = ptr->prev; + } + if (block && (block->first == ptr)) { + block->first = ptr->next; + } /* Remove ptr from use chains where it is the user */ expr = triple_rhs(state, ptr, 0); for(; expr; expr = triple_rhs(state, ptr, expr)) { @@ -4571,7 +4548,7 @@ static struct triple *array_to_pointer(struct compile_state *state, struct tripl type = new_type( TYPE_POINTER | (def->type->type & QUAL_MASK), def->type->left, 0); - if ((def->op == OP_SDECL) || is_const(def)) { + if ((def->op == OP_SDECL) || IS_CONST_OP(def->op)) { struct triple *addrconst; if ((def->op != OP_SDECL) && (def->op != OP_BLOBCONST)) { internal_error(state, def, "bad array constant"); @@ -9586,7 +9563,7 @@ static struct block *basic_block(struct compile_state *state, struct triple *first) { struct block *block; - struct triple *ptr; + struct triple *ptr, *final; int op; if (first->op != OP_LABEL) { internal_error(state, 0, "block does not start with a label"); @@ -9595,6 +9572,11 @@ static struct block *basic_block(struct compile_state *state, if (first->u.block != 0) { return first->u.block; } + /* Lookup the final instruction. + * It is important that the final instruction has it's own + * basic block. + */ + final = RHS(state->main_function, 0)->prev; /* Allocate another basic block structure */ state->last_vertex += 1; block = xcmalloc(sizeof(*block), "block"); @@ -9602,7 +9584,8 @@ static struct block *basic_block(struct compile_state *state, block->vertex = state->last_vertex; ptr = first; do { - if ((ptr != first) && (ptr->op == OP_LABEL) && ptr->use) { + if ((ptr != first) && (ptr->op == OP_LABEL) && + ((ptr->use) || ptr == final)) { break; } block->last = ptr; @@ -10486,10 +10469,10 @@ static void insert_phi_operations(struct compile_state *state) /* Count how many edges flow into this block */ in_edges = front->users; /* Insert a phi function for this variable */ - get_occurance(front->first->occurance); + get_occurance(var->occurance); phi = alloc_triple( state, OP_PHI, var->type, -1, in_edges, - front->first->occurance); + var->occurance); phi->u.block = front; MISC(phi, 0) = var; use_triple(var, phi); @@ -10515,12 +10498,71 @@ static void insert_phi_operations(struct compile_state *state) xfree(work); } + +static int count_and_number_adecls(struct compile_state *state) +{ + struct triple *first, *ins; + int adecls = 0; + first = RHS(state->main_function, 0); + ins = first; + do { + if (ins->op == OP_ADECL) { + adecls += 1; + ins->id = adecls; + } + ins = ins->next; + } while(ins != first); + return adecls; +} + +static struct triple *peek_triple(struct triple_set **stacks, struct triple *var) +{ + struct triple_set *head; + struct triple *top_val; + top_val = 0; + head = stacks[var->id]; + if (head) { + top_val = head->member; + } + return top_val; +} + +static void push_triple(struct triple_set **stacks, struct triple *var, struct triple *val) +{ + struct triple_set *new; + /* Append new to the head of the list, + * it's the only sensible behavoir for a stack. + */ + new = xcmalloc(sizeof(*new), "triple_set"); + new->member = val; + new->next = stacks[var->id]; + stacks[var->id] = new; +} + +static void pop_triple(struct triple_set **stacks, struct triple *var, struct triple *oldval) +{ + struct triple_set *set, **ptr; + ptr = &stacks[var->id]; + while(*ptr) { + set = *ptr; + if (set->member == oldval) { + *ptr = set->next; + xfree(set); + /* Only free one occurance from the stack */ + return; + } + else { + ptr = &set->next; + } + } +} + /* * C(V) * S(V) */ static void fixup_block_phi_variables( - struct compile_state *state, struct block *parent, struct block *block) + struct compile_state *state, struct triple_set **stacks, struct block *parent, struct block *block) { struct block_set *set; struct triple *ptr; @@ -10545,8 +10587,8 @@ static void fixup_block_phi_variables( internal_error(state, ptr, "no var???"); } /* Find the current value of the variable */ - val = var->use->member; - if ((val->op == OP_WRITE) || (val->op == OP_READ)) { + val = peek_triple(stacks, var); + if (val && ((val->op == OP_WRITE) || (val->op == OP_READ))) { internal_error(state, val, "bad value in phi"); } if (edge >= TRIPLE_RHS(ptr->sizes)) { @@ -10567,7 +10609,7 @@ static void fixup_block_phi_variables( static void rename_block_variables( - struct compile_state *state, struct block *block) + struct compile_state *state, struct triple_set **stacks, struct block *block) { struct block_set *user; struct triple *ptr, *next, *last; @@ -10586,11 +10628,11 @@ static void rename_block_variables( struct triple *var, *val; var = RHS(ptr, 0); unuse_triple(var, ptr); - if (!var->use) { + /* Find the current value of the variable */ + val = peek_triple(stacks, var); + if (!val) { error(state, ptr, "variable used without being set"); } - /* Find the current value of the variable */ - val = var->use->member; if ((val->op == OP_WRITE) || (val->op == OP_READ)) { internal_error(state, val, "bad value in read"); } @@ -10623,24 +10665,24 @@ static void rename_block_variables( propogate_use(state, ptr, tval); unuse_triple(var, ptr); /* Push OP_WRITE ptr->right onto a stack of variable uses */ - push_triple(var, tval); + push_triple(stacks, var, tval); } if (ptr->op == OP_PHI) { struct triple *var; var = MISC(ptr, 0); /* Push OP_PHI onto a stack of variable uses */ - push_triple(var, ptr); + push_triple(stacks, var, ptr); } last = ptr; } block->last = last; /* Fixup PHI functions in the cf successors */ - fixup_block_phi_variables(state, block, block->left); - fixup_block_phi_variables(state, block, block->right); + fixup_block_phi_variables(state, stacks, block, block->left); + fixup_block_phi_variables(state, stacks, block, block->right); /* rename variables in the dominated nodes */ for(user = block->idominates; user; user = user->next) { - rename_block_variables(state, user->member); + rename_block_variables(state, stacks, user->member); } /* pop the renamed variable stack */ last = block->first; @@ -10654,7 +10696,7 @@ static void rename_block_variables( struct triple *var; var = RHS(ptr, 0); /* Pop OP_WRITE ptr->right from the stack of variable uses */ - pop_triple(var, RHS(ptr, 1)); + pop_triple(stacks, var, RHS(ptr, 1)); release_triple(state, ptr); continue; } @@ -10662,7 +10704,7 @@ static void rename_block_variables( struct triple *var; var = MISC(ptr, 0); /* Pop OP_WRITE ptr->right from the stack of variable uses */ - pop_triple(var, ptr); + pop_triple(stacks, var, ptr); } last = ptr; } @@ -10708,15 +10750,117 @@ static void prune_block_variables(struct compile_state *state, } } +struct phi_triple { + struct triple *phi; + unsigned orig_id; + int alive; +}; + +static void keep_phi(struct compile_state *state, struct phi_triple *live, struct triple *phi) +{ + struct triple **slot; + int zrhs, i; + if (live[phi->id].alive) { + return; + } + live[phi->id].alive = 1; + zrhs = TRIPLE_RHS(phi->sizes); + slot = &RHS(phi, 0); + for(i = 0; i < zrhs; i++) { + struct triple *used; + used = slot[i]; + if (used && (used->op == OP_PHI)) { + keep_phi(state, live, used); + } + } +} + +static void prune_unused_phis(struct compile_state *state) +{ + struct triple *first, *phi; + struct phi_triple *live; + int phis, i; + + + /* Find the first instruction */ + first = RHS(state->main_function, 0); + + /* Count how many phi functions I need to process */ + phis = 0; + for(phi = first->next; phi != first; phi = phi->next) { + if (phi->op == OP_PHI) { + phis += 1; + } + } + + /* Mark them all dead */ + live = xcmalloc(sizeof(*live) * (phis + 1), "phi_triple"); + phis = 0; + for(phi = first->next; phi != first; phi = phi->next) { + if (phi->op != OP_PHI) { + continue; + } + live[phis].alive = 0; + live[phis].orig_id = phi->id; + live[phis].phi = phi; + phi->id = phis; + phis += 1; + } + + /* Mark phis alive that are used by non phis */ + for(i = 0; i < phis; i++) { + struct triple_set *set; + for(set = live[i].phi->use; !live[i].alive && set; set = set->next) { + if (set->member->op != OP_PHI) { + keep_phi(state, live, live[i].phi); + break; + } + } + } + + /* Delete the extraneous phis */ + for(i = 0; i < phis; i++) { + struct triple **slot; + int zrhs, j; + if (!live[i].alive) { + release_triple(state, live[i].phi); + continue; + } + phi = live[i].phi; + slot = &RHS(phi, 0); + zrhs = TRIPLE_RHS(phi->sizes); + for(j = 0; j < zrhs; j++) { + if(!slot[j]) { + error(state, phi, "variable not set on all paths to use"); + } + } + } + xfree(live); +} + + static void transform_to_ssa_form(struct compile_state *state) { + struct triple_set **stacks; + int adecls; insert_phi_operations(state); #if 0 printf("@%s:%d\n", __FILE__, __LINE__); print_blocks(state, stdout); #endif - rename_block_variables(state, state->first_block); + + /* Allocate stacks for the Variables */ + adecls = count_and_number_adecls(state); + stacks = xcmalloc(sizeof(stacks[0])*(adecls + 1), "adecl stacks"); + rename_block_variables(state, stacks, state->first_block); + xfree(stacks); + prune_block_variables(state, state->first_block); + +#if 1 + prune_unused_phis(state); +#endif + } @@ -11198,6 +11342,15 @@ static void insert_copies_to_phi(struct compile_state *state) unuse_triple(val, phi); use_triple(move, phi); + /* Walk up the dominator tree until I have found the appropriate block */ + while(eblock && !tdominates(state, val, eblock->last)) { + eblock = eblock->idom; + } + if (!eblock) { + internal_error(state, phi, "Cannot find block dominated by %p", + val); + } + /* Walk through the block backwards to find * an appropriate location for the OP_COPY. */ @@ -11589,6 +11742,8 @@ static int count_triples(struct compile_state *state) } while (ins != first); return triples; } + + struct dead_triple { struct triple *triple; struct dead_triple *work_next; @@ -14761,21 +14916,40 @@ static void verify_domination(struct compile_state *state) ins = first; do { for(set = ins->use; set; set = set->next) { - struct triple **expr; - if (set->member->op == OP_PHI) { - continue; - } - /* See if the use is on the righ hand side */ - expr = triple_rhs(state, set->member, 0); - for(; expr ; expr = triple_rhs(state, set->member, expr)) { - if (*expr == ins) { + struct triple **slot; + struct triple *use_point; + int i, zrhs; + use_point = 0; + zrhs = TRIPLE_RHS(ins->sizes); + slot = &RHS(set->member, 0); + /* See if the use is on the right hand side */ + for(i = 0; i < zrhs; i++) { + if (slot[i] == ins) { break; } } - if (expr && - !tdominates(state, ins, set->member)) { - internal_error(state, set->member, - "non dominated rhs use?"); + if (i < zrhs) { + use_point = set->member; + if (set->member->op == OP_PHI) { + struct block_set *bset; + int edge; + bset = set->member->u.block->use; + for(edge = 0; bset && (edge < i); edge++) { + bset = bset->next; + } + if (!bset) { + internal_error(state, set->member, + "no edge for phi rhs %d\n", i); + } + use_point = bset->member->last; + } + } + if (use_point && + !tdominates(state, ins, use_point)) { + internal_warning(state, ins, + "ins does not dominate rhs use"); + internal_error(state, use_point, + "non dominated rhs use point?"); } } ins = ins->next; diff --git a/util/romcc/tests/fail_test2.c b/util/romcc/tests/fail_test2.c new file mode 100644 index 0000000000..74d6eb1d94 --- /dev/null +++ b/util/romcc/tests/fail_test2.c @@ -0,0 +1,18 @@ +static void main(void) +{ + + unsigned min; + int value, latency; + + + latency = -2; + + if (latency > (((min) >> 8) & 0xff)) { + value = 0xa; + } + + if (value < 0) return; + + ((min) = (((min) & ~0xff))); + +} diff --git a/util/romcc/tests/fail_test3.c b/util/romcc/tests/fail_test3.c new file mode 100644 index 0000000000..84822839db --- /dev/null +++ b/util/romcc/tests/fail_test3.c @@ -0,0 +1,10 @@ +static void main(void) +{ + volatile unsigned long *val = (volatile unsigned long *)0x1234; + int i; + if (val[0] > 25) { + i = 7; + } + val[1] = i; + +} diff --git a/util/romcc/tests/simple_test55.c b/util/romcc/tests/simple_test55.c new file mode 100644 index 0000000000..d5cc2e894c --- /dev/null +++ b/util/romcc/tests/simple_test55.c @@ -0,0 +1,24 @@ +static void main(void) +{ + static const int sdivisor = 20; + const int *pdivisor; + unsigned rdpreamble; + unsigned divisor; + pdivisor = &sdivisor; + divisor = *pdivisor; + rdpreamble = 0; + + if (divisor == 20) { + rdpreamble = 18; + } + else { + if (divisor == 15) { + rdpreamble = 16; + } + else { + if (divisor == 12) { + rdpreamble = 15; + } + } + } +} diff --git a/util/romcc/tests/simple_test56.c b/util/romcc/tests/simple_test56.c new file mode 100644 index 0000000000..831ee9a4ca --- /dev/null +++ b/util/romcc/tests/simple_test56.c @@ -0,0 +1,43 @@ + +static void spd_enable_refresh(void) +{ + /* + * Effects: Uses serial presence detect to set the + * refresh rate in the DRAMC register. + * see spd_set_dramc for the other values. + * FIXME: Check for illegal/unsupported ram configurations and abort + */ + static const unsigned char refresh_rates[] = { + 0x01, /* Normal 15.625 us -> 15.6 us */ + 0x05, /* Reduced(.25X) 3.9 us -> 7.8 us */ + 0x05, /* Reduced(.5X) 7.8 us -> 7.8 us */ + 0x02, /* Extended(2x) 31.3 us -> 31.2 us */ + 0x03, /* Extended(4x) 62.5 us -> 62.4 us */ + 0x04, /* Extended(8x) 125 us -> 124.8 us */ + }; + /* Find the first dimm and assume the rest are the same */ + int byte; + unsigned device; + unsigned refresh_rate; + byte = -1; + device = 0x50; + while ((byte < 0) && (device <= 0x57)) { + byte = __builtin_inl(device); + device += 1; + } + if (byte < 0) { + /* We couldn't find anything we must have no memory */ + while(1); + } + byte &= 0x7f; + /* Default refresh rate be conservative */ + refresh_rate = 5; + /* see if the ram refresh is a supported one */ + if (byte < 6) { + refresh_rate = refresh_rates[byte]; + } + byte = __builtin_inb(0x57); + byte &= 0xf8; + byte |= refresh_rate; + __builtin_outb(byte, 0x57); +} -- cgit v1.2.3