nsz Git - libfirm/blob - ir/common/firmwalk.c

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