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

   1 /*
   2  * Copyright (C) 1995-2008 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 #include "config.h"
  28
  29 #ifdef HAVE_STRING_H
  30 # include <string.h>
  31 #endif
  32
  33 #include "firmwalk.h"
  34
  35 #include "entity_t.h"
  36 #include "irnode_t.h"
  37 #include "irprog_t.h"
  38 #include "irgwalk.h"
  39 #include "irtools.h"
  40
  41 #include "array.h"
  42 #include "obst.h"
  43 #include "pmap.h"
  44
  45 /** obstack for firm walker */
  46 static struct obstack fw_obst;
  47
  48 /** This map stores all types of firm */
  49 static pmap *type_map = NULL;
  50 /** This map stores all entities of firm */
  51 static pmap *entity_map = NULL;
  52
  53 /** Internal data structure of firm walker to collect
  54  *  some information of firm ir. The collected data will be stored
  55  *  into the link field of ir node. All graphs have a list of its
  56  *  blocks and all blocks have a list of their nodes. */
  57 typedef struct {
  58   ir_node **list; /**< List of blocks or nodes */
  59   void *link;     /**< Public link field. The public link field of firm nodes
  60                        is wrapped by set_firm_walk_link and
  61                        get_firm_walk_link. */
  62 } fw_data;
  63
  64 /*@{ */
  65 /** Access macros to fw_data structure */
  66 #define FW_GET_DATA_LIST(s)     ((s)->list)
  67 #define FW_SET_DATA_LIST(s, t)  ((s)->list = (t))
  68 #define FW_GET_DATA_LINK(s)     ((s)->link)
  69 #define FW_SET_DATA_LINK(s, t)  ((s)->link = (t))
  70 /*@} */
  71
  72 /** Returns own data struct of the firm walker.
  73  *
  74  *  If no structure defined (firm link is NULL) allocate a new
  75  *  struct to the fgd obstack. Only ir graph and block nodes
  76  *  will allocate this structure.
  77  *  - ir graph collect its block
  78  *  - block collect its nodes
  79  */
  80 static
  81 fw_data *fw_get_data(void *thing)
  82 {
  83   fw_data *data = NULL;
  84
  85   assert(thing);
  86   switch (get_kind(thing)) {
  87   case k_ir_graph:
  88     data = get_irg_link(thing);
  89     /* init block list of graph */
  90     if (NULL == data)
  91     {
  92       /* allocate new firm walk structure */
  93       data = obstack_alloc(&fw_obst, sizeof(fw_data));
  94       memset(data, 0, sizeof(fw_data));
  95       set_irg_link(thing, data);
  96       /* allocate block list */
  97       FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
  98     }
  99     break;
 100   case k_ir_node:
 101     /* init node list of block */
 102     if (is_Block(thing))
 103     {
 104       data = get_irn_link(thing);
 105       if (NULL == data)
 106       {
 107         /* allocate new firm walk structure */
 108         data = obstack_alloc(&fw_obst, sizeof(fw_data));
 109         memset(data, 0, sizeof(fw_data));
 110         set_irn_link(thing, data);
 111         /* allocate node list */
 112         FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
 113       }
 114     }
 115     break;
 116   default: {} /*  other kinds of firm nodes */
 117   }
 118
 119   return data;
 120 }
 121
 122 /** Free all collected data in ir graphs and nodes.
 123  *  An ir graph or an ir block node has a list as a
 124  *  dynamic array, which will be deleted here.  */
 125 static
 126 void fw_free_data(void *thing)
 127 {
 128   fw_data *data = NULL;
 129
 130   assert(thing);
 131
 132   switch (get_kind(thing)) {
 133   case k_ir_graph:
 134     data = get_irg_link(thing);
 135     /* delete block list of graph */
 136     if (NULL != data)
 137     {
 138       DEL_ARR_F(FW_GET_DATA_LIST(data));
 139       set_irg_link(thing, NULL);
 140     }
 141     break;
 142   case k_ir_node:
 143     /* delete node list of block */
 144     if (is_Block(thing))
 145     {
 146       data = get_irn_link(thing);
 147       if (NULL != data)
 148       {
 149         DEL_ARR_F(FW_GET_DATA_LIST(data));
 150         set_irn_link(thing, NULL);
 151       }
 152     }
 153     break;
 154   default: {} /*  other kinds of firm nodes */
 155   }
 156 }
 157
 158 /*  documentation in header file */
 159 void set_firm_walk_link(void *thing, void *link)
 160 {
 161   fw_data *data;
 162
 163   assert(thing);
 164   switch (get_kind(thing)) {
 165   case k_entity:
 166     set_entity_link(thing, link);
 167     break;
 168   case k_type:
 169     set_type_link(thing, link);
 170     break;
 171   case k_ir_graph:
 172     data = fw_get_data(thing);
 173     FW_SET_DATA_LINK(data, link);
 174     break;
 175   case k_ir_node:
 176     if (is_Block(thing))
 177     {
 178       data = fw_get_data(thing);
 179       FW_SET_DATA_LINK(data, link);
 180     }
 181     else
 182       set_irn_link(thing, link);
 183     break;
 184   case k_ir_mode:
 185     set_mode_link(thing, link);
 186     break;
 187   default: {} /*  other kinds of firm nodes */
 188   }
 189 }
 190
 191 /*  documentation in header file */
 192 void *get_firm_walk_link(void *thing)
 193 {
 194   fw_data *data;
 195   assert(thing);
 196   switch (get_kind(thing)) {
 197   case k_entity:
 198     return get_entity_link(thing);
 199   case k_type:
 200     return get_type_link(thing);
 201   case k_ir_graph:
 202     data = fw_get_data(thing);
 203     return FW_GET_DATA_LINK(data);
 204   case k_ir_node:
 205     if (is_Block(thing))
 206     {
 207       data = fw_get_data(thing);
 208       return FW_GET_DATA_LINK(data);
 209     }
 210     else
 211       return get_irn_link(thing);
 212   case k_ir_mode:
 213     return get_mode_link(thing);
 214   default:
 215     return NULL;
 216   }
 217 }
 218
 219 /** Fill maps of type and entity.
 220  *  This function will be called by the firm walk initializer
 221  *  to collect all types and entities of program's firm ir.
 222  *  All types will be collected in the hash table type_map
 223  *  and all entity are stored in entity_map. The mode of an
 224  *  type will be collected as well.
 225  *
 226  *  @param tore Type or entity
 227  *  @param env Environment pointer (currently unused)
 228  */
 229 static
 230 void fw_collect_tore(type_or_ent tore, void *env)
 231 {
 232   ir_type *tp;
 233   ir_entity *ent;
 234
 235   switch (get_kind(tore.ent)) {
 236   case k_entity:
 237     ent = tore.ent;
 238     /*  append entity to list */
 239     set_entity_link(ent, NULL);
 240     if (!pmap_contains(entity_map, ent))
 241       pmap_insert(entity_map, ent, env);
 242     break;
 243   case k_type:
 244     tp = tore.typ;
 245
 246     /*  append type to list */
 247     set_type_link(tp, NULL);
 248     if (!pmap_contains(type_map, tp))
 249       pmap_insert(type_map, tp, env);
 250     break;
 251   default: break;
 252   }
 253 }
 254
 255 /** Collect all data from nodes. Block appends itself to
 256  *  the corresponding ir graph and other nodes appends itself
 257  *  to block list. Collects also the modes of each node to get
 258  *  non-type modes.
 259  *
 260  *  @param irn IR node pointer.
 261  *  @param env Environment pointer (currently unused)
 262  */
 263 static
 264 void fw_collect_irn(ir_node *irn, void *env)
 265 {
 266   fw_data *data;
 267   (void) env;
 268
 269   /* block nodes. */
 270   if (is_Block(irn)) {
 271     /* add this block to ir graph's block list */
 272     data = fw_get_data(get_current_ir_graph());
 273     ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
 274   }
 275   /* non block nodes */
 276   else {
 277     /* add this node to block's node list */
 278     ir_node *block = get_nodes_block(irn);
 279     data = fw_get_data(block);
 280     ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
 281   }
 282 }
 283
 284 /** Irg walker function to free all collected data from nodes */
 285 static
 286 void fw_free_colleted_data(ir_node *irn, void *env)
 287 {
 288   (void) env;
 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 }