nsz Git - libfirm/blob - ir/stat/firmstat_t.h

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/stat/firmstat_t.h
   4  * Purpose:     Statistics for Firm. Internal data structures.
   5  * Author:      Michael Beck
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 2004 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11 #ifndef _FIRMSTAT_T_H_
  12 #define _FIRMSTAT_T_H_
  13
  14 /**
  15  * @file firmstat_t.h
  16  */
  17 #include "firmstat.h"
  18
  19 #include "irop_t.h"
  20 #include "irnode_t.h"
  21 #include "irgraph_t.h"
  22 #include "pset.h"
  23 #include "pdeq.h"
  24 #include "irprog.h"
  25 #include "irgwalk.h"
  26 #include "counter.h"
  27 #include "irhooks.h"
  28
  29 /* some useful macro. */
  30 #define ARR_SIZE(a)   (sizeof(a)/sizeof((a)[0]))
  31
  32 /*
  33  * just be make some things clear :-), the
  34  * poor man "generics"
  35  */
  36 #define HASH_MAP(type) hmap_##type
  37
  38 typedef pset hmap_node_entry_t;
  39 typedef pset hmap_graph_entry_t;
  40 typedef pset hmap_opt_entry_t;
  41 typedef pset hmap_block_entry_t;
  42 typedef pset hmap_be_block_entry_t;
  43 typedef pset hmap_reg_pressure_entry_t;
  44 typedef pset hmap_perm_stat_entry_t;
  45 typedef pset hmap_perm_class_entry_t;
  46 typedef pset hmap_ir_op;
  47 typedef pset hmap_distrib_entry_t;
  48
  49 /**
  50  * An entry in a distribution table
  51  */
  52 typedef struct _distrib_entry_t {
  53   counter_t      cnt;       /**< the current count */
  54   const void *object;   /**< the object which is counted */
  55 } distrib_entry_t;
  56
  57 /** The type of the hash function for objects in distribution tables. */
  58 typedef unsigned (*distrib_hash_fun)(const void *object);
  59
  60 /**
  61  * The distribution table.
  62  */
  63 typedef struct _distrib_tbl_t {
  64   struct obstack                cnts;       /**< obstack containing the distrib_entry_t entries */
  65   HASH_MAP(distrib_entry_t)     *hash_map;  /**< the hash map containing the distribution */
  66   distrib_hash_fun          hash_func;  /**< the hash function for object in this distribution */
  67   unsigned                  int_dist;   /**< non-zero, if it's a integer distribution */
  68 } distrib_tbl_t;
  69
  70 /**
  71  * possible address marker values
  72  */
  73 enum adr_marker_t {
  74   MARK_ADDRESS_CALC     = 1,    /**< the node is an address expression */
  75   MARK_REF_ADR          = 2,    /**< the node is referenced by an address expression */
  76   MARK_REF_NON_ADR      = 4,    /**< the node is referenced by a non-address expression */
  77 };
  78
  79 /**
  80  * An entry in the address_mark set
  81  */
  82 typedef struct _address_mark_entry_t {
  83   ir_node  *node;               /**< the node which this entry belongs to, needed for compare */
  84   unsigned mark;                /**< the mark, a bitmask of enum adr_marker_t */
  85 } address_mark_entry_t;
  86
  87 /**
  88  * An entry for ir_nodes, used in ir_graph statistics.
  89  */
  90 typedef struct _node_entry_t {
  91   counter_t   cnt_alive;    /**< amount of nodes in this entry */
  92   counter_t   new_node;     /**< amount of new nodes for this entry */
  93   counter_t   into_Id;      /**< amount of nodes that turned into Id's for this entry */
  94   const ir_op *op;          /**< the op for this entry */
  95 } node_entry_t;
  96
  97 enum leaf_call_state_t {
  98   LCS_UNKNOWN       = 0,      /**< state is unknown yet */
  99   LCS_LEAF_CALL     = 1,      /**< only leaf functions will be called */
 100   LCS_NON_LEAF_CALL = 2,      /**< at least one non-leaf function will be called or indetermined */
 101 };
 102
 103 /**
 104  * Graph counter indexes. The first one are accumulated once, the other are always deleted before an
 105  * snapshot is taken.
 106  */
 107 enum graph_counter_names {
 108   gcnt_acc_walked,               /**< walker walked over the graph, accumulated */
 109   gcnt_acc_walked_blocks,        /**< walker walked over the graph blocks, accumulated */
 110   gcnt_acc_was_inlined,          /**< number of times other graph were inlined, accumulated */
 111   gcnt_acc_got_inlined,          /**< number of times this graph was inlined, accumulated */
 112   gcnt_acc_strength_red,         /**< number of times strength reduction was successful on this graph, accumulated */
 113   gcnt_acc_real_func_call,       /**< number real function call optimization, accumulated */
 114
 115   /* --- non-accumulated values from here */
 116   _gcnt_non_acc,                 /**< first non-accumulated counter */
 117
 118   gcnt_edges = _gcnt_non_acc,    /**< number of DF edges in this graph */
 119   gcnt_all_calls,                /**< number of all calls */
 120   gcnt_call_with_cnst_arg,       /**< number of calls with const args */
 121   gcnt_indirect_calls,           /**< number of indirect calls */
 122   gcnt_pure_adr_ops,             /**< number of pure address operation */
 123   gcnt_all_adr_ops,              /**< number of all address operation */
 124   gcnt_global_adr,               /**< number of global load/store addresses. */
 125   gcnt_local_adr,                /**< number of local load/store addresses. */
 126   gcnt_param_adr,                /**< number of parameter load/store addresses. */
 127   gcnt_this_adr,                 /**< number of this load/store addresses. */
 128   gcnt_other_adr,                /**< number of other load/store addresses. */
 129   gcnt_if_conv,                  /**< number of if conversions */
 130
 131   /* --- must be the last enum constant --- */
 132   _gcnt_last = gcnt_if_conv + IF_RESULT_LAST                 /**< number of counters */
 133 };
 134
 135 /**
 136  * An entry for ir_graphs. These numbers are calculated for every IR graph.
 137  */
 138 typedef struct _graph_entry_t {
 139   struct obstack             recalc_cnts;                  /**< obstack containing the counters that are recalculated */
 140   HASH_MAP(node_entry_t)     *opcode_hash;                 /**< hash map containing the opcode counter */
 141   HASH_MAP(block_entry_t)    *block_hash;                  /**< hash map containing the block counter */
 142   HASH_MAP(block_entry_t)    *extbb_hash;                  /**< hash map containing the extended block counter */
 143   HASH_MAP(be_block_entry_t) *be_block_hash;               /**< hash map containing backend block information */
 144   counter_t                  cnt[_gcnt_last];               /**< counter */
 145   unsigned                   num_tail_recursion;           /**< number of tail recursion optimizations */
 146   HASH_MAP(opt_entry_t)      *opt_hash[FS_OPT_MAX];        /**< hash maps containing opcode counter for optimizations */
 147   ir_graph                   *irg;                         /**< the graph of this object */
 148   ir_entity                  *ent;                         /**< the entity of this graph if one exists */
 149   set                        *address_mark;                /**< a set containing the address marks of the nodes */
 150   unsigned                   is_deleted:1;                 /**< set if this irg was deleted */
 151   unsigned                   is_leaf:1;                    /**< set, if this irg is a leaf function */
 152   unsigned                   is_leaf_call:2;               /**< set, if this irg calls only leaf functions */
 153   unsigned                   is_recursive:1;               /**< set, if this irg has recursive calls */
 154   unsigned                   is_chain_call:1;              /**< set, if this irg is a chain call */
 155   unsigned                   is_analyzed:1;                /**< helper: set, if this irg was already analysed */
 156 } graph_entry_t;
 157
 158 /**
 159  * An entry for optimized ir_nodes
 160  */
 161 typedef struct _opt_entry_t {
 162   counter_t   count;    /**< optimization counter */
 163   const ir_op *op;      /**< the op for this entry */
 164 } opt_entry_t;
 165
 166 /**
 167  * An entry for register pressure.
 168  */
 169 typedef struct _reg_pressure_entry_t {
 170   const char *class_name; /**< name of the register class */
 171   int         pressure;   /**< the register pressure for this class */
 172 } reg_pressure_entry_t;
 173
 174 /**
 175  * An entry for permutation statistics.
 176  */
 177 typedef struct _perm_stat_entry_t {
 178   ir_node       *perm;       /**< the perm node */
 179   int            size;       /**< complete size */
 180   int            real_size;  /**< number of pairs with different registers */
 181   int            n_copies;   /**< number of copies created for lowering */
 182   int            n_exchg;    /**< number of exchanges created for lowering */
 183   distrib_tbl_t *cycles;     /**< distribution of cycle lengths */
 184   distrib_tbl_t *chains;     /**< distribution of chain lengths */
 185 } perm_stat_entry_t;
 186
 187 /**
 188  * An entry for permutation statistics per class.
 189  */
 190 typedef struct _perm_class_entry_t {
 191   const char                  *class_name; /**< name of the register class */
 192   int                          n_regs;     /**< number of register in this class */
 193   HASH_MAP(perm_stat_entry_t) *perm_stat;  /**< statistics about all perm nodes of this class */
 194 } perm_class_entry_t;
 195
 196 /**
 197  * An entry for a block or extended block in a ir-graph
 198  */
 199 typedef struct _be_block_entry_t {
 200   long                           block_nr;         /**< block nr */
 201   distrib_tbl_t                  *sched_ready;     /**< distribution of ready nodes per block */
 202   /**< the highest register pressures for this block for each register class */
 203   HASH_MAP(reg_pressure_entry_t) *reg_pressure;
 204   HASH_MAP(perm_class_entry_t)   *perm_class_stat; /**< statistics about perm nodes for each register class */
 205 } be_block_entry_t;
 206
 207 /**
 208  * Block counter indexes. The first one are accumulated once, the other are always deleted before an
 209  * snapshot is taken.
 210  */
 211 enum block_counter_names {
 212   bcnt_nodes,     /**< the counter of nodes in this block */
 213   bcnt_edges,     /**< the counter of edges in this block */
 214   bcnt_in_edges,  /**< the counter of edges incoming from other blocks to this block */
 215   bcnt_out_edges, /**< the counter of edges outgoing from this block to other blocks */
 216   bcnt_phi_data,  /**< the counter of data Phi nodes in this block */
 217
 218   /* --- must be the last enum constant --- */
 219   _bcnt_last      /**< number of counters */
 220 };
 221
 222 /**
 223  * An entry for a block or extended block in a ir-graph
 224  */
 225 typedef struct _block_entry_t {
 226   counter_t       cnt[_bcnt_last];  /**< counter */
 227   long            block_nr;         /**< block nr */
 228 } block_entry_t;
 229
 230 /** An entry for an extended block in a ir-graph */
 231 typedef block_entry_t extbb_entry_t;
 232
 233 /**
 234  * Some potential interesting float values
 235  */
 236 typedef enum _float_classify_t {
 237   STAT_FC_0,                /**< the float value 0.0 */
 238   STAT_FC_1,                /**< the float value 1.0 */
 239   STAT_FC_2,                /**< the float value 2.0 */
 240   STAT_FC_0_5,              /**< the float value 0.5 */
 241   STAT_FC_EXACT,            /**< an exact value */
 242   STAT_FC_OTHER,            /**< all other values */
 243   STAT_FC_MAX               /**< last value */
 244 } float_classify_t;
 245
 246 /**
 247  * constant info
 248  */
 249 typedef struct _constant_info_t {
 250   counter_t  int_bits_count[32];  /**< distribution of bit sizes of integer constants */
 251   counter_t  floats[STAT_FC_MAX]; /**< floating point constants */
 252   counter_t  others;              /**< all other constants */
 253 } constant_info_t;
 254
 255 /** forward */
 256 typedef struct _dumper_t dumper_t;
 257
 258 /**
 259  * handler for dumping an IRG
 260  *
 261  * @param dmp   the dumper
 262  * @param entry the IR-graph hash map entry
 263  */
 264 typedef void (*dump_graph_FUNC)(dumper_t *dmp, graph_entry_t *entry);
 265
 266 /**
 267  * handler for dumper init
 268  *
 269  * @param dmp   the dumper
 270  * @param name  name of the file to dump to
 271  */
 272 typedef void (*dump_init_FUNC)(dumper_t *dmp, const char *name);
 273
 274 /**
 275  * handler for dumper a constant info table
 276  *
 277  * @param dmp   the dumper
 278  */
 279 typedef void (*dump_const_table_FUNC)(dumper_t *dmp, const constant_info_t *tbl);
 280
 281 /**
 282  * handler for dumper finish
 283  *
 284  * @param dmp   the dumper
 285  */
 286 typedef void (*dump_finish_FUNC)(dumper_t *dmp);
 287
 288 /**
 289  * statistics info
 290  */
 291 typedef struct _statistic_info_t {
 292   unsigned                stat_options;   /**< statistic options: field must be first */
 293   struct obstack          cnts;           /**< obstack containing the counters that are incremented */
 294   struct obstack          be_data;        /**< obstack containing backend statistics data */
 295   HASH_MAP(graph_entry_t) *irg_hash;      /**< hash map containing the counter for irgs */
 296   HASH_MAP(ir_op)         *ir_op_hash;    /**< hash map containing all ir_ops (accessible by op_codes) */
 297   pdeq                    *wait_q;        /**< wait queue for leaf call decision */
 298   int                     recursive;      /**< flag for detecting recursive hook calls */
 299   int                     in_dead_node_elim;    /**< set, if dead node elimination runs */
 300   ir_op                   *op_Phi0;       /**< pseudo op for Phi0 */
 301   ir_op                   *op_PhiM;       /**< pseudo op for memory Phi */
 302   ir_op                   *op_ProjM;      /**< pseudo op for memory Proj */
 303   ir_op                   *op_MulC;       /**< pseudo op for multiplication by const */
 304   ir_op                   *op_DivC;       /**< pseudo op for division by const */
 305   ir_op                   *op_ModC;       /**< pseudo op for modulo by const */
 306   ir_op                   *op_DivModC;    /**< pseudo op for DivMod by const */
 307   ir_op                   *op_SelSel;     /**< pseudo op for Sel(Sel) */
 308   ir_op                   *op_SelSelSel;  /**< pseudo op for Sel(Sel(Sel)) */
 309   dumper_t                *dumper;        /**< list of dumper */
 310   int                     reassoc_run;    /**< if set, reassociation is running */
 311   constant_info_t         const_info;     /**< statistic info for constants */
 312 } stat_info_t;
 313
 314 /**
 315  * a dumper description
 316  */
 317 struct _dumper_t {
 318   dump_graph_FUNC         dump_graph;     /**< handler for dumping an irg */
 319   dump_const_table_FUNC   dump_const_tbl; /**< handler for dumping a const table */
 320   dump_init_FUNC          init;           /**< handler for init */
 321   dump_finish_FUNC        finish;         /**< handler for finish */
 322   FILE                    *f;             /**< the file to dump to */
 323   stat_info_t             *status;        /**< access to the global status */
 324   dumper_t                *next;          /**< link to the next dumper */
 325   pset                    *func_map;      /**< pset containing all registered functions */
 326   unsigned                tag;            /**< the id tag of the dumper */
 327 };
 328
 329 /**
 330  * helper: get an ir_op from an opcode
 331  */
 332 ir_op *stat_get_op_from_opcode(ir_opcode code);
 333
 334 /* API for distribution tables */
 335
 336 /**
 337  * creates a new distribution table.
 338  *
 339  * @param cmp_func   Compare function for objects in the distribution
 340  * @param hash_func  Hash function for objects in the distribution
 341  */
 342 distrib_tbl_t *stat_new_distrib_tbl(pset_cmp_fun cmp_func, distrib_hash_fun hash_func);
 343
 344 /**
 345  * creates a new distribution table for an integer distribution.
 346  */
 347 distrib_tbl_t *stat_new_int_distrib_tbl(void);
 348
 349 /**
 350  * destroys a distribution table.
 351  */
 352 void stat_delete_distrib_tbl(distrib_tbl_t *tbl);
 353
 354 /**
 355  * adds a new object count into the distribution table.
 356  */
 357 void stat_add_distrib_tbl(distrib_tbl_t *tbl, const void *object, const counter_t *cnt);
 358
 359 /**
 360  * adds a new key count into the integer distribution table.
 361  */
 362 void stat_add_int_distrib_tbl(distrib_tbl_t *tbl, int key, const counter_t *cnt);
 363
 364 /**
 365  * increases object count by one
 366  */
 367 void stat_inc_distrib_tbl(distrib_tbl_t *tbl, const void *object);
 368
 369 /**
 370  * increases key count by one
 371  */
 372 void stat_inc_int_distrib_tbl(distrib_tbl_t *tbl, int key);
 373
 374 /**
 375  * inserts a new object with count 0 into the distribution table
 376  * if object is already present, nothing happens
 377  */
 378 void stat_insert_distrib_tbl(distrib_tbl_t *tbl, const void *object);
 379
 380 /**
 381  * inserts a new key with count 0 into the integer distribution table
 382  * if key is already present, nothing happens
 383  */
 384 void stat_insert_int_distrib_tbl(distrib_tbl_t *tbl, int key);
 385
 386 /**
 387  * returns the sum over all counters in a distribution table
 388  */
 389 int stat_get_count_distrib_tbl(distrib_tbl_t *tbl);
 390
 391 /**
 392  * calculates the mean value of a distribution.
 393  */
 394 double stat_calc_mean_distrib_tbl(distrib_tbl_t *tbl);
 395
 396 /**
 397  * calculates the average value of a distribution
 398  */
 399 double stat_calc_avg_distrib_tbl(distrib_tbl_t *tbl);
 400
 401 /** evaluates each entry of a distribution table. */
 402 typedef void (*eval_distrib_entry_fun)(const distrib_entry_t *entry, void *env);
 403
 404 /**
 405  * iterates over all entries in a distribution table
 406  */
 407 void stat_iterate_distrib_tbl(distrib_tbl_t *tbl, eval_distrib_entry_fun eval, void *env);
 408
 409 /**
 410  * update info on Consts.
 411  *
 412  * @param node   The Const node
 413  * @param graph  The graph entry containing the call
 414  */
 415 void stat_update_const(stat_info_t *status, ir_node *node, graph_entry_t *graph);
 416
 417 /**
 418  * clears the const statistics for a new snapshot.
 419  */
 420 void stat_const_clear(stat_info_t *status);
 421
 422 /**
 423  * initialize the Const statistic.
 424  */
 425 void stat_init_const_cnt(stat_info_t *status);
 426
 427 /**
 428  * return a human readable name for an float classification
 429  */
 430 const char *stat_fc_name(float_classify_t classification);
 431
 432 /**
 433  * Update the register pressure of a block
 434  *
 435  * @param irg        the irg containing the block
 436  * @param block      the block for which the reg pressure should be set
 437  * @param pressure   the pressure
 438  * @param class_name the name of the register class
 439  */
 440 void stat_be_block_regpressure(ir_graph *irg, ir_node *block, int pressure, const char *class_name);
 441
 442 /**
 443  * Update the distribution of ready nodes of a block
 444  *
 445  * @param irg        the irg containing the block
 446  * @param block      the block for which the reg pressure should be set
 447  * @param num_ready  the number of ready nodes
 448  */
 449 void stat_be_block_sched_ready(ir_graph *irg, ir_node *block, int num_ready);
 450
 451 /**
 452  * Update the permutation statistic of a block
 453  *
 454  * @param class_name the name of the register class
 455  * @param perm       the perm node
 456  * @param block      the block containing the perm
 457  * @param size       the size of the perm
 458  * @param real_size  number of pairs with different registers
 459  */
 460 void stat_be_block_stat_perm(const char *class_name, int n_regs, ir_node *perm, ir_node *block,
 461                              int size, int real_size);
 462
 463 /**
 464  * Update the permutation statistic of a single perm
 465  *
 466  * @param class_name the name of the register class
 467  * @param perm       the perm node
 468  * @param block      the block containing the perm
 469  * @param is_chain   1 if chain, 0 if cycle
 470  * @param size       length of the cycle/chain
 471  * @param n_ops      the number of ops representing this cycle/chain after lowering
 472  */
 473 void stat_be_block_stat_permcycle(const char *class_name, ir_node *perm, ir_node *block,
 474                                   int is_chain, int size, int n_ops);
 475
 476 /**
 477  * Register an additional function for all dumper.  This function
 478  * is called in dump_snapshot once for each graph_entry and dumper.
 479  *
 480  * @param func  the dump function to register
 481  */
 482 void stat_register_dumper_func(dump_graph_FUNC func);
 483
 484 #endif /* _FIRMSTAT_T_H_ */