+ // find THE EDGE(a,b) - if exists
+
+ pmap_foreach(spi->afgraph_es, edg) {
+ if((edg->src == a || edg->tgt == b) || (edg->src == b || edg->tgt == a)) pmap_break(spi->afgraph_es);
+ }
+ // (a,b) are coalescable
+
+ if ((edg != NULL) && (edg->aff > 0))
+ {
+ return 1;
+ }
+ }
+ }
+ // (a,b) not coalescable
+
+ return 0;
+
+}
+
+
+void Check_Coalesce(void *env) {
+
+ /* return a subset of (ptr_set) = all potential coalescing pairs */
+
+ spilloc_env_t *spi = env;
+ pset *these = pset_new_ptr_default();
+ pset *those = pset_new_ptr_default();
+
+ entity *cpy, *ea, *eb;
+ Coalesce *coal;
+
+ foreach_pset(spi->ents, cpy) {
+ pset_insert_ptr(these, cpy);
+ pset_insert_ptr(those, cpy);
+ }
+
+ foreach_pset(these, ea) { /* (ena,enb) */
+ foreach_pset(those, eb) {
+
+ if(Ents_Coalesce(ea, eb, &spi) == 1)
+ {
+ /* markieren */
+
+
+ /* alloc and set new information*/
+ coal = obstack_alloc(&spi->ob, sizeof(*coal));
+ coal->ent_1 = ea;
+ coal->ent_2 = eb;
+
+ /* sammeln */
+ pset_insert_ptr(spi->coals, coal);
+ }
+ }
+ }
+}
+
+
+
+
+
+
+
+ir_node *find_phi_ent() {
+ return NULL;
+}
+
+ir_node *looptroop() {
+ return NULL;
+}
+
+
+
+
+
+
+
+
+
+int delta_configuration_locality(entity *ent, cacheline *cli_env, void *env) {
+
+ spilloc_env_t *spi = env;
+ cacheline *cli;
+ Node *node;
+
+ cli->ents = pset_new_ptr_default();
+
+ // teste ent in allen cachelines ...
+ pmap_foreach(spi->Cli_ents, cli) {
+
+ /* ausser der gegebenen cacheline(ent)*/
+ if(cli != cli_env) {
+ node = pmap_get(spi->afgraph, ent);
+ //node->vtx->ela = compute_Entity_Cache_Affinity(ent,rel,&spi);
+ node->vtx->ela = compute_Entity_Cache_Affinity(ent,(cli->ents),&spi);
+ }
+ }
+
+ return 0;
+}
+
+
+
+int is_pasteable(entity *ent, pset *co) {
+
+ /* RETURNs 1, IF ent could be moved to CACHELine co
+ */
+
+ int align;
+ int size;
+ int step,curr_pos,curr_end, etc_pos, etc_end;
+ entity *etc;
+
+ ir_type *stype = get_entity_type(ent);
+
+ align = get_type_alignment_bytes(stype);
+ size = get_type_size_bytes(stype);
+
+ // check all possible alignment-constrainted positions
+ for(step=0; (step*align) >= LINESIZE_BYTES; step++) {
+ curr_pos = (step*align);
+ curr_end = curr_pos + size;
+
+ // collision with prev and/or next neighbor
+ foreach_pset(co, etc) {
+ etc_pos = get_entity_offset_bytes(get_entity_type(etc));
+ etc_end = (get_entity_offset_bytes(get_entity_type(etc)) + get_type_size_bytes(get_entity_type(etc)));
+
+ if((etc_end < curr_pos) || (curr_end < etc_pos)) { /* (etc,ent) is OK */ }
+ else if((etc_pos < curr_pos) && (curr_pos < etc_end) && (etc_end < curr_end)) {return 0;}
+ else if((curr_pos < etc_pos) && (etc_end < curr_end)) {return 0;}
+ else if((etc_pos < curr_pos) && (curr_end < etc_end)) {return 0;}
+ else if((curr_pos < etc_pos) && (etc_pos < curr_end) && (etc_end > curr_end)) {return 0;}
+ }
+
+ // overlapping to next LINE
+ if(get_entity_offset_bytes(ent)+get_type_size_bytes(ent) > LINESIZE_BYTES) {return 0;}
+ }
+ return 1;
+}
+
+
+
+
+
+
+
+
+
+
+entity *min_configuration_locality(cacheline *cli_env, void *env) {
+
+ spilloc_env_t *spi = env;
+
+ cacheline *cli = cli_env;
+ entity *ent,*ret;
+ Node *node;
+ float min = 9999;
+
+ if(cli->ents == NULL) return NULL;
+
+ foreach_pset(cli->ents, ent) {
+ node = pmap_get(spi->afgraph, ent);
+ if(node->vtx->ela < min) {min = (float)node->vtx->ela; ret = node->vtx->ent;}
+ }
+
+ return ret;
+}
+
+void bbcache_REORDER (void *env) {
+
+ spilloc_env_t *spi = env;
+ int curr_ela, line_nr;
+ Node *node;
+ entity *ent,*cpy;
+ pset *Cli_ents;
+ pset *ws = pset_new_ptr_default();
+ pset *copy;
+ cacheline *cli, *mv2cli;
+
+ do{ /* first, find 'some' (= 1 ?) bad for each CACHELINE */
+ pmap_foreach(spi->Cli_ents, cli) {
+
+ /* ents(cacheline) holen - jeweils kleinste insert(ws) und remove(cacheline(i) = cli(i)) */
+
+ if(min_configuration_locality(&cli, &spi) != NULL) {
+
+ ent = min_configuration_locality(&cli, &spi);
+ pset_insert_ptr(ws, ent); // insert(ws,ent)
+ //pset_remove_ptr(Cli_ents,ent); // cacheline_remove(i,ent)
+
+ }
+ }
+
+
+
+ /* second, PASTE them AGAIN hopefully elsewhere*/
+ copy=pset_new_ptr(pset_count(ws));
+ foreach_pset(ws, ent) {pset_insert_ptr(copy,ent);}
+
+ foreach_pset(copy,cpy){
+
+ node = pmap_get(spi->afgraph,cpy);
+ curr_ela = node->vtx->ela;
+ mv2cli = NULL;
+ line_nr = -1;
+
+ pmap_foreach(spi->Cli_ents, cli) { /* for each CACHELINE */
+ if(delta_configuration_locality(cpy, &cli, &spi) > curr_ela){ // condition 1
+ if((is_pasteable(cpy,&cli) != 0)) { // condition 2
+
+ mv2cli = cli;
+ line_nr = cli->nr;
+
+ }
+ }
+ }
+
+ if((mv2cli != NULL) && (line_nr > 0)) {
+
+ cli = pmap_get(spi->Cli_ents, line_nr);
+ pset_insert_ptr(cli->ents,cpy);
+ pset_remove_ptr(ws,cpy);
+
+ }
+ }
+
+ del_pset(copy);
+
+ } while(pset_count(ws) > 0);
+}
+
+entity *MAX_affinity_ents(pset *ws, pset *layout_set, spilloc_env_t *env) {
+
+ //spilloc_env_t *spi = env;
+ //pset *layout = pset_new_ptr_default();
+ entity *ent, *max;
+ int x = 0;
+ int y;
+
+ //foreach_pset() {layout}
+
+ foreach_pset(ws, ent) {
+
+ y = compute_Entity_Cache_Affinity(ent, layout_set, env);
+
+ if(x <= y) {
+ max = ent;
+ x = y;
+ }
+ }
+
+ return max;
+
+}
+
+entity *max_configuration_locality(cacheline *cli_env, void *env) {
+
+ spilloc_env_t *spi = env;
+ cacheline *cli = cli_env;
+ entity *ent;
+ Node *node;
+ float min;
+ entity *ret;
+/*
+ min = 9999;
+ if(cli->ents == NULL) return NULL;
+
+ foreach_pset(cli->ents, ent) {
+ node = pmap_get(spi->afgraph, ent);
+ if(node->vtx->ela < min) {min = (float)node->vtx->ela; ret = node->vtx->ent;}
+ }
+*/
+ return ret;
+}
+
+int check_offset(void *env) {
+
+ spilloc_env_t *spi = env;
+ pset *cli_ent_set;
+ entity *ent;
+ int m,n;
+
+ cli_ent_set = pset_new_ptr_default();
+ if(is_pasteable(ent, cli_ent_set)) return ;
+
+ return -1;
+}
+
+int is_filled(pset *cli, pset *ws) {
+
+ int re = 1;
+ entity *ent;
+
+ foreach_pset(ws, ent) {
+ if (is_pasteable(ent, cli)) re = 0;
+ }
+
+ return re;
+}
+
+int bbcache_CHILIMBI (void *env) {
+
+ spilloc_env_t *spi = env;
+
+ entity *ent;
+ cacheline *cline;
+ pset *ws;
+ edge *edg, *max_edge;
+ entity *max, *last_max;
+
+ int o,p,q, x,y,z, i,j,k;
+
+
+
+ /* get workset: ws == (spi->ents) */
+ o = pset_count(spi->ents);
+ ws = pset_new_ptr(o);
+ foreach_pset(spi->ents,ent) {pset_insert_ptr(ws,ent);}
+
+
+ do {
+
+ cline = create_Cli_ent(&spi->ob);
+
+ cline->start = 0;
+ cline->end = 0;
+ cline->nr = 0;
+
+ p = 0;
+
+ /*
+ (1) start BY: adding the pair of ents
+ connected by
+ the maxinmum affinity edge
+ */
+
+
+ /* MAX affinity-edge */
+ foreach_pset(spi->afgraph_es, edg)
+ {
+
+ if((edg->aff > p) && (pset_find_ptr(ws, edg->src)) && (pset_find_ptr(ws, edg->tgt)))
+ {
+ p = edg->aff;
+ max_edge = edg;
+ }
+ }
+
+ o = pset_count(spi->afgraph_es);
+ if(o == 0) return -1;
+
+ if(is_pasteable(max_edge->src, cline->ents)) {
+ pset_insert_ptr(cline->ents, max_edge->src);
+ pset_remove_ptr(ws, max_edge->src);
+ }
+
+ if(is_pasteable(max_edge->tgt, cline->ents)) {
+ pset_insert_ptr(cline->ents, max_edge->tgt);
+ pset_remove_ptr(ws, max_edge->tgt);
+ }
+
+
+ /* (2) A single entity
+ is appended to the existing layout,
+ the one
+ that increases configuration locality
+ by the largest amount
+ */
+ o = pset_count(ws);
+ if(o == 0) return -2;
+
+ o = pset_count(cline->ents);
+ if(o != 0)
+ max = MAX_affinity_ents(ws, (cline->ents), spi);
+
+
+ if((o != 0) && (max != NULL) ) { // && (max->value != NULL)
+
+ do {
+
+ last_max = max;
+
+ // paste to layout set
+ if(is_pasteable(max, cline->ents)) {
+ pset_insert_ptr(cline->ents, max);
+ pset_remove_ptr(ws, max);
+ last_max = NULL;
+ }
+
+ // get the best-fit'in entity
+ o = pset_count(cline->ents);
+ p = pset_count(ws);
+ if(o != 0 && p != 0)
+ max = MAX_affinity_ents(ws, (cline->ents), spi);
+
+ } while( ((max != last_max) || (last_max != NULL) || (max == NULL)) && (p != 0));
+
+ }
+
+ /* insert one "filled" cacheline */
+ pset_insert_ptr(spi->chilimbi_Cli_ents, cline);
+
+ } while(ws != NULL && pset_count(ws) > 0);
+
+ del_pset(ws);
+ return 0;
+}
+
+void frame_information (spilloc_env_t spi) {
+
+ int frame_align;
+ ir_type *frame;
+
+ frame = get_irg_frame_type(spi.irg);
+ frame_align = get_type_alignment_bytes(frame);
+
+}
+
+void be_spill_loc(const be_chordal_env_t *chordal_env) {
+
+ spilloc_env_t spi;
+ pset *copy;
+ entity *ent,*cpy;
+ int max_off, i, start, end;
+ Node *node;
+ ent_position *pos;
+
+ /* Init */
+ obstack_init(&spi.ob);
+
+ spi.irg = chordal_env->irg;
+ spi.arch = chordal_env->birg->main_env->arch_env;
+
+ spi.ents = pset_new_ptr_default();
+ spi.nodes = pset_new_ptr_default();
+ spi.ent_nodes = pmap_create();
+
+ spi.ent_cnt = 0;
+ spi.node_cnt = 0;
+ spi.blk_cnt = 0;
+ spi.cli_cnt = 0;
+
+ spi.intval_cnt = 0;
+
+ spi.afgraph = pmap_create();
+ spi.afgraph_es = pset_new_ptr_default();
+ spi.afgraph_vs = pset_new_ptr_default();
+
+ spi.Cli_ents = pmap_create();
+ spi.position = pmap_create();
+ spi.coals = pset_new_ptr_default();
+
+ spi.chilimbi_Cli_ents = pset_new_ptr_default();
+
+
+
+ /* irg -> {ent} */
+ walk_types_entities(get_irg_frame_type(chordal_env->irg), _ents, &spi);
+ if(spi.ent_cnt != pset_count(spi.ents))
+ spi.ent_cnt = pset_count(spi.ents);
+
+
+
+ /* ent -> {irn} */
+ irg_walk_blkwise_graph(chordal_env->irg, NULL, _ent_nodes, &spi);
+ if(spi.node_cnt != pset_count(spi.nodes))
+ spi.ent_cnt = pset_count(spi.ents);
+
+
+ /* ent -> Node */
+ create_Vertex(&spi);
+
+
+
+ /* (ent,ent) -> edge */
+ copy = pset_new_ptr(spi.ent_cnt);
+ foreach_pset(spi.ents, ent) {pset_insert_ptr(copy,ent);}
+ foreach_pset(copy, cpy) {
+ foreach_pset(spi.ents, ent) {
+ if(ent != cpy)
+ create_Edge(ent,cpy,&spi);
+ }
+ }
+ del_pset(copy);
+
+
+
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+
+ /* use the dumb offset */
+
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+
+
+ /* {ent} -> max_off */
+ max_off = 0;
+ foreach_pset(spi.ents, ent) {
+ if(get_entity_offset_bytes(ent) > max_off) {max_off = get_entity_offset_bytes(ent);}
+ }
+
+
+
+ /* max_off -> max_cli */
+ i=1;
+ while((i * LINESIZE_BYTES) < max_off){
+ i++;
+ }
+ spi.cli_cnt = i;
+
+
+
+
+ /* {ent} -> {({ent},int), ({ent},int), ({ent},int),...,({ent},int)} */
+ for(i = 0; i < spi.cli_cnt; i++) {
+ start = (i * LINESIZE_BYTES);
+ end = start + LINESIZE_BYTES;
+ Cli_ents(start, end, (i + 1), &spi);
+ }
+
+
+
+ /* (ent,{ent}) -> int */
+
+ for(i = 1; i <= spi.cli_cnt; i++) {
+
+ cacheline *cline;
+
+ cline = pmap_get(spi.Cli_ents, i);
+ if(!cline) break;
+
+ foreach_pset(spi.ents, ent) {
+ node = pmap_get(spi.afgraph, ent);
+ //node->vtx->ela = compute_Entity_Cache_Affinity(ent,rel,&spi);
+ node->vtx->ela = compute_Entity_Cache_Affinity(ent,(cline->ents),&spi);
+ }
+ }
+
+
+ /* ======================================================================================================*/
+
+
+ /* {ent} -> {ent_position} (INIT) */
+
+ foreach_pset(spi.ents, ent) {
+
+ ent_position *epos;
+
+ epos = obstack_alloc(&spi.ob, sizeof(*epos));
+ epos->Cli = NULL;
+ epos->is_set = 0;
+ epos->offset = 0;
+ epos->nr = 0;
+ epos->ent = ent;
+ pmap_insert(spi.position,ent,epos);
+ }
+
+ /* {ent_position->offset} -> {ent_position} (SET) */
+
+ foreach_pset(spi.ents, ent) {
+ pos = pmap_get(spi.position, ent);
+ pos->offset = get_entity_offset_bytes(pos->ent);
+ }
+
+
+
+
+
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+
+ /* use the initial offset */
+
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+ /* ======================================================================================================*/
+
+
+
+
+
+
+
+
+ /* PRINT INFO's */
+ /*
+ ir_printf_ent_nodes(&spi); // <ent->nr>: ir_node->node_nr, ir_node->node_nr ....
+ ir_printf_ent_nodes_aff(&spi); // <ent->nr,ent->nr>: affinity
+ */
+
+ // CHILIMBI => BBCache - algorithm
+
+ bbcache_CHILIMBI(&spi);
+
+
+ /* PRINT INFO's */
+
+ ir_printf_chilimbi_cachelines(spi);
+
+
+ // HIGH affinity && NO values_interfere
+
+ //Check_Coalesce(&spi);
+
+
+
+
+
+
+
+
+
+ /* CLEAN */
+
+ del_pset(spi.ents);
+ del_pset(spi.nodes);
+ pmap_destroy(spi.ent_nodes);
+
+ pmap_destroy(spi.afgraph);
+ del_pset(spi.afgraph_es);
+ del_pset(spi.afgraph_vs);
+
+ pmap_destroy(spi.Cli_ents);
+ pmap_destroy(spi.position);
+
+ del_pset(spi.coals);
+
+ del_pset(spi.chilimbi_Cli_ents);
+
+ obstack_free(&spi.ob, NULL);