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