+int values_contemp(ir_node *a, ir_node *b) {
+
+ /* check, if 2 nodes lying within range */
+
+ int i;
+ ir_node *irn = a;
+ ir_node *prev;
+ ir_node *next;
+ int range = CONTEMP_RANGE;
+
+ // backward (until block-border)
+ for(i = 0; i < range; i++) {
+ if(sched_has_prev(irn)) {
+ prev = sched_prev(irn);
+ if(prev == b) return -1;
+ irn = prev;
+ }
+ }
+
+ // forward (until block-border)
+ for(i = 0, irn = a; i < range; i++) {
+ if(sched_has_next(irn)) {
+
+ next = sched_next(irn);
+ if(next == b) return 1;
+ irn = next;
+ }
+ }
+ return 0;
+}
+
+int count_Edge_Affinity(pset *a, pset *b) {
+
+ /* count entity *a and entity *b */
+
+ ir_node *a_node, *cpy;
+ pset *copy = pset_new_ptr(pset_count(b));
+ int cnt=0;
+
+ foreach_pset(b, cpy) {pset_insert_ptr(copy, cpy);}
+ foreach_pset(a, a_node) {
+ foreach_pset(copy, cpy) {
+ if (values_contemp(a_node, cpy) != 0)
+ cnt++;
+ }
+ }
+ del_pset(copy);
+ return cnt;
+
+}
+
+static void create_Edge(entity *a, entity *b, void *env) {
+
+ /* create a node in afgraph */
+
+ spilloc_env_t *spi = env;
+
+ pset *nodes_a,*nodes_b;
+ int aff;
+ Node *node;
+ edge *edg;
+
+ nodes_a = ((pset *)pmap_get(spi->ent_nodes, a));
+ nodes_b = ((pset *)pmap_get(spi->ent_nodes, b));
+ aff = 0;
+ if(nodes_a && nodes_b)aff = count_Edge_Affinity(nodes_a, nodes_b);
+
+ if(aff != 0)
+ {
+ // alloc
+ edg = obstack_alloc(&spi->ob, sizeof(*edg));
+
+ // init
+ edg->src = a;
+ node = (Node *)pmap_get(spi->afgraph, a);
+ edg->vtx_src = node->vtx;
+ edg->tgt = b;
+ node = (Node *)pmap_get(spi->afgraph, b);
+ edg->vtx_tgt = node->vtx;
+ edg->aff = aff;
+
+ // write
+ node = pmap_get(spi->afgraph, a);
+ pset_insert_ptr(node->edges, b);
+ node = pmap_get(spi->afgraph, b);
+ pset_insert_ptr(node->edges, a);
+ pset_insert_ptr(spi->afgraph_es, edg);
+ }
+}
+
+static void Cli_ents(int start, int end, int nr, void *env) {
+
+ spilloc_env_t *spi = env;
+ pset *surrounder = pset_new_ptr_default();
+ entity *ent;
+
+ cacheline *cli;
+
+ foreach_pset(spi->ents, ent)
+ {
+ if((start < get_entity_offset_bytes(ent)) && (get_entity_offset_bytes(ent) < end)) {
+ pset_insert_ptr(surrounder, ent);
+ }
+ }
+
+ cli = obstack_alloc(&spi->ob, sizeof(*cli));
+
+ cli->start = start;
+ cli->end = end;
+ cli->nr = nr;
+ cli->ents = pset_new_ptr_default();
+
+ foreach_pset(surrounder, ent) {pset_insert_ptr(cli->ents,ent);}
+ pmap_insert(spi->Cli_ents, (void *)nr, cli);
+ del_pset(surrounder);
+}
+
+static cacheline *create_Cli_ent(struct obstack *ob) {
+
+ cacheline *cli;
+
+ cli = obstack_alloc(ob, sizeof(*cli));
+
+ cli->start = 0;
+ cli->end = 0;
+ cli->nr = 0;
+ cli->ents = pset_new_ptr_default();
+
+ return cli;
+}
+
+
+
+
+
+
+int wt(entity *ent1, entity *ent2) {
+ /*Relative Distance of 2 Ents == from start to start*/
+
+ int o1, o2, cache_blk_size, dist, wt;
+
+ o1 = get_entity_offset_bytes(ent1);
+ o2 = get_entity_offset_bytes(ent2);
+
+ if (o1 < o2) {
+ ent1->type->size;
+ dist = (o2 - o1);
+ }
+ if (o1 > o2) dist = (o1 - o2);
+
+ cache_blk_size = LINESIZE_BYTES;
+ wt = ((cache_blk_size - dist) / cache_blk_size);
+ if(wt != 0) return wt;
+
+ // default
+ return 0;
+}
+
+int get_edge_affinity(entity *a, entity *b, pmap *graph) {
+
+ Node *node;
+ edge *edg;
+
+ if((pmap_find(graph,a))) {
+ node = pmap_get(graph, a);
+ foreach_pset(node->edges, edg) {
+ if(edg->src == a && edg->tgt == b) {
+ return edg->aff;
+ }
+ }
+ }
+ return 0;
+}
+
+int compute_Entity_Cache_Affinity(entity *ent, pset *surrs, void *env) {
+
+ spilloc_env_t *spi = env;
+ entity *sur;
+ int ela = 0;
+ int aff = 0;
+
+ if(pset_count(surrs) != 0) {
+ foreach_pset(surrs, sur)
+ {
+ aff = get_edge_affinity(ent, sur, spi->afgraph);
+ ela += (wt(ent, sur) * aff);
+ }
+ }
+ return ela;
+}
+
+
+void ir_printf_ent_nodes(void *env) {
+
+ spilloc_env_t *spi = env;
+
+ entity *ent;
+ pset *nodes;
+ ir_node *node;
+
+ printf("\n\n\n");
+ // printf("%c", get_irg_dump_name(spi->irg));
+
+ nodes = pset_new_ptr_default();
+ foreach_pset(spi->ents, ent) {
+ printf("\n <%d>",ent->nr);
+ nodes = pmap_get(spi->ent_nodes, ent);
+ if(nodes) {foreach_pset(nodes, node) {printf(" %d, ", node->node_nr);}}
+ }
+}
+
+
+void ir_printf_ent_nodes_aff(void *env) {
+
+ spilloc_env_t *spi = env;
+ edge *edg;
+ entity *ent;
+ pset *nodes;
+ ir_node *node;
+
+ printf("\n\n\n");
+
+ nodes = pset_new_ptr_default();
+ foreach_pset(spi->afgraph_es, edg) {
+ printf("\n <%d-%d> :",edg->src->nr, edg->tgt->nr);
+ printf(" %d \n", edg->aff);
+ }
+}
+
+void ir_printf_chilimbi_cachelines(spilloc_env_t env) {
+
+ spilloc_env_t spi = env;
+ cacheline *cline;
+ entity *ent;
+ int i=0;
+
+ printf("<< ");
+ foreach_pset(spi.chilimbi_Cli_ents, cline) {
+ printf("%d", i);
+ foreach_pset(cline->ents, ent)
+ {
+ printf("%d,", ent->nr);
+ }
+ i++;
+ }
+ printf(" >>\n");
+}
+
+
+
+
+
+
+
+
+
+
+
+
+int Entity_values_interfere(entity *ent_A, entity *ent_B, void *env) {
+
+ spilloc_env_t *spi = env;
+
+ ir_node *node_A, *node_B;
+ pset *nodes_A = pmap_get(spi->ent_nodes, ent_A);
+ pset *nodes_B = pmap_get(spi->ent_nodes, ent_B);
+
+ foreach_pset(nodes_A, node_A) {
+ foreach_pset(nodes_B, node_B) {
+ if(values_interfere(node_A, node_B)) {
+ return 0;
+ }
+ }
+ }
+ return 1;
+}
+
+int Ents_Coalesce (entity *a, entity *b, void *env) {
+
+ spilloc_env_t *spi = env;
+ edge *edg;
+ Node *aNode,*bNode;
+
+ /* check (ent,ent)-interfere */
+
+ if(Entity_values_interfere(a,b,&spi) == 1) {
+
+ aNode = pmap_get(spi->afgraph, a);
+ bNode = pmap_get(spi->afgraph, b);
+
+ if(pset_find_ptr(aNode->edges,b) && pset_find_ptr(bNode->edges,a))
+ {
+
+ // 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) {