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 "bespillbelady.h"
  41 #include "bera.h"
  42 #include "beraextern.h"
  43 #include "bechordal_t.h"
  44 #include "beifg.h"
  45 #include "beifg_impl.h"
  46 #include "becopyopt.h"
  47 #include "becopystat.h"
  48 #include "bessadestr.h"
  49 #include "beabi.h"
  50 #include "belower.h"
  51 #include "bestat.h"
  52 #include "typewalk.h"
  53 #include "error.h"
  54
  55
  56
  57 typedef struct _spilloc_env_t {
  58         struct obstack ob;
  59         pset *ents;
  60         int entcnt;
  61         ir_graph *irg;
  62         pmap *nodents;
  63         pmap *afgraph;
  64 } spilloc_env_t;
  65
  66
  67 typedef struct _vertex {
  68         entity *ent;
  69         int node_nr;
  70         pset *edges;
  71 } vertex;
  72
  73
  74
  75 typedef struct _edge {
  76         entity *ent;
  77         unsigned int wt_val_interfere;
  78         unsigned int wt_con_interfere;
  79         struct edge *next;
  80 } edge;
  81
  82
  83 #define STRUCTSIZE sizeof(vertex)
  84 #define NIL (-1)
  85 #define ABSENT (-2)
  86
  87 static void add_ent(entity *ent, void *env) {
  88         spilloc_env_t *spi = env;
  89         entity *e = obstack_alloc(&spi->ob, sizeof(*e));
  90
  91         e = ent;
  92         pset_insert_ptr(spi->ents, e);
  93         spi->entcnt++;
  94 }
  95
  96 static void data_init(spilloc_env_t *env) {
  97         pset *ps = pset_new_ptr_default();
  98         entity *e;
  99
 100         foreach_pset(env->ents, e) {
 101                 pmap_insert(env->nodents, e, ps);
 102         }
 103 }
 104
 105 static void get_entity_nodes(ir_node *irn, void *env) {
 106         entity *e, *ent;
 107         spilloc_env_t *spi = env;
 108
 109         e = get_irn_entity_attr(irn);
 110         //get_entity_additional_properties();
 111         if (e)
 112         {
 113                 foreach_pset(spi->ents, ent) {
 114
 115                         if ((ent->nr == e->nr) && (ent->ld_name == e->ld_name) )
 116                         {
 117                                 pset *ps = pmap_get(spi->nodents, ent);
 118                                 if (ps && (!pset_find_ptr(pmap_get(spi->nodents, ent),irn))) {
 119                                         pset_insert_ptr(pmap_get(spi->nodents, ent), irn);
 120                                 }
 121                         }
 122                 }
 123         }
 124 }
 125
 126 pset *get_entity_irn(entity *ent, void *env) {
 127         spilloc_env_t *spi = env;
 128
 129         pset *pirn = pmap_get(spi->nodents, ent);
 130         if (pirn)
 131         {
 132                 return pirn;
 133         }
 134         return NULL;
 135 }
 136
 137 int entities_interfere(entity *e1, entity *e2, void *env) {
 138         spilloc_env_t *spi = env;
 139         ir_node *n1, *n2;
 140
 141         pset *pe1 = pmap_get(spi->nodents, e1);
 142         pset *pe2 = pmap_get(spi->nodents, e2);
 143
 144         foreach_pset(pe1, n1) {
 145                 foreach_pset(pe2, n2) {
 146                         if (values_interfere(n1, n2)) return 1;
 147                 }
 148         }
 149         return 0;
 150 }
 151
 152 static void set_aff_graph(void *env) {
 153         spilloc_env_t *spi = env;
 154         entity *e, *cmp;
 155         vertex *v;
 156         int i = 1;
 157
 158         foreach_pset(spi->ents, e) {
 159                 vertex *ver = obstack_alloc(&spi->ob, sizeof(*ver));
 160                 ver->edges = pset_new_ptr_default();
 161                 ver->ent = e;
 162                 ver->node_nr = i;
 163                 pmap_insert(spi->afgraph, e, ver);
 164                 i++;
 165         }
 166
 167         foreach_pset(spi->ents, e) {
 168                 foreach_pset(spi->ents, cmp) {
 169                         if (entities_interfere(e, cmp, &spi) == 1) {
 170                                 v = pmap_get(spi->afgraph, e);
 171                                 pset_insert_ptr(v->edges, cmp);
 172                         }
 173                 }
 174         }
 175 }
 176
 177 void be_spill_loc(const be_chordal_env_t *chordal_env) {
 178
 179         spilloc_env_t spi;
 180
 181         // create initial graph representing data structure
 182         obstack_init(&spi.ob);
 183         spi.ents = pset_new_ptr_default();
 184         spi.entcnt = 0;
 185         spi.irg = chordal_env->irg;
 186         spi.nodents = pmap_create();
 187         spi.afgraph = pmap_create();
 188
 189
 190         /* Walks over all entities in the type */
 191         walk_types_entities(get_irg_frame_type(chordal_env->irg), add_ent, &spi);
 192
 193         data_init(&spi);
 194         irg_walk_blkwise_graph(chordal_env->irg, NULL, get_entity_nodes, &spi);
 195
 196
 197         /*clean*/
 198         del_pset(spi.ents);
 199         pmap_destroy(spi.nodents);
 200         pmap_destroy(spi.afgraph);
 201         obstack_free(&spi.ob, NULL);
 202 }