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                 adj_head->degree = 0;
  68                 INIT_LIST_HEAD(&adj_head->list);
  69                 pmap_insert(ifg->list_map, irn, adj_head);
  70         }
  71
  72         return adj_head;
  73 }
  74
  75 static list_element_t *get_new_list_element(ifg_list_t *ifg, ir_node *irn)
  76 {
  77         list_element_t *element;
  78
  79         element = obstack_alloc(&ifg->obst, sizeof(*element));
  80         element->irn = irn;
  81         INIT_LIST_HEAD(&element->list);
  82
  83         return element;
  84 }
  85
  86 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 */
  87 {
  88         adj_head_t *adj_head;
  89         list_element_t *new_element;
  90         list_element_t *element;
  91         int is_element = 0;
  92
  93         adj_head = get_or_set_adj_head(ifg, a);
  94         list_for_each_entry(list_element_t, element, &adj_head->list, list){
  95                 if(element->irn == b){
  96                         is_element = 1;
  97                         break;
  98                 }
  99         }
 100         if (!is_element){ /* if B is not yet a neighbour of A add the node to A's neighbours */
 101                 new_element = get_new_list_element(ifg, b);
 102                 adj_head->degree++;
 103                 list_add(&new_element->list, &adj_head->list) ;
 104         }
 105
 106         adj_head = get_or_set_adj_head(ifg, b);
 107         is_element = 0;
 108         list_for_each_entry(list_element_t, element, &adj_head->list, list){
 109                 if(element->irn == a){
 110                         is_element = 1;
 111                 }
 112         }
 113         if (!is_element){ /* if A is not yet a neighbour of B add the node to B's neighbours */
 114                 new_element = get_new_list_element(ifg, a);
 115                 adj_head->degree++;
 116                 list_add(&new_element->list, &adj_head->list);
 117         }
 118 }
 119
 120 static void find_nodes(const ifg_list_t *ifg, adj_iter_t *it)
 121 {
 122         pmap_entry *entry;
 123         entry = pmap_first(ifg->list_map); /* find the first node */
 124         it->ifg = ifg;
 125         it->ifg->list_map = ifg->list_map;
 126         it->entry = entry;
 127         it->curr_adj_head = entry->value;
 128
 129         return;
 130 }
 131
 132 static ir_node *get_next_node(adj_iter_t *it)
 133 {
 134         adj_head_t *adj_head;
 135
 136         pmap_entry *entry;
 137         ir_node *irn;
 138
 139         if (it->curr_adj_head == NULL)
 140                 return NULL;
 141         else
 142         {
 143                 adj_head = it->curr_adj_head;
 144                 irn = adj_head->irn; /* return the last found node */
 145                 entry = it->entry;
 146                 it->irn = irn;
 147                 it->entry = pmap_next(it->ifg->list_map); /*find the next node */
 148                 if (it->entry != NULL)
 149                         it->curr_adj_head = it->entry->value;
 150                 else
 151                         it->curr_adj_head = NULL;
 152         }
 153   return irn;
 154 }
 155
 156 static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in one given block */
 157 {
 158         ifg_list_t *ifg = data;
 159         struct list_head *head  = get_block_border_head(ifg->env, bl);
 160         border_t *b;
 161         int delete_nodeset = 0;
 162         nodeset *live = new_nodeset(ifg->env->cls->n_regs);
 163         ir_node *live_irn;
 164         adj_head_t *adj_head;
 165
 166         assert(is_Block(bl) && "There is no block to work on.");
 167
 168         foreach_border_head(head, b) /* follow the borders of the block */
 169         {
 170                 //if(get_irn_node_nr(b->irn) == 2049)
 171                 //      printf("Hallo");
 172                 if (b->is_def) {
 173                         adj_head = get_or_set_adj_head(ifg, b->irn);
 174                         nodeset_insert(live, b->irn);
 175 //                      if (b->is_real) /* b is a new node */ {
 176                                 foreach_nodeset(live, live_irn) {
 177                                         if (b->irn != live_irn) /* add b as a neighbour to each previous found adjacent node */
 178                                                 add_edge(ifg, b->irn, live_irn);
 179 //                              }
 180                         }
 181                 }
 182
 183                 else {
 184                         if (nodeset_find(live,b->irn)) /* b is used, deleting... */
 185                                 nodeset_remove(live, b->irn);
 186                 }
 187         }
 188         if (delete_nodeset)
 189                 del_nodeset(live);
 190 }
 191
 192
 193 static void find_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *irn)
 194 {
 195         ir_node *node = (void *) irn;
 196         list_element_t *element;
 197         adj_head_t *adj_head = pmap_get(ifg->list_map, node);
 198
 199         assert(adj_head && "There is no entry for this node.");
 200
 201         if (adj_head->list.next == &adj_head->list)
 202         {
 203                 /* element has no neighbours */
 204                 it->irn = NULL;
 205                 it->curr_adj_head = adj_head;
 206                 it->curr_list_element = NULL;
 207                 return;
 208         }
 209
 210         element = list_entry(adj_head->list.next, list_element_t, list); /* get the first neighbour of the given node irn */
 211
 212         it->curr_list_element = element;
 213         it->curr_adj_head = adj_head;
 214         it->irn = element->irn;
 215
 216         return;
 217 }
 218
 219 static ir_node *get_next_neighbour(adj_iter_t *it)
 220 {
 221         ir_node *res;
 222         list_element_t *element;
 223         adj_head_t *adj_head = it->curr_adj_head;
 224
 225         if(it->irn != NULL) /* return the previous found neighbour */
 226                 res = it->irn;
 227         else
 228         {
 229                 if(it->curr_list_element != NULL)
 230                 {
 231                         res = it->curr_list_element->irn; /* was last element */
 232                         it ->curr_list_element = NULL;
 233                         return res;
 234                 }
 235                 else
 236                         return NULL;
 237         }
 238
 239         element = list_entry(it->curr_list_element->list.next, list_element_t, list); /* find the next neighbour */
 240         if (element->list.next == &it->curr_list_element->list) /* single element (only one neighbour) */
 241         {
 242                 it->irn = NULL;
 243                 it->curr_list_element = NULL;
 244                 return res;
 245         }
 246
 247         if(element->list.next == &adj_head->list) /* reaching end of list */
 248                 it->irn = NULL;
 249         else
 250                 it->irn = element->irn;
 251
 252         it->curr_list_element = element;
 253
 254         return res;
 255 }
 256
 257
 258 /* PUBLIC FUNCTIONS */
 259 static void ifg_list_free(void *self)
 260 {
 261         ifg_list_t *ifg = self;
 262         obstack_free(&ifg->obst, NULL);
 263         pmap_destroy(ifg->list_map);
 264         free(self);
 265 }
 266
 267 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
 268 {
 269         const ifg_list_t *ifg = self;
 270         ir_node *node_a = (void *) a;
 271         ir_node *node_b = (void *) b;
 272         adj_head_t *adj_head;
 273         list_element_t *element;
 274         int is_element = 0;
 275
 276         adj_head = pmap_get(ifg->list_map, node_a);
 277         assert(adj_head && "There is no entry for the first node.");
 278
 279         //if (adj_head == NULL) /* node is not in this ifg */
 280         //      return 1;
 281
 282         list_for_each_entry(list_element_t, element, &adj_head->list, list)
 283                 if(element->irn == b)
 284                         is_element = 1;
 285
 286         adj_head = pmap_get(ifg->list_map, node_b);
 287         assert(adj_head && "There is no entry for the second node");
 288
 289         //if (adj_head == NULL) /* node is not in this ifg */
 290         //      return 1;
 291
 292         list_for_each_entry(list_element_t, element, &adj_head->list, list)
 293                 if(element->irn == a)
 294                         is_element = 1;
 295
 296         return is_element;
 297 }
 298
 299 static ir_node *ifg_list_neighbours_begin(const void *self, adj_iter_t *it, const ir_node *irn)
 300 {
 301         find_first_neighbour(self, it, irn);
 302         return get_next_neighbour(it);
 303 }
 304
 305 static ir_node *ifg_list_neighbours_next(const void *self, adj_iter_t *it)
 306 {
 307         return get_next_neighbour(it);
 308 }
 309
 310 static void ifg_list_neighbours_break(const void *self, adj_iter_t *it)
 311 {
 312 }
 313
 314 static ir_node *ifg_list_nodes_begin(const void *self, adj_iter_t *it)
 315 {
 316         find_nodes(self, it);
 317         return get_next_node(it);
 318 }
 319
 320 static ir_node *ifg_list_nodes_next(const void *self, adj_iter_t *it)
 321 {
 322         return get_next_node(it);
 323 }
 324
 325 static void ifg_list_nodes_break(const void *self, adj_iter_t *it)
 326 {
 327 }
 328
 329 static int ifg_list_degree(const void *self, const ir_node *irn)
 330 {
 331         const ifg_list_t *ifg = self;
 332         adj_head_t *adj_head;
 333
 334         adj_head = pmap_get(ifg->list_map, (void *) irn);
 335         assert(adj_head && "There is no entry for this node.");
 336
 337         return adj_head->degree;
 338 }
 339
 340 static const be_ifg_impl_t ifg_list_impl = {
 341         sizeof(adj_iter_t),
 342         sizeof(adj_iter_t),
 343         0,
 344         ifg_list_free,
 345         ifg_list_connected,
 346         ifg_list_neighbours_begin,
 347         ifg_list_neighbours_next,
 348         ifg_list_neighbours_break,
 349         ifg_list_nodes_begin,
 350         ifg_list_nodes_next,
 351         ifg_list_nodes_break,
 352         NULL,
 353         NULL,
 354         NULL,
 355         ifg_list_degree
 356 };
 357
 358 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
 359 {
 360         ifg_list_t *ifg         = xmalloc(sizeof(*ifg));
 361         ifg->impl               = &ifg_list_impl;
 362         ifg->list_map           = pmap_create();
 363         ifg->env                        = env;
 364
 365         obstack_init(&ifg->obst);
 366         dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
 367
 368         obstack_finish(&ifg->obst);
 369
 370         return (be_ifg_t *) ifg;
 371 }