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