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 "typewalk.h"
  28 #include "irtools.h"
  29
  30 #include "array.h"
  31 #include "obst.h"
  32 #include "pmap.h"
  33
  34 /** obstack for firm walker */
  35 static struct obstack fw_obst;
  36
  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 /** Fill maps of type and entity.
 209  *  This function will be called by the firm walk initializer
 210  *  to collect all types and entities of program's firm ir.
 211  *  All types will be collected in the hash table type_map
 212  *  and all entity are stored in entity_map. The mode of an
 213  *  type will be collected as well.
 214  *
 215  *  @param tore Type or entity
 216  *  @param env Environment pointer (currently unused)
 217  */
 218 static
 219 void fw_collect_tore(type_or_ent *tore, void *env)
 220 {
 221   ir_type *tp;
 222   entity *ent;
 223
 224   switch (get_kind(tore)) {
 225   case k_entity:
 226     ent = (entity *)tore;
 227     /*  append entity to list */
 228     set_entity_link(ent, NULL);
 229     if (!pmap_contains(entity_map, ent))
 230       pmap_insert(entity_map, ent, env);
 231     break;
 232   case k_type:
 233     tp = (ir_type *)tore;
 234
 235     /*  append type to list */
 236     set_type_link(tp, NULL);
 237     if (!pmap_contains(type_map, tp))
 238       pmap_insert(type_map, tp, env);
 239     break;
 240   default: break;
 241   }
 242 }
 243
 244 /** Collect all data from nodes. Block appends itself to
 245  *  the corresponding ir graph and other nodes appends itself
 246  *  to block list. Collects also the modes of each node to get
 247  *  non-type modes.
 248  *
 249  *  @param irn IR node pointer.
 250  *  @param env Environment pointer (currently unused)
 251  */
 252 static
 253 void fw_collect_irn(ir_node *irn, void *env)
 254 {
 255   fw_data *data;
 256
 257   /* block nodes. */
 258   if (is_Block(irn)) {
 259     /* add this block to ir graph's block list */
 260     data = fw_get_data(get_current_ir_graph());
 261     ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
 262   }
 263   /* non block nodes */
 264   else {
 265     /* add this node to block's node list */
 266     ir_node *block = get_nodes_block(irn);
 267     data = fw_get_data(block);
 268     ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
 269   }
 270 }
 271
 272 /** Irg walker function to free all collected data from nodes */
 273 static
 274 void fw_free_colleted_data(ir_node *irn, void *env)
 275 {
 276   /* Free node list from blocks */
 277   if (is_Block(irn))
 278   {
 279     fw_free_data(irn);
 280   }
 281 }
 282
 283 /** Initialize all walking data.
 284  *
 285  *  Collect all specific data like types, entities, ir graphs, blocks, nodes
 286  *  from current firm structures.
 287  */
 288 void firm_walk_init(firm_walk_flags flags)
 289 {
 290   int i;
 291
 292   /* init obstack */
 293   obstack_init(&fw_obst);
 294
 295   /*  Init map of type and entity. If map or list
 296       already exists, free it. */
 297   if (type_map)
 298     pmap_destroy(type_map);
 299   type_map = pmap_create();
 300
 301   if (entity_map)
 302     pmap_destroy(entity_map);
 303   entity_map = pmap_create();
 304
 305   /*  Collect all types (also unused types) if flag is set */
 306   if (FW_WITH_ALL_TYPES & flags)
 307     type_walk(fw_collect_tore, NULL, NULL);
 308
 309   /*  for each ir graph */
 310   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 311     ir_graph *irg = get_irp_irg(i);
 312     set_irg_link(irg, NULL);
 313
 314     type_walk_irg(irg, fw_collect_tore, NULL, NULL);
 315
 316     irg_walk_graph(irg, firm_clear_link, fw_collect_irn, NULL);
 317   }
 318 }
 319
 320 /** This function should call after using the firm walker to free
 321  *  all collected data and frees the used obstack */
 322 void firm_walk_finalize(void)
 323 {
 324   int i;
 325
 326   /* free all used maps and lists */
 327   pmap_destroy(type_map);
 328   type_map = NULL;
 329   pmap_destroy(entity_map);
 330   entity_map = NULL;
 331
 332   /*  free all collected data from ir graphs and nodes */
 333   for (i = 0; i < get_irp_n_irgs(); i++)
 334   {
 335     ir_graph *irg = get_irp_irg(i);
 336     fw_free_data(irg);
 337     irg_walk_graph(get_irp_irg(i), NULL, fw_free_colleted_data, NULL);
 338   }
 339
 340   /* free obstack */
 341   obstack_free(&fw_obst, NULL);
 342 }
 343
 344 /** Dumps the firm ir.
 345  *
 346  *  After initializing the firm walker by calling firm_walk_init()
 347  *  the firm structure could be accessed by defining the firm walk interface
 348  *  wif. This function could be called several times to customize the
 349  *  walk order or definitions.
 350  *
 351  *  @param wif Walk interface which contains the callback function
 352  *
 353  *  @see firm_walk_interface */
 354 void firm_walk(firm_walk_interface *wif)
 355 {
 356   int mode_i, irg_i, block_i, block_list_len, irn_i, irn_list_len;
 357   pmap_entry *entry;
 358   fw_data *data;
 359   ir_node *block, **block_list, **irn_list;
 360   ir_graph *saved_irg = current_ir_graph;
 361
 362   assert(wif && "firm_walk() in firmwalk.c: No walking interface defined!");
 363
 364   /* walk over all modes */
 365   if (wif->do_mode_init) wif->do_mode_init(wif->env);
 366   if (wif->do_mode)
 367   {
 368     for (mode_i = get_irp_n_modes() - 1; mode_i >= 0; --mode_i)
 369       wif->do_mode(get_irp_mode(mode_i), wif->env);
 370   }
 371   if (wif->do_mode_finalize) wif->do_mode_finalize(wif->env);
 372
 373   /* walk over all types */
 374   if (wif->do_type_init) wif->do_type_init(wif->env);
 375   if (wif->do_type)
 376   {
 377     for (entry = pmap_first(type_map); entry; entry = pmap_next(type_map))
 378       wif->do_type((ir_type *)entry->key, wif->env);
 379   }
 380   if (wif->do_type_finalize) wif->do_type_finalize(wif->env);
 381
 382   /* walk over all entities */
 383   if (wif->do_entity_init) wif->do_entity_init(wif->env);
 384   if (wif->do_entity)
 385   {
 386     for (entry = pmap_first(entity_map); entry; entry = pmap_next(entity_map))
 387       wif->do_entity((entity *)entry->key, wif->env);
 388   }
 389   if (wif->do_entity_finalize) wif->do_entity_finalize(wif->env);
 390
 391
 392   /* Dump graphs ================================================= */
 393   if (wif->do_graph_init) wif->do_graph_init(wif->env);
 394
 395   for (irg_i = 0; irg_i < get_irp_n_irgs(); irg_i++)
 396   {
 397     current_ir_graph = get_irp_irg(irg_i);
 398
 399     /* walk over all ir graph */
 400     if (wif->do_graph) wif->do_graph(current_ir_graph, wif->env);
 401
 402     /* walk over all irg's block nested ========================== */
 403     data = fw_get_data(current_ir_graph);
 404     block_list = FW_GET_DATA_LIST(data);
 405     block_list_len = ARR_LEN(block_list);
 406     for (block_i = 0; block_i < block_list_len; block_i++)
 407     {
 408       if (wif->do_block_init) wif->do_block_init(current_ir_graph, wif->env);
 409
 410       block = (ir_node *)block_list[block_i];
 411       if (wif->do_block) wif->do_block(block, wif->env);
 412
 413       /* walk over all block's ir nodes nested =================== */
 414       data = fw_get_data(block);
 415       irn_list = FW_GET_DATA_LIST(data);
 416       irn_list_len = ARR_LEN(irn_list);
 417
 418       /*  call block as prefix ir node */
 419       if ((wif->do_node) &&
 420           (wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX)))
 421         wif->do_node(block, wif->env);
 422
 423       /*  do ir nodes in prefix or postfix order? */
 424       if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
 425         irn_i = irn_list_len-1;
 426       else
 427         irn_i = 0;
 428
 429       while (irn_i >= 0 && irn_i < irn_list_len)
 430       {
 431         if (wif->do_node) wif->do_node((ir_node *)irn_list[irn_i], wif->env);
 432
 433         /*  do ir nodes in prefix or postfix order? */
 434         if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
 435           irn_i--;
 436         else
 437           irn_i++;
 438       }
 439       /*  call block as postfix ir node */
 440       if ((wif->do_node) &&
 441           ((wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX))
 442            == FW_DUMP_BLOCK_AS_IRN))
 443         wif->do_node(block, wif->env);
 444
 445       /* wall over all block's ir nodes nested end =============== */
 446
 447       if(wif->do_block_post)
 448         wif->do_block_post(block, wif->env);
 449
 450     } /*  for each block */
 451
 452     if (wif->do_block_finalize)
 453       wif->do_block_finalize(current_ir_graph, wif->env);
 454
 455     /* walk over all irg's block nested end ====================== */
 456     if(wif->do_graph_post)
 457       wif->do_graph_post(current_ir_graph, wif->env);
 458
 459   } /*  for each ir graph irg */
 460
 461   if(wif->do_graph_finalize)
 462     wif->do_graph_finalize(wif->env);
 463
 464   /** ### ToDo: Dump const_code_irg ?? No! Dump const code with entities, types etc. */
 465
 466   /* restore the state of current_ir_graph */
 467   current_ir_graph = saved_irg;
 468 }