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

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