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