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