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

   1 /**
   2  * @file   beifg_list.c
   3  * @date   18.11.2005
   4  * @author Sebastian Hack
   5  *
   6  * Copyright (C) 2005 Universitaet Karlsruhe
   7  * Released under the GPL
   8  */
   9 #ifdef HAVE_CONFIG_H
  10 #include "config.h"
  11 #endif
  12
  13 #include <stdlib.h>
  14
  15 #include "belive_t.h"
  16 #include "list.h"
  17
  18 #include "irnode_t.h"
  19 #include "irgraph_t.h"
  20 #include "irgwalk.h"
  21 #include "benodesets.h"
  22
  23 #include "be_t.h"
  24 #include "bera.h"
  25 #include "beifg_t.h"
  26 #include "bechordal_t.h"
  27
  28 #define MAX(x, y) ((x) > (y) ? (x) : (y))
  29
  30 typedef struct _ifg_list_t {
  31         const be_ifg_impl_t *impl;
  32         const be_chordal_env_t *env;
  33         struct obstack obst;
  34         pmap *list_map;
  35 } ifg_list_t;
  36
  37 typedef struct _list_element_t {
  38         struct list_head list;
  39         ir_node *irn;
  40 } list_element_t;
  41
  42 typedef struct _adj_head_t {
  43         struct list_head list;
  44         struct list_head *next_adj_head;
  45         ir_node *irn;
  46         int degree;
  47 } adj_head_t;
  48
  49 typedef struct _adj_iter_t {
  50         ifg_list_t *ifg;
  51         ir_node *irn;
  52         adj_head_t *curr_adj_head;
  53         list_element_t *curr_list_element;
  54         pmap_entry *entry;
  55 } adj_iter_t;
  56
  57 /* PRIVATE FUNCTIONS */
  58
  59 static adj_head_t *get_or_set_adj_head(ifg_list_t *ifg, ir_node *irn)
  60 {
  61         adj_head_t *adj_head;
  62
  63         adj_head = pmap_get(ifg->list_map, irn);
  64         if(!adj_head){
  65                 adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head));
  66                 adj_head->irn = irn;
  67                 INIT_LIST_HEAD(&adj_head->list);
  68                 pmap_insert(ifg->list_map, irn, adj_head);
  69         }
  70
  71         return adj_head;
  72 }
  73
  74 static list_element_t *get_new_list_element(ifg_list_t *ifg, ir_node *irn)
  75 {
  76         list_element_t *element;
  77
  78         element = obstack_alloc(&ifg->obst, sizeof(*element));
  79         element->irn = irn;
  80         INIT_LIST_HEAD(&element->list);
  81
  82         return element;
  83 }
  84
  85 static void add_edge(ifg_list_t *ifg, ir_node *a, ir_node *b) /* add node B as a neighbour to A and vice versa */
  86 {
  87         adj_head_t *adj_head;
  88         list_element_t *new_element;
  89         list_element_t *element;
  90         int is_element = 0;
  91
  92         adj_head = get_or_set_adj_head(ifg, a);
  93         list_for_each_entry(list_element_t, element, &adj_head->list, list){
  94                 if(element->irn == b){
  95                         is_element = 1;
  96                         break;
  97                 }
  98         }
  99         if (!is_element){ /* if B is not yet a neighbour of A add the node to A's neighbours */
 100                 new_element = get_new_list_element(ifg, b);
 101                 adj_head->degree++;
 102                 list_add(&new_element->list, &adj_head->list) ;
 103         }
 104
 105         adj_head = get_or_set_adj_head(ifg, b);
 106         is_element = 0;
 107         list_for_each_entry(list_element_t, element, &adj_head->list, list){
 108                 if(element->irn == a){
 109                         is_element = 1;
 110                 }
 111         }
 112         if (!is_element){ /* if A is not yet a neighbour of B add the node to B's neighbours */
 113                 new_element = get_new_list_element(ifg, a);
 114                 adj_head->degree++;
 115                 list_add(&new_element->list, &adj_head->list);
 116         }
 117 }
 118
 119 static void find_nodes(const ifg_list_t *ifg, adj_iter_t *it)
 120 {
 121         pmap_entry *entry;
 122         entry = pmap_first(ifg->list_map); /* find the first node */
 123         it->ifg = ifg;
 124         it->ifg->list_map = ifg->list_map;
 125         it->entry = entry;
 126         it->curr_adj_head = entry->value;
 127
 128         return;
 129 }
 130
 131 static ir_node *get_next_node(adj_iter_t *it)
 132 {
 133         adj_head_t *adj_head;
 134
 135         pmap_entry *entry;
 136         ir_node *irn;
 137
 138         if (it->curr_adj_head == NULL)
 139                 return NULL;
 140         else
 141         {
 142                 adj_head = it->curr_adj_head;
 143                 irn = adj_head->irn; /* return the last found node */
 144                 entry = it->entry;
 145                 it->irn = irn;
 146                 it->entry = pmap_next(it->ifg->list_map); /*find the next node */
 147                 if (it->entry != NULL)
 148                         it->curr_adj_head = it->entry->value;
 149                 else
 150                         it->curr_adj_head = NULL;
 151         }
 152   return irn;
 153 }
 154
 155 static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in one given block */
 156 {
 157         ifg_list_t *ifg = data;
 158         struct list_head *head  = get_block_border_head(ifg->env, bl);
 159         border_t *b;
 160         int delete_nodeset = 0;
 161         nodeset *live = new_nodeset(ifg->env->cls->n_regs);
 162         ir_node *live_irn;
 163         adj_head_t *adj_head;
 164
 165         assert(is_Block(bl) && "There is no block to work on.");
 166
 167         foreach_border_head(head, b) /* follow the borders of the block */
 168         {
 169                 //if(get_irn_node_nr(b->irn) == 2049)
 170                 //      printf("Hallo");
 171                 if (b->is_def) {
 172                         adj_head = get_or_set_adj_head(ifg, b->irn);
 173                         nodeset_insert(live, b->irn);
 174 //                      if (b->is_real) /* b is a new node */ {
 175                                 foreach_nodeset(live, live_irn) {
 176                                         if (b->irn != live_irn) /* add b as a neighbour to each previous found adjacent node */
 177                                                 add_edge(ifg, b->irn, live_irn);
 178 //                              }
 179                         }
 180                 }
 181
 182                 else {
 183                         if (nodeset_find(live,b->irn)) /* b is used, deleting... */
 184                                 nodeset_remove(live, b->irn);
 185                 }
 186         }
 187         if (delete_nodeset)
 188                 del_nodeset(live);
 189 }
 190
 191
 192 static void find_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *irn)
 193 {
 194         ir_node *node = (void *) irn;
 195         list_element_t *element;
 196         adj_head_t *adj_head = pmap_get(ifg->list_map, node);
 197
 198         assert(adj_head && "There is no entry for this node.");
 199
 200         if (adj_head->list.next == &adj_head->list)
 201         {
 202                 /* element has no neighbours */
 203                 it->irn = NULL;
 204                 it->curr_adj_head = adj_head;
 205                 it->curr_list_element = NULL;
 206                 return;
 207         }
 208
 209         element = list_entry(adj_head->list.next, list_element_t, list); /* get the first neighbour of the given node irn */
 210
 211         it->curr_list_element = element;
 212         it->curr_adj_head = adj_head;
 213         it->irn = element->irn;
 214
 215         return;
 216 }
 217
 218 static ir_node *get_next_neighbour(adj_iter_t *it)
 219 {
 220         ir_node *res;
 221         list_element_t *element;
 222         adj_head_t *adj_head = it->curr_adj_head;
 223
 224         if(it->irn != NULL) /* return the previous found neighbour */
 225                 res = it->irn;
 226         else
 227         {
 228                 if(it->curr_list_element != NULL)
 229                 {
 230                         res = it->curr_list_element->irn; /* was last element */
 231                         it ->curr_list_element = NULL;
 232                         return res;
 233                 }
 234                 else
 235                         return NULL;
 236         }
 237
 238         element = list_entry(it->curr_list_element->list.next, list_element_t, list); /* find the next neighbour */
 239         if (element->list.next == &it->curr_list_element->list) /* single element (only one neighbour) */
 240         {
 241                 it->irn = NULL;
 242                 it->curr_list_element = NULL;
 243                 return res;
 244         }
 245
 246         if(element->list.next == &adj_head->list) /* reaching end of list */
 247                 it->irn = NULL;
 248         else
 249                 it->irn = element->irn;
 250
 251         it->curr_list_element = element;
 252
 253         return res;
 254 }
 255
 256
 257 /* PUBLIC FUNCTIONS */
 258 static void ifg_list_free(void *self)
 259 {
 260         ifg_list_t *ifg = self;
 261         obstack_free(&ifg->obst, NULL);
 262         pmap_destroy(ifg->list_map);
 263         free(self);
 264 }
 265
 266 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
 267 {
 268         const ifg_list_t *ifg = self;
 269         ir_node *node_a = (void *) a;
 270         ir_node *node_b = (void *) b;
 271         adj_head_t *adj_head;
 272         list_element_t *element;
 273         int is_element = 0;
 274
 275         adj_head = pmap_get(ifg->list_map, node_a);
 276         assert(adj_head && "There is no entry for the first node.");
 277
 278         //if (adj_head == NULL) /* node is not in this ifg */
 279         //      return 1;
 280
 281         list_for_each_entry(list_element_t, element, &adj_head->list, list)
 282                 if(element->irn == b)
 283                         is_element = 1;
 284
 285         adj_head = pmap_get(ifg->list_map, node_b);
 286         assert(adj_head && "There is no entry for the second node");
 287
 288         //if (adj_head == NULL) /* node is not in this ifg */
 289         //      return 1;
 290
 291         list_for_each_entry(list_element_t, element, &adj_head->list, list)
 292                 if(element->irn == a)
 293                         is_element = 1;
 294
 295         return is_element;
 296 }
 297
 298 static ir_node *ifg_list_neighbours_begin(const void *self, adj_iter_t *it, const ir_node *irn)
 299 {
 300         find_first_neighbour(self, it, irn);
 301         return get_next_neighbour(it);
 302 }
 303
 304 static ir_node *ifg_list_neighbours_next(const void *self, adj_iter_t *it)
 305 {
 306         return get_next_neighbour(it);
 307 }
 308
 309 static void ifg_list_neighbours_break(const void *self, adj_iter_t *it)
 310 {
 311 }
 312
 313 static ir_node *ifg_list_nodes_begin(const void *self, adj_iter_t *it)
 314 {
 315         find_nodes(self, it);
 316         return get_next_node(it);
 317 }
 318
 319 static ir_node *ifg_list_nodes_next(const void *self, adj_iter_t *it)
 320 {
 321         return get_next_node(it);
 322 }
 323
 324 static void ifg_list_nodes_break(const void *self, adj_iter_t *it)
 325 {
 326 }
 327
 328 static int ifg_list_degree(const void *self, const ir_node *irn)
 329 {
 330         const ifg_list_t *ifg = self;
 331         adj_head_t *adj_head;
 332
 333         adj_head = pmap_get(ifg->list_map, (void *) irn);
 334         assert(!adj_head && "There is no entry for this node.");
 335
 336         return adj_head->degree;
 337 }
 338
 339 static const be_ifg_impl_t ifg_list_impl = {
 340         sizeof(adj_iter_t),
 341         sizeof(adj_iter_t),
 342         0,
 343         ifg_list_free,
 344         ifg_list_connected,
 345         ifg_list_neighbours_begin,
 346         ifg_list_neighbours_next,
 347         ifg_list_neighbours_break,
 348         ifg_list_nodes_begin,
 349         ifg_list_nodes_next,
 350         ifg_list_nodes_break,
 351         NULL,
 352         NULL,
 353         NULL,
 354         ifg_list_degree
 355 };
 356
 357 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
 358 {
 359         ifg_list_t *ifg         = xmalloc(sizeof(*ifg));
 360         ifg->impl               = &ifg_list_impl;
 361         ifg->list_map           = pmap_create();
 362         ifg->env                        = env;
 363
 364         obstack_init(&ifg->obst);
 365         dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
 366
 367         obstack_finish(&ifg->obst);
 368
 369         return (be_ifg_t *) ifg;
 370 }