diff options
Diffstat (limited to 'libbanshee/engine/setst-sort.c')
| -rw-r--r-- | libbanshee/engine/setst-sort.c | 907 |
1 files changed, 907 insertions, 0 deletions
diff --git a/libbanshee/engine/setst-sort.c b/libbanshee/engine/setst-sort.c new file mode 100644 index 00000000000..5d89817ed00 --- /dev/null +++ b/libbanshee/engine/setst-sort.c @@ -0,0 +1,907 @@ +/* + * Copyright (c) 2000-2001 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + */ + +#include <regions.h> +#include <assert.h> +#include <stdio.h> +#include "bounds.h" +#include "setst-sort.h" + + +struct setst_union_ +{ +#ifdef NONSPEC + sort_kind sort; +#endif + int type; + stamp st; + gen_e_list exprs; + gen_e_list proj_cache; +}; + +struct setst_inter_ +{ +#ifdef NONSPEC + sort_kind sort; +#endif + int type; + stamp st; + gen_e_list exprs; +}; + +struct setst_constant_ +{ +#ifdef NONSPEC + sort_kind sort; +#endif + int type; + stamp st; + char *name; +}; + +typedef struct setst_inter_ *setst_inter_; +typedef struct setst_union_ *setst_union_; +typedef struct setst_constant_ *setst_constant_; + +static region tlb_cache_region; +static jcoll_dict tlb_dict; +static setst_var_list setst_vars; +static bool setst_changed = FALSE; + +region setst_region; +term_hash setst_hash; +struct setst_stats setst_stats; + +stamp setst_get_stamp(gen_e e) +{ +#ifdef NONSPEC + assert(e->sort == setst_sort); +#endif + + if ( ((setst_term)e)->type == VAR_TYPE) + return st_get_stamp( (setst_var)e ); + + else + return ((setst_term)e)->st; +} + +static bool eq(gen_e e1, gen_e e2) +{ + return ( setst_get_stamp(e1) == setst_get_stamp(e2) ); +} + +static gen_e_list get_union(gen_e e) +{ + assert ( ((setst_term)e)->type == UNION_TYPE); + + return ( (setst_union_) e)->exprs; +} + +static gen_e_list get_inter(gen_e e) +{ + assert ( ((setst_term)e)->type == INTER_TYPE); + + return ( (setst_inter_) e)->exprs; +} + +static void update_lower_bound(setst_var v, gen_e e) +{ + if (setst_is_var(e)) + { + if (st_add_lb(v,(setst_var)e)) + { + setst_stats.redundant_var++; + } + else + { + setst_stats.added_var++; + setst_changed = TRUE; + } + } + else + { + if (st_add_source(v, e,setst_get_stamp(e))) + { + setst_stats.redundant_source++; + } + else + { + setst_stats.added_source++; + setst_changed = TRUE; + } + } + +} + +static void update_upper_bound(setst_var v, gen_e e) +{ + assert(! setst_is_var(e)); + + if (st_add_sink(v,e,setst_get_stamp(e))) + { + setst_stats.redundant_sink++; + } + else + { + setst_stats.added_sink++; + setst_changed = TRUE; + } +} + + +void setst_inclusion(con_match_fn_ptr con_match,gen_e e1, gen_e e2) +{ + if (eq(e1,e2)) + return; + + else if ( setst_is_zero(e1) || setst_is_one(e2) ) + return; + + else if (setst_is_union(e1)) + { + gen_e_list_scanner scan; + gen_e temp; + + gen_e_list exprs = get_union(e1); + + gen_e_list_scan(exprs,&scan); + while (gen_e_list_next(&scan,&temp)) + { + setst_inclusion(con_match,temp,e2); + } + + return; + } + + else if (setst_is_inter(e2)) + { + gen_e_list_scanner scan; + gen_e temp; + + gen_e_list exprs = get_inter(e2); + + gen_e_list_scan(exprs,&scan); + while (gen_e_list_next(&scan,&temp)) + { + setst_inclusion(con_match,e1,temp); + } + + return; + } + + else if (setst_is_var(e2)) + { + setst_var v = (setst_var)e2; + + update_lower_bound(v,e1); + } + + else if (setst_is_var(e1)) + { + setst_var v = (setst_var)e1; + + update_upper_bound(v,e2); + } + + else con_match(e1,e2); +} + +#ifdef NONSPEC +static struct setst_term zero = {ZERO_TYPE,setst_sort,ZERO_TYPE}; +static struct setst_term one = {ONE_TYPE,setst_sort,ONE_TYPE}; +#else +static struct setst_term zero = {ZERO_TYPE,ZERO_TYPE}; +static struct setst_term one = {ONE_TYPE,ONE_TYPE}; +#endif /* NONSPEC */ + +gen_e setst_zero(void) +{ + return (gen_e)&zero; +} + +gen_e setst_one(void) +{ + return (gen_e)&one; +} + +gen_e setst_fresh(const char *name) +{ + setst_var v = st_fresh(setst_region,name); + setst_var_list_cons(v,setst_vars); + return (gen_e)v; +} + +gen_e setst_fresh_large(const char *name) +{ + setst_var v = st_fresh_large(setst_region,name); + setst_var_list_cons(v,setst_vars); + return (gen_e)v; +} + +gen_e setst_fresh_small(const char *name) +{ + setst_var v = st_fresh_small(setst_region,name); + setst_var_list_cons(v,setst_vars); + return (gen_e)v; +} + +gen_e setst_constant(const char *str) deletes +{ + stamp st[2]; + gen_e result; + char *name = rstrdup(setst_region,str); + + assert (str != NULL); + + st[0] = CONSTANT_TYPE; + st[1] = stamp_string(name); + + if ( (result = term_hash_find(setst_hash,st,2)) == NULL) + { + setst_constant_ c = ralloc(setst_region, struct setst_constant_); + c->type = CONSTANT_TYPE; + c->st = stamp_fresh(); + c->name = name; + + result = (gen_e) c; + term_hash_insert(setst_hash,result,st,2); + + setst_stats.distinct_constants++; + + return result; + } + + else + { + setst_stats.hashed_constants++; + return result; + } +} + +static bool filter_zero(const gen_e e) +{ + return (!setst_is_zero(e)); +} + + +static bool filter_one(const gen_e e) +{ + return (!setst_is_one(e)); +} + +gen_e setst_union(gen_e_list exprs) deletes +{ + gen_e_list filtered = gen_e_list_filter(setst_region,exprs,filter_zero); + + if ( gen_e_list_empty(filtered) ) + { + setst_stats.filtered_unions++; + return setst_zero(); + } + else if (gen_e_list_length(filtered) == 1) + { + setst_stats.filtered_unions++; + return gen_e_list_head(filtered); + } + + else + { + int i = 0; + gen_e temp,result; + gen_e_list_scanner scan; + stamp st[ gen_e_list_length(filtered) + 1 ]; + + st[0] = UNION_TYPE; + + gen_e_list_scan(filtered,&scan); + while (gen_e_list_next(&scan,&temp)) + { + st[++i] = setst_get_stamp(temp); + } + + if ( (result = + term_hash_find(setst_hash,st,gen_e_list_length(filtered)+1)) + == NULL ) + { + struct setst_union_ *u = ralloc(setst_region,struct setst_union_); + + u->type = UNION_TYPE; + u->st = stamp_fresh(); + u->proj_cache = new_gen_e_list(setst_region); + u->exprs = filtered; + + result = (gen_e)u; + term_hash_insert(setst_hash,result,st,gen_e_list_length(filtered)+1); + + setst_stats.distinct_unions++; + return result; + } + else + { + setst_stats.hashed_unions++; + return result; + } + } +} + +gen_e setst_inter(gen_e_list exprs) deletes +{ + gen_e_list filtered = gen_e_list_filter(setst_region,exprs,filter_one); + + if ( gen_e_list_empty(filtered) ) + { + setst_stats.filtered_intersections++; + return setst_one(); + } + else if (gen_e_list_length(filtered) == 1) + { + setst_stats.filtered_intersections++; + return gen_e_list_head(filtered); + } + + else + { + int i = 0; + gen_e temp,result; + gen_e_list_scanner scan; + stamp st[ gen_e_list_length(filtered) + 1 ]; + + st[0] = INTER_TYPE; + + gen_e_list_scan(filtered,&scan); + while (gen_e_list_next(&scan,&temp)) + { + st[++i] = setst_get_stamp(temp); + } + + if ( (result = + term_hash_find(setst_hash,st,gen_e_list_length(filtered)+1)) + == NULL ) + { + struct setst_inter_ *u = ralloc(setst_region,struct setst_inter_); + + u->type = UNION_TYPE; + u->st = stamp_fresh(); + u->exprs = filtered; + + result = (gen_e)u; + term_hash_insert(setst_hash,result,st,gen_e_list_length(filtered)+1); + + setst_stats.distinct_intersections++; + + return result; + } + else + { + setst_stats.hashed_intersections++; + return result; + } + } +} + + +gen_e_list setst_get_union(gen_e e) +{ + assert (((setst_term)e)->type == UNION_TYPE); + + return ((setst_union_)e)->exprs; +} + + +gen_e_list setst_get_inter(gen_e e) +{ + assert (((setst_term)e)->type == INTER_TYPE); + + return ((setst_inter_)e)->exprs; +} + +static void invalidate_tlb_cache(void) +{ + assert(tlb_cache_region); + + jcoll_delete_dict(tlb_dict); + setst_var_list_app(setst_vars,st_clear_tlb_cache); + deleteregion_ptr(&tlb_cache_region); + + tlb_cache_region = newregion(); + tlb_dict = jcoll_create_dict(tlb_cache_region,setst_get_stamp); +} + +static void set_tlb_cache(setst_var v,jcoll j) +{ + st_set_tlb_cache(v,j); +} + +static void collect_sinks(bounds b,setst_var v) +{ + gen_e sink; + gen_e_list_scanner scan; + + gen_e_list_scan(st_get_sinks(v),&scan); + + while (gen_e_list_next(&scan,&sink)) + { + bounds_add(b,sink,setst_get_stamp(sink)); + } +} + +static void collect_sources(bounds b, setst_var v) +{ + gen_e source; + gen_e_list_scanner scan; + + gen_e_list_scan(st_get_sources(v),&scan); + + while (gen_e_list_next(&scan,&source)) + { + bounds_add(b,source,setst_get_stamp(source)); + } +} + +static void collect_lower_bounds(bounds b, setst_var v) +{ + setst_var lb; + setst_var_list_scanner scan; + + setst_var_list_scan(st_get_lbs(v),&scan); + + while (setst_var_list_next(&scan,&lb)) + { + bounds_add(b,(gen_e)lb,st_get_stamp(lb)); + } +} + +static void apply_sources(setst_var witness, bounds sources) +{ + gen_e source; + gen_e_list_scanner scan; + + gen_e_list_scan(bounds_exprs(sources),&scan); + + while (gen_e_list_next(&scan,&source)) + { + if ( st_add_source(witness,source,setst_get_stamp(source))) + setst_stats.redundant_source++; + + else + setst_stats.added_source++; + } +} + +static void apply_sinks(setst_var witness, bounds sinks) +{ + gen_e sink; + gen_e_list_scanner scan; + + gen_e_list_scan(bounds_exprs(sinks),&scan); + + while (gen_e_list_next(&scan,&sink)) + { + if (st_add_sink(witness,sink,setst_get_stamp(sink))) + setst_stats.redundant_sink++; + + else + setst_stats.added_sink++; + } +} + +static void apply_lower_bounds(setst_var witness,bounds lower) +{ + gen_e lb; + gen_e_list_scanner scan; + + gen_e_list_scan(bounds_exprs(lower),&scan); + + while (gen_e_list_next(&scan,&lb)) + { + if (st_add_lb(witness,(setst_var)lb)) + setst_stats.redundant_var++; + else + setst_stats.added_var++; + } +} + +static void collapse_cycle(setst_var witness, setst_var_list cycle) deletes +{ + setst_var_list_scanner var_scan; + setst_var temp; + region scratch_rgn = newregion(); + + bounds sources = bounds_create(scratch_rgn); + bounds sinks = bounds_create(scratch_rgn); + bounds lower = bounds_create(scratch_rgn); + + + setst_stats.cycles_collapsed++; + + /* force at least another iteration */ + setst_changed = TRUE; + + /* collect all bounds */ + setst_var_list_scan(cycle,&var_scan); + while (setst_var_list_next(&var_scan,&temp)) + { + collect_sources(sources,temp); + collect_sinks(sinks,temp); + collect_lower_bounds(lower,temp); + } + + /* unify all vars */ + st_unify(witness,cycle); + + /* add all bounds back */ + apply_sources(witness,sources); + apply_sinks(witness,sinks); + apply_lower_bounds(witness,lower); + + /* cleanup */ + bounds_delete(sources); + bounds_delete(sinks); + bounds_delete(lower); + deleteregion(scratch_rgn); + + /* remove self edges */ + st_repair_bounds(witness); +} +/* +static bool cycle_detect(setst_var goal, setst_var_list path, + setst_var_list *result) +{ + int pos = st_get_path_pos(goal); + setst_stats.cycles_searched++; + + if (pos) + { + setst_var_list_scanner scan; + setst_var temp; + setst_var_list cycle = new_setst_var_list(tlb_cache_region); + + setst_var_list_scan(path,&scan); + while(setst_var_list_next(&scan,&temp)) + { + if (st_get_path_pos(temp) >= pos) + setst_var_list_cons(temp,cycle); + } + + *result = cycle; + return TRUE; + } + + else + return FALSE; +} + +*/ +static bool cycle_detect(setst_var goal, setst_var_list path, + setst_var_list *result) +{ + setst_var_list cycle = + setst_var_list_reverse(setst_var_list_copy(tlb_cache_region,path)); + + setst_stats.cycles_searched++; + + while (!setst_var_list_empty(cycle) && + !eq((gen_e)setst_var_list_head(cycle),(gen_e)goal)) + { + setst_var_list_tail(cycle); + } + + if (setst_var_list_empty(cycle)) + { + return FALSE; + } + else + { + *result = cycle; + return TRUE; + } +} + +static jcoll tlb_aux(gen_e e,int path_len,setst_var_list path) deletes +{ + if (setst_is_var(e)) + { + setst_var_list cycle; + setst_var v = (setst_var)e; + if ( cycle_detect(v,path,&cycle) ) + { + setst_stats.cycles_length += setst_var_list_length(cycle); + collapse_cycle(v,cycle); + return NULL; + } + else + { + if (st_get_tlb_cache(v) != NULL) + return st_get_tlb_cache(v); + else + { + jcoll result; + setst_var_list_scanner scan; + setst_var lb; + jcoll_list jvars = new_jcoll_list(tlb_cache_region); + + gen_e_list sources = gen_e_list_copy(tlb_cache_region, + st_get_sources(v)); + + st_set_path_pos(v,path_len); + setst_var_list_scan(st_get_lbs(v),&scan); + while (setst_var_list_next(&scan,&lb)) + { + setst_var_list_cons(v,path); + jcoll_list_cons(tlb_aux((gen_e)lb,++path_len,path), + jvars); + setst_var_list_tail(path); + } + + if (! gen_e_list_empty(sources)) + jcoll_list_cons(jcoll_create_chain(tlb_dict,sources), + jvars); + result = jcoll_jjoin(tlb_dict,jvars); + set_tlb_cache(v,result); + st_set_path_pos(v,0); + return result; + } + + } + } + else if (setst_is_union(e)) + { + gen_e_list_scanner scan; + gen_e temp; + jcoll_list jexprs = new_jcoll_list(tlb_cache_region); + + gen_e_list_scan(setst_get_union(e),&scan); + while (gen_e_list_next(&scan,&temp)) + { + jcoll_list_cons(tlb_aux(temp,++path_len,path),jexprs); + } + + return jcoll_jjoin(tlb_dict,jexprs); + } + else + { + fail("Unmatched case in setst tlb computation\n"); + return NULL; + } +} +static gen_e_list tlb(gen_e e) +{ + return jcoll_flatten(tlb_dict, + tlb_aux(e,1,new_setst_var_list(tlb_cache_region)) ); +} +static void match_sinks(incl_fn_ptr setst_incl) +{ + gen_e_list_scanner tlb_scanner, sink_scanner; + setst_var_list_scanner var_scanner; + setst_var v; + gen_e lb, sink; + + setst_var_list_scan(setst_vars,&var_scanner); + + while (setst_var_list_next(&var_scanner,&v)) + { + gen_e_list tlbs = tlb((gen_e)v); + gen_e_list snks = st_get_sinks(v); + + + if(gen_e_list_empty(st_get_sinks(v))) + { + setst_stats.no_sinks++; + continue; + } + else if(st_get_seen(v)) + { + setst_stats.incycle_vars++; + continue; + } + else if (gen_e_list_length(tlbs) == st_get_src_sz(v) + && gen_e_list_length(snks) == st_get_snk_sz(v) ) + { + setst_stats.unchanged_vars++; + continue; + } + st_set_seen(v,TRUE); + + st_set_src_sz(v,gen_e_list_length(tlbs)); + st_set_snk_sz(v,gen_e_list_length(snks)); + + gen_e_list_scan(tlbs,&tlb_scanner); + + while (gen_e_list_next(&tlb_scanner,&lb)) + { + gen_e_list_scan(snks,&sink_scanner); + + while (gen_e_list_next(&sink_scanner,&sink)) + setst_incl(lb,sink); + } + } +} +static void iterate(incl_fn_ptr setst_incl) +{ + setst_var_list_scanner var_scanner; + setst_var v; + /* static int iterations = 0; */ + setst_changed = FALSE; + + setst_var_list_scan(setst_vars,&var_scanner); + while (setst_var_list_next(&var_scanner,&v)) + { + st_set_seen(v,FALSE); + } + + invalidate_tlb_cache(); + match_sinks(setst_incl); + + /* fprintf(stderr,"Iterations : %d\n",++iterations); */ + + if (setst_changed) + iterate(setst_incl); +} +gen_e_list setst_tlb(gen_e e,incl_fn_ptr setst_incl) deletes +{ + if (! setst_changed) + { + return tlb(e); + } + else + { + iterate(setst_incl); + return tlb(e); + } + +} + +void setst_set_proj_cache(gen_e e, gen_e elem) +{ + if (setst_is_union(e)) + { + setst_union_ u = (setst_union_)e; + gen_e_list_cons(elem,u->proj_cache); + } +} + +gen_e_list setst_get_proj_cache(gen_e e) +{ + + if (setst_is_union(e)) + { + setst_union_ u = (setst_union_)e; + return u->proj_cache; + } + else + { + fail("Term does not cache projections\n"); + return NULL; + } +} + +void setst_init(void) +{ + setst_region = newregion(); + tlb_cache_region = newregion(); + setst_hash = make_term_hash(setst_region); + setst_vars = new_setst_var_list(setst_region); + tlb_dict = jcoll_create_dict(tlb_cache_region,setst_get_stamp); +} + +void setst_reset(void) deletes +{ + term_hash_delete(setst_hash); + deleteregion_ptr(&setst_region); + + setst_region = newregion(); + setst_hash = make_term_hash(setst_region); + setst_vars = new_setst_var_list(setst_region); + invalidate_tlb_cache(); + setst_changed = FALSE; +} + +bool setst_is_zero(gen_e e) +{ + return ((setst_term)e)->type == ZERO_TYPE; +} + +bool setst_is_one(gen_e e) +{ + return ((setst_term)e)->type == ONE_TYPE; +} + +bool setst_is_var(gen_e e) +{ + return ((setst_term)e)->type == VAR_TYPE; +} + +bool setst_is_union(gen_e e) +{ + return ((setst_term)e)->type == UNION_TYPE; +} + +bool setst_is_inter(gen_e e) +{ + return ((setst_term)e)->type == INTER_TYPE; +} + +char *setst_get_constant_name(gen_e e) +{ + assert( ((setst_term)e)->type == CONSTANT_TYPE ); + + return ((setst_constant_)e)->name; +} + +void setst_print_stats(FILE *f) +{ + fprintf(f,"\n========== SetST Var Stats ==========\n"); + fprintf(f,"Fresh : %d\n",setst_stats.fresh); + fprintf(f,"Fresh Small : %d\n",setst_stats.fresh_small); + fprintf(f,"Fresh Large : %d\n",setst_stats.fresh_large); + fprintf(f,"Total : %d\n",setst_stats.fresh + setst_stats.fresh_small + + setst_stats.fresh_large); + fprintf(f,"\n========== SetST Sort Stats ==========\n"); + fprintf(f,"\n"); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Additions"); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Var: %d\n",setst_stats.added_var); + fprintf(f,"Source: %d\n",setst_stats.added_source); + fprintf(f,"Sink: %d",setst_stats.added_sink); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Total: %d",setst_stats.added_var + setst_stats.added_source + + setst_stats.added_sink); + fprintf(f,"\n"); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Redundant"); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Var: %d\n",setst_stats.redundant_var); + fprintf(f,"Source: %d\n",setst_stats.redundant_source); + fprintf(f,"Sink: %d",setst_stats.redundant_sink); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Total: %d\n", + setst_stats.redundant_var + setst_stats.redundant_source + + setst_stats.redundant_sink); + + fprintf(f,"\n"); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Iteration Optimizations"); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Skipped vars: %d\n",setst_stats.incycle_vars); + fprintf(f,"Unchanged vars: %d\n",setst_stats.unchanged_vars); + fprintf(f,"Vars w/o sinks: %d\n",setst_stats.no_sinks); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Cycles"); + fprintf(f,"\n------------------------------\n"); + fprintf(f,"Collapsed: %d\n",setst_stats.cycles_collapsed); + fprintf(f,"Searched: %d\n",setst_stats.cycles_searched); + fprintf(f,"Hit rate: %f\n", + ((float)setst_stats.cycles_collapsed)/((float)setst_stats.cycles_searched)); + fprintf(f,"Average Length: %f\n", + ((float)setst_stats.cycles_length) / ((float)setst_stats.cycles_collapsed)); + fprintf(f,"=====================================\n"); +} + |