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

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