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

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