nsz Git - libfirm/blob - ir/be/bespillloc.c

   1 /*      be_spill_loc (ation) -> BY Sven Polk*/
   2 #ifdef HAVE_CONFIG_H
   3 #include "config.h"
   4 #endif
   5
   6 #include "obst.h"
   7 #include "list.h"
   8 #include "bitset.h"
   9 #include "iterator.h"
  10
  11 #include "irmode_t.h"
  12 #include "irgraph_t.h"
  13 #include "irprintf_t.h"
  14 #include "irgwalk.h"
  15 #include "irdump.h"
  16 #include "irdom.h"
  17 #include "debug.h"
  18 #include "xmalloc.h"
  19
  20 #include "beutil.h"
  21 #include "besched.h"
  22 #include "benumb_t.h"
  23 #include "besched_t.h"
  24 #include "belive_t.h"
  25 #include "bechordal_t.h"
  26
  27 #include "obst.h"
  28 #include "set.h"
  29 #include "pdeq.h"
  30 #include "pset.h"
  31 #include "bitset.h"
  32
  33 #include "irprintf_t.h"
  34
  35 #include "irgraph.h"
  36 #include "irnode.h"
  37 #include "irmode.h"
  38 #include "irgwalk.h"
  39 #include "iredges_t.h"
  40 #include "ircons_t.h"
  41 #include "irprintf.h"
  42
  43
  44
  45 #include "irprog.h"
  46 #include "irgopt.h"
  47 #include "irdump.h"
  48 #include "phiclass.h"
  49 #include "irdom_t.h"
  50 #include "iredges_t.h"
  51 #include "irloop_t.h"
  52 #include "irtools.h"
  53 #include "return.h"
  54
  55 #include "bearch_t.h"
  56 #include "firm/bearch_firm.h"
  57 #include "ia32/bearch_ia32.h"
  58 #include "arm/bearch_arm.h"
  59 #include "ppc32/bearch_ppc32.h"
  60 #include "mips/bearch_mips.h"
  61
  62 #include "be_t.h"
  63 #include "benumb_t.h"
  64 #include "beutil.h"
  65 #include "benode_t.h"
  66 #include "beirgmod.h"
  67 #include "besched_t.h"
  68 #include "belistsched.h"
  69 #include "belive_t.h"
  70
  71 #include "bespillbelady.h"
  72 #include "bera.h"
  73 #include "beraextern.h"
  74 #include "bechordal_t.h"
  75 #include "beifg.h"
  76 #include "beifg_impl.h"
  77 #include "becopyopt.h"
  78 #include "becopystat.h"
  79 #include "bessadestr.h"
  80 #include "beabi.h"
  81 #include "belower.h"
  82 #include "bestat.h"
  83
  84 #include "error.h"
  85
  86 #include "irnode_t.h"
  87 #include "entity_t.h"
  88
  89 #include "irprintf.h"
  90
  91 #include "irphase.h"
  92 #include "irphase_t.h"
  93
  94 #include "typewalk.h"
  95
  96 //#include "bespillloc_t.h"
  97 #include "bespillloc.h"
  98
  99 #define LPP_SERVER "i44pc52"
 100 #define LPP_SOLVER "cplex"
 101
 102 // "cat /proc/cpuinfo" cache size : 512 KB => wahrscheinlich L2
 103 // arranged into 32-byte cache lines
 104
 105
 106
 107 #define LINESIZE_BYTES (32)
 108
 109 #define L1SIZE   (64)
 110 #define L2SIZE   (512)
 111
 112 #define L1SIZE_BYTES   (L1SIZE * 1024)
 113 #define L2SIZE_BYTES   (L2SIZE * 1024)
 114
 115 #define L1LINECOUNT (L1SIZE_BYTES / LINESIZE_BYTES)
 116 #define L2LINECOUNT (L2SIZE_BYTES / LINESIZE_BYTES)
 117
 118 #define ASSOCIATIVE   (1)
 119 #define BLOCKFACTOR   (2)
 120 #define CONTEMP_RANGE (10)
 121
 122
 123
 124
 125 typedef struct _spilloc_env_t {
 126
 127         struct obstack ob;
 128
 129         ir_graph                 *irg;
 130         const arch_env_t *arch;
 131
 132         pset *ents;
 133         pset *nodes;
 134         pmap *ent_nodes;
 135
 136         pmap *afgraph;
 137         pset *afgraph_vs;
 138         pset *afgraph_es;
 139
 140         int   ent_cnt;
 141         int   node_cnt;
 142
 143         int   blk_cnt;
 144         int       cli_cnt;
 145
 146         int       intval_cnt;
 147         int       intval[100];
 148
 149         pmap *Cli_ents;
 150         pmap *position;
 151         pset *coals;
 152
 153         pset *chilimbi_Cli_ents;
 154
 155         //lpp_t *lpp;
 156
 157 } spilloc_env_t;
 158
 159
 160
 161 typedef struct _cacheline {
 162         int   start;
 163         int   end;
 164         int   nr;               // (1,...,n)
 165         pset *ents;
 166 } cacheline;
 167
 168
 169
 170 typedef struct _vertex {
 171         entity          *ent;
 172         int                     offset_bits;
 173         int                     offset_bytes;
 174
 175         pset            *neighbors;             /* The neighboring entities */
 176         int         ela;                        /* entity layout affinity */
 177     cacheline   *Cli;
 178         int         is_coal;            /* singled/doubled position */
 179 } vertex;
 180
 181
 182
 183 typedef struct _edge {
 184         entity *src;
 185         entity *tgt;
 186         vertex *vtx_src;
 187         vertex *vtx_tgt;
 188         int     aff;
 189 } edge;
 190
 191
 192
 193 typedef struct _Node { /*Prototype Row of Graph-Matrix*/
 194         vertex *vtx;
 195         pset   *edges;  /*The outgoin' edges of vtx*/
 196         int     status;
 197 } Node;
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209 typedef struct _ent_position {
 210         int                     is_set;
 211         int                     offset;
 212         cacheline       *Cli;
 213         int                     nr;
 214         entity          *ent;
 215 } ent_position;
 216
 217
 218
 219
 220
 221
 222
 223
 224 typedef struct _Coalesce {
 225         entity *ent_1;
 226         entity *ent_2;
 227 } Coalesce;
 228
 229
 230
 231
 232
 233
 234
 235 static void _ents(entity*, void*);
 236 static void _ent_nodes(ir_node*, void*);
 237
 238 static void create_Vertex(void*);
 239 static void create_Edge(entity*, entity*, void*);
 240
 241 int             values_contemp(ir_node*, ir_node*);
 242 int             count_Edge_Affinity(pset*, pset*);
 243
 244 static void     Cli_ents(int, int, int, void*);
 245 static cacheline *create_Cli_ent(struct obstack*);
 246
 247 int             wt(entity*, entity*);
 248 int             get_edge_affinity(entity*, entity*, void*);
 249 int             compute_Entity_Cache_Affinity(entity*, pset*, void*);
 250
 251 void    ir_printf_ent_nodes(void*);
 252 void    ir_printf_ent_nodes_aff(void*) ;
 253
 254 int             Entity_values_interfere(entity*, entity*, void*);
 255 int             Ents_Coalesce (entity*, entity*, void*);
 256 void     Check_Coalesce(void*);
 257
 258 int             delta_configuration_locality(entity*, cacheline*, void*);
 259
 260 int             check_offset(void*);
 261 int             is_filled(pset*, pset*);
 262
 263 entity *min_configuration_locality(cacheline*, void*);
 264 entity *max_configuration_locality(cacheline*, void*);
 265 void    bbcache_REORDER (void*);
 266
 267 int             is_pasteable(entity*, pset*);
 268 entity *MAX_affinity_ents(pset*, pset*, void*);
 269 int             bbcache_CHILIMBI (void*);
 270
 271
 272
 273
 274
 275 static void _ents(entity *_entity, void *env) {
 276         /* GET all ents from stack-frame of the current irg*/
 277
 278         spilloc_env_t *spi = env;
 279         entity *ent = obstack_alloc(&spi->ob, sizeof(*ent));
 280
 281         ent = _entity;
 282         pset_insert_ptr(spi->ents, ent);
 283         spi->ent_cnt++;
 284 }
 285
 286 static void _ent_nodes(ir_node *irn, void *env) {
 287         /* GET ir_node(s) for each found entity */
 288
 289         spilloc_env_t *spi = env;
 290         entity *ir_ent, *ent;
 291         ir_node *node;
 292         pset *nodes;
 293
 294         ir_ent = arch_get_frame_entity(spi->arch, irn);
 295         if (ir_ent)
 296         {
 297                 foreach_pset(spi->ents, ent)
 298                 {
 299                         if(ir_ent == ent)
 300                         {
 301                                 if(!pmap_find(spi->ent_nodes, ent)) {
 302                                         nodes = pset_new_ptr_default();
 303                                         pmap_insert(spi->ent_nodes, ent, nodes);
 304
 305                                 }
 306                                 nodes = pmap_get(spi->ent_nodes, ent);
 307                                 node = obstack_alloc(&spi->ob, sizeof(*node));
 308                                 node = irn;
 309
 310                                 pset_insert_ptr(nodes, node);           /* entity and their ir_node(set)*/
 311
 312                                 pset_insert_ptr(spi->nodes, node);      /* 'only' all ir_node(s)*/
 313
 314                                 spi->node_cnt++;
 315                         }
 316                 }
 317         }
 318 }
 319
 320 static void create_Vertex(void *env) {
 321
 322         spilloc_env_t *spi = env;
 323         entity *ent;
 324         Node *node;
 325
 326
 327         foreach_pset(spi->ents, ent)
 328         {
 329                 /* alloc */
 330
 331                 node   = obstack_alloc(&spi->ob, sizeof(*node));
 332                 node->vtx = obstack_alloc(&spi->ob, sizeof(*(node->vtx)));
 333                 node->edges = pset_new_ptr_default();
 334
 335                 /* init */
 336                 node->vtx->ent                  = ent;
 337                 node->vtx->offset_bits  = 0;
 338                 node->vtx->offset_bytes = 0;
 339                 node->vtx->ela                  = 0;
 340                 node->vtx->neighbors    = pset_new_ptr_default();
 341                 /*
 342                 node->vtx->Cli->end     = 0;
 343                 node->vtx->Cli->start   = 0;
 344                 node->vtx->Cli->nr              = 0;
 345                 node->vtx->Cli->ents   = pset_new_ptr_default();
 346                 */
 347                 node->status                    = 0;
 348
 349                 /* write */
 350                 pmap_insert(spi->afgraph, ent, node);
 351                 pset_insert_ptr(spi->afgraph_vs, node);
 352         }
 353 }
 354
 355 int values_contemp(ir_node *a, ir_node *b) {
 356
 357         /* check, if 2 nodes lying within range */
 358
 359         int i;
 360         ir_node *irn = a;
 361         ir_node *prev;
 362         ir_node *next;
 363         int range = CONTEMP_RANGE;
 364
 365         // backward (until block-border)
 366         for(i = 0; i < range; i++) {
 367                 if(sched_has_prev(irn)) {
 368                         prev = sched_prev(irn);
 369                         if(prev == b) return -1;
 370                         irn = prev;
 371                 }
 372         }
 373
 374         // forward (until block-border)
 375         for(i = 0, irn = a; i < range; i++) {
 376                 if(sched_has_next(irn)) {
 377
 378                         next = sched_next(irn);
 379                         if(next == b) return 1;
 380                         irn = next;
 381                 }
 382         }
 383         return 0;
 384 }
 385
 386 int count_Edge_Affinity(pset *a, pset *b) {
 387
 388         /* count entity *a and entity *b */
 389
 390         ir_node *a_node, *cpy;
 391         pset *copy = pset_new_ptr(pset_count(b));
 392         int cnt=0;
 393
 394         foreach_pset(b, cpy) {pset_insert_ptr(copy, cpy);}
 395         foreach_pset(a, a_node) {
 396                 foreach_pset(copy, cpy) {
 397                          if (values_contemp(a_node, cpy) != 0)
 398                                  cnt++;
 399                 }
 400         }
 401         del_pset(copy);
 402         return cnt;
 403
 404 }
 405
 406 static void create_Edge(entity *a, entity *b, void *env) {
 407
 408         /* create a node in afgraph */
 409
 410         spilloc_env_t *spi = env;
 411
 412         pset *nodes_a,*nodes_b;
 413         int aff;
 414         Node *node;
 415         edge *edg;
 416
 417         nodes_a = ((pset *)pmap_get(spi->ent_nodes, a));
 418         nodes_b = ((pset *)pmap_get(spi->ent_nodes, b));
 419         aff = 0;
 420         if(nodes_a && nodes_b)aff = count_Edge_Affinity(nodes_a, nodes_b);
 421
 422         if(aff != 0)
 423         {
 424                 // alloc
 425                 edg = obstack_alloc(&spi->ob, sizeof(*edg));
 426
 427                 // init
 428                 edg->src = a;
 429                 node = (Node *)pmap_get(spi->afgraph, a);
 430                 edg->vtx_src = node->vtx;
 431                 edg->tgt = b;
 432                 node = (Node *)pmap_get(spi->afgraph, b);
 433                 edg->vtx_tgt = node->vtx;
 434                 edg->aff = aff;
 435
 436                 // write
 437                 node = pmap_get(spi->afgraph, a);
 438                 pset_insert_ptr(node->edges, b);
 439                 node = pmap_get(spi->afgraph, b);
 440                 pset_insert_ptr(node->edges, a);
 441                 pset_insert_ptr(spi->afgraph_es, edg);
 442         }
 443 }
 444
 445 static void Cli_ents(int start, int end, int nr, void *env) {
 446
 447         spilloc_env_t *spi = env;
 448         pset *surrounder = pset_new_ptr_default();
 449         entity *ent;
 450
 451         cacheline *cli;
 452
 453         foreach_pset(spi->ents, ent)
 454         {
 455                         if((start < get_entity_offset_bytes(ent)) && (get_entity_offset_bytes(ent) < end)) {
 456                                 pset_insert_ptr(surrounder, ent);
 457                         }
 458         }
 459
 460         cli = obstack_alloc(&spi->ob, sizeof(*cli));
 461
 462         cli->start      = start;
 463         cli->end        = end;
 464         cli->nr         = nr;
 465         cli->ents       = pset_new_ptr_default();
 466
 467         foreach_pset(surrounder, ent) {pset_insert_ptr(cli->ents,ent);}
 468         pmap_insert(spi->Cli_ents, (void *)nr, cli);
 469         del_pset(surrounder);
 470 }
 471
 472 static cacheline *create_Cli_ent(struct obstack *ob) {
 473
 474         cacheline *cli;
 475
 476         cli = obstack_alloc(ob, sizeof(*cli));
 477
 478         cli->start      = 0;
 479         cli->end        = 0;
 480         cli->nr         = 0;
 481         cli->ents       = pset_new_ptr_default();
 482
 483         return cli;
 484 }
 485
 486
 487
 488
 489
 490
 491 int wt(entity *ent1, entity *ent2) {
 492         /*Relative Distance of 2 Ents == from start to start*/
 493
 494         int o1, o2, cache_blk_size, dist, wt;
 495
 496         o1 = get_entity_offset_bytes(ent1);
 497         o2 = get_entity_offset_bytes(ent2);
 498
 499         if (o1 < o2) {
 500                 ent1->type->size;
 501                 dist = (o2 - o1);
 502         }
 503         if (o1 > o2) dist = (o1 - o2);
 504
 505         cache_blk_size = LINESIZE_BYTES;
 506         wt = ((cache_blk_size - dist) / cache_blk_size);
 507         if(wt != 0) return wt;
 508
 509         // default
 510         return 0;
 511 }
 512
 513 int get_edge_affinity(entity *a, entity *b, pmap *graph) {
 514
 515         Node *node;
 516         edge *edg;
 517
 518         if((pmap_find(graph,a))) {
 519                 node = pmap_get(graph, a);
 520                 foreach_pset(node->edges, edg) {
 521                         if(edg->src == a && edg->tgt == b) {
 522                                 return edg->aff;
 523                         }
 524                 }
 525         }
 526         return 0;
 527 }
 528
 529 int compute_Entity_Cache_Affinity(entity *ent, pset *surrs, void *env) {
 530
 531         spilloc_env_t *spi = env;
 532         entity *sur;
 533         int ela = 0;
 534         int aff = 0;
 535
 536         if(pset_count(surrs) != 0) {
 537                 foreach_pset(surrs, sur)
 538                 {
 539                         aff = get_edge_affinity(ent, sur, spi->afgraph);
 540                         ela += (wt(ent, sur) * aff);
 541                 }
 542         }
 543         return ela;
 544 }
 545
 546
 547 void ir_printf_ent_nodes(void *env) {
 548
 549         spilloc_env_t *spi = env;
 550
 551         entity *ent;
 552         pset *nodes;
 553         ir_node *node;
 554
 555         printf("\n\n\n");
 556         // printf("%c", get_irg_dump_name(spi->irg));
 557
 558         nodes = pset_new_ptr_default();
 559         foreach_pset(spi->ents, ent) {
 560                 printf("\n <%d>",ent->nr);
 561                 nodes = pmap_get(spi->ent_nodes, ent);
 562                 if(nodes) {foreach_pset(nodes, node) {printf(" %d, ", node->node_nr);}}
 563         }
 564 }
 565
 566
 567 void ir_printf_ent_nodes_aff(void *env) {
 568
 569         spilloc_env_t *spi = env;
 570         edge *edg;
 571         entity *ent;
 572         pset *nodes;
 573         ir_node *node;
 574
 575         printf("\n\n\n");
 576
 577         nodes = pset_new_ptr_default();
 578         foreach_pset(spi->afgraph_es, edg) {
 579                 printf("\n <%d-%d> :",edg->src->nr, edg->tgt->nr);
 580                 printf(" %d \n", edg->aff);
 581         }
 582 }
 583
 584 void ir_printf_chilimbi_cachelines(spilloc_env_t env) {
 585
 586         spilloc_env_t spi = env;
 587         cacheline *cline;
 588         entity *ent;
 589         int i=0;
 590
 591         printf("<< ");
 592         foreach_pset(spi.chilimbi_Cli_ents, cline) {
 593                 printf("%d", i);
 594                 foreach_pset(cline->ents, ent)
 595                 {
 596                         printf("%d,", ent->nr);
 597                 }
 598                 i++;
 599         }
 600         printf(" >>\n");
 601 }
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614 int Entity_values_interfere(entity *ent_A, entity *ent_B, void *env) {
 615
 616         spilloc_env_t *spi = env;
 617
 618         ir_node *node_A, *node_B;
 619         pset *nodes_A = pmap_get(spi->ent_nodes, ent_A);
 620         pset *nodes_B = pmap_get(spi->ent_nodes, ent_B);
 621
 622         foreach_pset(nodes_A, node_A) {
 623                 foreach_pset(nodes_B, node_B) {
 624                         if(values_interfere(node_A, node_B)) {
 625                                 return 0;
 626                         }
 627                 }
 628         }
 629         return 1;
 630 }
 631
 632 int Ents_Coalesce (entity *a, entity *b, void *env) {
 633
 634         spilloc_env_t *spi = env;
 635         edge *edg;
 636         Node *aNode,*bNode;
 637
 638                         /* check  (ent,ent)-interfere */
 639
 640         if(Entity_values_interfere(a,b,&spi) == 1) {
 641
 642                 aNode = pmap_get(spi->afgraph, a);
 643                 bNode = pmap_get(spi->afgraph, b);
 644
 645                 if(pset_find_ptr(aNode->edges,b) && pset_find_ptr(bNode->edges,a))
 646                 {
 647
 648                         // find THE EDGE(a,b) - if exists
 649
 650                         pmap_foreach(spi->afgraph_es, edg) {
 651                                 if((edg->src == a || edg->tgt == b) || (edg->src == b || edg->tgt == a)) pmap_break(spi->afgraph_es);
 652                         }
 653                         // (a,b) are coalescable
 654
 655                         if ((edg != NULL) && (edg->aff > 0))
 656                         {
 657                                 return 1;
 658                         }
 659                 }
 660         }
 661                         // (a,b) not coalescable
 662
 663         return 0;
 664
 665 }
 666
 667
 668 void Check_Coalesce(void *env) {
 669
 670         /* return a subset of (ptr_set) = all potential coalescing pairs */
 671
 672         spilloc_env_t *spi = env;
 673         pset *these = pset_new_ptr_default();
 674         pset *those = pset_new_ptr_default();
 675
 676         entity *cpy, *ea, *eb;
 677         Coalesce *coal;
 678
 679         foreach_pset(spi->ents, cpy) {
 680                 pset_insert_ptr(these, cpy);
 681                 pset_insert_ptr(those, cpy);
 682         }
 683
 684         foreach_pset(these, ea) {               /* (ena,enb) */
 685                 foreach_pset(those, eb) {
 686
 687                         if(Ents_Coalesce(ea, eb, &spi) == 1)
 688                         {
 689                                 /* markieren */
 690
 691
 692                                 /* alloc and set new information*/
 693                                 coal = obstack_alloc(&spi->ob, sizeof(*coal));
 694                                 coal->ent_1 = ea;
 695                                 coal->ent_2 = eb;
 696
 697                                 /* sammeln */
 698                                 pset_insert_ptr(spi->coals, coal);
 699                         }
 700                 }
 701         }
 702 }
 703
 704
 705
 706
 707
 708
 709
 710 ir_node *find_phi_ent() {
 711         return NULL;
 712 }
 713
 714 ir_node *looptroop() {
 715         return NULL;
 716 }
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726 int delta_configuration_locality(entity *ent, cacheline *cli_env, void *env) {
 727
 728         spilloc_env_t *spi = env;
 729         cacheline *cli;
 730         Node *node;
 731
 732         cli->ents = pset_new_ptr_default();
 733
 734         // teste ent in allen cachelines ...
 735         pmap_foreach(spi->Cli_ents, cli) {
 736
 737                 /* ausser der gegebenen cacheline(ent)*/
 738                 if(cli != cli_env) {
 739                         node = pmap_get(spi->afgraph, ent);
 740                         //node->vtx->ela = compute_Entity_Cache_Affinity(ent,rel,&spi);
 741                         node->vtx->ela = compute_Entity_Cache_Affinity(ent,(cli->ents),&spi);
 742                 }
 743         }
 744
 745         return 0;
 746 }
 747
 748
 749
 750 int is_pasteable(entity *ent, pset *co) {
 751
 752         /*      RETURNs 1, IF ent could be moved to CACHELine co
 753         */
 754
 755         int align;
 756         int size;
 757         int step,curr_pos,curr_end, etc_pos, etc_end;
 758         entity *etc;
 759
 760         ir_type *stype = get_entity_type(ent);
 761
 762         align = get_type_alignment_bytes(stype);
 763         size  = get_type_size_bytes(stype);
 764
 765         // check all possible alignment-constrainted positions
 766         for(step=0; (step*align) >= LINESIZE_BYTES; step++) {
 767                 curr_pos = (step*align);
 768                 curr_end = curr_pos + size;
 769
 770                 // collision with prev and/or next neighbor
 771                 foreach_pset(co, etc) {
 772                         etc_pos = get_entity_offset_bytes(get_entity_type(etc));
 773                         etc_end = (get_entity_offset_bytes(get_entity_type(etc)) + get_type_size_bytes(get_entity_type(etc)));
 774
 775                         if((etc_end < curr_pos) || (curr_end < etc_pos)) { /* (etc,ent) is OK  */ }
 776                         else if((etc_pos < curr_pos) && (curr_pos < etc_end) && (etc_end < curr_end)) {return 0;}
 777                         else if((curr_pos < etc_pos) && (etc_end < curr_end)) {return 0;}
 778                         else if((etc_pos < curr_pos) && (curr_end < etc_end)) {return 0;}
 779                         else if((curr_pos < etc_pos) && (etc_pos < curr_end) && (etc_end > curr_end)) {return 0;}
 780                 }
 781
 782                 // overlapping to next LINE
 783                 if(get_entity_offset_bytes(ent)+get_type_size_bytes(ent) > LINESIZE_BYTES) {return 0;}
 784         }
 785         return 1;
 786 }
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797 entity *min_configuration_locality(cacheline *cli_env, void *env) {
 798
 799         spilloc_env_t *spi = env;
 800
 801         cacheline *cli = cli_env;
 802         entity *ent,*ret;
 803         Node *node;
 804         float min = 9999;
 805
 806         if(cli->ents == NULL) return NULL;
 807
 808         foreach_pset(cli->ents, ent) {
 809                 node = pmap_get(spi->afgraph, ent);
 810                 if(node->vtx->ela < min) {min = (float)node->vtx->ela; ret = node->vtx->ent;}
 811         }
 812
 813         return ret;
 814 }
 815
 816 void bbcache_REORDER (void *env) {
 817
 818         spilloc_env_t *spi = env;
 819         int  curr_ela, line_nr;
 820         Node *node;
 821         entity *ent,*cpy;
 822         pset *Cli_ents;
 823         pset *ws = pset_new_ptr_default();
 824         pset *copy;
 825         cacheline *cli, *mv2cli;
 826
 827         do{     /* first, find 'some' (= 1 ?) bad for each CACHELINE */
 828                 pmap_foreach(spi->Cli_ents, cli) {
 829
 830                         /* ents(cacheline) holen - jeweils kleinste insert(ws) und remove(cacheline(i) = cli(i)) */
 831
 832                         if(min_configuration_locality(&cli, &spi) != NULL) {
 833
 834                                 ent = min_configuration_locality(&cli, &spi);
 835                                 pset_insert_ptr(ws, ent);                                                               // insert(ws,ent)
 836                                 //pset_remove_ptr(Cli_ents,ent);                                                        // cacheline_remove(i,ent)
 837
 838                         }
 839                 }
 840
 841
 842
 843                 /* second, PASTE them AGAIN hopefully elsewhere*/
 844                 copy=pset_new_ptr(pset_count(ws));
 845                 foreach_pset(ws, ent) {pset_insert_ptr(copy,ent);}
 846
 847                 foreach_pset(copy,cpy){
 848
 849                         node = pmap_get(spi->afgraph,cpy);
 850                         curr_ela = node->vtx->ela;
 851                         mv2cli = NULL;
 852                         line_nr = -1;
 853
 854                         pmap_foreach(spi->Cli_ents, cli) {                                                                      /* for each CACHELINE */
 855                                 if(delta_configuration_locality(cpy, &cli, &spi) > curr_ela){       // condition 1
 856                                         if((is_pasteable(cpy,&cli) != 0)) {                                                         // condition 2
 857
 858                                                 mv2cli = cli;
 859                                                 line_nr = cli->nr;
 860
 861                                         }
 862                                 }
 863                         }
 864
 865                         if((mv2cli != NULL) && (line_nr > 0)) {
 866
 867                                 cli = pmap_get(spi->Cli_ents, line_nr);
 868                                 pset_insert_ptr(cli->ents,cpy);
 869                                 pset_remove_ptr(ws,cpy);
 870
 871                         }
 872                 }
 873
 874                 del_pset(copy);
 875
 876         } while(pset_count(ws) > 0);
 877 }
 878
 879 entity *MAX_affinity_ents(pset *ws, pset *layout_set, spilloc_env_t *env) {
 880
 881         //spilloc_env_t *spi = env;
 882         //pset *layout = pset_new_ptr_default();
 883         entity *ent, *max;
 884         int x = 0;
 885         int y;
 886
 887         //foreach_pset() {layout}
 888
 889         foreach_pset(ws, ent) {
 890
 891                 y = compute_Entity_Cache_Affinity(ent, layout_set, env);
 892
 893                 if(x <= y) {
 894                         max = ent;
 895                         x = y;
 896                 }
 897         }
 898
 899         return max;
 900
 901 }
 902
 903 entity *max_configuration_locality(cacheline *cli_env, void *env) {
 904
 905         spilloc_env_t *spi = env;
 906         cacheline *cli = cli_env;
 907         entity *ent;
 908         Node *node;
 909         float min;
 910         entity *ret;
 911 /*
 912         min = 9999;
 913         if(cli->ents == NULL) return NULL;
 914
 915         foreach_pset(cli->ents, ent) {
 916                 node = pmap_get(spi->afgraph, ent);
 917                 if(node->vtx->ela < min) {min = (float)node->vtx->ela; ret = node->vtx->ent;}
 918         }
 919 */
 920         return ret;
 921 }
 922
 923 int check_offset(void *env) {
 924
 925         spilloc_env_t *spi = env;
 926         pset *cli_ent_set;
 927         entity *ent;
 928         int m,n;
 929
 930         cli_ent_set = pset_new_ptr_default();
 931         if(is_pasteable(ent, cli_ent_set)) return ;
 932
 933         return -1;
 934 }
 935
 936 int is_filled(pset *cli, pset *ws) {
 937
 938         int re = 1;
 939         entity *ent;
 940
 941         foreach_pset(ws, ent) {
 942                 if (is_pasteable(ent, cli)) re = 0;
 943         }
 944
 945         return re;
 946 }
 947
 948 int bbcache_CHILIMBI (void *env) {
 949
 950         spilloc_env_t *spi = env;
 951
 952         entity *ent;
 953         cacheline *cline;
 954         pset *ws;
 955         edge *edg, *max_edge;
 956         entity *max, *last_max;
 957
 958         int o,p,q, x,y,z, i,j,k;
 959
 960
 961
 962                 /* get workset: ws == (spi->ents) */
 963         o = pset_count(spi->ents);
 964         ws = pset_new_ptr(o);
 965         foreach_pset(spi->ents,ent) {pset_insert_ptr(ws,ent);}
 966
 967
 968         do {
 969
 970                 cline = create_Cli_ent(&spi->ob);
 971
 972                 cline->start = 0;
 973                 cline->end   = 0;
 974                 cline->nr    = 0;
 975
 976                 p = 0;
 977
 978                 /*
 979                    (1) start BY: adding the pair of ents
 980                        connected by
 981                            the maxinmum affinity edge
 982                 */
 983
 984
 985                         /* MAX affinity-edge */
 986                 foreach_pset(spi->afgraph_es, edg)
 987                 {
 988
 989                         if((edg->aff > p) && (pset_find_ptr(ws, edg->src)) && (pset_find_ptr(ws, edg->tgt)))
 990                         {
 991                                 p = edg->aff;
 992                                 max_edge = edg;
 993                         }
 994                 }
 995
 996                 o = pset_count(spi->afgraph_es);
 997                 if(o == 0) return -1;
 998
 999                 if(is_pasteable(max_edge->src, cline->ents)) {
1000                         pset_insert_ptr(cline->ents, max_edge->src);
1001                         pset_remove_ptr(ws, max_edge->src);
1002                 }
1003
1004                 if(is_pasteable(max_edge->tgt, cline->ents)) {
1005                         pset_insert_ptr(cline->ents, max_edge->tgt);
1006                         pset_remove_ptr(ws, max_edge->tgt);
1007                 }
1008
1009
1010                 /* (2) A single entity
1011                            is appended to the existing layout,
1012                            the one
1013                            that increases configuration locality
1014                            by the largest amount
1015                 */
1016                 o = pset_count(ws);
1017                 if(o == 0) return -2;
1018
1019                 o = pset_count(cline->ents);
1020                 if(o != 0)
1021                         max = MAX_affinity_ents(ws, (cline->ents), spi);
1022
1023
1024                 if((o != 0) && (max != NULL) ) { // && (max->value != NULL)
1025
1026                         do {
1027
1028                                 last_max = max;
1029
1030                                         // paste to layout set
1031                                 if(is_pasteable(max, cline->ents)) {
1032                                         pset_insert_ptr(cline->ents, max);
1033                                         pset_remove_ptr(ws, max);
1034                                         last_max = NULL;
1035                                 }
1036
1037                                         // get the best-fit'in entity
1038                                 o = pset_count(cline->ents);
1039                                 p = pset_count(ws);
1040                                 if(o != 0 && p != 0)
1041                                         max = MAX_affinity_ents(ws, (cline->ents), spi);
1042
1043                         } while( ((max != last_max) || (last_max != NULL) || (max == NULL)) && (p != 0));
1044
1045                 }
1046
1047                         /* insert one "filled" cacheline */
1048                 pset_insert_ptr(spi->chilimbi_Cli_ents, cline);
1049
1050         } while(ws != NULL && pset_count(ws) > 0);
1051
1052         del_pset(ws);
1053         return 0;
1054 }
1055
1056 void frame_information (spilloc_env_t spi) {
1057
1058         int frame_align;
1059         ir_type *frame;
1060
1061         frame = get_irg_frame_type(spi.irg);
1062         frame_align = get_type_alignment_bytes(frame);
1063
1064 }
1065
1066 void be_spill_loc(const be_chordal_env_t *chordal_env) {
1067
1068         spilloc_env_t spi;
1069         pset *copy;
1070         entity *ent,*cpy;
1071         int max_off, i, start, end;
1072         Node *node;
1073         ent_position *pos;
1074
1075                 /* Init */
1076         obstack_init(&spi.ob);
1077
1078         spi.irg   = chordal_env->irg;
1079         spi.arch          = chordal_env->birg->main_env->arch_env;
1080
1081         spi.ents            = pset_new_ptr_default();
1082         spi.nodes           = pset_new_ptr_default();
1083         spi.ent_nodes   = pmap_create();
1084
1085         spi.ent_cnt     = 0;
1086         spi.node_cnt    = 0;
1087         spi.blk_cnt     = 0;
1088         spi.cli_cnt         = 0;
1089
1090         spi.intval_cnt  = 0;
1091
1092         spi.afgraph         = pmap_create();
1093         spi.afgraph_es  = pset_new_ptr_default();
1094         spi.afgraph_vs  = pset_new_ptr_default();
1095
1096         spi.Cli_ents    = pmap_create();
1097         spi.position    = pmap_create();
1098         spi.coals       = pset_new_ptr_default();
1099
1100         spi.chilimbi_Cli_ents = pset_new_ptr_default();
1101
1102
1103
1104                 /* irg -> {ent}  */
1105         walk_types_entities(get_irg_frame_type(chordal_env->irg), _ents, &spi);
1106         if(spi.ent_cnt != pset_count(spi.ents))
1107                 spi.ent_cnt = pset_count(spi.ents);
1108
1109
1110
1111                 /* ent -> {irn} */
1112         irg_walk_blkwise_graph(chordal_env->irg, NULL, _ent_nodes, &spi);
1113         if(spi.node_cnt != pset_count(spi.nodes))
1114                 spi.ent_cnt = pset_count(spi.ents);
1115
1116
1117                 /* ent -> Node */
1118         create_Vertex(&spi);
1119
1120
1121
1122                 /* (ent,ent) -> edge */
1123         copy = pset_new_ptr(spi.ent_cnt);
1124         foreach_pset(spi.ents, ent)     {pset_insert_ptr(copy,ent);}
1125         foreach_pset(copy, cpy) {
1126                 foreach_pset(spi.ents, ent) {
1127                         if(ent != cpy)
1128                                 create_Edge(ent,cpy,&spi);
1129                 }
1130         }
1131         del_pset(copy);
1132
1133
1134
1135         /* ======================================================================================================*/
1136         /* ======================================================================================================*/
1137         /* ======================================================================================================*/
1138         /* ======================================================================================================*/
1139
1140                                                                                 /* use the dumb offset */
1141
1142         /* ======================================================================================================*/
1143         /* ======================================================================================================*/
1144         /* ======================================================================================================*/
1145         /* ======================================================================================================*/
1146
1147
1148                 /* {ent} -> max_off */
1149         max_off = 0;
1150         foreach_pset(spi.ents, ent) {
1151                 if(get_entity_offset_bytes(ent) > max_off) {max_off = get_entity_offset_bytes(ent);}
1152         }
1153
1154
1155
1156                         /* max_off -> max_cli */
1157         i=1;
1158         while((i * LINESIZE_BYTES) < max_off){
1159                 i++;
1160         }
1161         spi.cli_cnt = i;
1162
1163
1164
1165
1166                 /* {ent} -> {({ent},int), ({ent},int), ({ent},int),...,({ent},int)} */
1167         for(i = 0; i < spi.cli_cnt; i++) {
1168                 start = (i * LINESIZE_BYTES);
1169                 end   = start + LINESIZE_BYTES;
1170                 Cli_ents(start, end, (i + 1), &spi);
1171         }
1172
1173
1174
1175                 /* (ent,{ent}) -> int */
1176
1177         for(i = 1; i <= spi.cli_cnt; i++) {
1178
1179                 cacheline *cline;
1180
1181                 cline = pmap_get(spi.Cli_ents, i);
1182                 if(!cline) break;
1183
1184                 foreach_pset(spi.ents, ent) {
1185                         node = pmap_get(spi.afgraph, ent);
1186                         //node->vtx->ela = compute_Entity_Cache_Affinity(ent,rel,&spi);
1187                         node->vtx->ela = compute_Entity_Cache_Affinity(ent,(cline->ents),&spi);
1188                 }
1189         }
1190
1191
1192         /* ======================================================================================================*/
1193
1194
1195                         /* {ent} -> {ent_position} (INIT) */
1196
1197         foreach_pset(spi.ents, ent) {
1198
1199                 ent_position *epos;
1200
1201                 epos = obstack_alloc(&spi.ob, sizeof(*epos));
1202                 epos->Cli                       = NULL;
1203                 epos->is_set            = 0;
1204                 epos->offset            = 0;
1205                 epos->nr                        = 0;
1206                 epos->ent                       = ent;
1207                 pmap_insert(spi.position,ent,epos);
1208         }
1209
1210                         /* {ent_position->offset} -> {ent_position} (SET) */
1211
1212         foreach_pset(spi.ents, ent) {
1213                 pos = pmap_get(spi.position, ent);
1214                 pos->offset = get_entity_offset_bytes(pos->ent);
1215         }
1216
1217
1218
1219
1220
1221         /* ======================================================================================================*/
1222         /* ======================================================================================================*/
1223         /* ======================================================================================================*/
1224         /* ======================================================================================================*/
1225
1226                                                                                 /* use the initial offset */
1227
1228         /* ======================================================================================================*/
1229         /* ======================================================================================================*/
1230         /* ======================================================================================================*/
1231         /* ======================================================================================================*/
1232
1233
1234
1235
1236
1237
1238
1239
1240                         /* PRINT INFO's */
1241         /*
1242         ir_printf_ent_nodes(&spi);              // <ent->nr>: ir_node->node_nr, ir_node->node_nr ....
1243         ir_printf_ent_nodes_aff(&spi);  // <ent->nr,ent->nr>: affinity
1244         */
1245
1246                 // CHILIMBI => BBCache - algorithm
1247
1248         bbcache_CHILIMBI(&spi);
1249
1250
1251                         /* PRINT INFO's */
1252
1253         ir_printf_chilimbi_cachelines(spi);
1254
1255
1256                 // HIGH affinity  &&  NO values_interfere
1257
1258         //Check_Coalesce(&spi);
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268                         /* CLEAN */
1269
1270         del_pset(spi.ents);
1271         del_pset(spi.nodes);
1272         pmap_destroy(spi.ent_nodes);
1273
1274         pmap_destroy(spi.afgraph);
1275         del_pset(spi.afgraph_es);
1276         del_pset(spi.afgraph_vs);
1277
1278         pmap_destroy(spi.Cli_ents);
1279         pmap_destroy(spi.position);
1280
1281         del_pset(spi.coals);
1282
1283         del_pset(spi.chilimbi_Cli_ents);
1284
1285         obstack_free(&spi.ob, NULL);
1286
1287 }