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