nsz Git - libfirm/blob - ir/ir/iredges.c

   1 /**
   2  * Always available outs.
   3  * @author Sebastian Hack
   4  * @date 14.1.2005
   5  */
   6
   7 #ifdef HAVE_CONFIG_H
   8 #include "config.h"
   9 #endif
  10
  11 #include "irnode_t.h"
  12 #include "iredges_t.h"
  13 #include "irdump_t.h"
  14 #include "irprintf.h"
  15 #include "irhooks.h"
  16 #include "debug.h"
  17 #include "set.h"
  18
  19 static firm_dbg_module_t *dbg;
  20
  21 #if FIRM_EDGES_INPLACE
  22
  23 #define TIMES37(x) (((x) << 5) + ((x) << 2) + (x))
  24
  25 #define get_irn_out_list_head(irn) (&get_irn_out_info(irn)->outs)
  26
  27 static int edge_cmp(const void *p1, const void *p2, size_t len)
  28 {
  29         const ir_edge_t *e1 = p1;
  30         const ir_edge_t *e2 = p2;
  31         int res = e1->src == e2->src && e1->pos == e2->pos;
  32
  33         return !res;
  34 }
  35
  36 static INLINE unsigned edge_hash(const ir_edge_t *edge)
  37 {
  38         unsigned result = HASH_PTR(edge->src);
  39         result = TIMES37(result) + edge->pos;
  40         return result;
  41 }
  42
  43 /**
  44  * Initialize the out information for a graph.
  45  * @note Dead node elim can call this on an already initialized graph.
  46  */
  47 void edges_init_graph(ir_graph *irg)
  48 {
  49         if(edges_activated(irg)) {
  50                 irg_edge_info_t *info = _get_irg_edge_info(irg);
  51                 int amount = 2048;
  52
  53                 if(info->edges) {
  54                         amount = set_count(info->edges);
  55                         del_set(info->edges);
  56                 }
  57
  58                 info->edges = new_set(edge_cmp, amount);
  59         }
  60 }
  61
  62 void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir_graph *irg)
  63 {
  64         const char *msg = "";
  65
  66         if(!edges_activated(irg))
  67                 return;
  68
  69         assert(node_is_in_irgs_storage(irg, src) && "source not in irg");
  70
  71         /*
  72          * Only do something, if the old and new target differ.
  73          */
  74         if(tgt != old_tgt) {
  75                 int is_block_edge = is_Block(src);
  76                 set *edges = _get_irg_edge_info(irg)->edges;
  77                 ir_block_edge_t space;
  78                 ir_edge_t *templ = (ir_edge_t *) &space;
  79                 ir_edge_t *edge;
  80                 size_t size;
  81
  82     /*
  83      * This is scray, but:
  84      * If two entries in a set do not have the same size, they are
  85      * treated as unequal, ignoring the comparison function.
  86      * So, edges from blocks have extra storage (they are
  87      * ir_block_edge_t's).
  88      */
  89     size = is_block_edge ? sizeof(ir_block_edge_t) : sizeof(ir_edge_t);
  90
  91                 /* Initialize the edge template to search in the set. */
  92     memset(templ, 0, size);
  93 #ifdef DEBUG_libfirm
  94                 templ->src_nr = get_irn_node_nr(src);
  95 #endif
  96                 templ->src = src;
  97                 templ->pos = pos;
  98                 templ->invalid = 0;
  99                 templ->present = 0;
 100
 101                 /*
 102                  * If the target is NULL, the edge shall be deleted.
 103                  */
 104                 if(tgt == NULL) {
 105                         /* search the edge in the set. */
 106                         edge = set_find(edges, templ, size, edge_hash(templ));
 107
 108                         /* mark the edge invalid if it was found */
 109                         if(edge) {
 110         ir_block_edge_t *block_edge = (ir_block_edge_t *) edge;
 111
 112                                 msg = "deleting";
 113                                 list_del(&edge->list);
 114                                 edge->invalid = 1;
 115                                 edge->pos = -2;
 116                                 edge->src = NULL;
 117
 118         /*
 119          * If the edge is a cf edge, we delete it also
 120          * from the list of all block successor edges.
 121          */
 122         if(is_block_edge)
 123           list_del(&block_edge->succ_list);
 124                         }
 125
 126                         /* If the edge was not found issue a warning on the debug stream */
 127                         else {
 128                                 msg = "edge to delete not found!\n";
 129                         }
 130                 } /* if */
 131
 132                 /*
 133                  * The target is not NULL and the old target differs
 134                  * from the new target, the edge shall be moved (if the
 135                  * old target was != NULL) or added (if the old target was
 136                  * NULL).
 137                  */
 138                 else {
 139                         struct list_head *head = _get_irn_outs_head(tgt);
 140
 141       /*
 142        * The list head in the block of the edges target.
 143        * Therein all control flow edges directed at that block
 144        * are recorded.
 145        */
 146       struct list_head *succ_head =
 147         is_block_edge ? _get_block_succ_head(get_nodes_block(tgt)) : NULL;
 148
 149       ir_block_edge_t *block_edge;
 150
 151                         if(!node_is_in_irgs_storage(irg, tgt))
 152                                 return;
 153
 154                         assert(head->next && head->prev &&
 155                                         "target list head must have been initialized");
 156
 157                         /*
 158                          * insert the edge, if it is not yet in the set or return
 159                          * the instance in the set.
 160                          */
 161                         edge = set_insert(edges, templ, size, edge_hash(templ));
 162       block_edge = (ir_block_edge_t *) edge;
 163
 164 #ifdef DEBUG_libfirm
 165                         assert(!edge->invalid && "Invalid edge encountered");
 166 #endif
 167
 168                         /* If the old target is not null, the edge is moved. */
 169                         if(old_tgt) {
 170                                 msg = "redirecting";
 171                                 list_move(&edge->list, head);
 172
 173         /* If the edge is a cf edge, move it from the successor list. */
 174         if(is_block_edge)
 175           list_move(&block_edge->succ_list, succ_head);
 176
 177                                 _get_irn_edge_info(old_tgt)->out_count -= 1;
 178                         }
 179
 180                         /* The old target was null, thus, the edge is newly created. */
 181                         else {
 182                                 msg = "adding";
 183                                 list_add(&edge->list, head);
 184
 185         /*
 186          * If the edge is cf edge, enter it into the successor list
 187          * of the target node's block.
 188          */
 189         if(is_block_edge)
 190           list_add(&block_edge->succ_list, succ_head);
 191                         }
 192
 193                         _get_irn_edge_info(tgt)->out_count += 1;
 194                 } /* else */
 195         }
 196
 197         /* If the target and the old target are equal, nothing is done. */
 198         DBG((dbg, LEVEL_5, "announce out edge: %n[%p] %d-> %n[%p](%n[%p]): %s\n",
 199                                 src, src, pos, tgt, tgt, old_tgt, old_tgt, msg));
 200 }
 201
 202 void edges_node_deleted(ir_node *old, ir_graph *irg)
 203 {
 204         if(edges_activated(irg)) {
 205                 int not_a_block = !is_Block(old);
 206                 ir_edge_t templ;
 207                 int i, n;
 208
 209                 templ.src = old;
 210                 DBG((dbg, LEVEL_5, "node deleted: %n\n", old));
 211
 212                 /* Change to get_irn_n */
 213                 for(i = -not_a_block, n = get_irn_arity(old); i < n; ++i) {
 214                         ir_node *old_tgt = get_irn_n(old, i);
 215                         DBG((dbg, LEVEL_5, "\tdelete to old target %n\n", old_tgt));
 216                         edges_notify_edge(old, i, NULL, old_tgt, irg);
 217                 }
 218
 219         }
 220 }
 221
 222 void edges_invalidate(ir_node *irn, ir_graph *irg)
 223 {
 224         edges_node_deleted(irn, irg);
 225 }
 226
 227 static void build_edges_walker(ir_node *irn, void *data)
 228 {
 229         ir_graph *irg = data;
 230         int not_a_block = !is_Block(irn);
 231         int i, n;
 232
 233         for(i = -not_a_block, n = get_irn_arity(irn); i < n; ++i)
 234                 edges_notify_edge(irn, i, get_irn_n(irn, i), NULL, irg);
 235 }
 236
 237 static void init_lh_walker(ir_node *irn, void *data)
 238 {
 239         INIT_LIST_HEAD(_get_irn_outs_head(irn));
 240         if(is_Block(irn))
 241                 INIT_LIST_HEAD(_get_block_succ_head(irn));
 242 }
 243
 244 void edges_activate(ir_graph *irg)
 245 {
 246         irg_edge_info_t *info = _get_irg_edge_info(irg);
 247
 248         info->activated = 1;
 249         edges_init_graph(irg);
 250         irg_walk_graph(irg, init_lh_walker, build_edges_walker, irg);
 251 }
 252
 253 void edges_deactivate(ir_graph *irg)
 254 {
 255         irg_edge_info_t *info = _get_irg_edge_info(irg);
 256
 257         info->activated = 0;
 258         if(info->edges) {
 259                 del_set(info->edges);
 260     info->edges = NULL;
 261   }
 262 }
 263
 264 int (edges_activated)(const ir_graph *irg)
 265 {
 266         return _edges_activated(irg);
 267 }
 268
 269
 270 /**
 271  * Reroute all use-edges from a node to another.
 272  * @param from The node whose use-edges shall be withdrawn.
 273  * @param to The node to which all the use-edges of @p from shall be
 274  * sent to.
 275  */
 276 void edges_reroute(ir_node *from, ir_node *to, ir_graph *irg)
 277 {
 278         if(edges_activated(irg)) {
 279                 struct list_head *head = _get_irn_outs_head(from);
 280
 281                 DBG((firm_dbg_register(DBG_EDGES), LEVEL_5,
 282                                         "reroute from %n to %n\n", from, to));
 283
 284                 while(head != head->next) {
 285                         ir_edge_t *edge = list_entry(head->next, ir_edge_t, list);
 286                         // DBG((dbg, LEVEL_5, "\t%n %d\n", edge->src, edge->pos));
 287                         assert(edge->pos >= -1);
 288                         set_irn_n(edge->src, edge->pos, to);
 289                 }
 290         }
 291 }
 292
 293 static void verify_set_presence(ir_node *irn, void *data)
 294 {
 295         ir_graph *irg = data;
 296         set *edges = _get_irg_edge_info(irg)->edges;
 297         int not_a_block = !is_Block(irn);
 298         int i, n;
 299
 300         for(i = 0, n = get_irn_arity(irn) + not_a_block; i < n; ++i) {
 301     ir_block_edge_t space;
 302                 ir_edge_t *templ = (ir_edge_t *) &space;
 303                 ir_edge_t *e;
 304     size_t size = not_a_block ? sizeof(ir_edge_t) : sizeof(ir_block_edge_t);
 305
 306                 templ->src = irn;
 307                 templ->pos = i - not_a_block;
 308
 309                 e = set_find(edges, templ, size, edge_hash(templ));
 310                 if(e != NULL)
 311                         e->present = 1;
 312                 else
 313                         DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is missing\n", irn, templ->pos));
 314         }
 315 }
 316
 317 static void verify_list_presence(ir_node *irn, void *data)
 318 {
 319         const ir_edge_t *e;
 320
 321         foreach_out_edge(irn, e) {
 322                 ir_node *tgt = get_irn_n(e->src, e->pos);
 323                 if(irn != tgt)
 324                         DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is no out edge of %n but of %n\n",
 325                                         e->src, e->pos, irn, tgt));
 326         }
 327
 328 }
 329
 330 void edges_verify(ir_graph *irg)
 331 {
 332         set *edges = _get_irg_edge_info(irg)->edges;
 333         ir_edge_t *e;
 334
 335         /* Clear the present bit in all edges available. */
 336         for(e = set_first(edges); e; e = set_next(edges))
 337                 e->present = 0;
 338
 339         irg_walk_graph(irg, verify_set_presence, verify_list_presence, irg);
 340
 341         /*
 342          * Dump all edges which are not invalid and not present.
 343          * These edges are superfluous and their presence in the
 344          * edge set is wrong.
 345          */
 346         for(e = set_first(edges); e; e = set_next(edges)) {
 347                 if(!e->invalid && !e->present)
 348                         DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is superfluous\n", e->src, e->pos));
 349         }
 350 }
 351
 352 void init_edges(void)
 353 {
 354         dbg = firm_dbg_register(DBG_EDGES);
 355         /* firm_dbg_set_mask(dbg, -1); */
 356 }
 357
 358
 359 const ir_edge_t *(get_irn_out_edge_first)(const ir_node *irn)
 360 {
 361         return _get_irn_out_edge_first(irn);
 362 }
 363
 364 const ir_edge_t *(get_irn_out_edge_next)(const ir_node *irn, const ir_edge_t *last)
 365 {
 366         return _get_irn_out_edge_next(irn, last);
 367 }
 368
 369 ir_node *(get_edge_src_irn)(const ir_edge_t *edge)
 370 {
 371         return _get_edge_src_irn(edge);
 372 }
 373
 374 int (get_edge_src_pos)(const ir_edge_t *edge)
 375 {
 376         return _get_edge_src_pos(edge);
 377 }
 378
 379 int (get_irn_n_edges)(const ir_node *irn)
 380 {
 381   return _get_irn_n_edges(irn);
 382 }
 383
 384
 385 #endif /* FIRM_EDGES_INPLACE */