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