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

   1 /**
   2  * @file   beifg_std.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 "list.h"
  16
  17 #include "irnode_t.h"
  18 #include "irgraph_t.h"
  19 #include "irgwalk.h"
  20
  21 #include "be_t.h"
  22 #include "bera.h"
  23 #include "beifg_t.h"
  24 #include "bechordal_t.h"
  25
  26 #define MAX(x, y) ((x) > (y) ? (x) : (y))
  27
  28 typedef struct _ifg_std_t ifg_std_t;
  29
  30 struct _ifg_std_t {
  31         const be_ifg_impl_t *impl;
  32         const be_chordal_env_t *env;
  33 };
  34
  35 static void ifg_std_free(void *self)
  36 {
  37         free(self);
  38 }
  39
  40 static int ifg_std_connected(const void *self, const ir_node *a, const ir_node *b)
  41 {
  42         return values_interfere(a, b);
  43 }
  44
  45 typedef struct _nodes_iter_t {
  46         const be_chordal_env_t *env;
  47         struct obstack obst;
  48         int n;
  49         int curr;
  50         ir_node **nodes;
  51 } nodes_iter_t;
  52
  53 static void nodes_walker(ir_node *bl, void *data)
  54 {
  55         nodes_iter_t *it = data;
  56         struct list_head *head = get_block_border_head(it->env, bl);
  57
  58         border_t *b;
  59
  60         foreach_border_head(head, b) {
  61                 if(b->is_def && b->is_real) {
  62                         obstack_ptr_grow(&it->obst, b->irn);
  63                         it->n++;
  64                 }
  65         }
  66 }
  67
  68 static void find_nodes(const void *self, void *iter) {
  69         const ifg_std_t *ifg = self;
  70         nodes_iter_t *it = iter;
  71
  72         obstack_init(&it->obst);
  73         it->n    = 0;
  74         it->curr = 0;
  75
  76         irg_block_walk_graph(ifg->env->irg, nodes_walker, NULL, iter);
  77         it->nodes = obstack_finish(&it->obst);
  78 }
  79
  80 static ir_node *get_next_node(void *iter)
  81 {
  82         nodes_iter_t *it = iter;
  83         ir_node *res     = NULL;
  84
  85         if(it->curr < it->n)
  86                 res = it->nodes[it->curr++];
  87
  88         if(it->curr >= it-> n && it->nodes) {
  89                 obstack_free(&it->obst, NULL);
  90                 it->nodes = NULL;
  91         }
  92
  93         return res;
  94 }
  95
  96 static ir_node *ifg_std_nodes_begin(const void *self, void *iter)
  97 {
  98         find_nodes(self, iter);
  99         return get_next_node(iter);
 100 }
 101
 102 static ir_node *ifg_std_nodes_next(const void *self, void *iter)
 103 {
 104         return get_next_node(iter);
 105 }
 106
 107 typedef struct _adj_iter_t {
 108         const be_chordal_env_t *env;
 109         const ir_node *irn;
 110         struct obstack obst;
 111         int degree;
 112         unsigned visited_nr;
 113         unsigned build_list : 1;
 114
 115         int curr;
 116         ir_node **neighbours;
 117 } adj_iter_t;
 118
 119 static void find_neighbour_walker(ir_node *block, void *data)
 120 {
 121         adj_iter_t *it          = data;
 122         unsigned visited        = it->visited_nr;
 123         struct list_head *head  = get_block_border_head(it->env, block);
 124
 125         border_t *b;
 126         int has_started = 0;
 127
 128         foreach_border_head(head, b) {
 129                 ir_node *irn = b->irn;
 130
 131                 if(irn == it->irn)
 132                         has_started = b->is_def;
 133
 134                 /*
 135                  * If the def/use of the node is inside the live range
 136                  * of the node in question, they interfere.
 137                  * To avoid that a node is added twice, we record the
 138                  * visit in the visited number provided by core firm.
 139                  */
 140                 else if(has_started && get_irn_visited(irn) < visited) {
 141                         if(it->build_list)
 142                                 obstack_ptr_grow(&it->obst, irn);
 143
 144                         set_irn_visited(irn, visited);
 145                         it->degree++;
 146                 }
 147         }
 148 }
 149
 150 static void find_neighbours(const ifg_std_t *ifg, adj_iter_t *it, const ir_node *irn, int build_list)
 151 {
 152         if(build_list)
 153                 obstack_init(&it->obst);
 154
 155         it->env        = ifg->env;
 156         it->irn        = irn;
 157         it->degree     = 0;
 158         it->visited_nr = get_irg_visited(ifg->env->irg) + 1;
 159         it->build_list = build_list;
 160         it->neighbours = NULL;
 161         it->curr       = 0;
 162
 163         set_irg_visited(ifg->env->irg, it->visited_nr);
 164         dom_tree_walk(get_nodes_block(irn), find_neighbour_walker, NULL, it);
 165
 166         if(build_list)
 167                 it->neighbours = obstack_finish(&it->obst);
 168 }
 169
 170 static ir_node *get_next_neighbour(adj_iter_t *it) {
 171         ir_node *res = NULL;
 172
 173         if(it->curr < it->degree)
 174                 res = it->neighbours[it->curr++];
 175
 176         if(it->curr >= it->degree && it->neighbours) {
 177                 obstack_free(&it->obst, NULL);
 178                 it->neighbours = NULL;
 179         }
 180
 181         return res;
 182 }
 183
 184 static ir_node *ifg_std_neighbours_begin(const void *self, void *iter, const ir_node *irn)
 185 {
 186         find_neighbours(self, iter, irn, 1);
 187         return get_next_neighbour(iter);
 188 }
 189
 190 static ir_node *ifg_std_neighbours_next(const void *self, void *iter)
 191 {
 192         return get_next_neighbour(iter);
 193 }
 194
 195 static int ifg_std_degree(const void *self, const ir_node *irn)
 196 {
 197         adj_iter_t it;
 198         find_neighbours(self, &it, irn, 0);
 199         return it.degree;
 200 }
 201
 202 static const be_ifg_impl_t ifg_std_impl = {
 203         MAX(sizeof(adj_iter_t), sizeof(nodes_iter_t)),
 204         ifg_std_free,
 205         ifg_std_connected,
 206         ifg_std_neighbours_begin,
 207         ifg_std_neighbours_next,
 208         ifg_std_nodes_begin,
 209         ifg_std_nodes_next,
 210         ifg_std_degree
 211 };
 212
 213 be_ifg_t *be_ifg_std_new(const be_chordal_env_t *env)
 214 {
 215         ifg_std_t *ifg = malloc(sizeof(*ifg));
 216
 217         ifg->impl = &ifg_std_impl;
 218         ifg->env  = env;
 219
 220         return (be_ifg_t *) ifg;
 221 }