nsz Git - libfirm/blob - ir/common/firmwalk.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/common/firmwalk.c
   4  * Purpose:     Walker that touches all Firm data structures
   5  * Author:      Sebastian Felis
   6  * Modified by:
   7  * Created:     7.2003
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2003 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifdef HAVE_CONFIG_H
  14 # include "config.h"
  15 #endif
  16
  17 #ifdef HAVE_STRING_H
  18 # include <string.h>
  19 #endif
  20
  21 #include "firmwalk.h"
  22
  23 #include "entity_t.h"
  24 #include "irnode_t.h"
  25 #include "irprog_t.h"
  26 #include "irgwalk.h"
  27 #include "irtools.h"
  28
  29 #include "array.h"
  30 #include "obst.h"
  31 #include "pmap.h"
  32
  33 /** obstack for firm walker */
  34 static struct obstack fw_obst;
  35
  36 /** This map stores all types of firm */
  37 static pmap *mode_map = NULL;
  38 /** This map stores all types of firm */
  39 static pmap *type_map = NULL;
  40 /** This map stores all entities of firm */
  41 static pmap *entity_map = NULL;
  42
  43 /** Internal data structure of firm walker to collect
  44  *  some information of firm ir. The collected data will be stored
  45  *  into the link field of ir node. All graphs have a list of its
  46  *  blocks and all blocks have a list of their nodes. */
  47 typedef struct {
  48   ir_node **list; /**< List of blocks or nodes */
  49   void *link;     /**< Public link field. The public link field of firm nodes
  50                        is wrapped by set_firm_walk_link and
  51                        get_firm_walk_link. */
  52 } fw_data;
  53
  54 /*@{ */
  55 /** Access macros to fw_data structure */
  56 #define FW_GET_DATA_LIST(s)     ((s)->list)
  57 #define FW_SET_DATA_LIST(s, t)  ((s)->list = (t))
  58 #define FW_GET_DATA_LINK(s)     ((s)->link)
  59 #define FW_SET_DATA_LINK(s, t)  ((s)->link = (t))
  60 /*@} */
  61
  62 /** Returns own data struct of the firm walker.
  63  *
  64  *  If no structure defined (firm link is NULL) allocate a new
  65  *  struct to the fgd obstack. Only ir graph and block nodes
  66  *  will allocate this structure.
  67  *  - ir graph collect its block
  68  *  - block collect its nodes
  69  */
  70 static
  71 fw_data *fw_get_data(void *thing)
  72 {
  73   fw_data *data = NULL;
  74
  75   assert(thing);
  76   switch (get_kind(thing)) {
  77   case k_ir_graph:
  78     data = get_irg_link(thing);
  79     /* init block list of graph */
  80     if (NULL == data)
  81     {
  82       /* allocate new firm walk structure */
  83       data = obstack_alloc(&fw_obst, sizeof(fw_data));
  84       memset(data, 0, sizeof(fw_data));
  85       set_irg_link(thing, data);
  86       /* allocate block list */
  87       FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
  88     }
  89     break;
  90   case k_ir_node:
  91     /* init node list of block */
  92     if (is_Block(thing))
  93     {
  94       data = get_irn_link(thing);
  95       if (NULL == data)
  96       {
  97         /* allocate new firm walk structure */
  98         data = obstack_alloc(&fw_obst, sizeof(fw_data));
  99         memset(data, 0, sizeof(fw_data));
 100         set_irn_link(thing, data);
 101         /* allocate node list */
 102         FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
 103       }
 104     }
 105     break;
 106   default: {} /*  other kinds of firm nodes */
 107   }
 108
 109   return data;
 110 }
 111
 112 /** Free all collected data in ir graphs and nodes.
 113  *  An ir graph or an ir block node has a list as a
 114  *  dynamic array, which will be deleted here.  */
 115 static
 116 void fw_free_data(void *thing)
 117 {
 118   fw_data *data = NULL;
 119
 120   assert(thing);
 121
 122   switch (get_kind(thing)) {
 123   case k_ir_graph:
 124     data = get_irg_link(thing);
 125     /* delete block list of graph */
 126     if (NULL != data)
 127     {
 128       DEL_ARR_F(FW_GET_DATA_LIST(data));
 129       set_irg_link(thing, NULL);
 130     }
 131     break;
 132   case k_ir_node:
 133     /* delete node list of block */
 134     if (is_Block(thing))
 135     {
 136       data = get_irn_link(thing);
 137       if (NULL != data)
 138       {
 139         DEL_ARR_F(FW_GET_DATA_LIST(data));
 140         set_irn_link(thing, NULL);
 141       }
 142     }
 143     break;
 144   default: {} /*  other kinds of firm nodes */
 145   }
 146 }
 147
 148 /*  documentation in header file */
 149 void set_firm_walk_link(void *thing, void *link)
 150 {
 151   fw_data *data;
 152
 153   assert(thing);
 154   switch (get_kind(thing)) {
 155   case k_entity:
 156     set_entity_link(thing, link);
 157     break;
 158   case k_type:
 159     set_type_link(thing, link);
 160     break;
 161   case k_ir_graph:
 162     data = fw_get_data(thing);
 163     FW_SET_DATA_LINK(data, link);
 164     break;
 165   case k_ir_node:
 166     if (is_Block(thing))
 167     {
 168       data = fw_get_data(thing);
 169       FW_SET_DATA_LINK(data, link);
 170     }
 171     else
 172       set_irn_link(thing, link);
 173     break;
 174   case k_ir_mode:
 175     set_mode_link(thing, link);
 176     break;
 177   default: {} /*  other kinds of firm nodes */
 178   }
 179 }
 180
 181 /*  documentation in header file */
 182 void *get_firm_walk_link(void *thing)
 183 {
 184   fw_data *data;
 185   assert(thing);
 186   switch (get_kind(thing)) {
 187   case k_entity:
 188     return get_entity_link(thing);
 189   case k_type:
 190     return get_type_link(thing);
 191   case k_ir_graph:
 192     data = fw_get_data(thing);
 193     return FW_GET_DATA_LINK(data);
 194   case k_ir_node:
 195     if (is_Block(thing))
 196     {
 197       data = fw_get_data(thing);
 198       return FW_GET_DATA_LINK(data);
 199     }
 200     else
 201       return get_irn_link(thing);
 202   case k_ir_mode:
 203     return get_mode_link(thing);
 204   default:
 205     return NULL;
 206   }
 207 }
 208
 209 /** Fill maps of type and entity.
 210  *  This function will be called by the firm walk initializer
 211  *  to collect all types and entities of program's firm ir.
 212  *  All types will be collected in the hash table type_map
 213  *  and all entity are stored in entity_map. The mode of an
 214  *  type will be collected as well.
 215  *
 216  *  @param tore Type or entity
 217  *  @param env Environment pointer (currently unused)
 218  */
 219 static
 220 void fw_collect_tore(type_or_ent *tore, void *env)
 221 {
 222   ir_mode *mode;
 223   type *tp;
 224   entity *ent;
 225
 226   switch (get_kind(tore)) {
 227   case k_entity:
 228     ent = (entity *)tore;
 229     /*  append entity to list */
 230     set_entity_link(ent, NULL);
 231     if (!pmap_contains(entity_map, ent))
 232       pmap_insert(entity_map, ent, env);
 233     break;
 234   case k_type:
 235     tp = (type *)tore;
 236     mode = get_type_mode(tp);
 237     /*  append type to list */
 238     set_type_link(tp, NULL);
 239     if (!pmap_contains(type_map, tp))
 240       pmap_insert(type_map, tp, env);
 241
 242     /* insert only modes (non atomic types, i.e. class, array or struct
 243        have no mode. The link field will be cleared in the walk_do_mode()
 244        callback function. */
 245     if ((NULL != mode) && (!pmap_contains(mode_map, mode)))
 246       pmap_insert(mode_map, mode, env);
 247     break;
 248   default: break;
 249   }
 250 }
 251
 252 /** Collect all data from nodes. Block appends itself to
 253  *  the corresponding ir graph and other nodes appends itself
 254  *  to block list. Collects also the modes of each node to get
 255  *  non-type modes.
 256  *
 257  *  @param irn IR node pointer.
 258  *  @param env Environment pointer (currently unused)
 259  */
 260 static
 261 void fw_collect_irn(ir_node *irn, void *env)
 262 {
 263   fw_data *data;
 264   ir_mode *mode = get_irn_mode(irn);
 265
 266   /* The link field will be cleared in the walk_do_mode()
 267     callback function. */
 268   if ((NULL != mode) && (!pmap_contains(mode_map, mode)))
 269     pmap_insert(mode_map, mode, env);
 270
 271   /* block nodes. */
 272   if (is_Block(irn))
 273   {
 274     /* add this block to ir graph's block list */
 275     data = fw_get_data(get_current_ir_graph());
 276     ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
 277   }
 278   /* non block nodes */
 279   else
 280   {
 281     /* add this node to block's node list */
 282     ir_node *block = get_nodes_block(irn);
 283     data = fw_get_data(block);
 284     ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
 285   }
 286 }
 287
 288 /** Irg walker function to free all collected data from nodes */
 289 static
 290 void fw_free_colleted_data(ir_node *irn, void *env)
 291 {
 292   /* Free node list from blocks */
 293   if (is_Block(irn))
 294   {
 295     fw_free_data(irn);
 296   }
 297 }
 298
 299 /** Initialize all walking data.
 300  *
 301  *  Collect all specific data like types, entities, ir graphs, blocks, nodes
 302  *  from current firm structures.
 303  */
 304 void firm_walk_init(firm_walk_flags flags)
 305 {
 306   int i;
 307
 308   /* init obstack */
 309   obstack_init(&fw_obst);
 310
 311   /*  Init map of modes and lists of type and entity. If map or list
 312       allready exists, free it. */
 313   if (mode_map)
 314   {
 315     pmap_destroy(mode_map);
 316   }
 317   mode_map = pmap_create();
 318
 319   if (type_map)
 320   {
 321     pmap_destroy(type_map);
 322   }
 323   type_map = pmap_create();
 324
 325   if (entity_map)
 326   {
 327     pmap_destroy(entity_map);
 328   }
 329   entity_map = pmap_create();
 330
 331   /* insert internal modes to mode hash. The link field will be cleared
 332      in the walk_do_mode() callback function.
 333      Other used modes are added by collecting types */
 334
 335   /*
 336      ### RG: should be done by inspection the mode of all irn
 337
 338      pmap_insert(mode_map, mode_BB, NULL);
 339      pmap_insert(mode_map, mode_T, NULL);
 340      pmap_insert(mode_map, mode_ANY, NULL);
 341      pmap_insert(mode_map, mode_BAD, NULL);
 342      pmap_insert(mode_map, mode_X, NULL);
 343      pmap_insert(mode_map, mode_M, NULL);
 344      pmap_insert(mode_map, mode_b, NULL);
 345   */
 346
 347   /*  Collect all types (also unused types) if flag is set */
 348   if (FW_WITH_ALL_TYPES & flags)
 349     type_walk(fw_collect_tore, NULL, NULL);
 350
 351   /*  for each ir graph */
 352   for (i = 0; i < get_irp_n_irgs(); i++)
 353   {
 354     ir_graph *irg = get_irp_irg(i);
 355     set_irg_link(irg, NULL);
 356
 357     type_walk_irg(irg, fw_collect_tore, NULL, NULL);
 358
 359     irg_walk_graph(irg, firm_clear_link, fw_collect_irn, NULL);
 360   }
 361 }
 362
 363 /** This function should call after using the firm walker to free
 364  *  all collected data and frees the used obstack */
 365 void firm_walk_finalize(void)
 366 {
 367   int i;
 368
 369   /* free all used maps and lists */
 370   pmap_destroy(mode_map);
 371   mode_map = NULL;
 372   pmap_destroy(type_map);
 373   type_map = NULL;
 374   pmap_destroy(entity_map);
 375   entity_map = NULL;
 376
 377   /*  free all collected data from ir graphs and nodes */
 378   for (i = 0; i < get_irp_n_irgs(); i++)
 379   {
 380     ir_graph *irg = get_irp_irg(i);
 381     fw_free_data(irg);
 382     irg_walk_graph(get_irp_irg(i), NULL, fw_free_colleted_data, NULL);
 383   }
 384
 385   /* free obstack */
 386   obstack_free(&fw_obst, NULL);
 387 }
 388
 389 /** Dumps the firm ir.
 390  *
 391  *  After initializing the firm walker by calling firm_walk_init()
 392  *  the firm structure could be accessed by definign the firm walk interface
 393  *  wif. This function could be called serveral times to customize the
 394  *  walk order or definitions.
 395  *
 396  *  @param wif Walk interface which contains the callback function
 397  *
 398  *  @see firm_walk_interface */
 399 void firm_walk(firm_walk_interface *wif)
 400 {
 401   int irg_i, block_i, block_list_len, irn_i, irn_list_len;
 402   pmap_entry *entry;
 403   fw_data *data;
 404   ir_node *block, **block_list, **irn_list;
 405   ir_graph *saved_irg = current_ir_graph;
 406
 407   assert(wif && "firm_walk() in firmwalk.c: No walking interface defined!");
 408
 409   /* walk over all modes */
 410   if (wif->do_mode_init) wif->do_mode_init(wif->env);
 411   if (wif->do_mode)
 412   {
 413     for (entry = pmap_first(mode_map); entry; entry = pmap_next(mode_map))
 414     {
 415       set_mode_link((ir_mode*)entry->key, NULL);
 416       wif->do_mode(entry->key, wif->env);
 417     }
 418   }
 419   if (wif->do_mode_finalize) wif->do_mode_finalize(wif->env);
 420
 421   /* walk over all types */
 422   if (wif->do_type_init) wif->do_type_init(wif->env);
 423   if (wif->do_type)
 424   {
 425     for (entry = pmap_first(type_map); entry; entry = pmap_next(type_map))
 426       wif->do_type((type *)entry->key, wif->env);
 427   }
 428   if (wif->do_type_finalize) wif->do_type_finalize(wif->env);
 429
 430   /* walk over all entities */
 431   if (wif->do_entity_init) wif->do_entity_init(wif->env);
 432   if (wif->do_entity)
 433   {
 434     for (entry = pmap_first(entity_map); entry; entry = pmap_next(entity_map))
 435       wif->do_entity((entity *)entry->key, wif->env);
 436   }
 437   if (wif->do_entity_finalize) wif->do_entity_finalize(wif->env);
 438
 439
 440   /* Dump graphs ================================================= */
 441   if (wif->do_graph_init) wif->do_graph_init(wif->env);
 442
 443   for (irg_i = 0; irg_i < get_irp_n_irgs(); irg_i++)
 444   {
 445     current_ir_graph = get_irp_irg(irg_i);
 446
 447     /* walk over all ir graph */
 448     if (wif->do_graph) wif->do_graph(current_ir_graph, wif->env);
 449
 450     /* walk over all irg's block nested ========================== */
 451     data = fw_get_data(current_ir_graph);
 452     block_list = FW_GET_DATA_LIST(data);
 453     block_list_len = ARR_LEN(block_list);
 454     for (block_i = 0; block_i < block_list_len; block_i++)
 455     {
 456       if (wif->do_block_init) wif->do_block_init(current_ir_graph, wif->env);
 457
 458       block = (ir_node *)block_list[block_i];
 459       if (wif->do_block) wif->do_block(block, wif->env);
 460
 461       /* walk over all block's ir nodes nested =================== */
 462       data = fw_get_data(block);
 463       irn_list = FW_GET_DATA_LIST(data);
 464       irn_list_len = ARR_LEN(irn_list);
 465
 466       /*  call block as prefix ir node */
 467       if ((wif->do_node) &&
 468           (wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX)))
 469         wif->do_node(block, wif->env);
 470
 471       /*  do ir nodes in prefix or postfix order? */
 472       if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
 473         irn_i = irn_list_len-1;
 474       else
 475         irn_i = 0;
 476
 477       while (irn_i >= 0 && irn_i < irn_list_len)
 478       {
 479         if (wif->do_node) wif->do_node((ir_node *)irn_list[irn_i], wif->env);
 480
 481         /*  do ir nodes in prefix or postfix order? */
 482         if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
 483           irn_i--;
 484         else
 485           irn_i++;
 486       }
 487       /*  call block as postfix ir node */
 488       if ((wif->do_node) &&
 489           ((wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX))
 490            == FW_DUMP_BLOCK_AS_IRN))
 491         wif->do_node(block, wif->env);
 492
 493       /* wall over all block's ir nodes nested end =============== */
 494
 495       if(wif->do_block_post)
 496         wif->do_block_post(block, wif->env);
 497
 498     } /*  for each block */
 499
 500     if (wif->do_block_finalize)
 501       wif->do_block_finalize(current_ir_graph, wif->env);
 502
 503     /* walk over all irg's block nested end ====================== */
 504     if(wif->do_graph_post)
 505       wif->do_graph_post(current_ir_graph, wif->env);
 506
 507   } /*  for each ir graph irg */
 508
 509   if(wif->do_graph_finalize)
 510     wif->do_graph_finalize(wif->env);
 511
 512   /** ### ToDo: Dump const_code_irg ?? No! Dump const code with entities, types etc. */
 513
 514   /* restore the state of current_ir_graph */
 515   current_ir_graph = saved_irg;
 516 }