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

   1 #include "obst.h"
   2 #include "pset.h"
   3 #include "irprintf_t.h"
   4 #include "irgraph.h"
   5 #include "irnode.h"
   6 #include "irmode.h"
   7 #include "irgwalk.h"
   8 #include "iredges_t.h"
   9 #include "ircons_t.h"
  10 #include "irprintf.h"
  11
  12 #include "obst.h"
  13 #include "bitset.h"
  14
  15 #include "irprog.h"
  16 #include "irgopt.h"
  17 #include "irdump.h"
  18 #include "phiclass.h"
  19 #include "irdom_t.h"
  20 #include "iredges_t.h"
  21 #include "irloop_t.h"
  22 #include "irtools.h"
  23 #include "return.h"
  24
  25 #include "bearch.h"
  26 #include "firm/bearch_firm.h"
  27 #include "ia32/bearch_ia32.h"
  28 #include "arm/bearch_arm.h"
  29 #include "ppc32/bearch_ppc32.h"
  30 #include "mips/bearch_mips.h"
  31
  32 #include "be_t.h"
  33 #include "benumb_t.h"
  34 #include "beutil.h"
  35 #include "benode_t.h"
  36 #include "beirgmod.h"
  37 #include "besched_t.h"
  38 #include "belistsched.h"
  39 #include "belive_t.h"
  40 #include "bespillilp.h"
  41 #include "bespillbelady.h"
  42 #include "bera.h"
  43 #include "beraextern.h"
  44 #include "bechordal_t.h"
  45 #include "beifg.h"
  46 #include "beifg_impl.h"
  47 #include "becopyopt.h"
  48 #include "becopystat.h"
  49 #include "bessadestr.h"
  50 #include "beabi.h"
  51 #include "belower.h"
  52 #include "bestat.h"
  53 #include "typewalk.h"
  54 #include "error.h"
  55
  56
  57
  58 typedef struct _spilloc_env_t {
  59         struct obstack ob;
  60         pset *ents;
  61         int entcnt;
  62         ir_graph *irg;
  63         pmap *nodents;
  64         pmap *afgraph;
  65 } spilloc_env_t;
  66
  67
  68 typedef struct _vertex {
  69         entity *ent;
  70         int node_nr;
  71         pset *edges;
  72 } vertex;
  73
  74
  75
  76 typedef struct _edge {
  77         entity *ent;
  78         unsigned int wt_val_interfere;
  79         unsigned int wt_con_interfere;
  80         struct edge *next;
  81 } edge;
  82
  83
  84 #define STRUCTSIZE sizeof(vertex)
  85 #define NIL (-1)
  86 #define ABSENT (-2)
  87
  88 static void add_ent(entity *ent, void *env) {
  89         spilloc_env_t *spi = env;
  90         entity *e = obstack_alloc(&spi->ob, sizeof(*e));
  91
  92         e = ent;
  93         pset_insert_ptr(spi->ents, e);
  94         spi->entcnt++;
  95 }
  96
  97 static void data_init(spilloc_env_t *env) {
  98         pset *ps = pset_new_ptr_default();
  99         entity *e;
 100
 101         foreach_pset(env->ents, e) {
 102                 pmap_insert(env->nodents, e, ps);
 103         }
 104 }
 105
 106 static void get_entity_nodes(ir_node *irn, void *env) {
 107         entity *e, *ent;
 108         spilloc_env_t *spi = env;
 109
 110         e = get_irn_entity_attr(irn);
 111         //get_entity_additional_properties();
 112         if (e)
 113         {
 114                 foreach_pset(spi->ents, ent) {
 115
 116                         if ((ent->nr == e->nr) && (ent->ld_name == e->ld_name) )
 117                         {
 118                                 pset *ps = pmap_get(spi->nodents, ent);
 119                                 if (ps && (!pset_find_ptr(pmap_get(spi->nodents, ent),irn))) {
 120                                         pset_insert_ptr(pmap_get(spi->nodents, ent), irn);
 121                                 }
 122                         }
 123                 }
 124         }
 125 }
 126
 127 pset *get_entity_irn(entity *ent, void *env) {
 128         spilloc_env_t *spi = env;
 129
 130         pset *pirn = pmap_get(spi->nodents, ent);
 131         if (pirn)
 132         {
 133                 return pirn;
 134         }
 135         return NULL;
 136 }
 137
 138 int entities_interfere(entity *e1, entity *e2, void *env) {
 139         spilloc_env_t *spi = env;
 140         ir_node *n1, *n2;
 141
 142         pset *pe1 = pmap_get(spi->nodents, e1);
 143         pset *pe2 = pmap_get(spi->nodents, e2);
 144
 145         foreach_pset(pe1, n1) {
 146                 foreach_pset(pe2, n2) {
 147                         if (values_interfere(n1, n2)) return 1;
 148                 }
 149         }
 150         return 0;
 151 }
 152
 153 static void set_aff_graph(void *env) {
 154         spilloc_env_t *spi = env;
 155         entity *e, *cmp;
 156         vertex *v;
 157         int i = 1;
 158
 159         foreach_pset(spi->ents, e) {
 160                 vertex *ver = obstack_alloc(&spi->ob, sizeof(*ver));
 161                 ver->edges = pset_new_ptr_default();
 162                 ver->ent = e;
 163                 ver->node_nr = i;
 164                 pmap_insert(spi->afgraph, e, ver);
 165                 i++;
 166         }
 167
 168         foreach_pset(spi->ents, e) {
 169                 foreach_pset(spi->ents, cmp) {
 170                         if (entities_interfere(e, cmp, &spi) == 1) {
 171                                 v = pmap_get(spi->afgraph, e);
 172                                 pset_insert_ptr(v->edges, cmp);
 173                         }
 174                 }
 175         }
 176 }
 177
 178 void be_spill_loc(const be_chordal_env_t *chordal_env) {
 179
 180         spilloc_env_t spi;
 181
 182         // create initial graph representing data structure
 183         obstack_init(&spi.ob);
 184         spi.ents = pset_new_ptr_default();
 185         spi.entcnt = 0;
 186         spi.irg = chordal_env->irg;
 187         spi.nodents = pmap_create();
 188         spi.afgraph = pmap_create();
 189
 190
 191         /* Walks over all entities in the type */
 192         walk_types_entities(get_irg_frame_type(chordal_env->irg), add_ent, &spi);
 193
 194         data_init(&spi);
 195         irg_walk_blkwise_graph(chordal_env->irg, NULL, get_entity_nodes, &spi);
 196
 197
 198         /*clean*/
 199         del_pset(spi.ents);
 200         pmap_destroy(spi.nodents);
 201         pmap_destroy(spi.afgraph);
 202         obstack_free(&spi.ob, NULL);
 203 }