diff options
author | Eric Biederman <ebiederm@xmission.com> | 2003-06-16 16:57:34 +0000 |
---|---|---|
committer | Eric Biederman <ebiederm@xmission.com> | 2003-06-16 16:57:34 +0000 |
commit | f96a810f11681ba436b446e9451e02cffcd525f5 (patch) | |
tree | 93564c28ab184dc3fe53f6576de95b2ce1c8e5e6 /util/romcc/romcc.c | |
parent | d3e377a520d6ad5997f2ef7c8fc1b823d6d0e7f2 (diff) |
- Reduce the algorithmic complexity of parts of the register allocator
so the worst case runtime of romcc is much more predictable
git-svn-id: svn://svn.coreboot.org/coreboot/trunk@879 2b7e53f0-3cfb-0310-b3e9-8179ed1497e1
Diffstat (limited to 'util/romcc/romcc.c')
-rw-r--r-- | util/romcc/romcc.c | 298 |
1 files changed, 172 insertions, 126 deletions
diff --git a/util/romcc/romcc.c b/util/romcc/romcc.c index 561ba24110..d0e13e2d2c 100644 --- a/util/romcc/romcc.c +++ b/util/romcc/romcc.c @@ -847,7 +847,11 @@ struct type { #define MAX_REGISTERS 75 #define MAX_REG_EQUIVS 16 +#if 1 +#define REGISTER_BITS 16 +#else #define REGISTER_BITS 28 +#endif #define MAX_VIRT_REGISTERS (1<<REGISTER_BITS) #define TEMPLATE_BITS 6 #define MAX_TEMPLATES (1<<TEMPLATE_BITS) @@ -862,9 +866,22 @@ struct type { #define REG_VIRT5 (MAX_REGISTERS + 5) /* Provision for 8 register classes */ +#if 1 +#define REG_SHIFT 0 +#define REGC_SHIFT REGISTER_BITS +#define REGC_MASK (((1 << MAX_REGC) - 1) << REGISTER_BITS) #define REG_MASK (MAX_VIRT_REGISTERS -1) #define ID_REG(ID) ((ID) & REG_MASK) #define SET_REG(ID, REG) ((ID) = (((ID) & ~REG_MASK) | ((REG) & REG_MASK))) +#define ID_REGCM(ID) (((ID) & REGC_MASK) >> REGC_SHIFT) +#define SET_REGCM(ID, REGCM) ((ID) = (((ID) & ~REGC_MASK) | (((REGCM) << REGC_SHIFT) & REGC_MASK))) +#define SET_INFO(ID, INFO) ((ID) = (((ID) & ~(REG_MASK | REGC_MASK)) | \ + (((INFO).reg) & REG_MASK) | ((((INFO).regcm) << REGC_SHIFT) & REGC_MASK))) +#else +#define REG_MASK (MAX_VIRT_REGISTERS -1) +#define ID_REG(ID) ((ID) & REG_MASK) +#define SET_REG(ID, REG) ((ID) = (((ID) & ~REG_MASK) | ((REG) & REG_MASK))) +#endif static unsigned arch_reg_regcm(struct compile_state *state, int reg); static unsigned arch_regcm_normalize(struct compile_state *state, unsigned regcm); @@ -10843,7 +10860,7 @@ static void free_variable_lifetimes( } -typedef struct triple *(*wvl_cb_t)( +typedef void (*wvl_cb_t)( struct compile_state *state, struct reg_block *blocks, struct triple_reg_set *live, struct reg_block *rb, struct triple *ins, void *arg); @@ -10873,7 +10890,7 @@ static void walk_variable_lifetimes(struct compile_state *state, } /* Walk through the basic block calculating live */ for(done = 0, ptr = block->last; !done; ptr = prev) { - struct triple **expr, *result; + struct triple **expr; prev = ptr->prev; done = (ptr == block->first); @@ -10886,20 +10903,11 @@ static void walk_variable_lifetimes(struct compile_state *state, /* Inform the callback function of what is * going on. */ - result = cb(state, blocks, live, rb, ptr, arg); + cb(state, blocks, live, rb, ptr, arg); /* Remove the current definition from live */ do_triple_unset(&live, ptr); - /* If the current instruction was deleted continue */ - if (!result) { - if (block->last == ptr) { - block->last = prev; - } - continue; - } - - /* Add the current uses to live. * * It is safe to skip phi functions because they do @@ -11769,7 +11777,7 @@ static void initialize_live_ranges( } while(ins != first); } -static struct triple *graph_ins( +static void graph_ins( struct compile_state *state, struct reg_block *blocks, struct triple_reg_set *live, struct reg_block *rb, struct triple *ins, void *arg) @@ -11783,7 +11791,7 @@ static struct triple *graph_ins( * the interference graph. */ if (!triple_is_def(state, ins)) { - return ins; + return; } def = rstate->lrd[ins->id].lr; @@ -11805,11 +11813,11 @@ static struct triple *graph_ins( } add_live_edge(rstate, def, lr); } - return ins; + return; } -static struct triple *print_interference_ins( +static void print_interference_ins( struct compile_state *state, struct reg_block *blocks, struct triple_reg_set *live, struct reg_block *rb, struct triple *ins, void *arg) @@ -11855,7 +11863,7 @@ static struct triple *print_interference_ins( if (triple_is_branch(state, ins)) { printf("\n"); } - return ins; + return; } static int coalesce_live_ranges( @@ -11962,17 +11970,11 @@ static int coalesce_live_ranges( } -struct coalesce_conflict { - struct triple *ins; - int index; -}; -static struct triple *spot_coalesce_conflict(struct compile_state *state, +static void fix_coalesce_conflicts(struct compile_state *state, struct reg_block *blocks, struct triple_reg_set *live, struct reg_block *rb, struct triple *ins, void *arg) { - struct coalesce_conflict *conflict = arg; int zlhs, zrhs, i, j; - int found; /* See if we have a mandatory coalesce operation between * a lhs and a rhs value. If so and the rhs value is also @@ -11980,101 +11982,113 @@ static struct triple *spot_coalesce_conflict(struct compile_state *state, * we would have two definitions in the same live range simultaneously * alive. */ - found = -1; zlhs = TRIPLE_LHS(ins->sizes); if ((zlhs == 0) && triple_is_def(state, ins)) { zlhs = 1; } zrhs = TRIPLE_RHS(ins->sizes); - for(i = 0; (i < zlhs) && (found == -1); i++) { + for(i = 0; i < zlhs; i++) { struct reg_info linfo; linfo = arch_reg_lhs(state, ins, i); if (linfo.reg < MAX_REGISTERS) { continue; } - for(j = 0; (j < zrhs) && (found == -1); j++) { + for(j = 0; j < zrhs; j++) { struct reg_info rinfo; struct triple *rhs; struct triple_reg_set *set; + int found; + found = 0; rinfo = arch_reg_rhs(state, ins, j); if (rinfo.reg != linfo.reg) { continue; } rhs = RHS(ins, j); - for(set = live; set && (found == -1); set = set->next) { + for(set = live; set && !found; set = set->next) { if (set->member == rhs) { - found = j; + found = 1; } } + if (found) { + struct triple *copy; + copy = pre_copy(state, ins, j); + copy->id |= TRIPLE_FLAG_PRE_SPLIT; + } } } - /* Only update conflict if we are the least dominated conflict */ - if ((found != -1) && - (!conflict->ins || tdominates(state, ins, conflict->ins))) { - conflict->ins = ins; - conflict->index = found; - } - return ins; + return; } -static void resolve_coalesce_conflict( - struct compile_state *state, struct coalesce_conflict *conflict) +static void replace_set_use(struct compile_state *state, + struct triple_reg_set *head, struct triple *orig, struct triple *new) { - struct triple *copy; - copy = pre_copy(state, conflict->ins, conflict->index); - copy->id |= TRIPLE_FLAG_PRE_SPLIT; + struct triple_reg_set *set; + for(set = head; set; set = set->next) { + if (set->member == orig) { + set->member = new; + } + } } - -static struct triple *spot_tangle(struct compile_state *state, - struct reg_block *blocks, struct triple_reg_set *live, - struct reg_block *rb, struct triple *ins, void *arg) +static void replace_block_use(struct compile_state *state, + struct reg_block *blocks, struct triple *orig, struct triple *new) { - struct triple **tangle = arg; - char used[MAX_REGISTERS]; - struct triple_reg_set *set; - - /* Find out which registers have multiple uses at this point */ - memset(used, 0, sizeof(used)); - for(set = live; set; set = set->next) { - struct reg_info info; - info = find_lhs_color(state, set->member, 0); - if (info.reg == REG_UNSET) { - continue; - } - reg_inc_used(state, used, info.reg); + int i; +#warning "WISHLIST visit just those blocks that need it *" + for(i = 1; i <= state->last_vertex; i++) { + struct reg_block *rb; + rb = &blocks[i]; + replace_set_use(state, rb->in, orig, new); + replace_set_use(state, rb->out, orig, new); } +} - /* Now find the least dominated definition of a register in - * conflict I have seen so far. - */ - for(set = live; set; set = set->next) { - struct reg_info info; - info = find_lhs_color(state, set->member, 0); - if (used[info.reg] < 2) { - continue; - } - if (!*tangle || tdominates(state, set->member, *tangle)) { - *tangle = set->member; +static void color_instructions(struct compile_state *state) +{ + struct triple *ins, *first; + first = RHS(state->main_function, 0); + ins = first; + do { + if (triple_is_def(state, ins)) { + struct reg_info info; + info = find_lhs_color(state, ins, 0); + if (info.reg >= MAX_REGISTERS) { + info.reg = REG_UNSET; + } + SET_INFO(ins->id, info); } + ins = ins->next; + } while(ins != first); +} + +static struct reg_info read_lhs_color( + struct compile_state *state, struct triple *ins, int index) +{ + struct reg_info info; + if ((index == 0) && triple_is_def(state, ins)) { + info.reg = ID_REG(ins->id); + info.regcm = ID_REGCM(ins->id); } - return ins; + else if (index < TRIPLE_LHS(ins->sizes)) { + info = read_lhs_color(state, LHS(ins, index), 0); + } + else { + internal_error(state, ins, "Bad lhs %d", index); + info.reg = REG_UNSET; + info.regcm = 0; + } + return info; } -static void resolve_tangle(struct compile_state *state, struct triple *tangle) +static struct triple *resolve_tangle( + struct compile_state *state, struct triple *tangle) { struct reg_info info, uinfo; struct triple_set *set, *next; struct triple *copy; -#if 0 - fprintf(stderr, "Resolving tangle: %p\n", tangle); - print_blocks(state, stderr); -#endif +#warning "WISHLIST recalculate all affected instructions colors" info = find_lhs_color(state, tangle, 0); -#if 0 - fprintf(stderr, "color: %d\n", info.reg); -#endif for(set = tangle->use; set; set = next) { struct triple *user; int i, zrhs; @@ -12086,26 +12100,84 @@ static void resolve_tangle(struct compile_state *state, struct triple *tangle) continue; } uinfo = find_rhs_post_color(state, user, i); -#if 0 - fprintf(stderr, "%p rhs %d color: %d\n", - user, i, uinfo.reg); -#endif if (uinfo.reg == info.reg) { copy = pre_copy(state, user, i); copy->id |= TRIPLE_FLAG_PRE_SPLIT; + SET_INFO(copy->id, uinfo); } } } + copy = 0; uinfo = find_lhs_pre_color(state, tangle, 0); -#if 0 - fprintf(stderr, "pre color: %d\n", uinfo.reg); -#endif if (uinfo.reg == info.reg) { + struct reg_info linfo; copy = post_copy(state, tangle); copy->id |= TRIPLE_FLAG_PRE_SPLIT; + linfo = find_lhs_color(state, copy, 0); + SET_INFO(copy->id, linfo); } + info = find_lhs_color(state, tangle, 0); + SET_INFO(tangle->id, info); + + return copy; +} + + +static void fix_tangles(struct compile_state *state, + struct reg_block *blocks, struct triple_reg_set *live, + struct reg_block *rb, struct triple *ins, void *arg) +{ + struct triple *tangle; + do { + char used[MAX_REGISTERS]; + struct triple_reg_set *set; + tangle = 0; + + /* Find out which registers have multiple uses at this point */ + memset(used, 0, sizeof(used)); + for(set = live; set; set = set->next) { + struct reg_info info; + info = read_lhs_color(state, set->member, 0); + if (info.reg == REG_UNSET) { + continue; + } + reg_inc_used(state, used, info.reg); + } + + /* Now find the least dominated definition of a register in + * conflict I have seen so far. + */ + for(set = live; set; set = set->next) { + struct reg_info info; + info = read_lhs_color(state, set->member, 0); + if (used[info.reg] < 2) { + continue; + } + if (!tangle || tdominates(state, set->member, tangle)) { + tangle = set->member; + } + } + /* If I have found a tangle resolve it */ + if (tangle) { + struct triple *post_copy; + post_copy = resolve_tangle(state, tangle); + if (post_copy) { + replace_block_use(state, blocks, tangle, post_copy); + } + if (post_copy && (tangle != ins)) { + replace_set_use(state, live, tangle, post_copy); + } + } + } while(tangle); + return; } +static void correct_tangles( + struct compile_state *state, struct reg_block *blocks) +{ + color_instructions(state); + walk_variable_lifetimes(state, blocks, fix_tangles, 0); +} struct least_conflict { struct reg_state *rstate; @@ -12114,7 +12186,7 @@ struct least_conflict { struct triple_reg_set *live; size_t count; }; -static struct triple *least_conflict(struct compile_state *state, +static void least_conflict(struct compile_state *state, struct reg_block *blocks, struct triple_reg_set *live, struct reg_block *rb, struct triple *ins, void *arg) { @@ -12128,7 +12200,7 @@ static struct triple *least_conflict(struct compile_state *state, * can be the conflict instruction. */ if (!triple_is_def(state, ins)) { - return ins; + return; } /* See if live ranges at this instruction are a @@ -12144,12 +12216,12 @@ static struct triple *least_conflict(struct compile_state *state, } } if (!edge && (lr != conflict->ref_range)) { - return ins; + return; } count++; } if (count <= 1) { - return ins; + return; } /* See if there is an uncolored member in this subset. @@ -12162,7 +12234,7 @@ static struct triple *least_conflict(struct compile_state *state, } } if (!set && (conflict->ref_range != REG_UNSET)) { - return ins; + return; } @@ -12208,7 +12280,7 @@ static struct triple *least_conflict(struct compile_state *state, ; } } - return ins; + return; } static void find_range_conflict(struct compile_state *state, @@ -12975,49 +13047,23 @@ static void allocate_registers(struct compile_state *state) do { struct live_range **point, **next; - struct triple *tangle; - struct coalesce_conflict conflict; int coalesced; /* Restore ids */ ids_from_rstate(state, &rstate); - do { - /* Cleanup the temporary data structures */ - cleanup_rstate(state, &rstate); - - /* Compute the variable lifetimes */ - rstate.blocks = compute_variable_lifetimes(state); + /* Cleanup the temporary data structures */ + cleanup_rstate(state, &rstate); - /* Find an invalid mandatory live range coalesce */ - conflict.ins = 0; - conflict.index = -1; - walk_variable_lifetimes( - state, rstate.blocks, spot_coalesce_conflict, &conflict); - - /* If a tangle was found resolve it */ - if (conflict.ins) { - resolve_coalesce_conflict(state, &conflict); - } - } while(conflict.ins); - - do { - /* Cleanup the temporary data structures */ - cleanup_rstate(state, &rstate); + /* Compute the variable lifetimes */ + rstate.blocks = compute_variable_lifetimes(state); - /* Compute the variable lifetimes */ - rstate.blocks = compute_variable_lifetimes(state); + /* Fix invalid mandatory live range coalesce conflicts */ + walk_variable_lifetimes( + state, rstate.blocks, fix_coalesce_conflicts, 0); - /* Find two simultaneous uses of the same register */ - tangle = 0; - walk_variable_lifetimes( - state, rstate.blocks, spot_tangle, &tangle); - - /* If a tangle was found resolve it */ - if (tangle) { - resolve_tangle(state, tangle); - } - } while(tangle); + /* Fix two simultaneous uses of the same register */ + correct_tangles(state, rstate.blocks); if (state->debug & DEBUG_INSERTED_COPIES) { printf("After resolve_tangles\n"); |