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