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