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