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