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