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

   1 /**
   2  * @file   beifg_clique.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
  22 #include "be_t.h"
  23 #include "bera.h"
  24 #include "beifg_t.h"
  25 #include "bechordal_t.h"
  26
  27 typedef struct _cli_head_t {
  28         struct list_head list;
  29         struct _cli_head_t *next_cli_head;
  30         ir_node *min;
  31         ir_node *max;
  32 } cli_head_t;
  33
  34 typedef struct _ifg_clique_t {
  35         const be_ifg_impl_t *impl;
  36         const be_chordal_env_t *env;
  37         cli_head_t *cli_root;
  38         struct obstack obst;
  39         cli_head_t *curr_cli_head;
  40 } ifg_clique_t;
  41
  42 typedef struct _cli_element_t {
  43         ir_node *irn;
  44         struct list_head list;
  45 } cli_element_t;
  46
  47 typedef struct _cli_iter_t {
  48         ifg_clique_t *ifg;
  49         cli_head_t *curr_cli_head;
  50         cli_element_t *curr_cli_element;
  51         unsigned long curr_irg_visited;
  52         const ir_node *curr_irn;
  53 } cli_iter_t;
  54
  55 /* PRIVATE FUNCTIONS */
  56 static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
  57 {
  58         cli_head_t *cli_head;
  59         cli_head_t *new_cli_head;
  60
  61         if (ifg->cli_root == NULL)
  62         {
  63                 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
  64                 INIT_LIST_HEAD(&new_cli_head->list);
  65                 ifg->cli_root = new_cli_head;
  66         }
  67         else
  68         {
  69                 cli_head = ifg->cli_root;
  70                 while(!(cli_head->next_cli_head == NULL))
  71                 {
  72                         cli_head = cli_head->next_cli_head;
  73                 }
  74                 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
  75                 INIT_LIST_HEAD(&new_cli_head->list);
  76                 cli_head->next_cli_head = new_cli_head;
  77         }
  78
  79         new_cli_head->min = NULL;
  80         new_cli_head->max = NULL;
  81         new_cli_head->next_cli_head = NULL;
  82         ifg->curr_cli_head = new_cli_head;
  83
  84         return new_cli_head;
  85 }
  86
  87 static cli_element_t *get_new_cli_element(ifg_clique_t *ifg)
  88 {
  89         cli_element_t *cli_element;
  90
  91         cli_element = obstack_alloc(&ifg->obst, sizeof(*cli_element));
  92         INIT_LIST_HEAD(&cli_element->list);
  93
  94         return cli_element;
  95 }
  96
  97 static void write_clique(nodeset *live_set, ifg_clique_t *ifg)
  98 {
  99         ir_node *live_irn;
 100         ir_node *test_node;
 101         int test_int = 0;
 102         ir_node *max_node = NULL;
 103         ir_node *min_node = NULL;
 104         cli_element_t *new_element = NULL;
 105         cli_element_t *element = NULL;
 106         cli_head_t *cli_head = get_new_cli_head(ifg);
 107         int is_element = 0;
 108
 109         foreach_nodeset(live_set, live_irn)
 110         {
 111                 /* test if node is max or min dominator*/
 112                 test_node = live_irn;
 113                 if (max_node == NULL)
 114                 {
 115                         max_node = test_node;
 116                         min_node = test_node;
 117                 }
 118                 else
 119                 {
 120                         test_int = value_dominates(test_node, max_node);
 121                         if (test_int == 1)
 122                         {
 123                                 max_node = test_node;
 124                         }
 125                         test_int = value_dominates(min_node, test_node);
 126                         if (test_int == 1)
 127                         {
 128                                 min_node = test_node;
 129                         }
 130
 131                         list_for_each_entry(cli_element_t, element, &cli_head->list, list){
 132                                 if(element->irn == live_irn){
 133                                         is_element = 1;
 134                                         break;
 135                                 }
 136                         }
 137
 138                         if (!is_element){
 139                                 new_element = get_new_cli_element(ifg);
 140                                 new_element->irn = live_irn;
 141                                 list_add(&new_element->list, &cli_head->list) ;
 142                         }
 143                 }
 144         }
 145
 146         cli_head->min = min_node;
 147         cli_head->max = max_node;
 148 }
 149
 150 static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it)
 151 {
 152         cli_element_t *element;
 153         cli_head_t *cli_head = ifg->cli_root;
 154
 155         assert((cli_head == NULL) && "There is no node to work on!");
 156
 157         it->curr_cli_head = cli_head;
 158
 159         if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */
 160         {
 161                 element = list_entry(cli_head->list.next, cli_element_t, list);
 162                 it->curr_cli_element = element;
 163
 164                 inc_irg_visited(get_irn_irg(element->irn));
 165                 it->curr_irg_visited = get_irg_visited(get_irn_irg(element->irn));
 166         }
 167
 168         return;
 169 }
 170
 171 static ir_node *get_next_node(cli_iter_t *it)
 172 {
 173         cli_head_t *cli_head = NULL;
 174         cli_element_t *element = it->curr_cli_element;
 175         unsigned long irn_visited = get_irn_visited(element->irn);
 176
 177         ir_node *irn;
 178
 179         if (!(element == it->curr_cli_element))
 180         {
 181                 irn = element->irn;
 182                 element = list_entry(cli_head->list.next, cli_element_t, list);
 183                 it->curr_cli_element = element;
 184         }
 185         else
 186         {
 187                 cli_head = it->curr_cli_head;
 188                 if (!(cli_head->next_cli_head == NULL))
 189                 {
 190                         irn = element->irn;
 191                         cli_head = cli_head->next_cli_head;
 192                         it->curr_cli_head = cli_head;
 193                         element = list_entry(cli_head->list.next, cli_element_t, list);
 194                         it->curr_cli_element = element;
 195                 }
 196                 else
 197                 {
 198                         return NULL;
 199                 }
 200         }
 201
 202         if (irn_visited == it->curr_irg_visited)
 203         {
 204                 irn = get_next_node(it);
 205         }
 206
 207         set_irn_visited(irn, it->curr_irg_visited);
 208         return irn;
 209 }
 210
 211 static void find_neighbour_walker(ir_node *bl, void *data)
 212 {
 213         ifg_clique_t *ifg       = data;
 214         struct list_head *head  = get_block_border_head(ifg->env, bl);
 215         border_t *b;
 216         int was_def = 0;
 217         nodeset *live = new_nodeset(ifg->env->cls->n_regs);
 218
 219         assert(is_Block(bl) && "There is no block to work on.");
 220
 221         foreach_border_head(head, b) /* follow the borders of the block */
 222         {
 223                 ir_node *irn = b->irn;
 224
 225                 if (b->is_def) /* b is a new node */
 226                 {
 227                         nodeset_insert(live, irn);
 228                         if(b->is_real)
 229                         {
 230                                 was_def = 1;
 231                         }
 232                 }
 233                 else
 234                 {
 235                         if (!(b->is_def))
 236                         {
 237                                 if (was_def == 1) /* if there is a USE after a DEF... */
 238                                 {
 239                                         write_clique(live, ifg); /* ...add the clique. */
 240                                         was_def = 0;
 241                                 }
 242                                 nodeset_remove(live, irn);
 243                         }
 244                 }
 245         }
 246         del_nodeset(live);
 247 }
 248
 249 static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn)
 250 {
 251         cli_head_t *cli_head = ifg->cli_root;
 252         cli_element_t *element;
 253
 254         int is_dominated_by_max = 0;
 255         int dominates_min = 0;
 256
 257         assert(!cli_head && "There is no root entry for a cli_head.");
 258
 259         while(!(cli_head->next_cli_head == NULL))
 260         {
 261                 is_dominated_by_max = value_dominates(cli_head->max, irn);
 262                 dominates_min = value_dominates(irn, cli_head->min);
 263
 264                 if ((is_dominated_by_max && dominates_min) /* node is in clique */
 265                                 || (irn == cli_head->max)
 266                                 || (irn == cli_head->min))
 267                 {
 268                         element = list_entry(cli_head->list.next, cli_element_t, list);
 269
 270                         it->curr_cli_element = element;
 271                         it->curr_cli_head = cli_head;
 272                         break;
 273                 }
 274                 else
 275                 {
 276                         cli_head = cli_head->next_cli_head;
 277                 }
 278         }
 279         it->curr_irn = irn;
 280
 281         inc_irg_visited(get_irn_irg(irn));
 282         it->curr_irg_visited = get_irg_visited(get_irn_irg(irn));
 283         return;
 284 }
 285
 286 static ir_node *get_next_neighbour(cli_iter_t *it)
 287 {
 288         ir_node *res = NULL;
 289         cli_element_t *element = NULL;
 290         cli_head_t *cli_head = NULL;
 291         int is_dominated_by_max;
 292         int dominates_min;
 293         const ir_node *irn = it->curr_irn;
 294         unsigned long irn_visited = 0;
 295
 296         res = it->curr_cli_element->irn;
 297
 298         /* get next element */
 299
 300         element = list_entry(it->curr_cli_element->list.next, cli_element_t, list);
 301         irn_visited = get_irn_visited(element->irn);
 302
 303         if ((cli_head_t *)element == it->curr_cli_head) /* end of clique, search next one */
 304         {
 305                 cli_head = cli_head->next_cli_head;
 306                 while(!(cli_head->next_cli_head == NULL))
 307                 {
 308                         is_dominated_by_max = value_dominates(cli_head->max, irn);
 309                         dominates_min = value_dominates(irn, cli_head->min);
 310
 311                         if ((is_dominated_by_max && dominates_min) /* node is in clique */
 312                                         || (irn == cli_head->max)
 313                                         || (irn == cli_head->min))
 314                         {
 315                                 element = list_entry(cli_head->list.next, cli_element_t, list);
 316
 317                                 it->curr_cli_element = element;
 318                                 it->curr_cli_head = cli_head;
 319                                 break;
 320                         }
 321                         else
 322                         {
 323                                 cli_head = cli_head->next_cli_head;
 324                         }
 325                 }
 326         }
 327         else /* get next element of this clique */
 328         {
 329                 it->curr_cli_element = element;
 330         }
 331
 332         if (irn_visited == it->curr_irg_visited)
 333         {
 334                 irn = get_next_neighbour(it);
 335         }
 336
 337         set_irn_visited(res, it->curr_irg_visited);
 338
 339         return res;
 340 }
 341
 342
 343 /* PUBLIC FUNCTIONS */
 344
 345 static void ifg_clique_free(void *self)
 346 {
 347         ifg_clique_t *ifg = self;
 348         obstack_free(&ifg->obst, NULL);
 349
 350         free(self);
 351 }
 352
 353 static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b)
 354 {
 355         cli_iter_t *it = NULL;
 356         int connected = -1;
 357         ir_node *irn = NULL;
 358
 359         find_first_neighbour(self, it, a);
 360         connected = 0;
 361         irn = get_next_neighbour(it);
 362         while (irn != NULL)
 363         {
 364                 if (irn == b)
 365                 {
 366                         connected = 1;
 367                 }
 368                 irn = get_next_neighbour(it);
 369         }
 370
 371         return connected;
 372 }
 373
 374 static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const ir_node *irn)
 375 {
 376         find_first_neighbour(self, iter, irn);
 377         return get_next_neighbour(iter);
 378 }
 379
 380 static ir_node *ifg_clique_neighbours_next(const void *self, void *iter)
 381 {
 382         return get_next_neighbour(iter);
 383 }
 384
 385 static void ifg_clique_neighbours_break(const void *self, void *iter)
 386 {
 387         return;
 388 }
 389
 390 static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
 391 {
 392         find_nodes(self, iter);
 393         return get_next_node(iter);
 394 }
 395
 396 static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
 397 {
 398         return get_next_node(iter);
 399 }
 400
 401 static void ifg_clique_nodes_break(const void *self, void *iter)
 402 {
 403         return;
 404 }
 405
 406 static int ifg_clique_degree(const void *self, const ir_node *irn)
 407 {
 408         int degree = -1;
 409         cli_iter_t *it = NULL;
 410
 411         find_first_neighbour(self, it, irn);
 412         degree = 0;
 413         irn = get_next_neighbour(it);
 414         while (irn != NULL)
 415         {
 416                 degree++;
 417                 irn = get_next_neighbour(it);
 418         }
 419
 420         return degree;
 421 }
 422
 423 static const be_ifg_impl_t ifg_clique_impl = {
 424         sizeof(cli_iter_t),
 425         sizeof(cli_iter_t),
 426         0,
 427         ifg_clique_free,
 428         ifg_clique_connected,
 429         ifg_clique_neighbours_begin,
 430         ifg_clique_neighbours_next,
 431         ifg_clique_neighbours_break,
 432         ifg_clique_nodes_begin,
 433         ifg_clique_nodes_next,
 434         ifg_clique_nodes_break,
 435         NULL,
 436         NULL,
 437         NULL,
 438         ifg_clique_degree
 439 };
 440
 441 be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
 442 {
 443         ifg_clique_t *ifg       = xmalloc(sizeof(*ifg));
 444         ifg->impl               = &ifg_clique_impl;
 445         ifg->env                        = env;
 446
 447         ifg->cli_root           = NULL;
 448         obstack_init(&ifg->obst);
 449
 450         dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
 451
 452         obstack_finish(&ifg->obst);
 453         return (be_ifg_t *) ifg;
 454 }