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

   1 /**
   2  * @file   beifg_pointer.c
   3  * @date   20.03.2006
   4  * @author Sebastian Hack
   5  *
   6  * Copyright (C) 2005 Universitaet Karlsruhe
   7  * Released under the GPL
   8  */
   9
  10 #if 0
  11 #ifdef HAVE_CONFIG_H
  12 #include "config.h"
  13 #endif
  14
  15 #include <stdlib.h>
  16
  17 #include "belive_t.h"
  18 #include "list.h"
  19
  20 #include "irnode_t.h"
  21 #include "irgraph_t.h"
  22 #include "irgwalk.h"
  23
  24 #include "be_t.h"
  25 #include "bera.h"
  26 #include "beifg_t.h"
  27 #include "bechordal_t.h"
  28
  29 typedef struct _cli_head_t {
  30   struct list_head list;
  31         struct _cli_head_t *next_cli_head;
  32         ir_node *min;
  33         ir_node *max;
  34 } cli_head_t;
  35
  36 typedef struct _ifg_pointer_t {
  37         const be_ifg_impl_t *impl;
  38         const be_chordal_env_t *env;
  39         cli_head_t *cli_root;
  40         struct obstack obst;
  41 } ifg_pointer_t;
  42
  43 typedef struct _cli_element_t {
  44         ir_node *irn;
  45         struct list_head list;
  46 } cli_element_t;
  47
  48 typedef struct _cli_iter_t {
  49         ifg_pointer_t *ifg;
  50         cli_head_t *curr_cli_head;
  51         cli_element_t *curr_cli_element;
  52         unsigned long curr_irg_visited;
  53         const ir_node *curr_irn;
  54 } cli_iter_t;
  55
  56 /* PRIVATE FUNCTIONS */
  57 static cli_head_t *get_new_cli_head(void *data)
  58 {
  59         cli_iter_t *it = data;
  60         cli_head_t *cli_head;
  61         cli_head_t *new_cli_head;
  62
  63         if (it->ifg->cli_root == NULL)
  64         {
  65         new_cli_head = obstack_alloc(&it->ifg->obst, sizeof(*new_cli_head));
  66         INIT_LIST_HEAD(&new_cli_head->list);
  67
  68         new_cli_head->next_cli_head = NULL;
  69         it->ifg->cli_root = new_cli_head;
  70         it->curr_cli_head = new_cli_head;
  71         }
  72         else
  73         {
  74                 cli_head = it->ifg->cli_root;
  75                 while(!(cli_head->next_cli_head == NULL))
  76                 {
  77                         cli_head = cli_head->next_cli_head;
  78                 }
  79                 new_cli_head = obstack_alloc(&it->ifg->obst, sizeof(*new_cli_head));
  80                 INIT_LIST_HEAD(&new_cli_head->list);
  81                 cli_head->next_cli_head = new_cli_head;
  82                 it->curr_cli_head = new_cli_head;
  83         }
  84
  85         cli_head->min = NULL;
  86         cli_head->max = NULL;
  87
  88         return new_cli_head;
  89 }
  90
  91 static cli_head_t *get_first_cli_head(void *data)
  92 {
  93         cli_iter_t *it = data;
  94
  95         return it->ifg->cli_root;
  96 }
  97
  98 static void write_clique(pset *live_set, void *data)
  99 {
 100         ir_node *live_irn;
 101         ir_node *test_node;
 102         int test_int = 0;
 103         ir_node *max_node;
 104         ir_node *min_node;
 105         cli_iter_t *it = data;
 106         pset *live = live_set;
 107         cli_element_t *element;
 108         int is_element = 0;
 109
 110         cli_head_t *cli_head = get_new_cli_head(it);
 111
 112         for(live_irn = pset_first(live); live_irn; live_irn = pset_next(live))
 113         {
 114                 /* test if node is max or min dominator*/
 115                 test_node = live_irn;
 116                 if (max_node == NULL)
 117                 {
 118                         max_node = test_node;
 119                         min_node = test_node;
 120                 }
 121                 else
 122                 {
 123                         test_int = value_dominates(test_node, max_node);
 124                         if (test_int == 1)
 125                         {
 126                                 max_node = test_node;
 127                         }
 128                         test_int = value_dominates(min_node, test_node);
 129                         if (test_int == 1)
 130                         {
 131                                 min_node = test_node;
 132                         }
 133                 }
 134
 135                 list_for_each_entry(cli_element_t, element, &cli_head->list, list){
 136                         if(element->irn == live_irn){
 137                                 is_element = 1;
 138                                 break;
 139                         }
 140                 }
 141                 if (!is_element){
 142                         element->irn = live_irn;
 143                         list_add(&element->list, &cli_head->list) ;
 144                 }
 145         }
 146         cli_head->min = min_node;
 147         cli_head->max = max_node;
 148 }
 149
 150 static void find_nodes(const void *self, void *iter)
 151 {
 152         const ifg_clique_t *ifg  = self;
 153         cli_iter_t *it = iter;
 154         cli_element_t *element = NULL;
 155         cli_head_t *cli_head = get_first_cli_head(it);
 156
 157         assert((cli_head == NULL) && "There is no node to work on!");
 158
 159         it->curr_cli_head = cli_head;
 160         it->curr_cli_element = element;
 161
 162         element = list_entry(cli_head->list.next, cli_element_t, list);
 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         return;
 168 }
 169
 170 static ir_node *get_next_node(void *iter)
 171 {
 172         cli_iter_t *it = iter;
 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         cli_iter_t *it          = data;
 214         struct list_head *head  = get_block_border_head(it->ifg->env, bl);
 215         border_t *b;
 216         int was_def = 0;
 217
 218         pset *live = put_live_in(bl, pset_new_ptr_default());
 219
 220         assert(is_Block(bl) && "There is no block to work on.");
 221
 222         list_for_each_entry_reverse(border_t, b, head, list)
 223         {
 224                 ir_node *irn = b->irn;
 225
 226                 if (!(pset_find_ptr(live, irn)) && (b->is_def))
 227                 {
 228                         pset_insert_ptr(live, irn);
 229                         was_def = 1;
 230                 }
 231
 232                 else if (!(b->is_def) && (was_def == 1))
 233                 {
 234                         if (was_def == 1)
 235                         {
 236                                 write_clique(live, it);
 237                                 was_def = 0;
 238                         }
 239                         pset_remove_ptr(live, irn);
 240                 }
 241         }
 242         del_pset(live);
 243 }
 244
 245 static ifg_clique_t *build_neighbours(const be_chordal_env_t *env)
 246 {
 247         ifg_clique_t *ifg = NULL;
 248         cli_iter_t *it = NULL;
 249
 250         it->ifg                         = ifg;
 251         it->curr_cli_head               = NULL;
 252         it->curr_cli_element    = NULL;
 253         it->curr_irg_visited    = get_irg_visited(env->irg);
 254
 255         obstack_init(&it->ifg->obst);
 256         dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, it);
 257
 258         return ifg;
 259 }
 260
 261 static void find_first_neighbour(const void *self, void *iter, const ir_node *irn)
 262 {
 263         const ifg_clique_t *ifg = self;
 264         cli_iter_t *it = iter;
 265
 266         cli_head_t *cli_head = ifg->cli_root;
 267         cli_element_t *element;
 268
 269         int is_dominated_by_max = 0;
 270         int dominates_min = 0;
 271
 272         assert(!cli_head && "There is no root entry for a cli_head.");
 273
 274         while(!(cli_head->next_cli_head == NULL))
 275         {
 276                 is_dominated_by_max = value_dominates(cli_head->max, irn);
 277                 dominates_min = value_dominates(irn, cli_head->min);
 278
 279                 if ((is_dominated_by_max && dominates_min) /* node is in clique */
 280                                 || (irn == cli_head->max)
 281                                 || (irn == cli_head->min))
 282                 {
 283                         element = list_entry(cli_head->list.next, cli_element_t, list);
 284
 285                         it->curr_cli_element = element;
 286                         it->curr_cli_head = cli_head;
 287                         break;
 288                 }
 289                 else
 290                 {
 291                         cli_head = cli_head->next_cli_head;
 292                 }
 293         }
 294         it->curr_irn = irn;
 295
 296         inc_irg_visited(get_irn_irg(irn));
 297         it->curr_irg_visited = get_irg_visited(get_irn_irg(irn));
 298         return;
 299 }
 300
 301 static ir_node *get_next_neighbour(cli_iter_t *it)
 302 {
 303         ir_node *res = NULL;
 304         cli_element_t *element = NULL;
 305         cli_head_t *cli_head = NULL;
 306         int is_dominated_by_max;
 307         int dominates_min;
 308         const ir_node *irn = it->curr_irn;
 309         unsigned long irn_visited = 0;
 310
 311         res = it->curr_cli_element->irn;
 312
 313         /* get next element */
 314
 315         element = list_entry(it->curr_cli_element->list.next, cli_element_t, list);
 316         irn_visited = get_irn_visited(element->irn);
 317
 318         if ((cli_head_t *)element == it->curr_cli_head) /* end of clique, search next one */
 319         {
 320                 cli_head = cli_head->next_cli_head;
 321                 while(!(cli_head->next_cli_head == NULL))
 322                 {
 323                         is_dominated_by_max = value_dominates(cli_head->max, irn);
 324                         dominates_min = value_dominates(irn, cli_head->min);
 325
 326                         if ((is_dominated_by_max && dominates_min) /* node is in clique */
 327                                         || (irn == cli_head->max)
 328                                         || (irn == cli_head->min))
 329                         {
 330                                 element = list_entry(cli_head->list.next, cli_element_t, list);
 331
 332                                 it->curr_cli_element = element;
 333                                 it->curr_cli_head = cli_head;
 334                                 break;
 335                         }
 336                         else
 337                         {
 338                                 cli_head = cli_head->next_cli_head;
 339                         }
 340                 }
 341         }
 342         else /* get next element of this clique */
 343         {
 344                 it->curr_cli_element = element;
 345         }
 346
 347         if (irn_visited == it->curr_irg_visited)
 348         {
 349                 irn = get_next_neighbour(it);
 350         }
 351
 352         set_irn_visited(res, it->curr_irg_visited);
 353
 354         return res;
 355 }
 356
 357
 358 /* PUBLIC FUNCTIONS */
 359
 360 static void ifg_pointer_free(void *self)
 361 {
 362         ifg_clique_t *ifg = self;
 363
 364         free(self);
 365 }
 366
 367 static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b)
 368 {
 369         cli_iter_t *it = NULL;
 370         int connected = -1;
 371         ir_node *irn = NULL;
 372
 373         find_first_neighbour(self, it, a);
 374         connected = 0;
 375         irn = get_next_neighbour(it);
 376         while (irn != NULL)
 377         {
 378                 if (irn == b)
 379                 {
 380                         connected = 1;
 381                 }
 382                 irn = get_next_neighbour(it);
 383         }
 384
 385         return connected;
 386 }
 387
 388 static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn)
 389 {
 390         find_first_neighbour(self, iter, irn);
 391         return get_next_neighbour(iter);
 392 }
 393
 394 static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter)
 395 {
 396         return get_next_neighbour(iter);
 397 }
 398
 399 static void ifg_pointer_neighbours_break(const void *self, void *iter)
 400 {
 401         return;
 402 }
 403
 404 static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter)
 405 {
 406         find_nodes(self, iter);
 407         return get_next_node(iter);
 408 }
 409
 410 static ir_node *ifg_pointer_nodes_next(const void *self, void *iter)
 411 {
 412         return get_next_node(iter);
 413 }
 414
 415 static void ifg_pointer_nodes_break(const void *self, void *iter)
 416 {
 417         return;
 418 }
 419
 420 static int ifg_pointer_degree(const void *self, const ir_node *irn)
 421 {
 422         int degree = -1;
 423         cli_iter_t *it = NULL;
 424
 425         find_first_neighbour(self, it, irn);
 426         degree = 0;
 427         irn = get_next_neighbour(it);
 428         while (irn != NULL)
 429         {
 430                 degree++;
 431                 irn = get_next_neighbour(it);
 432         }
 433
 434         return degree;
 435 }
 436
 437 static const be_ifg_impl_t ifg_pointer_impl = {
 438         sizeof(cli_iter_t),
 439         0,
 440         0,
 441         ifg_pointer_free,
 442         ifg_pointer_connected,
 443         ifg_pointer_neighbours_begin,
 444         ifg_pointer_neighbours_next,
 445         ifg_pointer_neighbours_break,
 446         ifg_pointer_nodes_begin,
 447         ifg_pointer_nodes_next,
 448         ifg_pointer_nodes_break,
 449         NULL,
 450         NULL,
 451         NULL,
 452         ifg_pointer_degree
 453 };
 454
 455 be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env)
 456 {
 457         ifg_pointer_t *ifg      = malloc(sizeof(*ifg));
 458         ifg->impl               = &ifg_pointer_impl;
 459
 460         ifg->cli_root           = NULL;
 461         ifg->env                        = env;
 462
 463         ifg = build_neighbours(env);
 464
 465         return (be_ifg_t *) ifg;
 466 }
 467
 468 #endif