nsz Git - libfirm/blob - ir/be/beprofile.c

   1 /** vim: set sw=4 ts=4:
   2  * @file   beprofile.c
   3  * @date   2006-04-06
   4  * @author Adam M. Szalkowski
   5  * @cvs-id $Id$
   6  *
   7  * Code instrumentation and execution count profiling
   8  *
   9  * Copyright (C) 2006 Universitaet Karlsruhe
  10  * Released under the GPL
  11  */
  12 #ifdef HAVE_CONFIG_H
  13 #include "config.h"
  14 #endif
  15
  16 #include <math.h>
  17
  18 #include "hashptr.h"
  19 #include "debug.h"
  20 #include "obst.h"
  21 #include "set.h"
  22 #include "list.h"
  23 #include "pmap.h"
  24
  25 #include "entity.h"
  26 #include "irprintf.h"
  27 #include "irgwalk.h"
  28 #include "irdump_t.h"
  29 #include "irnode_t.h"
  30 #include "ircons_t.h"
  31 #include "irloop_t.h"
  32 #include "iredges.h"
  33 #include "execfreq.h"
  34 #include "irvrfy.h"
  35 #include "type.h"
  36 #include "entity.h"
  37
  38 #include "be_t.h"
  39 #include "belive_t.h"
  40 #include "besched_t.h"
  41 #include "beirgmod.h"
  42 #include "bearch.h"
  43 #include "beabi.h"
  44 #include "benode_t.h"
  45 #include "beutil.h"
  46 #include "ircons.h"
  47 #include "irhooks.h"
  48 #include "iredges.h"
  49
  50 #include "bechordal_t.h"
  51
  52 #ifdef WITH_LIBCORE
  53 #include <libcore/lc_opts.h>
  54 #include <libcore/lc_opts_enum.h>
  55 #endif /* WITH_LIBCORE */
  56
  57 #include "beprofile.h"
  58
  59 typedef struct _block_id_walker_data_t {
  60         tarval        **array;
  61         unsigned int    id;
  62         ir_node *symconst;
  63 } block_id_walker_data_t;
  64
  65 typedef struct _execcount_t {
  66         unsigned int block;
  67         unsigned int count;
  68 } execcount_t;
  69
  70 static int
  71 cmp_execcount(const void * a, const void * b, size_t size)
  72 {
  73         return ((execcount_t*)a)->block != ((execcount_t*)b)->block;
  74 }
  75
  76 static void
  77 block_counter(ir_node * bb, void * data)
  78 {
  79         unsigned int  *count = data;
  80         *count = *count + 1;
  81 }
  82
  83 static unsigned int
  84 count_blocks(ir_graph * irg)
  85 {
  86         unsigned int count = 0;
  87
  88         irg_block_walk_graph(irg, block_counter, NULL, &count);
  89         return count;
  90 }
  91
  92 /* keep the execcounts here because they are only read once per compiler run */
  93 static set * profile = NULL;
  94 static hook_entry_t hook;
  95
  96 /**
  97  * Instrument a block with code needed for profiling
  98  */
  99 static void
 100 instrument_block(ir_node * bb, ir_node * address, unsigned int id)
 101 {
 102         ir_graph *irg = get_irn_irg(bb);
 103         ir_node  *start_block = get_irg_start_block(irg);
 104         ir_node  *load, *store, *offset, *add, *projm, *proji, *unknown;
 105         ir_node  *cnst;
 106
 107         /**
 108          * We can't instrument the start and end block as there are no real
 109          * instructions in these blocks
 110          */
 111         if(bb == start_block || bb == get_irg_end_block(irg))
 112                 return;
 113
 114         unknown = new_r_Unknown(irg, mode_M);
 115         cnst    = new_r_Const_long(irg, start_block, mode_Iu, get_mode_size_bytes(mode_Iu) * id);
 116         offset  = new_r_Add(irg, bb, address, cnst, mode_P);
 117         load    = new_r_Load(irg, bb, unknown, offset, mode_Iu);
 118         projm   = new_r_Proj(irg, bb, load, mode_M, pn_Load_M);
 119         proji   = new_r_Proj(irg, bb, load, mode_Iu, pn_Load_res);
 120         cnst    = new_r_Const_long(irg, start_block, mode_Iu, 1);
 121         add     = new_r_Add(irg, bb, proji, cnst, mode_Iu);
 122         store   = new_r_Store(irg, bb, projm, offset, add);
 123         projm   = new_r_Proj(irg, bb, store, mode_M, pn_Store_M);
 124         set_irn_link(bb, projm);
 125         set_irn_link(projm, load);
 126 }
 127
 128 typedef struct fix_env {
 129         ir_node *start_block;
 130         ir_node *end_block;
 131 } fix_env;
 132
 133 /**
 134  * SSA Construction for instrumentation code memory
 135  */
 136 static void
 137 fix_ssa(ir_node * bb, void * data)
 138 {
 139         fix_env *env = data;
 140         ir_node *mem;
 141         int     arity = get_Block_n_cfgpreds(bb);
 142
 143         /* start and end block are not instrumented, skip! */
 144         if (bb == env->start_block || bb == env->end_block)
 145                 return;
 146
 147         if (arity == 1) {
 148                 mem = get_irn_link(get_Block_cfgpred_block(bb, 0));
 149         } else {
 150                 int n;
 151                 ir_node **ins;
 152                 ir_graph *irg = current_ir_graph;
 153
 154                 NEW_ARR_A(ir_node*, ins, arity);
 155                 for (n = arity - 1; n >= 0; --n) {
 156                         ins[n] = get_irn_link(get_Block_cfgpred_block(bb, n));
 157                 }
 158                 mem = new_r_Phi(irg, bb, arity, ins, mode_M);
 159         }
 160         set_Load_mem(get_irn_link(get_irn_link(bb)), mem);
 161 }
 162
 163
 164 /**
 165  * Generates a new irg which calls the initializer
 166  *
 167  * Pseudocode:
 168  *       void __firmprof_initializer(void) { __init_firmprof(ent_filename, bblock_id, bblock_counts, n_blocks); }
 169  */
 170 static ir_graph *
 171 gen_initializer_irg(entity * ent_filename, entity * bblock_id, entity * bblock_counts, int n_blocks)
 172 {
 173         ir_node *start_block;
 174
 175         ir_node   *ins[4];
 176         ident     *name = new_id_from_str("__firmprof_initializer");
 177         entity    *ent  = new_entity(get_glob_type(), name, new_type_method(name, 0, 0));
 178         ir_node   *ret, *call, *symconst;
 179         symconst_symbol sym;
 180
 181         ident     *init_name = new_id_from_str("__init_firmprof");
 182         ir_type   *init_type = new_type_method(init_name, 4, 0);
 183         ir_type   *uint, *uintptr, *string;
 184         entity    *init_ent;
 185         ir_graph  *irg;
 186         ir_node   *bb;
 187         ir_type   *empty_frame_type;
 188
 189         set_entity_ld_ident(ent, name);
 190
 191         uint    = new_type_primitive(new_id_from_str("__uint"), mode_Iu);
 192         uintptr = new_type_pointer(new_id_from_str("__uintptr"), uint, mode_P);
 193         string  = new_type_pointer(new_id_from_str("__charptr"), new_type_primitive(new_id_from_str("__char"), mode_Bs), mode_P);
 194
 195         set_method_param_type(init_type, 0, string);
 196         set_method_param_type(init_type, 1, uintptr);
 197         set_method_param_type(init_type, 2, uintptr);
 198         set_method_param_type(init_type, 3, uint);
 199         init_ent = new_entity(get_glob_type(), init_name, init_type);
 200         set_entity_ld_ident(init_ent, init_name);
 201
 202         irg = new_ir_graph(ent, 0);
 203         empty_frame_type = get_irg_frame_type(irg);
 204         set_type_size_bytes(empty_frame_type, 0);
 205
 206         bb = get_cur_block();
 207
 208         start_block = get_irg_start_block(irg);
 209
 210         sym.entity_p = init_ent;
 211         symconst     = new_r_SymConst(irg, start_block, sym, symconst_addr_ent);
 212
 213         sym.entity_p = ent_filename;
 214         ins[0] = new_r_SymConst(irg, start_block, sym, symconst_addr_ent);
 215         sym.entity_p = bblock_id;
 216         ins[1] = new_r_SymConst(irg, start_block, sym, symconst_addr_ent);
 217         sym.entity_p = bblock_counts;
 218         ins[2] = new_r_SymConst(irg, start_block, sym, symconst_addr_ent);
 219         ins[3] = new_r_Const_long(irg, start_block, mode_Iu, n_blocks);
 220
 221         call = new_r_Call(irg, bb, get_irg_initial_mem(irg), symconst, 4, ins, init_type);
 222         ret = new_r_Return(irg, bb, new_r_Proj(irg, bb, call, mode_M, pn_Call_M_regular), 0, NULL);
 223         mature_immBlock(bb);
 224
 225         add_immBlock_pred(get_irg_end_block(irg), ret);
 226         mature_immBlock(get_irg_end_block(irg));
 227
 228         irg_finalize_cons(irg);
 229
 230         return irg;
 231 }
 232
 233 static void
 234 block_id_walker(ir_node * bb, void * data)
 235 {
 236         block_id_walker_data_t *wd = data;
 237
 238         wd->array[wd->id] = new_tarval_from_long(get_irn_node_nr(bb), mode_Iu);
 239         instrument_block(bb, wd->symconst, wd->id);
 240         ++wd->id;
 241 }
 242
 243 ir_graph *
 244 be_profile_instrument(const char *filename)
 245 {
 246         int            n, i;
 247         unsigned int   n_blocks = 0;
 248         entity        *bblock_id, *bblock_counts, *ent_filename;
 249         ir_type       *array_type, *integer_type, *string_type, *character_type;
 250         tarval       **tarval_array, **tarval_string, *tv;
 251         int            filename_len = strlen(filename)+1;
 252         ident         *cur_ident;
 253
 254         block_id_walker_data_t  wd;
 255         symconst_symbol sym;
 256
 257         integer_type   = new_type_primitive(new_id_from_str("__uint"), mode_Iu);
 258         array_type     = new_type_array(new_id_from_str("__block_info_array"), 1, integer_type);
 259         set_array_bounds_int(array_type, 0, 0, n_blocks);
 260
 261         character_type = new_type_primitive(new_id_from_str("__char"), mode_Bs);
 262         string_type    = new_type_array(new_id_from_str("__filename"), 1, character_type);
 263         set_array_bounds_int(string_type, 0, 0, filename_len);
 264
 265         cur_ident      = new_id_from_str("__FIRMPROF__BLOCK_IDS");
 266         bblock_id      = new_entity(get_glob_type(), cur_ident, array_type);
 267         set_entity_ld_ident(bblock_id, cur_ident);
 268         set_entity_variability(bblock_id, variability_initialized);
 269
 270         cur_ident      = new_id_from_str("__FIRMPROF__BLOCK_COUNTS");
 271         bblock_counts  = new_entity(get_glob_type(), cur_ident, array_type);
 272         set_entity_ld_ident(bblock_counts, cur_ident);
 273         set_entity_variability(bblock_counts, variability_initialized);
 274
 275         cur_ident      = new_id_from_str("__FIRMPROF__FILE_NAME");
 276         ent_filename   = new_entity(get_glob_type(), cur_ident, string_type);
 277         set_entity_ld_ident(ent_filename, cur_ident);
 278
 279         for (n = get_irp_n_irgs() - 1; n >= 0; --n) {
 280                 ir_graph *irg = get_irp_irg(n);
 281
 282                 n_blocks += count_blocks(irg);
 283         }
 284
 285         /* initialize count array */
 286         tarval_array = alloca(sizeof(*tarval_array) * n_blocks);
 287         tv = get_tarval_null(mode_Iu);
 288         for (i = 0; i < n_blocks; ++i) {
 289                 tarval_array[i] = tv;
 290         }
 291         set_array_entity_values(bblock_counts, tarval_array, n_blocks);
 292
 293         /* initialize function name string constant */
 294         tarval_string = alloca(sizeof(*tarval_string) * (filename_len));
 295         for (i = 0; i < filename_len; ++i) {
 296                 tarval_string[i] = new_tarval_from_long(filename[i], mode_Bs);
 297         }
 298         set_entity_variability(ent_filename, variability_constant);
 299         set_array_entity_values(ent_filename, tarval_string, filename_len);
 300
 301         /* initialize block id array and instrument blocks */
 302         wd.array = tarval_array;
 303         wd.id    = 0;
 304         for (n = get_irp_n_irgs() - 1; n >= 0; --n) {
 305                 ir_graph      *irg = get_irp_irg(n);
 306                 int            i;
 307                 ir_node       *endbb = get_irg_end_block(irg);
 308                 fix_env       env;
 309
 310                 set_current_ir_graph(irg);
 311
 312                 /* generate a symbolic constant pointing to the count array */
 313                 sym.entity_p = bblock_counts;
 314                 wd.symconst  = new_r_SymConst(irg, get_irg_start_block(irg), sym, symconst_addr_ent);
 315
 316                 irg_block_walk_graph(irg, block_id_walker, NULL, &wd);
 317                 env.start_block = get_irg_start_block(irg);
 318                 env.end_block   = get_irg_end_block(irg);
 319                 set_irn_link(env.start_block, get_irg_no_mem(irg));
 320                 irg_block_walk_graph(irg, fix_ssa, NULL, &env);
 321                 for (i = get_Block_n_cfgpreds(endbb) - 1; i >= 0; --i) {
 322                         ir_node *node = skip_Proj(get_Block_cfgpred(endbb, i));
 323                         ir_node *bb   = get_Block_cfgpred_block(endbb, i);
 324                         ir_node *sync;
 325                         ir_node *ins[2];
 326
 327                         switch (get_irn_opcode(node)) {
 328                         case iro_Return:
 329                                 ins[0] = get_irn_link(bb);
 330                                 ins[1] = get_Return_mem(node);
 331                                 sync   = new_r_Sync(irg, bb, 2, ins);
 332                                 set_Return_mem(node, sync);
 333                                 break;
 334                         case iro_Raise:
 335                                 ins[0] = get_irn_link(bb);
 336                                 ins[1] = get_Raise_mem(node);
 337                                 sync   = new_r_Sync(irg, bb, 2, ins);
 338                                 set_Raise_mem(node, sync);
 339                                 break;
 340                         default:
 341                                 /* a fragile's op exception. There should be another path to End,
 342                                    so ignore it */
 343                                 assert(is_fragile_op(node) && "unexpected End control flow predecessor");
 344                         }
 345                 }
 346         }
 347         set_array_entity_values(bblock_id, tarval_array, n_blocks);
 348
 349         return gen_initializer_irg(ent_filename, bblock_id, bblock_counts, n_blocks);
 350 }
 351
 352 static void
 353 profile_node_info(void *ctx, FILE *f, const ir_node *irn)
 354 {
 355         if(is_Block(irn)) {
 356                 fprintf(f, "profiled execution count: %u\n", be_profile_get_block_execcount(irn));
 357         }
 358 }
 359
 360 static void
 361 register_vcg_hook(void)
 362 {
 363         memset(&hook, 0, sizeof(hook));
 364         hook.hook._hook_node_info = profile_node_info;
 365         register_hook(hook_node_info, &hook);
 366 }
 367
 368 static void
 369 unregister_vcg_hook(void)
 370 {
 371         unregister_hook(hook_node_info, &hook);
 372 }
 373
 374 /**
 375  * Reads the corresponding profile info file if it exists and returns a
 376  * profile info struct
 377  */
 378 void
 379 be_profile_read(const char *filename)
 380 {
 381         FILE   *f;
 382         char    buf[8];
 383         size_t  ret;
 384
 385         f = fopen(filename, "r");
 386         if(f == NULL) {
 387                 return;
 388         }
 389         printf("found profile data '%s'.\n", filename);
 390
 391         /* check magic */
 392         ret = fread(buf, 8, 1, f);
 393         if(ret == 0 || strncmp(buf, "firmprof", 8) != 0) {
 394                 return;
 395         }
 396
 397         if(profile) be_profile_free();
 398         profile = new_set(cmp_execcount, 16);
 399
 400         do {
 401                 execcount_t  query;
 402                 ret = fread(&query, sizeof(unsigned int), 2, f);
 403
 404                 if(ret != 2) break;
 405
 406                 set_insert(profile, &query, sizeof(query), query.block);
 407         } while(1);
 408
 409         fclose(f);
 410         register_vcg_hook();
 411 }
 412
 413 /**
 414  * Frees the profile info
 415  */
 416 void
 417 be_profile_free(void)
 418 {
 419         if(profile) {
 420                 unregister_vcg_hook();
 421                 del_set(profile);
 422         }
 423 }
 424
 425 /**
 426  * Tells whether profile module has acquired data
 427  */
 428 int
 429 be_profile_has_data(void)
 430 {
 431         return (profile != NULL);
 432 }
 433
 434 /**
 435  * Get block execution count as determined be profiling
 436  */
 437 unsigned int
 438 be_profile_get_block_execcount(const ir_node *block)
 439 {
 440         execcount_t *ec, query;
 441
 442         if(!profile)
 443                 return 1;
 444
 445         query.block = get_irn_node_nr(block);
 446         ec = set_find(profile, &query, sizeof(query), get_irn_node_nr(block));
 447
 448         if(ec != NULL) {
 449                 return ec->count;
 450         } else {
 451                 ir_fprintf(stderr, "Warning: Profile contains no data for %+F\n",
 452                            block);
 453                 return 1;
 454         }
 455 }
 456
 457 typedef struct _intialize_execfreq_env_t {
 458         ir_graph *irg;
 459         exec_freq_t *execfreqs;
 460         double freq_factor;
 461 } initialize_execfreq_env_t;
 462
 463 static void initialize_execfreq(ir_node *block, void *data) {
 464         initialize_execfreq_env_t *env = data;
 465         double freq;
 466
 467         if(block == get_irg_start_block(env->irg)
 468            || block == get_irg_end_block(env->irg)) {
 469                 freq = 1.0;
 470         } else {
 471                 freq = be_profile_get_block_execcount(block);
 472                 freq *= env->freq_factor;
 473         }
 474
 475         set_execfreq(env->execfreqs, block, freq);
 476 }
 477
 478 exec_freq_t *be_create_execfreqs_from_profile(ir_graph *irg)
 479 {
 480         ir_node *block2 = NULL;
 481         ir_node *start_block;
 482         const ir_edge_t *edge;
 483         initialize_execfreq_env_t env;
 484         unsigned count;
 485
 486         env.execfreqs = create_execfreq(irg);
 487
 488         // find the successor to the start block
 489         start_block = get_irg_start_block(irg);
 490         foreach_block_succ(start_block, edge) {
 491                 ir_node *succ = get_edge_src_irn(edge);
 492                 if(succ != start_block) {
 493                         block2 = succ;
 494                         break;
 495                 }
 496         }
 497         assert(block2 != NULL);
 498
 499         count = be_profile_get_block_execcount(block2);
 500         if(count == 0) {
 501                 // the function was never executed, so fallback to estimated freqs
 502                 free_execfreq(env.execfreqs);
 503
 504                 return compute_execfreq(irg, 10);
 505         }
 506
 507         env.freq_factor = 1 / count;
 508         irg_block_walk_graph(irg, initialize_execfreq, NULL, &env);
 509
 510         return env.execfreqs;
 511 }