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 list stores all types of firm */
  21 static type **type_list = NULL;
  22 /** This list stores all entities of firm */
  23 static entity **entity_list = 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 FGD_GET_DATA_LIST(s)     ((s)->list)
  39 #define FGD_SET_DATA_LIST(s, t)  ((s)->list = (t))
  40 #define FGD_GET_DATA_LINK(s)     ((s)->link)
  41 #define FGD_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       FGD_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         FGD_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 static
  96 void fw_free_data(void *thing)
  97 {
  98   fw_data *data = NULL;
  99
 100   assert(thing);
 101
 102   switch (get_kind(thing)) {
 103   case k_ir_graph:
 104     data = get_irg_link(thing);
 105     /* delete block list of graph */
 106     if (NULL != data)
 107     {
 108       DEL_ARR_F(FGD_GET_DATA_LIST(data));
 109       set_irg_link(thing, NULL);
 110     }
 111     break;
 112   case k_ir_node:
 113     /* delete node list of block */
 114     if (is_Block(thing))
 115     {
 116       data = get_irn_link(thing);
 117       if (NULL != data)
 118       {
 119         DEL_ARR_F(FGD_GET_DATA_LIST(data));
 120         set_irn_link(thing, NULL);
 121       }
 122     }
 123     break;
 124   default: {} // other kinds of firm nodes
 125   }
 126 }
 127
 128 // documentation in header file
 129 void set_firm_walk_link(void *thing, void *link)
 130 {
 131   fw_data *data;
 132
 133   assert(thing);
 134   switch (get_kind(thing)) {
 135   case k_entity:
 136     set_entity_link(thing, link);
 137     break;
 138   case k_type:
 139     set_type_link(thing, link);
 140     break;
 141   case k_ir_graph:
 142     data = fw_get_data(thing);
 143     FGD_SET_DATA_LINK(data, link);
 144     break;
 145   case k_ir_node:
 146     if (is_Block(thing))
 147     {
 148       data = fw_get_data(thing);
 149       FGD_SET_DATA_LINK(data, link);
 150     }
 151     else
 152       set_irn_link(thing, link);
 153     break;
 154   case k_ir_mode:
 155     set_mode_link(thing, link);
 156     break;
 157   default: {} // other kinds of firm nodes
 158   }
 159 }
 160
 161 // documentation in header file
 162 void *get_firm_walk_link(void *thing)
 163 {
 164   fw_data *data;
 165   assert(thing);
 166   switch (get_kind(thing)) {
 167   case k_entity:
 168     return get_entity_link(thing);
 169   case k_type:
 170     return get_type_link(thing);
 171   case k_ir_graph:
 172     data = fw_get_data(thing);
 173     return FGD_GET_DATA_LINK(data);
 174   case k_ir_node:
 175     if (is_Block(thing))
 176     {
 177       data = fw_get_data(thing);
 178       return FGD_GET_DATA_LINK(data);
 179     }
 180     else
 181       return get_irn_link(thing);
 182   case k_ir_mode:
 183     return get_mode_link(thing);
 184   default:
 185     return NULL;
 186   }
 187 }
 188
 189 /** Set link field of a ir node to NULL */
 190 static
 191 void fw_clear_link(ir_node * node, void * env)
 192 {
 193   set_irn_link(node, NULL);
 194 }
 195
 196 /** Fill maps of type and entity
 197  *  This function will be called by the firm walk initializer
 198  *  to collect all types and entities of program's firm ir.
 199  *  All types will be colleced in the hash table type_map
 200  *  and all entity are stored in entity_map.
 201  *
 202  *  @param tore Type or entity
 203  *  @param env Environment pointer (currently unused)
 204  */
 205 static
 206 void fw_collect_tore(type_or_ent *tore, void *env)
 207 {
 208   ir_mode *mode;
 209   type *tp;
 210   entity *ent;
 211
 212   switch (get_kind(tore)) {
 213   case k_entity:
 214     ent = (entity *)tore;
 215     // append entity to list
 216     set_entity_link(ent, NULL);
 217     ARR_APP1(entity *, entity_list, ent);
 218     break;
 219   case k_type:
 220     tp = (type *)tore;
 221     mode = get_type_mode(tp);
 222     // append type to list
 223     set_type_link(tp, NULL);
 224     ARR_APP1(type *, type_list, tp);
 225
 226     /* insert only modes (non atomic types, i.e. class, array or struct
 227        have no mode. The link field will be cleared in the walk_do_mode()
 228        callback function. */
 229     if ((NULL != mode) && (!pmap_contains(mode_map, mode)))
 230       pmap_insert(mode_map, mode, env);
 231     break;
 232   default: break;
 233   }
 234 }
 235
 236 /** Collect all data from nodes. Block appends itself to
 237  *  the corresponding ir graph and other nodes appends itself
 238  *  to block list.
 239  *
 240  *  @param irn IR node pointer.
 241 f *  @param env Environment pointer (currently unused)
 242  */
 243 static
 244 void fw_collect_irn(ir_node *irn, void *env)
 245 {
 246   fw_data *data;
 247   /* block nodes. */
 248   if (is_Block(irn))
 249   {
 250     /* add this block to ir graph's block list */
 251     data = fw_get_data(get_current_ir_graph());
 252     ARR_APP1(ir_node *, FGD_GET_DATA_LIST(data), irn);
 253   }
 254   /* non block nodes */
 255   else
 256   {
 257     /* add this node to block's node list */
 258     ir_node *block = get_nodes_Block(irn);
 259     data = fw_get_data(block);
 260     ARR_APP1(ir_node *, FGD_GET_DATA_LIST(data), irn);
 261   }
 262 }
 263
 264 /** Irg walker function to free all collected data from nodes */
 265 static
 266 void fw_free_colleted_data(ir_node *irn, void *env)
 267 {
 268   /* Free node list from blocks */
 269   if (is_Block(irn))
 270   {
 271     fw_free_data(irn);
 272   }
 273 }
 274
 275 /** Initialize all walking data.
 276  *
 277  *  Collect all specific data like types, entities, ir graphs, blocks, nodes
 278  *  from current firm structures.
 279  */
 280 void firm_walk_init(firm_walk_flags flags)
 281 {
 282   int i;
 283
 284   /* init obstack */
 285   obstack_init(&fw_obst);
 286
 287   /*  Init map of modes and lists of type and entity. If map or list
 288       allready exists, free it. */
 289   if (mode_map)
 290   {
 291     pmap_destroy(mode_map);
 292   }
 293   mode_map = pmap_create();
 294
 295   if (type_list)
 296   {
 297     DEL_ARR_F(type_list);
 298   }
 299   type_list = NEW_ARR_F(type *, 0);
 300
 301   if (entity_list)
 302   {
 303     DEL_ARR_F(entity_list);
 304   }
 305   entity_list = NEW_ARR_F(entity *, 0);
 306
 307   /* insert internal modes to mode hash. The link field will be cleared
 308      in the walk_do_mode() callback function.
 309      Other used modes are added by collecting types */
 310   pmap_insert(mode_map, mode_BB, NULL);
 311   pmap_insert(mode_map, mode_T, NULL);
 312   pmap_insert(mode_map, mode_ANY, NULL);
 313   pmap_insert(mode_map, mode_BAD, NULL);
 314   pmap_insert(mode_map, mode_X, NULL);
 315   pmap_insert(mode_map, mode_M, NULL);
 316   pmap_insert(mode_map, mode_b, NULL);
 317
 318   // Collect all types (also unused types) if flag is set
 319   if (FGD_WITH_ALL_TYPES & flags)
 320     type_walk(fw_collect_tore, NULL, NULL);
 321
 322   // for each ir graph
 323   for (i = 0; i < get_irp_n_irgs(); i++)
 324   {
 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, fw_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(mode_map);
 342   mode_map = NULL;
 343   DEL_ARR_F(type_list);
 344   type_list = NULL;
 345   DEL_ARR_F(entity_list);
 346   entity_list = NULL;
 347
 348   // free all collected data from ir graphs and nodes
 349   for (i = 0; i < get_irp_n_irgs(); i++)
 350   {
 351     ir_graph *irg = get_irp_irg(i);
 352     fw_free_data(irg);
 353     irg_walk_graph(get_irp_irg(i), NULL, fw_free_colleted_data, NULL);
 354   }
 355
 356   /* free obstack */
 357   obstack_free(&fw_obst, NULL);
 358 }
 359
 360 /** Dumps the firm ir.
 361  *
 362  *  After initializing the firm walker by calling firm_walk_init()
 363  *  the firm structure could be accessed by definign the firm walk interface
 364  *  wif. This function could be called serveral times to customize the
 365  *  walk order or definitions.
 366  *
 367  *  @param wif Walk interface which contains the callback function
 368  *
 369  *  @see firm_walk_interface */
 370 void firm_walk(firm_walk_interface *wif)
 371 {
 372   int irg_i, block_i, block_list_len, irn_i, irn_list_len;
 373   pmap_entry *entry;
 374   fw_data *data;
 375   ir_graph *irg;
 376   ir_node *block, **block_list, **irn_list;
 377
 378   assert(wif && "firm_walk() in firmwalk.c: No walking interface defined!");
 379
 380   /* walk over all modes */
 381   if (wif->do_mode_init) wif->do_mode_init(wif->env);
 382   if (wif->do_mode)
 383   {
 384     for (entry = pmap_first(mode_map); entry; entry = pmap_next(mode_map))
 385     {
 386       set_mode_link((ir_mode*)entry->key, NULL);
 387       wif->do_mode(entry->key, wif->env);
 388     }
 389   }
 390   if (wif->do_mode_finalize) wif->do_mode_finalize(wif->env);
 391
 392   /* walk over all types */
 393   if (wif->do_type_init) wif->do_type_init(wif->env);
 394   if (wif->do_type)
 395   {
 396     int type_i, type_list_len = ARR_LEN(type_list);
 397     for (type_i = 0; type_i < type_list_len; type_i++)
 398       wif->do_type(type_list[type_i], wif->env);
 399   }
 400   if (wif->do_type_finalize) wif->do_type_finalize(wif->env);
 401
 402   /* walk over all entities */
 403   if (wif->do_entity_init) wif->do_entity_init(wif->env);
 404   if (wif->do_entity)
 405   {
 406     int entity_i, entity_list_len = ARR_LEN(entity_list);
 407     for (entity_i = 0; entity_i < entity_list_len; entity_i++)
 408       wif->do_entity(entity_list[entity_i], wif->env);
 409   }
 410   if (wif->do_entity_finalize) wif->do_entity_finalize(wif->env);
 411
 412
 413   /* Dump graphs ================================================= */
 414   if (wif->do_graph_init) wif->do_graph_init(wif->env);
 415
 416   for (irg_i = 0; irg_i < get_irp_n_irgs(); irg_i++)
 417   {
 418     irg = get_irp_irg(irg_i);
 419
 420     /* walk over all ir graph */
 421     if (wif->do_graph) wif->do_graph(irg, wif->env);
 422
 423     /* walk over all irg's block nested ========================== */
 424     data = fw_get_data(irg);
 425     block_list = FGD_GET_DATA_LIST(data);
 426     block_list_len = ARR_LEN(block_list);
 427     for (block_i = 0; block_i < block_list_len; block_i++)
 428     {
 429       if (wif->do_block_init) wif->do_block_init(irg, wif->env);
 430
 431       block = (ir_node *)block_list[block_i];
 432       if (wif->do_block) wif->do_block(block, wif->env);
 433
 434       /* walk over all block's ir nodes nested =================== */
 435       data = fw_get_data(block);
 436       irn_list = FGD_GET_DATA_LIST(data);
 437       irn_list_len = ARR_LEN(irn_list);
 438
 439       // call block as prefix ir node
 440       if ((wif->do_node) &&
 441           (wif->flags & FGD_DUMP_BLOCK_AS_IRN & !FGD_DUMP_IRN_IN_PREFIX))
 442         wif->do_node(block, wif->env);
 443
 444       // do ir nodes in prefix or postfix order?
 445       if (wif->flags & FGD_DUMP_IRN_IN_PREFIX)
 446         irn_i = irn_list_len-1;
 447       else
 448         irn_i = 0;
 449
 450       while (irn_i >= 0 && irn_i < irn_list_len)
 451       {
 452         if (wif->do_node) wif->do_node((ir_node *)irn_list[irn_i], wif->env);
 453
 454         // do ir nodes in prefix or postfix order?
 455         if (wif->flags & FGD_DUMP_IRN_IN_PREFIX)
 456           irn_i--;
 457         else
 458           irn_i++;
 459       }
 460       // call block as postfix ir node
 461       if ((wif->do_node) &&
 462           (wif->flags & (FGD_DUMP_BLOCK_AS_IRN | FGD_DUMP_IRN_IN_PREFIX)))
 463         wif->do_node(block, wif->env);
 464
 465       /* wall over all block's ir nodes nested end =============== */
 466
 467       if (wif->do_block_finalize) wif->do_block_finalize(irg, wif->env);
 468     } // for each block
 469
 470     /* walk over all irg's block nested end ====================== */
 471
 472   } // for each ir graph irg
 473   if (wif->do_graph_finalize) wif->do_graph_finalize(wif->env);
 474
 475   /** ### ToDo: Dump const_code_irg ?? */
 476 }