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
 270   /* block nodes. */
 271   if (is_Block(irn)) {
 272     /* add this block to ir graph's block list */
 273     data = fw_get_data(get_current_ir_graph());
 274     ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
 275   }
 276   /* non block nodes */
 277   else {
 278     /* add this node to block's node list */
 279     ir_node *block = get_nodes_block(irn);
 280     data = fw_get_data(block);
 281     ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
 282   }
 283 }
 284
 285 /** Irg walker function to free all collected data from nodes */
 286 static
 287 void fw_free_colleted_data(ir_node *irn, void *env)
 288 {
 289   /* Free node list from blocks */
 290   if (is_Block(irn))
 291   {
 292     fw_free_data(irn);
 293   }
 294 }
 295
 296 /** Initialize all walking data.
 297  *
 298  *  Collect all specific data like types, entities, ir graphs, blocks, nodes
 299  *  from current firm structures.
 300  */
 301 void firm_walk_init(firm_walk_flags flags)
 302 {
 303   int i;
 304
 305   /* init obstack */
 306   obstack_init(&fw_obst);
 307
 308   /*  Init map of type and entity. If map or list
 309       already exists, free it. */
 310   if (type_map)
 311     pmap_destroy(type_map);
 312   type_map = pmap_create();
 313
 314   if (entity_map)
 315     pmap_destroy(entity_map);
 316   entity_map = pmap_create();
 317
 318   /*  Collect all types (also unused types) if flag is set */
 319   if (FW_WITH_ALL_TYPES & flags)
 320     type_walk(fw_collect_tore, NULL, NULL);
 321
 322   /*  for each ir graph */
 323   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 324     ir_graph *irg = get_irp_irg(i);
 325     set_irg_link(irg, NULL);
 326
 327     type_walk_irg(irg, fw_collect_tore, NULL, NULL);
 328
 329     irg_walk_graph(irg, firm_clear_link, fw_collect_irn, NULL);
 330   }
 331 }
 332
 333 /** This function should call after using the firm walker to free
 334  *  all collected data and frees the used obstack */
 335 void firm_walk_finalize(void)
 336 {
 337   int i;
 338
 339   /* free all used maps and lists */
 340   pmap_destroy(type_map);
 341   type_map = NULL;
 342   pmap_destroy(entity_map);
 343   entity_map = NULL;
 344
 345   /*  free all collected data from ir graphs and nodes */
 346   for (i = 0; i < get_irp_n_irgs(); i++)
 347   {
 348     ir_graph *irg = get_irp_irg(i);
 349     fw_free_data(irg);
 350     irg_walk_graph(get_irp_irg(i), NULL, fw_free_colleted_data, NULL);
 351   }
 352
 353   /* free obstack */
 354   obstack_free(&fw_obst, NULL);
 355 }
 356
 357 /** Dumps the firm ir.
 358  *
 359  *  After initializing the firm walker by calling firm_walk_init()
 360  *  the firm structure could be accessed by defining the firm walk interface
 361  *  wif. This function could be called several times to customize the
 362  *  walk order or definitions.
 363  *
 364  *  @param wif Walk interface which contains the callback function
 365  *
 366  *  @see firm_walk_interface */
 367 void firm_walk(firm_walk_interface *wif)
 368 {
 369   int mode_i, irg_i, block_i, block_list_len, irn_i, irn_list_len;
 370   pmap_entry *entry;
 371   fw_data *data;
 372   ir_node *block, **block_list, **irn_list;
 373   ir_graph *saved_irg = current_ir_graph;
 374
 375   assert(wif && "firm_walk() in firmwalk.c: No walking interface defined!");
 376
 377   /* walk over all modes */
 378   if (wif->do_mode_init) wif->do_mode_init(wif->env);
 379   if (wif->do_mode)
 380   {
 381     for (mode_i = get_irp_n_modes() - 1; mode_i >= 0; --mode_i)
 382       wif->do_mode(get_irp_mode(mode_i), wif->env);
 383   }
 384   if (wif->do_mode_finalize) wif->do_mode_finalize(wif->env);
 385
 386   /* walk over all types */
 387   if (wif->do_type_init) wif->do_type_init(wif->env);
 388   if (wif->do_type)
 389   {
 390     for (entry = pmap_first(type_map); entry; entry = pmap_next(type_map))
 391       wif->do_type((ir_type *)entry->key, wif->env);
 392   }
 393   if (wif->do_type_finalize) wif->do_type_finalize(wif->env);
 394
 395   /* walk over all entities */
 396   if (wif->do_entity_init) wif->do_entity_init(wif->env);
 397   if (wif->do_entity)
 398   {
 399     for (entry = pmap_first(entity_map); entry; entry = pmap_next(entity_map))
 400       wif->do_entity((ir_entity *)entry->key, wif->env);
 401   }
 402   if (wif->do_entity_finalize) wif->do_entity_finalize(wif->env);
 403
 404
 405   /* Dump graphs ================================================= */
 406   if (wif->do_graph_init) wif->do_graph_init(wif->env);
 407
 408   for (irg_i = 0; irg_i < get_irp_n_irgs(); irg_i++)
 409   {
 410     current_ir_graph = get_irp_irg(irg_i);
 411
 412     /* walk over all ir graph */
 413     if (wif->do_graph) wif->do_graph(current_ir_graph, wif->env);
 414
 415     /* walk over all irg's block nested ========================== */
 416     data = fw_get_data(current_ir_graph);
 417     block_list = FW_GET_DATA_LIST(data);
 418     block_list_len = ARR_LEN(block_list);
 419     for (block_i = 0; block_i < block_list_len; block_i++)
 420     {
 421       if (wif->do_block_init) wif->do_block_init(current_ir_graph, wif->env);
 422
 423       block = (ir_node *)block_list[block_i];
 424       if (wif->do_block) wif->do_block(block, wif->env);
 425
 426       /* walk over all block's ir nodes nested =================== */
 427       data = fw_get_data(block);
 428       irn_list = FW_GET_DATA_LIST(data);
 429       irn_list_len = ARR_LEN(irn_list);
 430
 431       /*  call block as prefix ir node */
 432       if ((wif->do_node) &&
 433           (wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX)))
 434         wif->do_node(block, wif->env);
 435
 436       /*  do ir nodes in prefix or postfix order? */
 437       if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
 438         irn_i = irn_list_len-1;
 439       else
 440         irn_i = 0;
 441
 442       while (irn_i >= 0 && irn_i < irn_list_len)
 443       {
 444         if (wif->do_node) wif->do_node((ir_node *)irn_list[irn_i], wif->env);
 445
 446         /*  do ir nodes in prefix or postfix order? */
 447         if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
 448           irn_i--;
 449         else
 450           irn_i++;
 451       }
 452       /*  call block as postfix ir node */
 453       if ((wif->do_node) &&
 454           ((wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX))
 455            == FW_DUMP_BLOCK_AS_IRN))
 456         wif->do_node(block, wif->env);
 457
 458       /* wall over all block's ir nodes nested end =============== */
 459
 460       if(wif->do_block_post)
 461         wif->do_block_post(block, wif->env);
 462
 463     } /*  for each block */
 464
 465     if (wif->do_block_finalize)
 466       wif->do_block_finalize(current_ir_graph, wif->env);
 467
 468     /* walk over all irg's block nested end ====================== */
 469     if(wif->do_graph_post)
 470       wif->do_graph_post(current_ir_graph, wif->env);
 471
 472   } /*  for each ir graph irg */
 473
 474   if(wif->do_graph_finalize)
 475     wif->do_graph_finalize(wif->env);
 476
 477   /** ### ToDo: Dump const_code_irg ?? No! Dump const code with entities, types etc. */
 478
 479   /* restore the state of current_ir_graph */
 480   current_ir_graph = saved_irg;
 481 }